file.pdf (91.22 kB)
Preconditioner Approximations for Probabilistic Graphical Models
journal contribution
posted on 2006-06-01, 00:00 authored by Pradeep Ravikumar, John D. LaffertyWe 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.