nips nips2005 nips2005-204 nips2005-204-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Dmitry Malioutov, Alan S. Willsky, Jason K. Johnson
Abstract: This paper presents a new framework based on walks in a graph for analysis and inference in Gaussian graphical models. The key idea is to decompose correlations between variables as a sum over all walks between those variables in the graph. The weight of each walk is given by a product of edgewise partial correlations. We provide a walk-sum interpretation of Gaussian belief propagation in trees and of the approximate method of loopy belief propagation in graphs with cycles. This perspective leads to a better understanding of Gaussian belief propagation and of its convergence in loopy graphs. 1
[1] J. Pearl. Probabilistic inference in intelligent systems. Morgan Kaufmann, 1988.
[2] J. Yedidia, W. Freeman, and Y. Weiss. Understanding belief propagation and its generalizations. Exploring AI in the new millennium, pages 239–269, 2003.
[3] Y. Weiss and W. Freeman. Correctness of belief propagation in Gaussian graphical models of arbitrary topology. Neural Computation, 13:2173–2200, 2001.
[4] P. Rusmevichientong and B. Van Roy. An analysis of belief propagation on the turbo decoding graph with Gaussian densities. IEEE Trans. Information Theory, 48(2):745–765, Feb. 2001.
[5] S. Tatikonda and M. Jordan. Loopy belief propagation and Gibbs measures. UAI, 2002.
[6] J. Johnson, D. Malioutov, and A. Willsky. Walk-Summable Gaussian Networks and Walk-Sum Interpretation of Gaussian Belief Propagation. TR-2650, LIDS, MIT, 2005.
[7] K. Plarre and P. Kumar. Extended message passing algorithm for inference in loopy Gaussian graphical models. Ad Hoc Networks, 2004.
[8] M. Fisher. Critical temperatures of anisotropic Ising lattices II, general upper bounds. Physical Review, 162(2), 1967.
[9] A. Ihler, J. Fisher III, and A. Willsky. Message Errors in Belief Propagation. NIPS, 2004. ˆ ˆ Modify (8) as follows: ∆hi→j = (1 − α)∆hi→j + α(−Ji,j (Ji\j )−1 hi\j ) with 0 < α ≤ 1. In Example 2, with ρ = .39867 and α = .9 the means converge. 7 (n+1) (n) (n) (n)