A new look at survey propagation and its generalizations

ABSTRACT

This article provides a new conceptual perspective on survey propagation, which is an iterative algorithm recently introduced by the statistical physics community that is very effective in solving random k-SAT problems even with densities close to the satisfiability threshold. We first describe how any SAT formula can be associated with a novel family of Markov random fields (MRFs), parameterized by a real number ρ ∈ [0, 1]. We then show that applying belief propagation---a well-known “message-passing” technique for estimating marginal probabilities---to this family of MRFs recovers a known family of algorithms, ranging from pure survey propagation at one extreme (ρ = 1) to standard belief propagation on the uniform distribution over SAT assignments at the other extreme (ρ = 0). Configurations in these MRFs have a natural interpretation as partial satisfiability assignments, on which a partial order can be defined. We isolate cores as minimal elements in this partial ordering, which are also fixed points of survey propagation and the only assignments with positive probability in the MRF for ρ = 1. Our experimental results for k = 3 suggest that solutions of random formulas typically do not possess non-trivial cores. This makes it necessary to study the structure of the space of partial assignments for ρ < 1 and investigate the role of assignments that are very close to being cores. To that end, we investigate the associated lattice structure, and prove a weight-preserving identity that shows how any MRF with ρ > 0 can be viewed as a “smoothed” version of the uniform distribution over satisfying assignments (ρ = 0). Finally, we isolate properties of Gibbs sampling and message-passing algorithms that are typical for an ensemble of k-SAT problems.

REFERENCES

