jmlr jmlr2006 jmlr2006-95 jmlr2006-95-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Dmitry M. Malioutov, Jason K. Johnson, Alan S. Willsky
Abstract: We present a new framework based on walks in a graph for analysis and inference in Gaussian graphical models. The key idea is to decompose the correlation between each pair of 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 correlation coefficients. This representation holds for a large class of Gaussian graphical models which we call walk-summable. We give a precise characterization of this class of models, and relate it to other classes including diagonally dominant, attractive, nonfrustrated, and pairwise-normalizable. 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. The walk-sum perspective leads to a better understanding of Gaussian belief propagation and to stronger results for its convergence in loopy graphs. Keywords: Gaussian graphical models, walk-sum analysis, convergence of loopy belief propagation
E. G. Boman, D. Chen, O. Parekh, and S. Toledo. On factor width and symmetric H-matrices. Linear Algebra and its Applications, 405, 2005. D. C. Brydges, J. Frohlich, and A. D. Sokal. The random-walk representation of classical spin systems and correlation inequalities. Communications in mathematical physics, 91, 1983. V. Chandrasekaran, J. Johnson, and A. Willsky. Walk-sum analysis and convergence of embedded subgraph algorithms. In preparation. R. G. Cowell, A. P. Dawid, S. L. Lauritzen, and D. J. Spiegelhalter. Probabilistic Networks and Expert Systems. Springer-Verlag, 1999. M. Fisher. Critical temperatures of anisotropic Ising lattices II, general upper bounds. Physical Review, 1967. R. Godement. Analysis I. Springer-Verlag, 2004. J. Hammersley and P. Clifford. Markov fields on finite graphs and lattices. Unpublished manuscript, 1971. L. He, X. Liu, and G. Strang. Laplacian eigenvalues of growing tees. In Conf. on Math. Theory of Networks and Systems, 2000. R. Horn and C. Johnson. Matrix Analysis. Cambridge University Press, 1985. R. Horn and C. Johnson. Topics in Matrix Analysis. Cambridge University Press, 1991. A. T. Ihler, J. W. Fisher III, and A. S. Willsky. Loopy belief propagation: Convergence and effects of message errors. Journal of Machine Learning Research, 6, May 2005. J. Johnson. Walk-summable Gauss-Markov random fields. Unpublished manuscript, available at http://www.mit.edu/people/jasonj, December 2001. J. Johnson, D. Malioutov, and A. Willsky. Walk-sum interpretation and analysis of Gaussian belief propagation. In Advances in Neural Information Processing Systems, 2006. B. Jones and M. West. Covariance decomposition in undirected Gaussian graphical models. Biometrika, 92(4), 2005. S. Kirkland, J. J. McDonald, and M. Tsatsomeros. Sign patterns that require positive eigenvalues. Linear and Multilinear Algebra, 41, 1996. S. Lauritzen. Graphical Models. Oxford Statistical Science Series. Oxford University Press, 1996. C. Moallemi and B. Van Roy. Consensus propagation. In Advances in Neural Information Processing Systems, 2006a. C. Moallemi and B. Van Roy. Convergence of the min-sum message passing algorithm for quadratic optimization. Technical Report, March 2006b. 2063 M ALIOUTOV, J OHNSON AND W ILLSKY J. Mooij and H. Kappen. Sufficient conditions for convergence of loopy belief propagation. In Proc. Uncertainty in Artificial Intelligence, 2005. J. Pearl. Probabilistic inference in intelligent systems. Morgan Kaufmann, 1988. K. Plarre and P. Kumar. Extended message passing algorithm for inference in loopy Gaussian graphical models. In Ad Hoc Networks, 2004. W. Rudin. Principles of Mathematical Analysis. McGraw Hill, 3rd edition, 1976. 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), 2001. T. Speed and H. Kiiveri. Gaussian Markov distributions over finite graphs. The Annals of Statistics, 14(1), 1986. E. Sudderth, M. Wainwright, and A. Willsky. Embedded trees: Estimation of Gaussian processes on graphs with cycles. IEEE Trans. Signal Processing, 52(11), November 2004. S. Tatikonda and M. Jordan. Loopy belief propagation and Gibbs measures. In Uncertainty in Artificial Intelligence, 2002. R. S. Varga. Matrix iterative analysis. Springer-Verlag, 2000. M. Wainwright, T. Jaakkola, and A. Willsky. Tree-based reparameterization framework for analysis of sum-product and related algorithms. IEEE Trans. Information Theory, 49(5), 2003. Y. Weiss and W. Freeman. Correctness of belief propagation in Gaussian graphical models of arbitrary topology. Neural Computation, 13, 2001. J. Yedidia, W. Freeman, and Y. Weiss. Understanding belief propagation and its generalizations. Exploring AI in the new millennium, 2003. 2064