Most frugal explanations in Bayesian networks. (English) Zbl 1319.68205

Summary: Inferring the most probable explanation to a set of variables, given a partial observation of the remaining variables, is one of the canonical computational problems in Bayesian networks, with widespread applications in AI and beyond. This problem, known as MAP, is computationally intractable (NP-hard) and remains so even when only an approximate solution is sought. We propose a heuristic formulation of the MAP problem, denoted as Inference to the Most Frugal Explanation (MFE), based on the observation that many intermediate variables (that are neither observed nor to be explained) are irrelevant with respect to the outcome of the explanatory process. An explanation based on few samples (often even a singleton sample) from these irrelevant variables is typically almost as good as an explanation based on (the computationally costly) marginalization over these variables. We show that while MFE is computationally intractable in general (as is MAP), it can be tractably approximated under plausible situational constraints, and its inferences are fairly robust with respect to which intermediate variables are considered to be relevant.


68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q25 Analysis of algorithms and problem complexity


Full Text: DOI


[1] Abdelbar, A. M.; Hedetniemi, S. M., Approximating MAPs for belief networks is NP-hard and other theorems, Artif. Intell., 102, 21-38, (1998) · Zbl 0909.68077
[2] Beinlich, I.; Suermondt, G.; Chavez, R.; Cooper, G., The ALARM monitoring system: a case study with two probabilistic inference techniques for belief networks, (Hunter, J.; Cookson, J.; Wyatt, J., Proceedings of the Second European Conference on AI and Medicine, (1989), Springer-Verlag), 247-256
[3] Bodlaender, H. L., Treewidth: characterizations, applications, and computations, (Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science, (2006)), 1-14 · Zbl 1167.68404
[4] Bodlaender, H. L.; van den Eijkhof, F.; van der Gaag, L. C., On the complexity of the MPA problem in probabilistic networks, (van Harmelen, F., Proceedings of the Fifteenth European Conference on Artificial Intelligence, (2002), IOS Press Amsterdam), 675-679
[5] Bovens, L.; Olsson, E. J., Coherentism, reliability and Bayesian networks, Mind, 109, 686-719, (2000)
[6] Chajewska, U.; Halpern, J., Defining explanation in probabilistic systems, (Geiger, D.; Shenoy, P., Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence, (1997), Morgan Kaufmann San Francisco, CA), 62-71
[7] Cofiño, A. S.; Cano, R.; Sordo, C.; Gutiérrez, J. M., Bayesian networks for probabilistic weather prediction, (van Harmelen, F., Proceedings of the Fifteenth European Conference on Artificial Intelligence, (2002), IOS Press Amsterdam), 695-699
[8] Darwiche, A., Modeling and reasoning with Bayesian networks, (2009), CU Press Cambridge, UK · Zbl 1231.68003
[9] Darwiche, A.; Choi, A., Same-decision probability: a confidence measure for threshold-based decisions under noisy sensors, (Myllymäki, P.; Roos, T.; Jaakkola, T., Proceedings of the Fifth European Workshop on Probabilistic Graphical Models, (2010)), 113-120
[10] Demirer, R.; Mau, R.; Shenoy, C., Bayesian networks: a decision tool to improve portfolio risk analysis, J. Appl. Finance, 16, 106-119, (2006)
[11] Dey, S.; Stori, J. A., A Bayesian network approach to root cause diagnosis of process variations, Int. J. Mach. Tools Manuf., 45, 75-91, (2005)
[12] Downey, R. G.; Fellows, M. R., Parameterized complexity, (1999), Springer Verlag Berlin · Zbl 0914.68076
[13] Druzdzel, M., Some properties of joint probability distributions, (de Mantaras, R. L.; Poole, D., Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence, (1994), Morgan Kaufmann Publishers San Francisco, CA), 187-194
[14] Druzdzel, M. J.; Suermondt, H. J., Relevance in probabilistic models: “backyards“ in a “small world”, (Working Notes of the AAAI-1994 Fall Symposium Series: Relevance, (1994)), 60-63
[15] Fitelson, B., A probabilistic theory of coherence, Analysis, 63, 194-199, (2003) · Zbl 1038.03520
[16] Flum, G.; Grohe, M., Parameterized complexity theory, (2006), Springer Berlin
[17] Fodor, J. A., The modularity of mind, (1983), MIT Press Cambridge, MA
[18] Fodor, J. A., Modules, frames, fridgeons, sleeping dogs, and the music of the spheres, (Pylyshyn, Z. W., The Robot’s Dilemma: The Frame Problem in Artificial Intelligence, (1987), Ablex Publishing), 139-150
[19] Fodor, J. A.; Lepore, E., Holism: A Shopper’s guide, vol. 16, (1992), Blackwell Oxford
[20] Funke, J., Solving complex problems: exploration and control of complex social systems, (Sternberg, R. J.; Frensch, P. A., Complex Problem Solving: Principles and Mechanisms, (1991), Lawrence Erlbaum Associates), 185-222
[21] van der Gaag, L. C.; Renooij, S.; Witteman, C. L.M.; Aleman, B. M.P.; Taal, B. G., Probabilities for a probabilistic network: a case study in oesophageal cancer, Artif. Intell. Med., 25, 123-148, (2002)
[22] Garey, M. R.; Johnson, D. S., Computers and intractability. A guide to the theory of NP-completeness, (1979), W.H. Freeman and Co. San Francisco, CA · Zbl 0411.68039
[23] Geenen, P. L.; Elbers, A. R.W.; van der Gaag, L. C.; van der Loeffen, W. L.A., Development of a probabilistic network for clinical detection of classical swine fever, (Proceedings of the Eleventh Symposium of the International Society for Veterinary Epidemiology and Economics, (2006)), 667-669
[24] Geiger, D.; Verma, T.; Pearl, J., Identifying independence in Bayesian networks, Networks, 20, 507-534, (1990) · Zbl 0724.05066
[25] Gemela, J., Financial analysis using Bayesian networks, Appl. Stoch. Models Bus. Ind., 17, 57-67, (2001) · Zbl 0965.62088
[26] Glass, D. H., Coherence measures and inference to the best explanation, Synthese, 157, 275-296, (2007) · Zbl 1126.03009
[27] Glass, D. H., Inference to the best explanation: a comparison of approaches, (Bishop, M., Proceedings of the Second Symposium on Computing and Philosophy, The Society for the Study of Artificial Intelligence and the Simulation of Behaviour, (2009)), 22-27
[28] Glass, D. H., Inference to the best explanation: does it track truth?, Synthese, 185, 411-427, (2012) · Zbl 1274.62054
[29] Hempel, C. G., Aspects of scientific explanation, (1965), Free Press New York
[30] Jaynes, E., Probability theory: the logic of science, (2003), Cambridge University Press · Zbl 1045.62001
[31] Johnson-Laird, P. N.; Legrenzi, P.; Girotto, V.; Legrenzi, M. S.; Caverni, J., Naive probability: a mental model theory of extensional reasoning, Psychol. Rev., 106, 62-88, (1999)
[32] Kennett, R. J.; Korb, K. B.; Nicholson, A. E., Seabreeze prediction using Bayesian networks, (Cheung, D. W.L.; Williams, G.; Li, Q., Proceedings of the Fifth Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, (2001), Springer Verlag Berlin), 148-153 · Zbl 0978.68688
[33] Kragt, M. E.; Newhama, L. T.H.; Jakemana, A. J., A Bayesian network approach to integrating economic and biophysical modelling, (Anderssen, R.; Braddock, R.; Newham, L., Proceedings of the Eighteenth World IMACS/MODSIM Congress on Modelling and Simulation, (2009)), 2377-2383
[34] Kwisthout, J., The computational complexity of probabilistic networks, (2009), Faculty of Science, Utrecht University The Netherlands, Ph.D. thesis
[35] Kwisthout, J., Two new notions of abduction in Bayesian networks, (Bouvry, P.; etal., Proceedings of the 22nd Benelux Conference on Artificial Intelligence, (BNAIC’10), (2010)), 82-89
[36] Kwisthout, J., Most probable explanations in Bayesian networks: complexity and tractability, Int. J. Approx. Reason., 52, 1452-1469, (2011) · Zbl 1242.68332
[37] Kwisthout, J., Relevancy in problem solving: a computational framework, J. Probl. Solving, 5, 17-32, (2012)
[38] Kwisthout, J., Most frugal explanations: Occam’s razor applied to Bayesian abduction, (Hindriks, K.; de Weerdt, M.; van Riemsdijk, B.; Warnier, M., Proceedings of the 25th Benelux Conference on AI, (BNAIC’13), (2013)), 96-103
[39] Kwisthout, J., Most inforbable explanations: finding explanations in Bayesian networks that are both probable and informative, (van der Gaag, L., Proceedings of the Twelfth European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, (2013)), 328-339 · Zbl 1390.68659
[40] Kwisthout, J., Structure approximation of most probable explanations in Bayesian networks, (van der Gaag, L., Proceedings of the Twelfth European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, (2013)), 340-351 · Zbl 1390.68660
[41] Kwisthout, J.; Bodlaender, H. L.; van der Gaag, L. C., The complexity of finding kth most probable explanations in probabilistic networks, (Cerná, I.; Gyimóthy, T.; Hromkovic, J.; Jefferey, K.; Královic, R.; Vukolic, M.; Wolf, S., Proceedings of the 37th International Conference on Current Trends in Theory and Practice of Computer Science, (2011)), 356-367 · Zbl 1298.68202
[42] Kwisthout, J.; van Rooij, I., Bridging the gap between theory and practice of approximate Bayesian inference, Cogn. Syst. Res., 24, 2-8, (2013)
[43] Kwisthout, J.; Wareham, T.; van Rooij, I., Bayesian intractability is not an ailment approximation can cure, Cogn. Sci., 35, 779-1007, (2011)
[44] Lipton, P., Inference to the best explanation, (2004), Routledge London, UK
[45] Lucas, P. J.F.; de Bruijn, N.; Schurink, K.; Hoepelman, A., A probabilistic and decision-theoretic approach to the management of infectious disease at the ICU, Artif. Intell. Med., 3, 251-279, (2000)
[46] Murphy, K., The Bayes net toolbox for MATLAB, Comput. Sci. Stat., 33, 2001, (2001)
[47] Neapolitan, R. E., Probabilistic reasoning in expert systems. theory and algorithms, (1990), Wiley/Interscience New York, NY
[48] Nedevschi, S.; Sandhu, J. S.; Pal, J.; Fonseca, R.; Toyama, K., Bayesian networks: an exploratory tool for understanding ICT adoption, (Toyama, K., Proceedings of the International Conference on Information and Communication Technologies and Development, (2006)), 277-284
[49] Olsson, E. J., What is the problem of coherence and truth?, J. Philos., 99, 246-272, (2002)
[50] Papadimitriou, C. H., Computational complexity, (1994), Addison-Wesley · Zbl 0557.68033
[51] Park, J. D.; Darwiche, A., Complexity results and approximation settings for MAP explanations, J. Artif. Intell. Res., 21, 101-133, (2004) · Zbl 1080.68689
[52] Pearl, J., Probabilistic reasoning in intelligent systems: networks of plausible inference, (1988), Morgan Kaufmann Palo Alto, CA
[53] van Rooij, I., The tractable cognition thesis, Cogn. Sci., 32, 939-984, (2008)
[54] Shi, L.; Feldman, N.; Griffiths, T., Performing Bayesian inference with exemplar models, (Sloutsky, V.; Love, B.; McRae, K., Proceedings of the 30th Annual Conference of the Cognitive Science Society, (2008)), 745-750
[55] Shimony, S., The role of relevance in explanation I: irrelevance as statistical independence, Int. J. Approx. Reason., 8, 281-324, (1993) · Zbl 0776.68104
[56] Shimony, S. E., Finding MAPs for belief networks is NP-hard, Artif. Intell., 68, 399-410, (1994) · Zbl 0818.68097
[57] Stewart, N.; Chater, N.; Brown, G. D.A., Decision by sampling, Cogn. Psychol., 53, 1-26, (2006)
[58] Sticha, P. J.; Buede, D. M.; Rees, R. L., Bayesian model of the effect of personality in predicting decisionmaker behavior, (van der Gaag, L., Proceedings of the Fourth Bayesian Modelling Applications Workshop, (2006))
[59] Stockmeyer, L., The polynomial-time hierarchy, Theor. Comput. Sci., 3, 1-22, (1977) · Zbl 0353.02024
[60] Tenenbaum, J. B., How to grow a mind: statistics, structure, and abstraction, Science, 331, 1279-1285, (2011) · Zbl 1226.68087
[61] Torán, J., Complexity classes defined by counting quantifiers, J. ACM, 38, 752-773, (1991)
[62] Vul, E.; Goodman, N. D.; Griffiths, T. L.; Tenenbaum, J. B., One and done? optimal decisions from very few samples, (Taatgen, N.; van Rijn, H.; Schomaker, L.; Nerbonne, J., Proceedings of the 31st Annual Meeting of the Cognitive Science Society, (2009)), 66-72
[63] Wagner, K. W., The complexity of combinatorial problems with succinct input representation, Acta Inform., 23, 325-356, (1986) · Zbl 0621.68032
[64] Wasyluk, H.; Onisko, A.; Druzdzel, M. J., Support of diagnosis of liver disorders based on a causal Bayesian network model, Med. Sci. Monit., 7, 327-332, (2001)
[65] Wilson, D.; Sperber, D., Relevance theory, (Horn, L. R.; Ward, G., Handbook of Pragmatics, (2004), Blackwell Oxford, UK), 607-632
[66] Yuan, C.; Lim, H.; Lu, T., Most relevant explanations in Bayesian networks, J. Artif. Intell. Res., 42, 309-352, (2011) · Zbl 1263.68161
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.