nips nips2008 nips2008-40 nips2008-40-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Joris M. Mooij, Hilbert J. Kappen
Abstract: We propose a novel bound on single-variable marginal probability distributions in factor graphs with discrete variables. The bound is obtained by propagating local bounds (convex sets of probability distributions) over a subtree of the factor graph, rooted in the variable of interest. By construction, the method not only bounds the exact marginal probability distribution of a variable, but also its approximate Belief Propagation marginal (“belief”). Thus, apart from providing a practical means to calculate bounds on marginals, our contribution also lies in providing a better understanding of the error made by Belief Propagation. We show that our bound outperforms the state-of-the-art on some inference problems arising in medical diagnosis. 1
[1] G.F. Cooper. The computational complexity of probabilistic inferences. Artificial Intelligence, 42(23):393–405, March 1990.
[2] J. Pearl. Probabilistic Reasoning in Intelligent systems: Networks of Plausible Inference. Morgan Kaufmann, San Francisco, CA, 1988.
[3] M.J. Wainwright, T.S. Jaakkola, and A.S. Willsky. Tree-based reparameterization framework for analysis of sum-product and related algorithms. IEEE Transactions on Information Theory, 49(5):1120–1146, May 2003.
[4] S. C. Tatikonda. Convergence of the sum-product algorithm. In Proceedings 2003 IEEE Information Theory Workshop, pages 222–225, April 2003.
[5] Nobuyuki Taga and Shigeru Mase. Error bounds between marginal probabilities and beliefs of loopy belief propagation algorithm. In MICAI, pages 186–196, 2006.
[6] A. Ihler. Accuracy bounds for belief propagation. In Proceedings of the 23th Annual Conference on Uncertainty in Artificial Intelligence (UAI-07), July 2007.
[7] T. S. Jaakkola and M. Jordan. Recursive algorithms for approximating probabilities in graphical models. In Proc. Conf. Neural Information Processing Systems (NIPS 9), pages 487–493, Denver, CO, 1996.
[8] M. J. Wainwright, T. Jaakkola, and A. S. Willsky. A new class of upper bounds on the log partition function. IEEE Transactions on Information Theory, 51:2313–2335, July 2005.
[9] M. A. R. Leisink and H. J. Kappen. A tighter bound for graphical models. In Lawrence K. Saul, Yair Weiss, and L´ on Bottou, editors, Advances in Neural Information Processing Systems 13 (NIPS*2000), e pages 266–272, Cambridge, MA, 2001. MIT Press.
[10] M. Leisink and B. Kappen. Bound propagation. Journal of Artificial Intelligence Research, 19:139–154, 2003.
[11] J. M. Mooij and H. J. Kappen. Novel bounds on marginal probabilities. arXiv.org, arXiv:0801.3797 [math.PR], January 2008. Submitted to Journal of Machine Learning Research.
[12] S. C. Tatikonda and M. I. Jordan. Loopy belief propagation and Gibbs measures. In Proc. of the 18th Annual Conf. on Uncertainty in Artificial Intelligence (UAI-02), pages 493–500, San Francisco, CA, 2002. Morgan Kaufmann Publishers.
[13] J. M. Mooij. libDAI: A free/open source C++ library for discrete approximate inference methods, 2008. http://mloss.org/software/view/77/.
[14] B. Wemmenhove, J. M. Mooij, W. Wiegerinck, M. Leisink, H. J. Kappen, and J. P. Neijt. Inference in the Promedas medical expert system. In Proceedings of the 11th Conference on Artificial Intelligence in Medicine (AIME 2007), volume 4594 of Lecture Notes in Computer Science, pages 456–460. Springer, 2007.