Decomposition and Approximation of Loopy Bayesian Networks

• Autorzy: Dong, J. , Chen, F. , Huo, Y. , Liu, H.
• Języki publikacji: EN

Abstrakty

EN

This paper proposes a new method, conditional probability table (CPT) decomposition, to analyze the independent and deterministic components of CPT. This method can be used to approximate and analyze Baysian networks. The decomposition of Bayesian networks is accomplished by representing CPTs as a linear combination of extreme CPTs, which forms a new framework to conduct inference. Based on this new framework, inference in Bayesian networks can be done by decomposing them into less connected and weighted subnetworks. We can achieve exact inference if the original network is decomposed into singly-connected subnetworks. Besides, approximate inference can be done by discarding the subnetworks with small weights or by a partial decomposition and application of belief propagation (BP) on the still multiply-connected subnetworks. Experiments show that the decomposition-based approximation outperforms BP in most cases.

Słowa kluczowe

EN

Bayesian network; conditional probability table; decomposition; inference

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 125, nr 2
• Strony: 135--152
• Opis fizyczny: Bibliogr.19 poz., rys., wykr.

Twórcy

autor

Dong, J.

• Department of Automation, Tsinghua University, Beijing 100084, China,

autor

Chen, F.

• Department of Automation, Tsinghua University, Beijing 100084, China,

autor

Huo, Y.

• Department of Automation, Tsinghua University, Beijing 100084, China,

autor

Liu, H.

• Department of Automation, Tsinghua University, Beijing 100084, China,

Bibliografia

• [1] Boutilier, C., Friedman, N., Goldszmidt, M., Koller, D.: Context-Specific Independence in Bayesian Networks, Proceedings of the Twelfth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-96), Morgan Kaufmann, San Francisco, CA, 1996.
• [2] Choi, A., Darwiche, A.: An edge deletion semantics for belief propagation and its practical impact on approximation quality, proceedings of the 21st National Conference on Artificial Intelligence, AAAI Press, 2006.
• [3] Dechter, R.: Bucket Elimination: A Unifying Framework for Probabilistic Inference, Proceedings of the Twelfth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-96), 1996.
• [4] Diez, F. J., Galan, S. F.: Efficient computation for the noisy max, International Journal of Intelligent Systems, 18, 2002, 165 - 177.
• [5] Gomez, V, Kappen, H. J., Chertkov, M.: Approximate inference on planar graphs using loop calculus and belief propagation, Proceedings of the Twenty-Fifth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-09), Corvallis, Oregon, 2009.
• [6] Lauritzen, S. L., Spiegelhalter, D. J.: Local Computations with Probabilities on Graphical Structures and Their Application to Expert Systems, Journal of the Royal Statistical Society. Series B (Methodological), 50(2), 1988, 157-224.
• [7] Meshi, O., Jaimovich, A., Globerson, A., Friedman, N.: Convexifying the Bethe Free Energy, Proceedings of the Twenty-Fifth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-09), AUAI Press, Corvallis, Oregon, 2009.
• [8] Minka, T.: Expectation Propagation for approximate Bayesian inference, Proceedings of the Seventeenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-01), Morgan Kaufmann, San Francisco, CA, 2001.
• [9] Mooij, J., Kappen, H.: Loop corrections for approximate inference on factor graphs, The Journal of Machine Learning Research, 8, 2007, 1143.
• [10] Pakzad, P., Anantharam, V: Estimation and marginalization using Kikuchi approximation methods, Neural Computation, 17, 2003, 1836-1873.
• [11] Pearl, J.: Reverend Bayes on inference engines: A distributed hierarchical approach, Proceedings of the National Conference on Artificial Intelligence, Pittsburgh, PA, 1982.
• [12] Pearl, J.: Fusion, propagation, and structuring in belief networks, Artificial Intelligence, 29(3), 1986, 241 - 288.
• [13] Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1988.
• [14] Savicky, P., Vomlel, J.: Tensor rank-one decomposition of probability tables, the Proceedings of the 11th IPMU conference, Paris, France, July 2006.
• [15] Wainwright, M., Jaakkola, T., Willsky, A.: A new class of upper bounds on the log partition function, IEEE Transactions on Information Theory, 51(7), 2005, 2313 - 2335.
• [16] Wainwright, M. J., Jaakkola, T. S., Willsky, A. S.: Tree-reweighted belief propagation algorithms and approximate ML estimation via pseudo-moment matching, Workshop on Artificial Intelligence and Statistics, 2003.
• [17] Wainwright, M. J., Jordan, M. I.: Graphical Models, Exponential Families, and Variational Inference, Found. Trends Mach. Learn., 1, January 2008, 1-305.
• [18] Yedidia, J., Freeman, W., Weiss, Y.: Constructing free-energy approximations and generalized belief propagation algorithms, IEEE Transactions on Information Theory, 51(7), 2005, 2282-2312.
• [19] Zhang, N., Poole, D.: A simple approach to Bayesian network computations, Proceedings of the Biennial Conference-Canadian Society for Computational Studies of Intelligence, Citeseer, 1994.