jmlr jmlr2011 jmlr2011-34 jmlr2011-34-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Julian J. McAuley, TibĂŠrio S. Caetano
Abstract: Maximum A Posteriori inference in graphical models is often solved via message-passing algorithms, such as the junction-tree algorithm or loopy belief-propagation. The exact solution to this problem is well-known to be exponential in the size of the maximal cliques of the triangulated model, while approximate inference is typically exponential in the size of the model’s factors. In this paper, we take advantage of the fact that many models have maximal cliques that are larger than their constituent factors, and also of the fact that many factors consist only of latent variables (i.e., they do not depend on an observation). This is a common case in a wide variety of applications that deal with grid-, tree-, and ring-structured models. In such cases, we are able to decrease the exponent of complexity for message-passing by 0.5 for both exact and approximate inference. We demonstrate that message-passing operations in such models are equivalent to some variant of matrix multiplication in the tropical semiring, for which we offer an O(N 2.5 ) expected-case solution. Keywords: graphical models, belief-propagation, tropical matrix multiplication
Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms. AddisonWesley, 1983. Srinivas M. Aji and Robert J. McEliece. The generalized distributive law. IEEE Transactions on Information Theory, 46(2):325–343, 2000. Noga Alon, Zvi Galil, and Oded Margalit. On the exponent of the all pairs shortest path problem. Journal of Computer and System Sciences, 54(2):255–262, 1997. Xiang Bai, Xingwei Yang, Longin Jan Latecki, Wenyu Liu, and Zhuowen Tu. Learning contextsensitive shape similarity by graph transduction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(5):861–874, 2009. Timothy M. Chan. More algorithms for all-pairs shortest paths in weighted graphs. In Annual ACM Symposium on Theory of Computing, pages 590–598, 2007. James M. Coughlan and Sabino J. Ferreira. Finding deformable shapes using loopy belief propagation. In ECCV, 2002. Ren´ Donner, Georg Langs, and Horst Bischof. Sparse MRF appearance models for fast anatomical e structure localisation. In BMVC, 2007. Gal Elidan, Ian Mcgraw, and Daphne Koller. Residual belief propagation: informed scheduling for asynchronous message passing. In UAI, 2006. Pedro F. Felzenszwalb. Representation and detection of deformable shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(2):208–220, 2005. Pedro F. Felzenszwalb and Daniel P. Huttenlocher. EfÄ?Ĺš cient belief propagation for early vision. International Journal of Computer Vision, 70(1):41–54, 2006. 1386 FASTER A LGORITHMS FOR M AX -P RODUCT M ESSAGE -PASSING Robert W. Floyd. Algorithm 97: Shortest path. Communications of the ACM, 5(6):345, 1962. Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596–615, 1987. Delbert R. Fulkerson and O. A. Gross. Incidence matrices and interval graphs. PaciÄ?Ĺš c Journal of Mathematics, (15):835–855, 1965. Michel Galley. A skip-chain conditional random Ä?Ĺš eld for ranking meeting utterances by importance. In EMNLP, 2006. Stuart Geman and Donald Geman. Stochastic relaxation, gibbs distribution and the bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6(6):721–741, 1984. David R. Karger, Daphne Koller, and Steven J. Phillips. Finding the hidden path: time bounds for all-pairs shortest paths. SIAM Journal of Computing, 22(6):1199–1217, 1993. Leslie R. Kerr. The effect of algebraic structure on the computational complexity of matrix multiplication. PhD Thesis, 1970. Kristian Kersting, Babak Ahmadi, and Sriraam Natarajan. Counting belief propagation. In UAI, 2009. Uffe KjÄ‚Ĺšrulff. Inference in bayesian networks using nested junction trees. In Proceedings of the NATO Advanced Study Institute on Learning in Graphical Models, 1998. Vladimir Kolmogorov and Akiyoshi Shioura. New algorithms for the dual of the convex cost network Ä?Ĺš‚ow problem with application to computer vision. Technical report, University College London, 2007. Frank R. Kschischang, Brendan J. Frey, and Hans-Andrea Loeliger. Factor graphs and the sumproduct algorithm. IEEE Transactions on Information Theory, 47(2):498–519, 2001. M. Pawan Kumar and Philip Torr. Fast memory-efÄ?Ĺš cient generalized belief propagation. In ECCV, 2006. Xiang-Yang Lan, Stefan Roth, Daniel P. Huttenlocher, and Michael J. Black. EfÄ?Ĺš cient belief propagation with learned higher-order markov random Ä?Ĺš elds. In ECCV, 2006. Bruce D. Lucas and Takeo Kanade. An iterative image registration technique with an application to stereo vision. In IJCAI, 1981. Julian J. McAuley and Tib´ rio S. Caetano. Exact inference in graphical models: is there more to it? e CoRR, abs/0910.3301, 2009. Julian J. McAuley and Tib´ rio S. Caetano. Exploiting within-clique factorizations in junction-tree e algorithms. AISTATS, 2010a. Julian J. McAuley and Tib´ rio S. Caetano. Exploiting data-independence for fast belief-propagation. e ICML, 2010b. 1387 M C AULEY AND C AETANO Julian J. McAuley, Tib´ rio S. Caetano, and Marconi S. Barbosa. Graph rigidity, cyclic belief prope agation and point pattern matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 30(11):2047–2054, 2008. Alistair Moffat and Tadao Takaoka. An all pairs shortest path algorithm with expected time O(n2 log n). SIAM Journal of Computing, 16(6):1023–1031, 1987. James D. Park and Adnan Darwiche. A differential semantics for jointree algorithms. In NIPS, 2003. Mark A. Paskin. Thin junction tree Ä?Ĺš lters for simultaneous localization and mapping. In IJCAI, 2003. Kersten Petersen, Janis Fehr, and Hans Burkhardt. Fast generalized belief propagation for MAP estimation on 2D and 3D grid-like markov random Ä?Ĺš elds. In DAGM, 2008. Daniel Scharstein and Richard S. Szeliski. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. International Journal of Computer Vision, 47(1–3):7–42, 2001. Leonid Sigal and Michael J. Black. Predicting 3D people from 2D pictures. In AMDO, 2006. David Sontag, Talya Meltzer, Amir Globerson, Tommi Jaakkola, and Yair Weiss. Tightening LP relaxations for MAP using message passing. In UAI, 2008. Volker Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 14(3):354–356, 1969. Jian Sun, Nan-Ning Zheng, and Heung-Yeung Shum. Stereo matching using belief propagation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(7):787–800, 2003. Charles Sutton and Andrew McCallum. Introduction to Conditional Random Fields for Relational Learning. MIT Press, 2006. Philip A. Tresadern, Harish Bhaskar, Steve A. Adeshina, Chris J. Taylor, and Tim F. Cootes. Combining local and global shape models for deformable object matching. In BMVC, 2009. Yair Weiss. Correctness of local probability propagation in graphical models with loops. Neural Computation, 12:1–41, 2000. Ryan Williams. Matrix-vector multiplication in sub-quadratic time (some preprocessing required). In SODA, pages 1–11, 2007. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems. In FOCS, 2010. 1388