nips nips2012 nips2012-214 nips2012-214-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Andrew Delong, Olga Veksler, Anton Osokin, Yuri Boykov
Abstract: Inference in high-order graphical models has become important in recent years. Several approaches are based, for example, on generalized message-passing, or on transformation to a pairwise model with extra ‘auxiliary’ variables. We focus on a special case where a much more efficient transformation is possible. Instead of adding variables, we transform the original problem into a comparatively small instance of submodular vertex-cover. These vertex-cover instances can then be attacked by existing algorithms (e.g. belief propagation, QPBO), where they often run 4–15 times faster and find better solutions than when applied to the original problem. We evaluate our approach on synthetic data, then we show applications within a fast hierarchical clustering and model-fitting framework. 1
[1] Aggarwal, C.C., Orlin, J.B., & Tai, R.P. (1997) Optimized Crossover for the Independent Set Problem. Operations Research 45(2):226–234.
[2] Ahuja, R.K., Orlin, J.B., Stein, C. & Tarjan, R.E. (1994) Improved algorithms for bipartite network flow. SIAM Journal on Computing 23(5):906–933. ¨
[3] Ahuja, R.K., Ergun, O., Orlin, J.B., & Punnen, A.P. (2002) A survey of very large-scale neighborhood search techniques. Discrete Applied Mathematics 123(1–3):75–202.
[4] Delong, A., Veksler, O. & Boykov, Y. (2012) Fast Fusion Moves for Multi-Model Estimation. European Conference on Computer Vision.
[5] Boros, E. & Hammer, P.L. (2002) Pseudo-Boolean Optimization. Discrete App. Math. 123(1–3):155–225.
[6] Boykov, Y., Veksler, O., & Zabih, R. (2001) Fast Approximate Energy Minimization via Graph Cuts. IEEE Transactions on Pattern Recognition and Machine Intelligence. 23(11):1222–1239. 8
[7] Delong, A., Osokin, A., Isack, H.N., & Boykov, Y. (20120) Fast Approximate Energy Minimization with Label Costs. International Journal of Computer Vision 96(1):127. Earlier version in CVPR 2010.
[8] Delong, A., Veksler, O., Osokin, A., & Boykov, Y. (2012) Minimizing Sparse High-Order Energies by Submodular Vertex-Cover. Technical Report, Western University.
[9] Denis, P., Elder, J., & Estrada, F. (2008) Efficient Edge-Based Methods for Estimating Manhattan Frames in Urban Imagery. European Conference on Computer Vision.
[10] Freedman, D. & Drineas, P. (2005) Energy minimization via graph cuts: settling what is possible. IEEE Conference on Computer Vision and Pattern Recognition.
[11] Gallagher, A.C., Batra, D., & Parikh, D. (2011) Inference for order reduction in Markov random fields. IEEE Conference on Computer Vision and Pattern Recognition.
[12] Givoni, I.E., Chung, C., & Frey, B.J. (2011) Hierarchical Affinity Propagation. Uncertainty in AI.
[13] Gupta, R., Diwan, A., & Sarawagi, S. (2007) Efficient inference with cardinality-based clique potentials. International Conference on Machine Learning.
[14] Hammer, P.L., Hansen, P., & Simeone, B. (1984) Roof duality, complementation and persistency in quadratic 0-1 optimization. Mathematical Programming 28:121–155.
[15] Hochbaum, D.S. (2010) Submodular problems – approximations and algorithms. Arxiv preprint arXiv:1010.1945.
[16] Iwata, S., Fleischer, L. & Fujishige, S. (2001) A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions. Journal of the ACM 48:761–777.
[17] Iwata, S. & Orlin, J.B. (2009) A simple combinatorial algorithm for submodular function minimization. ACM-SIAM Symposium on Discrete Algorithms.
[18] Iwata, S. & Nagano, K. (2009) Submodular Function Minimization under Covering Constraints. IEEE Symposium on Foundations of Computer Science.
[19] Kohli, P., Kumar, M.P. & Torr, P.H.S. (2007) P 3 & Beyond: Solving Energies with Higher Order Cliques. IEEE Conference on Computer Vision and Pattern Recognition.
[20] Kolmogorov, V. (2010) Minimizing a sum of submodular functions. Arxiv preprint arXiv:1006.1990.
[21] Kolmogorov, V. (2006) Convergent Tree-Reweighted Message Passing for Energy Minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence 28(10):1568–1583.
[22] Kolmogorov, V., & Wainwright, M.J. (2005) On the optimality of tree-reweighted max-product messagepassing. Uncertainty in Artificial Intelligence.
[23] Kolmogorov, V. & Zabih, R. (2004) What Energy Functions Can Be Optimized via Graph Cuts? IEEE Transactions on Pattern Analysis and Machine Intelligence 26(2):147–159.
[24] Komodakis, N., Paragios, N., & Tziritas, G. (2008) Clustering via LP-based Stabilities. Neural Information Processing Systems.
[25] Komodakis, N., & Paragios, N. (2009) Beyond pairwise energies: Efficient optimization for higher-order MRFs. IEEE Computer Vision and Pattern Recognition.
[26] Ladick´ , L., Russell, C., Kohli, P., & Torr, P.H.S (2010) Graph Cut based Inference with Co-occurrence y Statistics. European Conference on Computer Vision.
[27] Lempitsky, V., Rother, C., Roth, S., & Blake, A. (2010) Fusion Moves for Markov Random Field Optimization. IEEE Transactions on Pattern Analysis and Machine Inference. 32(9):1392–1405.
[28] Nemhauser, G.L. and Trotter, L.E. (1975) Vertex packings: Structural properties and algorithms. Mathematical Programming 8(1):232–248.
[29] Osokin, A., & Vetrov, D. (2012) Submodular relaxations for MRFs with high-order potentials. HiPot: ECCV Workshop on Higher-Order Models and Global Constraints in Computer Vision.
[30] Pearl, J. (1988) Fusion, propagation, and structuring in belief networks. Artificial Intell. 29(3):251–288.
[31] Rother, C., Kohli, P., Feng, W., & Jia, J. (2009) Minimizing sparse higher order energy functions of discrete variables. IEEE Conference on Computer Vision and Pattern Recognition.
[32] Rother, C., Kolmogorov, V., Lempitsky, V., & Szummer, M. (2007) Optimizing Binary MRFs via Extended Roof Duality. IEEE Conference on Computer Vision and Pattern Recognition.
[33] Sontag, D., Meltzer, T., Globerson, A., Jaakkola, T., & Weiss, Y. (2008) Tightening LP relaxations for MAP using message passing. Uncertainty in Artificial Intelligence.
[34] Tarlow, D., Givoni, I.E., & Zemel, R.S. (2010) HOPMAP: Efficient message passing with high order potentials. International Conference on Artificial Intelligence and Statistics.
[35] Tarlow, D., & Zemel, R. (2012) Structured Output Learning with High Order Loss Functions. International Conference on Artificial Intelligence and Statistics.
[36] Tretyak, E., Barinova, O., Kohli, P., & Lempitsky, V. (2011) Geometric Image Parsing in Man-Made Environments. International Journal of Computer Vision 97(3):305–321.
[37] Tsang, E. (1993) Foundations of constraint satisfaction. Academic Press, London.
[38] Werner, T. (2008) High-arity Interactions, Polyhedral Relaxations, and Cutting Plane Algorithm for Soft Constraint Optimisation (MAP-MRF). IEEE Conference on Computer Vision and Pattern Recognition. 9