file.pdf (91.22 kB)
Download file

Preconditioner Approximations for Probabilistic Graphical Models

Download (91.22 kB)
journal contribution
posted on 01.06.2006, 00:00 by Pradeep Ravikumar, John D. Lafferty
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.

History

Date

01/06/2006

Usage metrics

Exports