Accession Number:

AD1007221

Title:

New Outer Bounds on the Marginal Polytope

Descriptive Note:

Conference Paper

Corporate Author:

Massachusetts Institute of Technology Cambridge United States

Personal Author(s):

Report Date:

2007-12-06

Pagination or Media Count:

8.0

Abstract:

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 the approximations of the marginals are significantly more accurate when using the tighter outer bounds. Finally, we demonstrate the advantage of the new constraints for finding the MAP assignment in protein structure prediction.

Descriptors:

Subject Categories:

Distribution Statement:

APPROVED FOR PUBLIC RELEASE