nips nips2009 nips2009-141 nips2009-141-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Kyomin Jung, Pushmeet Kohli, Devavrat Shah
Abstract: We consider the question of computing Maximum A Posteriori (MAP) assignment in an arbitrary pair-wise Markov Random Field (MRF). We present a randomized iterative algorithm based on simple local updates. The algorithm, starting with an arbitrary initial assignment, updates it in each iteration by first, picking a random node, then selecting an (appropriately chosen) random local neighborhood and optimizing over this local neighborhood. Somewhat surprisingly, we show that this algorithm finds a near optimal assignment within n log 2 n iterations with high probability for any n node pair-wise MRF with geometry (i.e. MRF graph with polynomial growth) with the approximation error depending on (in a reasonable manner) the geometric growth rate of the graph and the average radius of the local neighborhood – this allows for a graceful tradeoff between the complexity of the algorithm and the approximation error. Through extensive simulations, we show that our algorithm finds extremely good approximate solutions for various kinds of MRFs with geometry.
[1] M. Bayati, D. Shah, and M. Sharma. Maximum weight matching via max-product belief propagation. In IEEE ISIT, 2005.
[2] M. Bayati, D. Shah, and M. Sharma. Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality. IEEE Transactions on Information Theory, 54(3):1241– 1251, 2008.
[3] Y. Boykov, O. Veksler, and R. Zabih. Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell., 23(11):1222–1239, 2001.
[4] William Feller. An Introduction to Probability Theory and Its Applications. Wiley, 1957.
[5] Hans-Otto Georgii. Gibbs measures and phase transitions. Walter de Gruyter, 1988.
[6] A. Gupta, R. Krauthgamer, and J.R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In In Proceedings of the 44th annual Symposium on the Foundations of Computer Science, 2003.
[7] S. Har-Peled and M. Mendel. Fast construction of nets in low dimensional metrics, and their applications. In Proceedings of the twenty-first annual symposium on Computational geometry, pages 150–158. ACM New York, NY, USA, 2005.
[8] B. Huang and T. Jebara. Loopy belief propagation for bipartite maximum weight b-matching. Artificial Intelligence and Statistics (AISTATS), 2007.
[9] N. Komodakis and G. Tziritas. A new framework for approximate labeling via graph cuts. In International Conference on Computer Vision, pages 1018–1025, 2005.
[10] M. Pawan Kumar and Philip H. S. Torr. Improved moves for truncated convex models. In NIPS, pages 889–896, 2008.
[11] Stan Z. Li. Markov Random Field Modeling in Image Analysis. Springer, 2001.
[12] M. Malfait and D. Roose. Wavelet-based image denoising using a markov random field a priori model. IEEE Transactions on : Image Processing, 6(4):549–565, 1997.
[13] Christopher D. Manning and Hinrich Schutze. Foundations of Statistical Natural Language Processing. The MIT Press, 1999.
[14] J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. San Francisco, CA: Morgan Kaufmann, 1988.
[15] Thomas Richardson and Ruediger Ubanke. Modern Coding Theory. Cambridge University Press, 2008.
[16] S. Sanghavi, D. Shah, and A. Willsky. Message-passing for Maximum Weight Independent Set. In Proceedings of NIPS, 2007.
[17] R. Swendsen and J. Wang. Nonuniversal critical dynamics in monte carlo simulations. Phys. Rev. Letter., 58:86–88, 1987.
[18] O. Veksler. Graph cut based optimization for mrfs with truncated convex priors. In CVPR, 2007.
[19] Paul Viola and Michael J. Jones. Robust real-time face detection. International Journal of Computer Vision, 57(2):137–154, 2004.
[20] M. Wainwright and M. Jordan. Graphical models, exponential families, and variational inference. UC Berkeley, Dept. of Statistics, Technical Report 649, 2003.
[21] M. J. Wainwright, T. Jaakkola, and A. S. Willsky. Map estimation via agreement on (hyper)trees: Message-passing and linear-programming approaches. IEEE Transactions on Information Theory, 2005.
[22] J. Yedidia, W. Freeman, and Y. Weiss. Generalized belief propagation. Mitsubishi Elect. Res. Lab., TR-2000-26, 2000. 9