Quadratic programming relaxations for metric labeling and Markov random field MAP estimation

ABSTRACT

Quadratic program relaxations are proposed as an alternative to linear program relaxations and tree reweighted belief propagation for the metric labeling or MAP estimation problem. An additional convex relaxation of the quadratic approximation is shown to have additive approximation guarantees that apply even when the graph weights have mixed sign or do not come from a metric. The approximations are extended in a manner that allows tight variational relaxations of the MAP problem, although they generally involve non-convex optimization. Experiments carried out on synthetic data show that the quadratic approximations can be more accurate and computationally efficient than the linear programming and propagation based alternatives.

REFERENCES

• 1: Owe Axelsson , Vincent A. Barker, Finite element solution of boundary value problems: theory and computation, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
• 2: Dimitris Bertsimas , John Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997
• 3: Besag, J. (1986). On the statistical analysis of dirty pictures. Journal of the Royal Statistical Society, Series B.
• 4: Yuri Boykov , Olga Veksler , Ramin Zabih, Fast Approximate Energy Minimization via Graph Cuts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.11, p.1222-1239, November 2001 [doi>10.1109/34.969114]
• 5: C. Chekuri , S. Khanna , J. Naor , L. Zosin, A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem, SIAM Journal on Discrete Mathematics, v.18 n.3, p.608-625, 2005 [doi>10.1137/S0895480101396937]
• 6: Greig, D., Porteous, B., & Seheult, A. (1989). Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society, Series B, 51.
• 7: Jon Kleinberg , Eva Tardos, Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.14, October 17-18, 1999
• 8: Kolmogorov, V. (2005). Convergent tree-reweighted message passing for energy minimization. AISTATS.
• 9: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 10: Wainwright, M., Jaakkola, T., & Willsky, A. (2005). Map estimation via agreement on (hyper)trees: Message-passing and linear-programming approaches. IEEE Transactions on Information Theory, 51, 3697--3717.
• 11: Wainwright, M. J., & Jordan, M. I. (2003). Variational inference in graphical models: The view from the marginal polytope. Allerton Conference on Communication, Control, and Computing.
• 12: Weiss, Y., & Freeman, W. T. (2001). On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs. IEEE Transactions on Information Theory, 47.
• 13: Yedidia, J. S., Freeman, W. T., & Weiss, Y. (2001). Understanding belief propagation and its generalizations. IJCAI 2001 Distinguished Lecture track.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Quadratic programming methods

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

General Terms:
Theory