CMU thesis proposal: Approaches for approximate inference, structure learning and omputing event probability bounds in undirected graphical models

ate: 5/17/06 (Wednesday)
Time: 3:00pm
Place: 3305 Newell-Simon Hall
Speaker: Pradeep Ravikumar, PhD Candidate

Abstract:
Graphical models are a powerful tool for representing and manipulating probability distributions which are used in many fields, including image processing, document analysis, and error-control coding. In this thesis, we develop new approaches to three key tasks for undirected graphical models: inference, structure learning, and computing event probability bounds.

For the inference task of estimating the log-partition function and general event probabilities, we propose a preconditioner-based family of techniques. As with generalized mean field methods, the preconditioner approach focuses on sparse subgraphs, but optimizes linear system condition numbers rather than relative entropy. For the inference task of computing the maximum a posteriori (MAP) configuration, we propose a quadratic programming relaxation that is potentially more powerful than linear program relaxations and belief propagation approximations that are the current state of the art. The quadratic program relaxation is generally tight, but under certain conditions results in a non-convex problem, for which we propose a convex approximation with an additive bound guarantee. For the task of computing event probability bounds, we propose a family of generalized variational Chernoff bounds for graphical models, where we "variationally" derive probability bounds in terms of convex optimization problems involving certain support functions and a difference of log partition functions. For the task of learning the structure of the graph, instead of the standard heuristic search through the combinatorial space of graph structures, we are considering a parametrized optimization approach by looking at alternative parametrizations of the graph structure variable.

Thesis Committee:
John Lafferty (Chair)
Carlos Guestrin
Martin Wainwright (Univ. of California at Berkeley)
Eric Xing