Principal Investigator Alan Willsky
Approximate Inference by Recursive Cavity Modeling
(*) Recursive cavity modeling (RCM) is an approximate inference method for MRFs that blends exact recursive inference with variational methods that minimize relative entropy. The key idea is to build cavity models of subfields. Each cavity model provides a tractable, approximate model for statistics on the boundary of a subfield that is useful for inference outside of the subfield. Using a nested dissection procedure, these cavity models and a complementary set of blanket models can be built up recursively. Ultimately, this leads to approximate computation of the marginal distribution of each variable in the MRF.(*) Model thinning plays an important role in this approach. This involves selecting a tractable approximation to a given MRF based on a sub-graph of the MRF (e.g., a cavity or blanket model in RCM), which requires both selection of a sub-graph and parameter optimization to minimize relative entropy over the class of MRFs defined on this sub-graph (an information projection). An efficient information projection method was developed using chordal graph embedding and exploiting certain tractable representations of Fisher information for MRFs defined on chordal graphs.
Maximum-Entroy Relaxation for Learning Graphical Structure
(*) Maximum entropy relaxation (MER) is a convex optimization approach for thinning MRF models that was originally formulated as a method to select cavity models in the context of Jason's RCM algorithm. The usual approach to model thinning is to select a tractable approximation to a given MRF, based on a sub-graph of the original MRF, which involves both selection of a sub-graph and parameter optimization in the class of MRFs defined on that sub-graph to minimize relative entropy. Because sub-graph selection is combinatorial, the MER approach was formulated as a tractable alternative that simultaneously selects both the sub-graph and corresponding parameters through solution of a convex optimization problem. Formally, we seek to maximize entropy subject to a relaxed set of marginal constraints, which require that the marginals of the relaxed distribution are close to the corresponding marginals in the orginal distribution in the sense of relative entropy.
(*) In joint work, this idea was formalized in an exponential family representation for Gaussian and Boltzmann models. An approach was developed to solve these problems using a modified primal-dual interior point method, which exploits sparsity of Fisher information in chordal MRFs, and an incremental method for identifying the active set of constraints in the MER problem.
Lagrangian Relaxation for Intractable Graphical Models
(*) Lagrangian relaxation (LR) is an approximate method to estimate the most probable configuration of an intractable MRF. LR is formulated with respect to an augmented graphical model, which includes replicas of the nodes and edges of the original graph. By dualizing the constraint that replicated variables (and, more generally, replicated features) must be equal in any valid assignment, we obtain a relaxed, convex "dual" problem, which is tractable to solve provided the augmented graph has a low tree width. In particular, if the augmented graph is chosen to correspond to a set of spanning trees of the original graph, then we recover essentially the same formalism as in the tree-reweighted max-product approach developed by Martin Wainwright. More generally, we allow relaxations based on small sub-graphs, narrow sub-graphs, "unwound" computation trees and multiscale representations. These extensions can lead to reduced duality gaps and faster convergence in the iterative methods used to solve the dual problem.
Walk-Sum Analysis for Gaussian Graphical Models
(*) An interesting spin-off of Jason's work in GMRFs has been the novel walk-sum interpretation of inference in Gaussian graphical models. In a technical report, Jason introduced the class of walk-summable models; characterized some important, easily identified sub-classes of these models and provided a walk-sum analysis of certain iterative estimation algorithms, namely, the Gauss-Jacobi iteration, the (stationary) embedded-tree (ET) algorithm and a special-case of the cyclic, two-tree ET iteration. Later on, in joint work, this picture was further refined and applied to give a new interpretation of Gaussian belief propagation, which was therefore shown to converge in walk-summable models. Later still, Venkat and Jason generalized the walk-sum interpretation of ET to a much broader class of algorithms, including iterations based on arbitrary (non-cyclic) sequences of tractable sub-graphs.