• 1: Dimitris Achlioptas , Yuval Peres, The threshold for random k-SAT is 2^k (ln 2 - O(k)), Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780577]
• 2: Dimitris Achlioptas , Federico Ricci-Tersenghi, On the solution-space geometry of random constraint satisfaction problems, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132537]
• 3: Aurell, E., Gordon, U., and Kirkpatrick, S. 2004. Comparing beliefs, surveys, and random walks. In Proceedings of NIPS. MIT Press, Cambridge, MA.
• 4: Berger, N., Kenyon, C., Mossel, E., and Peres, Y. 2005. Glauber dynamics on trees and hyperbolic graphs. Probab. Theory Relat. Fields, 131(3):311--340. (Extended abstract by Kenyon, Mossel and Peres appeared in Proceedings of FOCS.)
• 5: Braunstein, A., Mézard, M., Weigt, M., and Zecchina, R. 2003. Constraint satisfaction by survey propagation. Technical report. (Preprint at URL:http://lanl.arXiv.org/cond-mat/0212451.)
• 6: A. Braunstein , M. Mézard , R. Zecchina, Survey propagation: An algorithm for satisfiability, Random Structures & Algorithms, v.27 n.2, p.201-226, September 2005 [doi>10.1002/rsa.v27:2]
• 7: Braunstein, A., and Zecchina, R. 2004. Survey propagation as local equilibrium equations. J. Stat. Mech. Theory and Experiments (JSTAT) 7, 06007.
• 8: Chvatal, V., and Reed, B. 1992. Mick gets some (the odds are on his side). In Proceedings of the Symposium on the Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 620--627.
• 9: Ciliberti, S., Mézard, M., and Zecchina, R. 2005. Message-passing algorithms for non-linear nodes and data compression. Technical report, November 2005. arXiv:cond-mat/0508723.
• 10: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 11: Gregory F. Cooper, The computational complexity of probabilistic inference using Bayesian belief networks (research note), Artificial Intelligence, v.42 n.2-3, p.393-405, March 1990 [doi>10.1016/0004-3702(90)90060-D ]
• 12: James M. Coughlan , Sabino J. Ferreira, Finding Deformable Shapes Using Loopy Belief Propagation, Proceedings of the 7th European Conference on Computer Vision-Part III, p.453-468, May 28-31, 2002
• 13: Paul Dagum , Michael Luby, Approximating probabilistic inference in Bayesian belief networks is NP-hard, Artificial Intelligence, v.60 n.1, p.141-153, March 1993 [doi>10.1016/0004-3702(93)90036-B ]
• 14: de la Vega, W. F. 1992. On random 2-sat. Unpublished manuscript.
• 15: Rina Dechter, Constraint Processing, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 16: Olivier Dubois , Yacine Boufkhad , Jacques Mandler, Typical random 3-SAT formulae and the satisfiability threshold, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.126-127, January 09-11, 2000, San Francisco, California, United States
• 17: Uriel Feige, Relations between average case complexity and approximation complexity, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509985]
• 18: William T. Freeman , Egon C. Pasztor , Owen T. Carmichael, Learning Low-Level Vision, International Journal of Computer Vision, v.40 n.1, p.25-47, Oct. 2000 [doi>10.1023/A:1026501619075]
• 19: Friedgut, E. 1999. Neccesary and sufficient conditions for sharp threhsolds of graph properties and the k-problem. J. Amer. Math. Soc. 12, 1017--1054.
• 20: Gallager, R. G. 1963. Low-density parity check codes. MIT Press, Cambridge, MA.
• 21: Goerdt, A. 1996. A remark on random 2-sat. J. Comput. Syst. Sci. 53, 469--486.
• 22: Janson, S., Luczak, T., and Rucinski, A. 2000. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York.
• 23: Alexis C. Kaporis , Lefteris M. Kirousis , Efthimios G. Lalas, The Probabilistic Analysis of a Greedy Satisfiability Algorithm, Proceedings of the 10th Annual European Symposium on Algorithms, p.574-585, September 17-21, 2002
• 24: Kschischang, F., Frey, B., and Loeliger, H.-A. 2001. Factor graphs and the sum-product algorithm. IEEE Trans. Inf. Theory 47, 498--519.
• 25: Vipin Kumar, Algorithms for constraint-satisfaction problems: a survey, AI Magazine, v.13 n.1, p.32-44, Spring 1992
• 26: Leonid A Levin, Average case complete problems, SIAM Journal on Computing, v.15 n.1, p.285-286, Feb. 1986 [doi>10.1137/0215020]
• 27: Elitza Maneva , Elchanan Mossel , Martin J. Wainwright, A new look at survey propagation and its generalizations, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 28: Martinelli, F. 1999. Lectures on Glauber dynamics for discrete spin models. In Lectures on probability theory and statistics (Saint-Flour, 1997). Lecture Notes in Math., vol. 1717. Springer-Verlag, Berlin, Germany, 93--191
• 29: Martinian, E., and Wainwright, M. J. 2006. Low density codes can achieve the Wyner-Ziv and Gelfand-Pinsker bounds. In International Symposium on Information Theory. IEEE Computer Society Press, Los Alamitos, CA.
• 30: Mézard, M., Parisi, G., and Zecchina, R. 2002. Analytic and algorithmic solution of random satisfiability problems. Science, 297, 812. (Scienceexpress published on-line 27-June-2002; 10.1126/science.1073287).
• 31: Mézard, M., Ricci-Tersenghi, F., and Zecchina, R. 2003. Two solutions to diluted p-spin models and XORSAT problems. J. Stat. Phys. 111, 505.
• 32: Mézard, M., and Zecchina, R. 2002. Random k-satisfiability: From an analytic solution to an efficient algorithm. Phys. Rev. E, 66.
• 33: Monasson, R., and Zecchina, R. 1997. Statistical mechanics of the random k-satisfiability model. Phys. Rev. E 3, 1357--1370.
• 34: Mora, T., Mézard, M., and Zecchina, R. 2005. Clustering of solutions in the random satisfiability problem. Phys. Rev. Lett. 94.
• 35: Parisi, G. 2002. On local equilibrium equations for clustering states. Technical report. Preprint at URL:http://lanl.arXiv.org/cs.CC/0212047.
• 36: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 37: Richardson, T., and Urbanke, R. 2001. The capacity of low-density parity check codes under message-passing decoding. IEEE Trans. Info. Theory 47, 599--618.
• 38: Rosenthal, J., Plotkin, J., and Franco, J. 1999. The probability of pure literals. J. Computat. Logic 9, 501--513.
• 39: Stuart J. Russell , Peter Norvig, Artificial Intelligence: A Modern Approach, Pearson Education, 2003
• 40: Selman, B., Kautz, H., and Cohen, B. 1996. Local search strategies for satisfiability testing. In D. S. Johnson and M. A. Trick, editors, Cliques, coloring, and satisfiability: Second DIMACS implementation challenge. (October 11-13, 1993), Providence, RI. American Mathematical Society.
• 41: Stanley, R. P. 1997. Enumerative Combinatorics. Vol. 1. Cambridge University Press, Cambridge, UK.
• 42: Tatikonda, S., and Jordan, M. I. 2002. Loopy belief propagation and Gibbs measures. In Proceedings of UAI. 493--500.
• 43: Wainwright, M. J., and Jordan, M. I. 2003. Graphical models, exponential families, and variational methods. Technical report, UC Berkeley, Department of Statitics, No. 649. Preprint at URL:http://www.eecs.berkeley.edu/~wainwrig/Papers/WaiJorVariational03.ps.
• 44: Wainwright, M. J., and Maneva, E. 2005. Lossy source encoding via message-passing and decimation over generalized codewords of LDGM codes. In Proceedings of IEEE International Symposium on Information Theory. IEEE Computer Society Press, Los Alamitos, CA, 1493--1497.
• 45: Jie Wang, Average-case computational complexity theory, Complexity theory retrospective II, Springer-Verlag New York, Inc., New York, NY, 1998
• 46: Max Welling , Yee Whye Teh, Belief Optimization for Binary Networks: A Stable Alternative to Loopy Belief Propagation, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.554-561, August 02-05, 2001
• 47: Yedidia, J., Freeman, W. T., and Weiss, Y. 2005. Constructing free energy approximations and generalized belief propagation algorithms. IEEE Trans. Inf. Theory 51, 7, 2282--2312.
• 48: Jonathan S. Yedidia , William T. Freeman , Yair Weiss, Understanding belief propagation and its generalizations, Exploring artificial intelligence in the new millennium, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 49: A. L. Yuille, CCCP algorithms to minimize the Bethe and Kikuchi free energies: convergent alternatives to belief propagation, Neural Computation, v.14 n.7, p.1691-1722, July 2002 [doi>10.1162/08997660260028674 ]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.0 GENERAL

General Terms:
Algorithms, Theory

Keywords:
k-SAT, Gibbs sampling, Markov random field, Satisfiability problems, belief propagation, factor graph, message-passing, sum-product, survey propagation