Convergence of Warning Propagation Algorithms for Random Satisfiable Instances
Author:
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [29]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    Message propagation algorithms are very effective in finding satisfying assignments for random kSAT instances and hard regions become more narrow. Unfortunately, this phenomenon is still lacks rigorous theoretical proofs. The Warning Propagation (WP) algorithm is the most basic message propagation algorithm. In order to analysis the WP algorithm convergence for random kCNF formulas, the study gives the sharp threshold point for the existence of cycles in the factor graph of random kCNF formulas, the threshold for the existence of cycles in model G(n,k,p) of random kCNF formulas is p=1/8n2 for k=3, p=d/n2. When d becomes asymptotically equal to 1/8, cycles begin to appear, but each component contains at most one cycle, the number of the components containing a single cycle and the length of cycle are a constant independent of n. Thus, the factor graph consists of a forest of trees plus a few components that have a single cycle. Then WHP (with high probability) after at most O(logn+s) iterations, WP converges on these instances. Here s is the size of the connected component.

    Reference
    [1] Bourgain J. Sharp thresholds of graph properties and the k-SAT problem. Journal of The American Mathematical Society, 1999, 12(4):1017-1054. [doi: 10.1090/S0894-0347-99-00305-7]
    [2] Kirkpatrick S, Selman B. Critical behavior in the satisfiability of random Boolean formulae. Science, 1994,264(5163):1297-1301.
    [doi: 10.1126/science.264.5163.1297]
    [3] Kaporis A, Kirousis L, Lalas E. The probabilistic analysis of a greedy satisfiability algorithm. Random Structures & Algorithms, 2006,28(4):444-480. [doi: 10.1002/rsa.v28:4]
    [4] Dubois O, Boufkhad Y, Mandler J. Typical random 3-sat formulae and the satisfiability threshold. Electronic Colloquium on Computational Complexity, 2003,10(007):1-2.
    [5] Moskewicz MW, Madigan CF, Zhao Y. Chaff: Engineering an efficient SAT solver. In: Proc. of the 38th Annual Design Automation Conf. (DAC 2001). New York: ACM, 2001. 530-535. [doi: 10.1145/378239.379017]
    [6] Aurell E, Gordon U, Kirkkpatrick S. Comparing beliefs, surveys, and random walks. Advances in Neural Information Processing Systems, 2004,17(1):1-8.
    [7] Mezard M, Parisi G. The cavity method at zero temperature. Journal of Statistical Physics, 2003,111(1-2):1-34. [doi: 10.1023/ A:1022221005097]
    [8] Mezard M, Zecchina R. Random k-satisifability problem: From an analytic solution to an efficient algorithm. Physical Review E, 2002,66(5):056126. [doi: 10.1103/PhysRevE.66.056126]
    [9] Maneva E, Mossel E, Wainwright M. A new look at survey propagation and its generalizations. Journal of the ACM, 2007,54(4): 1089-1098. [doi: 10.1145/1255443.1255445]
    [10] Braunstein A, Mezard M, Zecchina R. Survey propagation: An algorithm for satisfiability. Random Structures and Algorithms, 2005,27(2):201-226. [doi: 10.1002/rsa.20057]
    [11] Montanari A. Message passing algorithms: A success looking for theoreticians. In: Proc. of the 42nd ACM Symp. on Theory of Computing (STOC 2010). New York: ACM, 2010. 37-38. [doi: 10.1145/1806689.1806695]
    [12] Yedidia JS, Freeman WT, Weiss Y. Understanding belief propagation and its generalizations. Artificial Intelligence, 2003,8(1): 239-269.
    [13] Mezard M, Parisi G, Zecchina R. Analytic and algorithmic solution of random satisfiability problems. Science, 2002,297(5582): 812-815. [doi: 10.1126/science.1073287]
    [14] Kroc L, Sabharwal A, Selman B. Survey propagation revisited. In: Proc. of the 23rd Conf. on Uncertainty in Artificial Intelligence (UAI 2007). Corvallis: AUAI, 2007. 217-226.
    [15] Braunstein A, Zecchina R. Survey and belief propagation on random k-SAT. Lecture Notes in Computer Science, 2004,2919(1): 519-528. [doi: 10.1007/978-3-540-24605-3_38]
    [16] Xu K, Li W. Exact phase transitions in random constraint satisfaction problems. Journal of Artificial Intelligence Research, 2000, 12(1):93-103.
    [17] Liu T, Liu X, Wang C, Su K, Xu K. Large hinge width on sparse random hypergraphs. In: Proc. of the 22nd Int'l Joint Conf. on Artificial Intelligence (IJCAI 2011). Menlo Park: AAAI, 2011. 611-616. [doi: 10.5591/978-1-57735-516-8/IJCAI11-109]
    [18] Xu K, Li W. Many hard examples in exact phase transitions. Theory Computer Science, 2006,355(1):291-302. [doi: 10.1016/j.tcs. 2006.01.001]
    [19] Xu K, Boussemart F, Hemery F, Lecoutre C. Random constraint satisfaction: Easy generation of hard instances. Artificial Intelligence, 2007,171(1):514-534. [doi: 10.1016/j.artint.2007.04.001]
    [20] Zhao C, Zhou H, Zheng Z, Xu K. A message passing approach to random constraint satisfaction problems with growing domains. Journal of Statistical Mechanics, 2011,(02):02019. [doi: 10.1088/1742-5468/2011/02/P02019]
    [21] Yin M, Zhou J, Sun J, Gu W. Heuristic survey propagation algorithm for solving QBF problem. Ruanjian Xuebao/Journal of Software, 2011,22(7): 1538-1550 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3859.htm [doi: 10.3724/SP. J.1001.2011.03859]
    [22] Kschischang F, Frey B, Loeliger H. Factor graph and the sum-product algorithm. Information Theory, 2001,47(1):498-519.
    [23] Weiss Y. Correctness of local probability propagation in graphical models with loops. Neural Computation, 2000,12(1):1-41. [doi: 10.1162/089976600300015880]
    [24] Weiss Y, Freeman WT. Correctness of belief propagation in Gaussian graphical models of arbitrary topology. Neural Computation, 2001,13(10):2173-2200. [doi: 10.1162/089976601750541769]
    [25] Meltzer T, Globerson A, Weiss Y. Convergent message passing algorithms—A unifying view. In: Proc. of the 25th Conf. Annual Conf. on Uncertainty in Artificial Intelligence (UAI 2009). Corvallis: AUAI, 2009. 393-401. http://dblp.uni-trier.de/db/conf/uai/ uai2009.html#MeltzerGW09
    [26] Hazan T, Shashua A. Convergent message passing algorithms for inference over general graphs with convex free energies. Science, 2008,51(11):264-273.
    [27] Ruozzi N, Tatikonda S. Convergent and correct message passing schemes for optimization problems over graphical models. In: Proc. of the 26th Conf. on Uncertainty in Artificial Intelligence (UAI 2010). Corvallis: AUAI, 2010. 500. http://dblp.uni-trier.de/ db/conf/uai/uai2010.html#RuozziT10
    [28] Feige U, Mossel E, Vilenchik D. Complete convergence of message passing algorithms for some satisfiability problems. Lecture Notes in Computer Science, 2006,4410(1):339-350. [doi: 10.1007/11830924_32]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

王晓峰,许道云,韦立.随机可满足实例集上警示传播算法的收敛性.软件学报,2013,24(1):1-11

Copy
Share
Article Metrics
  • Abstract:5796
  • PDF: 7333
  • HTML: 0
  • Cited by: 0
History
  • Received:November 26,2011
  • Revised:March 27,2012
  • Online: December 29,2012
You are the first2044212Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063