nips nips2007 nips2007-141 nips2007-141-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: David Sontag, Tommi S. Jaakkola
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. 1
[1] E. Althaus, O. Kohlbacher, H.-P. Lenhof, and P. M¨ ller. A combinatorial approach to protein docking u with flexible side-chains. In RECOMB ’00, pages 15–24, 2000.
[2] F. Barahona. On cuts and matchings in planar graphs. Mathematical Programming, 60:53–68, 1993.
[3] F. Barahona, M. Gr¨ tschel, M. Junger, and G. Reinelt. An application of combinatorial optimization to o statistical physics and circuit layout design. Operations Research, 36(3):493–513, 1988.
[4] F. Barahona and A. R. Mahjoub. On the cut polytope. Mathematical Programming, 36:157–173, 1986.
[5] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2nd edition, 2001.
[6] M. M. Deza and M. Laurent. Geometry of Cuts and Metrics, volume 15 of Algorithms and Combinatorics. Springer, 1997.
[7] C. L. Kingsford, B. Chazelle, and M. Singh. Solving and analyzing side-chain positioning problems using linear and integer programming. Bioinformatics, 21(7):1028–1039, 2005.
[8] A. Koster, S. van Hoesel, and A. Kolen. The partial constraint satisfaction problem: Facets and lifting theorems. Operations Research Letters, 23:89–97, 1998.
[9] M. Wainwright, T. Jaakkola, and A. Willsky. MAP estimation via agreement on trees: message-passing and linear programming. IEEE Transactions on Information Theory, 51(11):3697–3717, November 2005.
[10] M. Wainwright, T. Jaakkola, and A. Willsky. A new class of upper bounds on the log partition function. IEEE Transactions on Information Theory, 51:2313–2335, July 2005.
[11] M. Wainwright and M. I. Jordan. Graphical models, exponential families and variational inference. Technical Report 649, UC Berkeley, Dept. of Statistics, 2003.
[12] M. Wainwright and M. I. Jordan. Log-determinant relaxation for approximate inference in discrete Markov random fields. IEEE Transactions on Signal Processing, 54(6):2099–2109, June 2006.
[13] D. B. West. Introduction to Graph Theory. Prentice Hall, 2001.
[14] C. Yanover, T. Meltzer, and Y. Weiss. Linear programming relaxations and belief propagation – an empirical study. JMLR Special Issue on Machine Learning and Large Scale Optimization, 7:1887–1907, September 2006.
[15] J. Yedidia, W. Freeman, and Y. Weiss. Bethe free energy, Kikuchi approximations, and belief propagation algorithms. Technical Report 16, Mitsubishi Electric Research Lab, 2001. 8