nips nips2004 nips2004-116 nips2004-116-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Alexander T. Ihler, John W. Fisher, Alan S. Willsky
Abstract: Belief propagation (BP) is an increasingly popular method of performing approximate inference on arbitrary graphical models. At times, even further approximations are required, whether from quantization or other simplified message representations or from stochastic approximation methods. Introducing such errors into the BP message computations has the potential to adversely affect the solution obtained. We analyze this effect with respect to a particular measure of message error, and show bounds on the accumulation of errors in the system. This leads both to convergence conditions and error bounds in traditional and approximate BP message passing. 1
[1] Y. Weiss. Correctness of local probability propagation in graphical models with loops. Neural Computation, 12(1), 2000.
[2] S. Tatikonda and M. Jordan. Loopy belief propagation and gibbs measures. In UAI, 2002.
[3] T. Heskes. On the uniqueness of loopy belief propagation fixed points. To appear in Neural Computation, 2004.
[4] D. Koller, U. Lerner, and D. Angelov. A general algorithm for approximate inference and its application to hybrid Bayes nets. In UAI 15, pages 324–333, 1999.
[5] J. M. Coughlan and S. J. Ferreira. Finding deformable shapes using loopy belief propagation. In ECCV 7, May 2002.
[6] E. B. Sudderth, A. T. Ihler, W. T. Freeman, and A. S. Willsky. Nonparametric belief propagation. In CVPR, 2003.
[7] M. Isard. PAMPAS: Real–valued graphical models for computer vision. In CVPR, 2003.
[8] T. Minka. Expecatation propagation for approximate bayesian inference. In UAI, 2001.
[9] A. T. Ihler, J. W. Fisher III, and A. S. Willsky. Communication-constrained inference. Technical Report TR-2601, Laboratory for Information and Decision Systems, 2004.
[10] L. Chen, M. Wainwright, M. Cetin, and A. Willsky. Data association based on optimization in graphical models with application to sensor networks. Submitted to Mathematical and Computer Modeling, 2004.
[11] P. Clifford. Markov random fields in statistics. In G. R. Grimmett and D. J. A. Welsh, editors, Disorder in Physical Systems, pages 19–32. Oxford University Press, Oxford, 1990.
[12] J. Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufman, San Mateo, 1988.
[13] J. S. Yedidia, W. T. Freeman, and Y. Weiss. Constructing free energy approximations and generalized belief propagation algorithms. Technical Report 2004-040, MERL, May 2004.
[14] A. T. Ihler, J. W. Fisher III, and A. S. Willsky. Message errors in belief propagation. Technical Report TR-2602, Laboratory for Information and Decision Systems, 2004.
[15] Hans-Otto Georgii. Gibbs measures and phase transitions. Studies in Mathematics. de Gruyter, Berlin / New York, 1988.
[16] S. Julier and J. Uhlmann. A general method for approximating nonlinear transformations of probability distributions. Technical report, RRG, Dept. of Eng. Science, Univ. of Oxford, 1996.
[17] A. Willsky. Relationships between digital signal processing and control and estimation theory. Proc. IEEE, 66(9):996–1017, September 1978.