×

Message-passing algorithms for inference and optimization. (English) Zbl 1252.82012

Summary: Message-passing algorithms can solve a wide variety of optimization, inference, and constraint satisfaction problems. The algorithms operate on factor graphs that visually represent and specify the structure of the problems. After describing some of their applications, I survey the family of belief propagation (BP) algorithms, beginning with a detailed description of the min-sum algorithm and its exactness on tree factor graphs, and then turning to a variety of more sophisticated BP algorithms, including free-energy based BP algorithms, “splitting” BP algorithms that generalize “tree-reweighted” BP, and the various BP algorithms that have been proposed to deal with problems with continuous variables.
The divide and conquer (DC) algorithm is a projection-based constraint satisfaction algorithm that deals naturally with continuous variables, and converges to exact answers for problems where the solution sets of the constraints are convex. I show how it exploits the “difference-map” dynamics to avoid traps that cause more naive alternating projection algorithms to fail for non-convex problems, and explain that it is a message-passing algorithm that can also be applied to optimization problems. The BP and DC algorithms are compared, both in terms of their fundamental justifications and their strengths and weaknesses.

MSC:

82-08 Computational methods (statistical mechanics) (MSC2010)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
65Y05 Parallel numerical computation
90B10 Deterministic network models in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bahl, L., Cocke, J., Jelinek, F., Raviv, J.: Optimal decoding of linear codes for minimizing symbol error rate. IEEE Trans. Inf. Theory 20, 284–287 (1974) · Zbl 0322.94005 · doi:10.1109/TIT.1974.1055186
[2] Barber, D.: Bayesian Reasoning and Machine Learning. Cambridge University Press, Cambridge (2011) · Zbl 1267.68001
[3] Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, Berlin (2011) · Zbl 1218.47001
[4] Bauschke, H.H., Combettes P.L., Luke D.R.: Phase retrieval, error reduction algorithm, and Fienup variants: a view from convex optimization. J. Opt. Soc. Am. A 19, 1334–1345 (2002) · doi:10.1364/JOSAA.19.001334
[5] Baxter, R.J.: Exactly Solved Models in Statistical Mechanics. Academic Press, San Diego (1982) · Zbl 0538.60093
[6] Berrou, C., Glavieux, A., Thitimajshima, P.: Near Shannon limit error-correcting coding and decoding: turbo-codes. In: Proc. 1993 IEEE Int. Conf. on Comm., pp. 1064–1070 (1993)
[7] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049
[8] Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimisation via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 29, 1222–1239 (2001) · doi:10.1109/34.969114
[9] Braunstein, A., Mézard, M., Parisi, G.: Survey propagation: an algorithm for satisfiability. Random Struct. Algorithms 27, 201–226 (2005) · Zbl 1087.68126 · doi:10.1002/rsa.20057
[10] Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. 35, 677–691 (1986) · Zbl 0593.94022 · doi:10.1109/TC.1986.1676819
[11] Chertkov, M., Chernyak, M.: Loop series for discrete statistical models on graphs. J. Stat. Mech. (2006) doi: 10.1088/1742-5468/2006/06/P06009 · Zbl 1244.82059
[12] Cormen, C.H., Leiserson, C.E., Rivest, R.L., Stein, C.: An Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009). Chap. 15 · Zbl 1187.68679
[13] Douglas, J., Rachford, H.H.: On the numerical solution of heat conduction problems in two or three space variables. Trans. Am. Math. Soc. 82, 421–439 (1956) · Zbl 0070.35401 · doi:10.1090/S0002-9947-1956-0084194-4
[14] Durbin, R., Eddy, S.R., Krogh, A., Mitchison, G.: Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, Cambridge (1998) · Zbl 0929.92010
[15] Elser, V., Rankenburg, I.: Deconstructing the energy landscape: constraint-based algorithms for folding heteropolymers. Phys. Rev. E 73, 026702 (2006) · doi:10.1103/PhysRevE.73.026702
[16] Elser, V., Rankenburg, I., Thibault, P.: Searching with iterated maps. Proc. Natl. Acad. Sci. USA 104, 418–423 (2007) · Zbl 1160.90495 · doi:10.1073/pnas.0606359104
[17] Felzenszwalb, P.F., Huttnelocher, D.P.: Efficient belief propagation for early vision. Int. J. Comput. Vis. 70, 41–54 (2006) · Zbl 05062736 · doi:10.1007/s11263-006-7899-4
[18] Fienup, J.R.: Phase retrieval algorithms: a comparison. Appl. Opt. 21, 2758–2769 (1982) · doi:10.1364/AO.21.002758
[19] Forney, G.D.: Codes on graphs: normal realizations. IEEE Trans. Inf. Theory 47, 520–548 (2001) · Zbl 0998.94021 · doi:10.1109/18.910573
[20] Forney, G.D.: The Viterbi algorithm. Proc. IEEE 61, 268–278 (1973) · doi:10.1109/PROC.1973.9030
[21] Freeman, W.T., Pasztor, E.C., Charmichael, O.T.: Learning low-level vision. Int. J. Comput. Vis. 40, 25–47 (2000) · Zbl 1012.68700 · doi:10.1023/A:1026501619075
[22] Gallager, R.G.: Information Theory and Reliable Communication. Wiley, New York (1968) · Zbl 0198.52201
[23] Gallager, R.G.: Low-Density Parity-Check Codes. MIT Press, Cambridge (1963) · Zbl 0156.40701
[24] Gamarnik, D., Shah, D., Wei, Y.: Belief propagation for min-cost network flow: convergence and correctness. In: Proc. of the 2010 ACM-SIAM Symp. on Discrete Algorithms (2010) · Zbl 1288.90116
[25] Geman, S., Geman, D.: Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images. IEEE Trans. Pattern Anal. Mach. Intell. 6, 721–741 (1984) · Zbl 0573.62030 · doi:10.1109/TPAMI.1984.4767596
[26] Gravel, S.: Using symmetries to solve asymmetric problems. Ph.D. dissertation, Cornell University, Ithica, NY (2009)
[27] Gravel, S., Elser, V.: Divide and concur: a general approach to constraint satisfaction. Phys. Rev. E 78, 036706 (2008) · doi:10.1103/PhysRevE.78.036706
[28] Hershey, J.R., Rennie, S.J., Olsen, P.A., Kristjansson, T.T.: Super-human multi-talker speech recognition: a graphical modeling approach. Comput. Speech Lang. 24, 45–66 (2010) · Zbl 05841337 · doi:10.1016/j.csl.2008.11.001
[29] Ihler, A., McAllester, D.: Particle belief propagation. In: Proc. of the 12th Int. Conf. on Artificial Intelligence and Statistics (2009)
[30] Ising, E.: A contribution to the theory of ferromagnetism. Z. Phys. 31, 253 (1925) · doi:10.1007/BF02980577
[31] Jelinek, F.: Statistical Methods for Speech Recognition. MIT Press, Cambridge (1997)
[32] Johnson, J.K., Bickson, D., Dolev, D.: Fixing convergence of Gaussian belief propagation. In: Proc. Int. Symposium Inform. Theory (2009)
[33] Jurafsky, D.: Martin, J.H: Speech and Language Processing. Prentice Hall, Upper Saddle River (2000)
[34] Kallus, Y., Elser, V., Gravel, S.: Method for dense packing discovery. Phys. Rev. E 82, 056707 (2010) · Zbl 1202.52018 · doi:10.1103/PhysRevE.82.056707
[35] Kalman, R.E.: A new approach to linear filtering and prediction problems. J. Basic Eng. 82, 35–45 (1960) · doi:10.1115/1.3662552
[36] Kikuchi, R.: A theory of cooperative phenomena. Phys. Rev. 81, 988–1003 (1951) · Zbl 0043.44002 · doi:10.1103/PhysRev.81.988
[37] Knuth, D.E.: The Art of Computer Programming, vol. 4A. Combinatorial Algorithms. Addison-Wesley, New York (2011). Sect. 7.1.4 · Zbl 1235.68030
[38] Koller, D., Friedman, N.: Probabilistic Graphical Models. MIT Press, Cambridge (2009) · Zbl 1183.68483
[39] Krauth, W.: Statistical Mechanics: Algorithms and Computations. Oxford University Press, Oxford (2006) · Zbl 1144.82002
[40] Kschischang, F.R., Frey, B.J., Loeliger, H.-A.: Factor graphs and the sum-product algorithm. IEEE Trans. Inf. Theory 47, 498–519 (2001) · Zbl 0998.68234 · doi:10.1109/18.910572
[41] Lauritzen, S.L.: Spiegelhalter, D.J.: Local computations with probabilities on graphical structures and their application to expert systems. J. R. Stat.Soc., Ser. B 50, 157–194 (1988) · Zbl 0684.68106
[42] Lions, P.-L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16, 964–979 (1979) · Zbl 0426.65050 · doi:10.1137/0716071
[43] Loeliger, H.-A.: An introduction to factor graphs. IEEE Signal Proc. Mag., 28–41 (2004)
[44] Loeliger, H.-A.: Least squares and Kalman filtering on Forney graphs. In: Blahut, R.E., Koetter, R. (eds.) Codes, Graphs, and Systems, pp. 113–135. Kluwer Academic, Norwell (2002) · Zbl 1147.93414
[45] Loeliger, H.-A., Dauwels, J., Hu, J., Korl, S., Ping, L., Kschischang, F.: The factor graph approach to model-based signal processing. Proc. IEEE 95, 1295–1322 (2007) · doi:10.1109/JPROC.2007.896497
[46] MacKay, D.J.C.: Information Theory, Inference, and Learning Algorithms. Cambridge University Press, Cambridge (2003) · Zbl 1055.94001
[47] Malioutov, D.M., Johnson, J.K., Willsky, A.S.: Walk-sums and belief propagation in Gaussian graphical models. J. Mach. Learn. Res. 7, 2031–2064 (2006) · Zbl 1222.68254
[48] Manning, C.D., Schutze, H.: Foundations of Statistical Natural Language Processing. MIT Press, Cambridge (1999)
[49] McEliece, R.J., MacKay, D.J.C., Cheng, J.F.: Turbo decoding as an instance of Pearl’s ”belief propagation” algorithm. IEEE J. Sel. Areas Commun. 16, 140–152 (1998) · doi:10.1109/49.661103
[50] Meltzer, T., Yanover, C., Weiss, Y.: Globally optimal solutions for energy minimization in stereo vision using reweighted belief propagation. In: Int. Conference on Computer Vision (2005)
[51] Mézard, M., Montanari, A.: Information, Physics, and Computation. Oxford University Press, Oxford (2009) · Zbl 1163.94001
[52] Mézard, M., Parisi, G., Virasaro, M.A.: Spin Glass Theory and Beyond. World Scientific, Singapore (1987) · Zbl 0992.82500
[53] Mézard, M., Parisi, G., Zecchina, R.: Analytic and algorithmic solution of random satisfiability problems. Science 297, 812–815 (2002) · doi:10.1126/science.1073287
[54] Minato, S.-E.: Zero-suppressed BDDs for set manipulation in combinatorial problems. In: Proc. 30th ACM/IEEE Design Automation Conference, pp. 272–277 (1993)
[55] Minka, T.P.: Expectation propagation for approximate Bayesian inference. In: Proc. of the 17th Conf. on Uncertainty in Artificial Intelligence, pp. 362–369 (2001)
[56] Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Francisco (1988) · Zbl 0746.68089
[57] Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1993) · Zbl 0557.68033
[58] Rabiner, L.: A tutorial on hidden Markov models and selected applications in speech recognition. Proc. IEEE 77, 257–286 (1989) · doi:10.1109/5.18626
[59] Richardson, T.: Error floors of LDPC codes. In: Proc. 41st Allerton Conf. Commun. Contr., Comput., Monticello, IL (2003)
[60] Richardson, T., Urbanke, R.: Modern Coding Theory. Cambridge University Press, Cambridge (2008) · Zbl 1188.94001
[61] Ruozzi, N., Tatikonda, S.: Convergent and correct message passing schemes for optimization problems over graphical models. Available at http://arxiv.org/abs/1002.3239 (2010) · Zbl 1317.68185
[62] Rusmevichientong, P., Van Roy, B.: An analysis of belief propagation on the turbo decoding graph with Gaussian densities. IEEE Trans. Inf. Theory 47, 745–765 (2001) · Zbl 1002.94042 · doi:10.1109/18.910586
[63] Russell, S., Norvig, P.: Artificial Intelligence, A Modern Approach, 3rd edn. Prentice Hall, Upper Saddle River (2009) · Zbl 0835.68093
[64] Ryan, W.E., Lin, S.: Channel Codes: Classical and Modern. Cambridge University Press, Cambridge (2009) · Zbl 1180.94002
[65] Sontag, D., Meltzer, T., Globerson, A., Jaakkola, T., Weiss, Y.: Tightening LP relaxations for MAP using message-passing. In: Uncertainty in Artificial Intelligence (2008)
[66] Sudderth, E.B., Freeman, W.T.: Signal and Image processing with belief propagation. IEEE Signal Process. Mag. 25, 114–141 (2008)
[67] Sudderth, E.B., Ihler, A., Isard, M., Freeman, W.T., Willsky, A.S.: Non-parametric belief propagation. Commun. ACM 53, 95–103 (2010) · doi:10.1145/1831407.1831431
[68] Tanner, R.M.: A recursive approach to low complexity codes. IEEE Trans. Inf. Theory 27, 533–547 (1981) · Zbl 0474.94029 · doi:10.1109/TIT.1981.1056404
[69] Vardy, A.: Trellis structure of codes. In: Pless, V.S., Huffman, W.C. (eds.) Handbook of Coding Theory, vol. 2, pp. 1989–2118. Elsevier, Amsterdam (1998) · Zbl 0922.94013
[70] Viterbi, A.J.: Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans. Inf. Theory 13, 260–269 (1967) · Zbl 0148.40501 · doi:10.1109/TIT.1967.1054010
[71] Wainwright, M.J., Jaakkola, T., Willsky, A.S.: A new class of upper bounds on the log partition function. IEEE Trans. Inf. Theory 51, 2313–2335 (2005) · Zbl 1310.94028 · doi:10.1109/TIT.2005.850091
[72] Wainwright, M.J., Jaakkola, T., Willsky, A.S.: Tree-based reparametrization framework for analysis of sum-product and related algorithms. IEEE Trans. Inf. Theory 45, 1120–1146 (2003) · Zbl 1063.68079 · doi:10.1109/TIT.2003.810642
[73] Wainwright, M.J., Jaakkola, T., Willsky, A.S.: MAP estimation via agreement on (hyper)trees: message-passing and linear programming approaches. IEEE Trans. Inf. Theory 51, 3697–3717 (2005) · Zbl 1318.94025 · doi:10.1109/TIT.2005.856938
[74] Wainwright, M.J., Jordan, M.I.: Graphical models, exponential families, and variational inference. Faund. Trends Mach. Learn. 1, 1–305 (2008) · Zbl 1193.62107 · doi:10.1561/2200000001
[75] Weiss, Y., Freeman, W.T.: On the optimality of the max-product belief propagation algorithm on arbitrary graphs. IEEE Trans. Inf. Theory 47, 736–744 (2001) · Zbl 1002.94057 · doi:10.1109/18.910585
[76] Yedidia, J.S., Freeman, W.T., Weiss, Y.: Understanding belief propagation and its generalizations. In: Lakemeyer, G., Nebel, B. (eds.) Exploring Artificial Intelligence in the New Millenium, pp. 239–270. Morgan Kaufmann, San Francisco (2003)
[77] Yedidia, J.S., Freeman, W.T., Weiss, Y.: Constructing free energy approximations and generalized belief propagation algorithms. IEEE Trans. Inf. Theory 51, 2282–2312 (2005) · Zbl 1283.94023 · doi:10.1109/TIT.2005.850085
[78] Yedidia, J.S., Wang, Y., Draper, S.C.: Divide and concur and difference-map BP decoders for LDPC codes. IEEE Trans. Inf. Theory 57, 786–802 (2011) · Zbl 1366.94733 · doi:10.1109/TIT.2010.2094815
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.