×

Approximate algorithms for credal networks with binary variables. (English) Zbl 1184.68510

Summary: This paper presents a family of algorithms for approximate inference in credal networks (that is, models based on directed acyclic graphs and set-valued probabilities) that contain only binary variables. Such networks can represent incomplete or vague beliefs, lack of data, and disagreements among experts; they can also encode models based on belief functions and possibilistic measures. All algorithms for approximate inference in this paper rely on exact inferences in credal networks based on polytrees with binary variables, as these inferences have polynomial complexity. We are inspired by approximate algorithms for Bayesian networks; thus the Loopy 2U algorithm resembles Loopy Belief Propagation, while the Iterated Partial Evaluation and Structured Variational 2U algorithms are, respectively, based on Localized Partial Evaluation and variational techniques.

MSC:

68T37 Reasoning under uncertainty in the context of artificial intelligence
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andersen, K. A.; Hooker, J. N., Bayesian logic, Decision Support Systems, 11, 91-210 (1994)
[2] Antonucci, A.; Zaffalon, M.; Ide, J.; Cozman, F. G., Binarization algorithms for approximate updating in credal nets, (Third European Starting AI Researcher Symposium (STAIRS’06) (2006), IOS Press), 120-131
[3] Antonucci, A.; Zaffalon, M., Equivalence between Bayesian and credal nets on an updating problem, (Lawry, J.; Miranda, E.; Bugarin, A.; Li, S.; Gil, M. A.; Grzegorzewski, P.; Hryniewicz, O., Soft Methods for Integrated Uncertainty Modelling (2006), Springer), 223-230 · Zbl 1106.68102
[4] I. Beinlich, H.J. Suermondt, R.M. Chavez, G.F. Cooper, The ALARM monitoring system: A case study with two probabilistic inference techniques for belief networks, in: Second European Conference on Artificial Intelligence in Medicine, 1989, pp. 247-256.; I. Beinlich, H.J. Suermondt, R.M. Chavez, G.F. Cooper, The ALARM monitoring system: A case study with two probabilistic inference techniques for belief networks, in: Second European Conference on Artificial Intelligence in Medicine, 1989, pp. 247-256.
[5] Biazzo, V.; Gilio, A., A generalization of the fundamental theorem of de Finetti for imprecise conditional probability assessments, International Journal of Approximate Reasoning, 24, 2-3, 251-272 (2000) · Zbl 0995.68124
[6] A. Cano, J.E. Cano, S. Moral, Convex sets of probabilities propagation by simulated annealing, in: G. Goos, J. Hartmanis, J. van Leeuwen (Eds.), International Conference on Information Processing and Management of Uncertainty in Knowledge-based Systems, Paris, France, July 1994, pp. 4-8.; A. Cano, J.E. Cano, S. Moral, Convex sets of probabilities propagation by simulated annealing, in: G. Goos, J. Hartmanis, J. van Leeuwen (Eds.), International Conference on Information Processing and Management of Uncertainty in Knowledge-based Systems, Paris, France, July 1994, pp. 4-8.
[7] Cano, A.; Moral, S., A genetic algorithm to approximate convex sets of probabilities, International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems, 2, 859-864 (1996)
[8] Cano, A.; Moral, S., Using probability trees to compute marginals with imprecise probabilities, International Journal of Approximate Reasoning, 29, 1-46 (2002) · Zbl 1015.68206
[9] Cano, A.; Gómez, M.; Moral, S., Hill-climbing and branch-and-bound algorithms for exact and approximate inference in credal networks, International Journal of Approximate Reasoning, 44, 3, 261-280 (2007) · Zbl 1116.68080
[10] Cano, J.; Delgado, M.; Moral, S., An axiomatic framework for propagating uncertainty in directed acyclic networks, International Journal of Approximate Reasoning, 8, 253-280 (1993) · Zbl 0777.68071
[11] Cheng, J.; Druzdzel, M., Computational investigation of low-discrepancy sequences in simulation algorithms for Bayesian networks, (Boutilier, C.; Goldszmidt, M., Conference on Uncertainty in Artificial Intelligence (2000), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers San Francisco, CA), 72-81
[12] Coletti, G.; Scozzafava, R., Probabilistic logic in a coherent setting, (Trends in Logic, vol. 15 (2002), Kluwer: Kluwer Dordrecht) · Zbl 1005.60007
[13] Coletti, G., Coherent numerical and ordinal probabilistic assessments, IEEE Transactions on Systems, Man and Cybernetics, 24, 12, 1747-1753 (1994) · Zbl 1371.68265
[14] Couso, I.; Moral, S.; Walley, P., A survey of concepts of independence for imprecise probabilities, Risk, Decision and Policy, 5, 165-181 (2000)
[15] Cowell, R. G.; Dawid, A. P.; Lauritzen, S. L.; Spiegelhalter, D. J., Probabilistic Networks and Expert Systems (1999), Springer-Verlag: Springer-Verlag New York · Zbl 0937.68121
[16] Cozman, F. G., Credal networks, Artificial Intelligence, 120, 199-233 (2000) · Zbl 0945.68163
[17] Cozman, F. G., Separation properties of sets of probabilities, (Boutilier, C.; Goldszmidt, M., Conference on Uncertainty in Artificial Intelligence (2000), Morgan Kaufmann: Morgan Kaufmann San Francisco), 107-115
[18] F.G. Cozman, Constructing sets of probability measures through Kuznetsov’s independence condition, in: International Symposium on Imprecise Probabilities and their Applications, Ithaca, New York, 2001, pp. 104-111.; F.G. Cozman, Constructing sets of probability measures through Kuznetsov’s independence condition, in: International Symposium on Imprecise Probabilities and their Applications, Ithaca, New York, 2001, pp. 104-111.
[19] Cozman, F. G., Graphical models for imprecise probabilities, International Journal of Approximate Reasoning, 39, 2-3, 167-184 (2005) · Zbl 1099.68111
[20] Darwiche, A., Recursive conditioning, Artificial Intelligence, 125, 1-2, 5-41 (2001) · Zbl 0969.68150
[21] de Campos, C. P.; Cozman, F. G., Inference in credal networks using multilinear programming, (Onaindia, E.; Staab, S., Second Starting AI Researchers’ Symposium (STAIRS) (2004), IOS Press: IOS Press Amsterdam, The Netherlands), 50-61
[22] C.P. de Campos, F.G. Cozman, Belief updating and learning in semi-qualitative probabilistic networks, in: F. Bacchus, T. Jaakkola (Eds.), Conference on Uncertainty in Artificial Intelligence (UAI), Edinburgh, Scotland, 2005, pp. 153-160.; C.P. de Campos, F.G. Cozman, Belief updating and learning in semi-qualitative probabilistic networks, in: F. Bacchus, T. Jaakkola (Eds.), Conference on Uncertainty in Artificial Intelligence (UAI), Edinburgh, Scotland, 2005, pp. 153-160.
[23] C.P. de Campos, F.G. Cozman, The inferential complexity of Bayesian and credal networks, in: International Joint Conference on Artificial Intelligence, Edinburgh, United Kingdom, 2005, pp. 1313-1318.; C.P. de Campos, F.G. Cozman, The inferential complexity of Bayesian and credal networks, in: International Joint Conference on Artificial Intelligence, Edinburgh, United Kingdom, 2005, pp. 1313-1318.
[24] Dechter, R., Bucket elimination: a unifying framework for probabilistic inference, (Horvitz, E.; Jensen, F., Conference on Uncertainty in Artificial Intelligence (1996), Morgan Kaufmann: Morgan Kaufmann San Francisco, California), 211-219 · Zbl 0910.68209
[25] D.L. Draper, S. Hanks, Localized partial evaluation of belief networks, in: Conference on Uncertainty in Artificial Intelligence, 1994, pp. 170-177.; D.L. Draper, S. Hanks, Localized partial evaluation of belief networks, in: Conference on Uncertainty in Artificial Intelligence, 1994, pp. 170-177.
[26] D.L. Draper, Localized Partial Evaluation of Belief Networks, PhD Thesis, Department of Computer Science, University of Washington, Washington, WA, 1995.; D.L. Draper, Localized Partial Evaluation of Belief Networks, PhD Thesis, Department of Computer Science, University of Washington, Washington, WA, 1995.
[27] Fagiuoli, E.; Zaffalon, M., 2U: An exact interval propagation algorithm for polytrees with binary variables, Artificial Intelligence, 106, 1, 77-107 (1998) · Zbl 0909.68083
[28] Ferreira da Rocha, J. C.; Cozman, F. G., Inference in credal networks: branch-and-bound methods and the A/R+ algorithm, International Journal of Approximate Reasoning, 39, 2-3, 279-296 (2005) · Zbl 1099.68112
[29] Ferreira da Rocha, J. C.; Cozman, F. G.; de Campos, C. P., Inference in polytrees with sets of probabilities, (Conference on Uncertainty in Artificial Intelligence (2003), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA, United States), 217-224
[30] Fung, R.; Chang, K., Weighting and integrating evidence for stochastic simulation in Bayesian networks, (Uncertainty in Artificial Intelligence (1990), Morgan Kaufmann), 209-219
[31] Geiger, D.; Verma, T.; Pearl, J., Identifying independence in Bayesian networks, Networks, 20, 507-534 (1990) · Zbl 0724.05066
[32] Gilks, W. R.; Richardson, S.; Spiegelhalter, D. J., Markov Chain Monte Carlo in Practice (1996), Chapman & Hall: Chapman & Hall London, England · Zbl 0832.00018
[33] Ha, V.; Haddawy, P., Theoretical foundations for abstraction-based probabilistic planning, (Horvitz, E.; Jensen, F., Conference on Uncertainty in Artificial Intelligence (1996), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA, United States), 291-298
[34] Hailperin, T., Sentential Probability Logic (1996), Lehigh University Press: Lehigh University Press Bethlehem, United States · Zbl 0922.03026
[35] Halpern, J. Y., Reasoning about Uncertainty (2003), MIT Press: MIT Press Cambridge, MA · Zbl 1090.68105
[36] Henrion, M., Propagation of uncertainty in Bayesian networks by probabilistic logic sampling, (Lemmer, J. F.; Kanal, L. N., Uncertainty in Artificial Intelligence 2 (1988), Elsevier/North-Holland: Elsevier/North-Holland Amsterdam, London, New York), 149-163
[37] Ide, J. S.; Cozman, F. G., Generating random Bayesian networks with constraints on induced width, (European Conference on Artificial Intelligence (2004), IOS Press: IOS Press Amsterdam, The Netherlands), 323-327
[38] Ide, J. S.; Cozman, F. G., Approximate inference in credal networks by variational mean field methods, (International Symposium on Imprecise Probabilities and their Applications (2005), Brightdoc: Brightdoc Pittsburgh, PA), 203-212
[39] J.S. Ide, F.G. Cozman, Set-based variational methods in credal networks: the SV2U algorithm, in: A.C. Garcia, F. Osório (Eds.), XXV Congresso da Sociedade Brasileira de ComputaçÃo, volume V Encontro Nacional de Inteligência Artificial, São Leopoldo, Rio Grande do Sul, Brazil, 2005, pp. 872-881.; J.S. Ide, F.G. Cozman, Set-based variational methods in credal networks: the SV2U algorithm, in: A.C. Garcia, F. Osório (Eds.), XXV Congresso da Sociedade Brasileira de ComputaçÃo, volume V Encontro Nacional de Inteligência Artificial, São Leopoldo, Rio Grande do Sul, Brazil, 2005, pp. 872-881.
[40] Ide, J. S.; Cozman, F. G., IPE and L2U: Approximate algorithms for credal networks, (Second Starting AI Researcher Symposium (STAIRS) (2004), IOS Press), 118-127
[41] Jaakkola, T. S., Tutorial on variational approximation methods, Advanced Mean Field Methods: Theory and Practice, 129-160 (2001)
[42] Jensen, F. V., An Introduction to Bayesian Networks (1996), Springer Verlag: Springer Verlag New York
[43] Jordan, M. I.; Ghahramani, Z.; Jaakkola, T. S., An introduction to variational methods for graphical models, Machine Learning, 37, 183-233 (1999) · Zbl 0945.68164
[44] Levi, I., The Enterprise of Knowledge (1980), MIT Press: MIT Press Cambridge, MA
[45] Li, Z.; D’Ambrosio, B., Efficient inference in Bayes networks as a combinatorial optimization problem, International Journal of Approximate Reasoning, 11, 55-81 (1994) · Zbl 0808.68098
[46] McEliece, R. J.; MacKay, D. J.C.; Cheng, J. F., Turbo decoding as an instance of Pearl’s ‘belief propagation’ algorithm, IEEE Journal on Selected Areas in Communication, 16, 2, 140-152 (1998), (CSD-99-1046)
[47] J.M. Mooij, H.J. Kappen, Sufficient conditions for convergence of loopy belief propagation, in: Conference on Uncertainty in Artificial Intelligence, 2005.; J.M. Mooij, H.J. Kappen, Sufficient conditions for convergence of loopy belief propagation, in: Conference on Uncertainty in Artificial Intelligence, 2005.
[48] K.P. Murphy, Y. Weiss, M.I. Jordan, Loopy belief propagation for approximate inference: An empirical study, in: Conference on Uncertainty in Artificial Intelligence, 1999, pp. 467-475.; K.P. Murphy, Y. Weiss, M.I. Jordan, Loopy belief propagation for approximate inference: An empirical study, in: Conference on Uncertainty in Artificial Intelligence, 1999, pp. 467-475.
[49] Neapolitan, R. E., Learning Bayesian Networks (2003), Prentice-Hall
[50] Nilsson, N. J., Probabilistic logic, Artificial Intelligence, 28, 71-87 (1986) · Zbl 0589.03007
[51] Pearl, J., Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (1988), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA
[52] Ramos, F. T.; Cozman, F. G., Anytime anyspace probabilistic inference, International Journal of Approximate Reasoning, 38, 53-80 (2005) · Zbl 1065.68097
[53] Renooij, S.; Parsons, S.; Pardieck, P., Using kappas as indicators of strength in qualitative probabilistic networks, (Nielsen, T. D.; Zhang, N. L., Seventh European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (2003), Springer Verlag), 87-99 · Zbl 1274.68550
[54] Roth, D., On the hardness of approximate reasoning, Artificial Intelligence, 82, 1-2, 273-302 (1996) · Zbl 1506.68143
[55] Saul, L. K.; Jaakkola, T. S.; Jordan, M. I., Mean field theory for sigmoid belief networks, Journal of Artificial Intelligence Research, 4, 61-76 (1996) · Zbl 0900.68379
[56] Saul, L. K.; Jordan, M. I., Exploiting tractable substructures in intractable networks, (Touretzky, D. S.; Mozer, M. C.; Hasselmo, M. E., Advances in Neural Information Processing Systems, vol. 8 (1996), MIT Press: MIT Press Cambridge, MA), 486-492
[57] Suermondt, H. J.; Cooper, G. F., Initialization for the method of conditioning in Bayesian belief networks, Artificial Intelligence, 50, 1, 83-94 (1991)
[58] Tatikonda, S. C.; Jordan, M. I., Loopy belief propagation and Gibbs measures, (Darwiche, A.; Friedman, N., Conference on Uncertainty in Artificial Intelligence (2002), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA), 493-500
[59] Tessem, B., Interval probability propagation, International Journal of Approximate Reasoning, 7, 95-120 (1992) · Zbl 0769.68113
[60] Walley, P., Statistical Reasoning with Imprecise Probabilities (1991), Chapman & Hall: Chapman & Hall London · Zbl 0732.62004
[61] Walley, P., Measures of uncertainty in expert systems, Artificial Intelligence, 83, 1-58 (1996) · Zbl 1506.68157
[62] Y. Weiss, W.T. Freeman, Correctness of Belief Propagation in Gaussian Graphical Models of Arbitrary Topology, Technical Report CSD-99-1046, CS Department, UC Berkeley, 1999.; Y. Weiss, W.T. Freeman, Correctness of Belief Propagation in Gaussian Graphical Models of Arbitrary Topology, Technical Report CSD-99-1046, CS Department, UC Berkeley, 1999. · Zbl 0992.68055
[63] J. Winn, Variational Message Passing and its Applications, PhD Thesis, Department of Physics, University of Cambridge, Cambridge, UK, 2003.; J. Winn, Variational Message Passing and its Applications, PhD Thesis, Department of Physics, University of Cambridge, Cambridge, UK, 2003.
[64] J.S. Yedidia, W.T. Freeman, Y. Weiss, Generalized belief propagation, in: Neural Information Processing Systems, 2000, pp. 689-695.; J.S. Yedidia, W.T. Freeman, Y. Weiss, Generalized belief propagation, in: Neural Information Processing Systems, 2000, pp. 689-695.
[65] M. Zaffalon, Inferenze e Decisioni in Condizioni di Incertezza con Modelli Grafici Orientati, PhD Thesis, Università di Milano, February 1997 (in Italian).; M. Zaffalon, Inferenze e Decisioni in Condizioni di Incertezza con Modelli Grafici Orientati, PhD Thesis, Università di Milano, February 1997 (in Italian).
[66] M. Zaffalon, Conservative rules for predictive inference with incomplete data, in: Fourth International Symposium on Imprecise Probabilities and their Applications, 2005, pp. 406-415.; M. Zaffalon, Conservative rules for predictive inference with incomplete data, in: Fourth International Symposium on Imprecise Probabilities and their Applications, 2005, pp. 406-415.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.