Timezone: »

 
Oral
New Outer Bounds on the Marginal Polytope
David Sontag · Tommi Jaakkola

Tue Dec 04 11:10 AM -- 11:30 AM (PST) @
in Session 2: Probabilistic Optimization »

We give a new class of outer bounds on the marginal polytope, and propose a cutting-plane algorithm for efficiently optimizing over these constraints. When combined with a concave upper bound on the entropy, this gives a new variational inference algorithm for probabilistic inference in discrete Markov Random Fields (MRFs). Valid constraints on the marginal polytope are derived through a series of projections onto the cut polytope. As a result, we obtain tighter upper bounds on the log-partition function. We also show empirically that our approximations of the marginals are significantly more accurate. Moreover, we demonstrate the advantage from the new constraints in finding the MAP assignment for protein structure prediction.

Author Information

David Sontag (MIT)
Tommi Jaakkola (MIT)

Tommi Jaakkola is a professor of Electrical Engineering and Computer Science at MIT. He received an M.Sc. degree in theoretical physics from Helsinki University of Technology, and Ph.D. from MIT in computational neuroscience. Following a Sloan postdoctoral fellowship in computational molecular biology, he joined the MIT faculty in 1998. His research interests include statistical inference, graphical models, and large scale modern estimation problems with predominantly incomplete data.

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors