Diffusion methods for classification with pairwise relationships

Felzenszwalb, Pedro; Svaiter, Benar

doi:10.1090/qam/1540

Authors: Pedro F. Felzenszwalb and Benar F. Svaiter
Journal: Quart. Appl. Math. 77 (2019), 793-810
MSC (2010): Primary 05C85, 65Kxx, 05C81
DOI: https://doi.org/10.1090/qam/1540
Published electronically: April 29, 2019
MathSciNet review: 4009332
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We define two algorithms for propagating information in classification problems with pairwise relationships. The algorithms are based on contraction maps and are related to non-linear diffusion and random walks on graphs. The approach is also related to message passing algorithms, including belief propagation and mean field methods. The algorithms we describe are guaranteed to converge on graphs with arbitrary topology. Moreover they always converge to a unique fixed point, independent of initialization. We prove that the fixed points of the algorithms under consideration define lower bounds on the energy function and the max-marginals of a Markov random field. The theoretical results also illustrate a relationship between message passing algorithms and value iteration for an infinite horizon Markov decision process. We illustrate the practical application of the algorithms under study with numerical experiments in image restoration and stereo depth estimation.

References

Umberto Bertelè and Francesco Brioschi, Nonserial dynamic programming, Academic Press, New York-London, 1972. Mathematics in Science and Engineering, Vol. 91. MR 0416607
Dimitri P. Bertsekas, Dynamic programming and optimal control. Vol. I, 3rd ed., Athena Scientific, Belmont, MA, 2005. MR 2183196
Julian Besag, Spatial interaction and the statistical analysis of lattice systems, J. Roy. Statist. Soc. Ser. B 36 (1974), 192–236. MR 373208
Julian Besag, On the statistical analysis of dirty pictures, J. Roy. Statist. Soc. Ser. B 48 (1986), no. 3, 259–302. MR 876840
Andrew Blake and Andrew Zisserman, Visual reconstruction, MIT Press Series in Artificial Intelligence, MIT Press, Cambridge, MA, 1987. MR 919733
Endre Boros and Peter L. Hammer, Pseudo-Boolean optimization, Discrete Appl. Math. 123 (2002), no. 1-3, 155–225. Workshop on Discrete Optimization, DO’99 (Piscataway, NJ). MR 1922334, DOI https://doi.org/10.1016/S0166-218X%2801%2900341-9

Yuri Boykov, Olga Veksler, and Ramin Zabih, Fast approximate energy minimization via graph cuts, IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(11):1222–1239, 2001.

Pedro F Felzenszwalb and Daniel P Huttenlocher, Efficient belief propagation for early vision, International Journal of Computer Vision, 70(1):41–54, 2006.

Pedro F. Felzenszwalb and Daniel P. Huttenlocher, Distance transforms of sampled functions, Theory Comput. 8 (2012), 415–428. MR 2967180, DOI https://doi.org/10.4086/toc.2012.v008a019

Pedro F. Felzenszwalb and Ramin Zabih, Dynamic programming and graph algorithms in computer vision, IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(4):721–740, 2011.

S. Geman and D. Geman, Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images, IEEE Transactions on Pattern Analysis and Machine Intelligence, 6:721–741, 1984.

D. M. Greig, B. T. Porteous, and A. H. Seheult, Exact maximum a posteriori estimation for binary images, Journal of the Royal Statistical Society. Series B (Methodological), pages 271–279, 1989.

Jon Kleinberg and Éva Tardos, Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields, J. ACM 49 (2002), no. 5, 616–639. MR 2145145, DOI https://doi.org/10.1145/585265.585268

Daphne Koller and Nir Friedman, Probabilistic graphical models, Adaptive Computation and Machine Learning, MIT Press, Cambridge, MA, 2009. Principles and techniques. MR 2778120

Vladimir Kolmogorov and Ramin Zabih, What energy functions can be minimized via graph cuts? IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2):147–159, 2004.

László Lovász, Random walks on graphs: A survey, Combinatorics, Paul Erdos is Eighty, 2(1):1–46, 1993.

Talya Meltzer, Amir Globerson, and Yair Weiss, Convergent message passing algorithms: a unifying view, In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pages 393–401, 2009.

Pradeep Ravikumar, Alekh Agarwal, and Martin J. Wainwright, Message-passing for graph-structured linear programs: proximal methods and rounding schemes, J. Mach. Learn. Res. 11 (2010), 1043–1080. MR 2629824

Bogdan Savchynskyy, Stefan Schmidt, Jörg Kappes, and Christoph Schnörr, Efficient MRF energy minimization via adaptive diminishing smoothing, In Uncertainty in AI, 2012.

Martin J. Wainwright, Tommi S. Jaakkola, and Alan S. Willsky, MAP estimation via agreement on trees: message-passing and linear programming, IEEE Trans. Inform. Theory 51 (2005), no. 11, 3697–3717. MR 2238992, DOI https://doi.org/10.1109/TIT.2005.856938

Martin J. Wainwright and Michael I. Jordan, Graphical models, exponential families, and variational inference, Foundations and Trends® in Machine Learning, 1(1-2):1–305, 2008.