nips nips2008 nips2008-104 nips2008-104-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Philip Torr, M. P. Kumar
Abstract: We consider the problem of obtaining the approximate maximum a posteriori estimate of a discrete random field characterized by pairwise potentials that form a truncated convex model. For this problem, we propose an improved st-MINCUT based move making algorithm. Unlike previous move making approaches, which either provide a loose bound or no bound on the quality of the solution (in terms of the corresponding Gibbs energy), our algorithm achieves the same guarantees as the standard linear programming (LP) relaxation. Compared to previous approaches based on the LP relaxation, e.g. interior-point algorithms or treereweighted message passing (TRW), our method is faster as it uses only the efficient st-MINCUT algorithm in its design. Furthermore, it directly provides us with a primal solution (unlike TRW and other related methods which solve the dual of the LP). We demonstrate the effectiveness of the proposed approach on both synthetic and standard real data problems. Our analysis also opens up an interesting question regarding the relationship between move making algorithms (such as α-expansion and the algorithms presented in this paper) and the randomized rounding schemes used with convex relaxations. We believe that further explorations in this direction would help design efficient algorithms for more complex relaxations.
[1] K. Alahari, P. Kohli, and P. H. S. Torr. Reduce, reuse & recycle: Efficiently solving multi-label MRFs. In CVPR, 2008.
[2] J. Besag. On the statistical analysis of dirty pictures. Journal of the Royal Statistical Society, Series B, 48:259–302, 1986.
[3] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[4] Y. Boykov, O. Veksler, and R. Zabih. Fast approximate energy minimization via graph cuts. PAMI, 23(11):1222–1239, 2001.
[5] C. Chekuri, S. Khanna, J. Naor, and L. Zosin. A linear programming formulation and approximation algorithms for the metric labelling problem. SIAM Journal on Disc. Math., 18(3):606–635, 2005.
[6] P. Felzenszwalb and D. Huttenlocher. Efficient belief propagation for early vision. In CVPR, 2004.
[7] A. Globerson and T. Jaakkola. Fixing max-product: Convergent message passing for MAP LPrelaxations. In NIPS, 2007.
[8] A. Gupta and E. Tardos. A constant factor approximation algorithm for a class of classification problems. In STOC, 2000.
[9] H. Ishikawa. Exact optimization for Markov random fields with convex priors. PAMI, 25(10):1333–1336, October 2003.
[10] V. Kolmogorov. Convergent tree-reweighted message passing for energy minimization. PAMI, 28(10):1568–1583, 2006.
[11] V. Kolmogorov and C. Rother. Comparison of energy minimization algorithms for highly connected graphs. In ECCV, pages II: 1–15, 2006.
[12] V. Kolmogorov and A. Shioura. New algorithms for the dual of the convex cost network flow problem with applications to computer vision. Technical report, University College London, 2007.
[13] N. Komodakis, N. Paragios, and G. Tziritas. MRF optimization via dual decomposition: Message-passing revisited. In ICCV, 2007.
[14] N. Komodakis and G. Tziritas. Approximate labeling via graph-cuts based on linear programming. PAMI, 2007.
[15] A. Koster, C. van Hoesel, and A. Kolen. The partial constraint satisfaction problem: Facets and lifting theorems. Operations Research Letters, 23(3-5):89–97, 1998.
[16] M. P. Kumar, V. Kolmogorov, and P. H. S. Torr. An analysis of convex relaxations for MAP estimation. In NIPS, 2007.
[17] M. P. Kumar and P. H. S. Torr. Improved moves for truncated convex models. Technical report, University of Oxford, 2008.
[18] J. Lafferty, A. McCallum, and F. Pereira. Conditional random fields: Probabilistic models for segmenting and labelling sequence data. In ICML, 2001.
[19] J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kauffman, 1988.
[20] P. Ravikumar, A. Agarwal, and M. Wainwright. Message-passing for graph-structured linear programs: Proximal projections, convergence and rounding schemes. In ICML, 2008.
[21] M. Schlesinger. Sintaksicheskiy analiz dvumernykh zritelnikh singnalov v usloviyakh pomekh (syntactic analysis of two-dimensional visual signals in noisy conditions). Kibernetika, 4:113–130, 1976.
[22] R. Szeliski, R. Zabih, D. Scharstein, O. Veksler, V. Kolmogorov, A. Agarwala, M. Tappen, and C. Rother. A comparative study of energy minimization methods for Markov random fields with smoothness-based priors. PAMI, 2008.
[23] O. Veksler. Graph cut based optimization for MRFs with truncated convex priors. In CVPR, 2007.
[24] M. Wainwright, T. Jaakkola, and A. Willsky. MAP estimation via agreement on trees: Message passing and linear programming. IEEE Trans. on Information Theory, 51(11):3697–3717, 2005.
[25] Y. Weiss, C. Yanover, and T. Meltzer. MAP estimation, linear programming and belief propagation with convex free energies. In UAI, 2007. 8