nips nips2005 nips2005-154 nips2005-154-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: John D. Lafferty, Pradeep K. Ravikumar
Abstract: We present a family of approximation techniques for probabilistic graphical models, based on the use of graphical preconditioners developed in the scientific computing literature. Our framework yields rigorous upper and lower bounds on event probabilities and the log partition function of undirected graphical models, using non-iterative procedures that have low time complexity. As in mean field approaches, the approximations are built upon tractable subgraphs; however, we recast the problem of optimizing the tractable distribution parameters and approximate inference in terms of the well-studied linear systems problem of obtaining a good matrix preconditioner. Experiments are presented that compare the new approximation schemes to variational methods. 1
M. Bern, J. R. Gilbert, B. Hendrickson, N. Nguyen, and S. Toledo. Support-graph preconditioners. Submitted to SIAM J. Matrix Anal. Appl., 2001. E. G. Boman and B. Hendrickson. Support theory for preconditioning. SIAM Journal on Matrix Analysis and Applications, 25, 2003. K. Gremban. Combinatorial preconditioners for sparse, symmetric, diagonally dominant linear systems. Ph.D. Thesis, Carnegie Mellon University, 1996, 1996. P. Ravikumar and J. Lafferty. Variational Chernoff bounds for graphical models. Proceedings of Uncertainty in Artificial Intelligence (UAI), 2004. P. M. Vaidya. Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. 1990. Unpublished manuscript, UIUC. M. J. Wainwright, T. Jaakkola, and A. S. Willsky. Tree-reweighted belief propagation and approximate ML estimation by pseudo-moment matching. 9th Workshop on Artificial Intelligence and Statistics, 2003. J. S. Yedidia, W. T. Freeman, and Y. Weiss. Understanding belief propagation and its generalizations. IJCAI 2001 Distinguished Lecture track, 2001.