微信服务号

微信订阅号

2025年5月5日 15:04 星期一
首页 > 过刊浏览>2021年第32卷第5期 >1360-1372. DOI:10.13328/j.cnki.jos.005844
PDF HTML阅读 XML下载 导出引用 引用提醒
可满足性问题中信念传播算法的收敛性分析
作者:
作者简介:

王晓峰(1980-),男,博士,副教授,CCF专业会员,主要研究领域为机器学习,人工智能,算法分析与设计.
姜久雷(1972-),男,博士,教授,CCF专业会员,主要研究领域为业务流程建模,服务计算,大数据分析.
许道云(1959-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为计算复杂性,可计算性分析.
李强(1987-),男,博士,副教授,CCF专业会员,主要研究领域为协同工程,机器学习.
杨德仁(1964-),男,博士,教授,主要研究领域为软件理论,软件工程.
刘欣欣(1994-),女,硕士生,主要研究领域为算法分析与设计.

通讯作者:

杨德仁,E-mail:deren.yang@nxmu.edu.cn

中图分类号:

TP301

基金项目:

国家自然科学基金（62062001，61762019，61762002，61862051，61962002）；宁夏自然科学基金（2020AAC03214，NZ17111，2019AAC03120，2019AAC03119，2020AAC03219）；北方民族大学重大专项基金（ZDZX201901）；北方民族大学校级一般科学基金（2019XYZJK05）


Convergence Analysis of Belief Propagation Algorithm for Satisfiability Problem
Author:
Fund Project:

National Natural Science Foundation of China (62062001, 61762019, 61762002, 61862051, 61962002); Natural Science Foundation of Ningxia (2020AAC03214, NZ17111, 2019AAC03120, 2019AAC03119, 2020AAC03219); Major Scientific Research Projects of North Minzu University (ZDZX201901); Scientific Research Projects of North Minzu University (2019XYZJK05)

  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [61]
    • |
  • 相似文献 [20]
    • | | |
  • 文章评论
    摘要:

    信念传播算法是基于因子图模型的消息传递算法，通过图中的边，将消息从一个结点传递给另一个结点，以高概率地确定部分变量的取值，这种方法被实验证明在求解可满足性问题时非常有效.然而，目前还未对其有效性从理论角度给予解释.通过对信念传播算法的收敛性分析，试图从理论上解释算法的有效性.在信息传播算法的信息迭代方程中，参数的取值范围为（0，1），将该取值范围扩展到整个实数空间，即（-∞，+∞）.利用压缩函数的数学原理，得到了信息迭代方程收敛的判定条件.选取随机可满足性问题实例进行实验模拟，验证了结论的正确性.

    Abstract:

    Belief propagation (BP) algorithm is a message passing algorithm based on a factor graph, and it passes messages from one node to another through edges in the graph to determine the value of some variables with high probability. This method is experimentally proven to be very effective when solving the satisfiability (SAT) problem. However, there is no explanation for its effectiveness from a theoretical point of view at present. Through the analysis of convergence of the BP algorithm, the effectiveness of the algorithm is explained theoretically. In this study, the sufficient conditions are also derived for convergence of the BP for satisfiability problem, and extending message (0,1) to message (-∞,+∞). Lastly, experimental results show that the conditions for convergence of BP are very effective in random SAT instances, and it proves the correctness of the conclusion.

    参考文献
    [1] Biere A, Heule M, Maaren H. van Walsh T. Handbook of Satisfiability. IOS Press, 2009.
    [2] Kirkpatrick S, Selman B. Critical behavior in the satisfiability of random Boolean formulae. Science, 1994,264(5163):1297-1301.
    [3] Mertens S, Mezard M, Zecchina R. Threshold values of random k-SAT from the cavity method. Random Structure Algorithms, 2006,28(3):340-373.
    [4] Kaporis A, Kirousis L, Lalas E. The probabilistic analysis of a greedy satisfiability algorithm. Random Structures&Algorithms, 2006,28(4):444-480.
    [5] Josep D, Kirousis L, Dieter M, Xavier PG. On the satisfiability threshold of formulas with three literals per clause. Theoretical Computer Science, 2009,410(30):2920-2934.
    [6] Xu K, Li W. Exact phase transitions in random constraint satisfaction problems. Journal of Artificial Intelligence Research, 2000, 12(1):93-103.
    [7] Xu K, Li W. Many hard examples in exact phase transitions. Theoretical Computer Science, 2006,355(3):291-302.
    [8] Xu K, Boussemart F, Hemery F. Random constraint satisfaction:Easy generation of hard satisfiable instances. Artificial Intelligence, 2007,171(8):514-534.
    [9] Davis M, Logemann G, Lovelan D. A machine program f or theorem proving. Communications of the ACM, 1962,5(7):394-397.
    [10] Moskewicz MW, Madigan CF, Zhao Y. Chaff:Engineering an efficient SAT solver. In:Proc. of the 38th Design Automation. 2001.530-535.
    [11] Goldberg E, Novikov Y. BerkMin:A fast and robust SAT-solver. In:Proc. of the Design Automation and Test in Europe. 2002.142-149.
    [12] Eén N, Sörensson N. An Extensible SAT-solver:Theory and Applications of Satisfiability. Berlin:Springer-Verlag, 2004.502-518.
    [13] Zhang H. SATO:An efficient propositional prover. In:Proc. of the Int'l Conf. on Automated Deduction. 1997.272-275.
    [14] Silva JP, Sakallah KA. GRASP:A search algorithm for propositional satisfiability. IEEE Trans. on Computers, 1999,48(5):506-521.
    [15] Selman B, Kautz H, Cohen B. Noise strategies for improving local search. In:Proc. of the AAAI. 1994.337-343.
    [16] Selman B, Levesque HJ, Mitchell D. A new method for solving hard satisfiability problem. In:Proc. of the AAAI. 1992.440-446.
    [17] Pearl J. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufman Publishers, 1988.
    [18] Zhao CY, Zheng ZM. A belief-propagation algorithm based on variable entropy for constraint satisfaction problems. SCIENTIA SINICA Informationis, 2012,42(9):1170-1180(in Chinese with English abstract).
    [19] Yin MH, Zhou JP, Sun JG, Gu WX. Heuristic survey propagation algorithm for solving QBF problem. Ruan Jian Xue Bao/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]
    [20] Ravanbakhsh S, Greiner R. Perturbed message passing for constraint satisfaction problems. Artificial Intelligence, arXiv Preprint arXiv:1401.6686, 2014.
    [21] Chieu HL, Lee WS. Relaxed survey propagation for the weighted maximum satisfiability problem. Journal of Artificial Intelligence Research, 2009,36(1):229-266.
    [22] Bayati M, Shah D, Sharma M. Max product for maximum weight matching:Convergence, correctness, and LP duality. IEEE Trans. on Information Theory, 2007,54(3):1241-1251.
    [23] Coja-Oghlan A, Mossel E, Vilenchik D. A spectral approach to analyzing belief propagation for 3-colouring. Combinatorics, Probability and Computing, 2009,18(6):881-912.
    [24] Gamarnik D, Shah D, Wei Y. Belief propagation for min-cost network flow:Convergence and correctness. Operations Research, 2012,60(2):410-428.
    [25] Sanghavi S, Malioutov DM, Willsky AS. Belief propagation and LP relaxation for weighted matching in general graphs. IEEE Trans. on Information Theory, 2011,57(4):2203-2212.
    [26] Sanghavi S, Shah D, Willsky AS. Message passing for maximum weight independent set. IEEE Trans. on Information Theory, 2009, 55(11):4822-4834.
    [27] Hetterich S. Analysing survey propagation guided decimation on random formulas. arXiv Preprint arXiv:1602.08519, 2016.
    [28] Amin CO. On belief propagation guided decimation for random k-SAT. In:Proc. of the 22nd Annual ACMSIAM Symp. on Discrete Algorithms. San Francisco, 2016.957-966.
    [29] Marino R, et al. The backtracking survey propagation algorithm for solving random K-SAT problems. Nature Communications, 2016,7:Article No.12996.[doi:10.1038/ncomms12996(2016)]
    [30] Braunstein A, Mezard M, Zecchina R. Survey propagation:An algorithm for satisfiability. Random Structures and Algorithms, 2005,27(2):201-226.
    [31] Maneva E, Mossel E, Wainwright M. A new look at survey propagation and its generalizations. Journal of the ACM, 2007,54(4):1089-1098.
    [32] Yedidia JS, Freeman WT, Weiss Y. Understanding belief propagation and its generalizations. Artificial Intelligence, 2003,8(1):239-269.
    [33] Braunstein A, Zecchina R. Survey and belief propagation on random k-SAT. LNCS, 2004,2919(1):519-528.
    [34] Weiss Y. Correctness of local probability propagation in graphical models with loops. Neural Computation, 2000,12(1):1-41.
    [35] Weiss Y, Freeman WT. Correctness of belief propagation in gaussian graphical models of arbitrary topology. Neural Computation, 2001,13(10):2173-2200.
    [36] Tatikonda S, Jordan MI. Loopy belief propagation and Gibbs measure. In:Proc. of the 18th Annual Conf. on Uncertainty in Artificial Intelligence. 2002.493-500.
    [37] Heskes T. On the uniqueness of loopy belief propagation fixed points. Neural Computation, 2004,16(11):2379-2413.
    [38] Ihler AT, Lii JWF, Willsky AS. Loopy belief propagation:Convergence and effects of message errors. Machine Learning Research, 2005,6(1):905-936.
    [39] Shi XQ, Schonfeld D, Tuninetti D. Message error analysis of loopy belief propagation for the sum-product algorithm. Computer and Information Science, 2010,1009:1-30.
    [40] Feige U, Mossel E, Vilenchik D. Complete convergence of message passing algorithms for some satisfiability problems. Theory of Computing, 2013,9(19):617-651.
    [41] Wang XF, Xu DY, Wei L. Convergence of warning propagation algorithms for random satisfiable instances. Ruan Jian Xue Bao/Journal of Software, 2013,24(1):1-11(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4213.htm[doi:10.3724/SP.J.1001.2013.04213]
    [42] Wang XF, Xu DY. Convergence of the belief propagation algorithm for RB model instances. Ruan Jian Xue Bao/Journal of Software, 2016,27(11):2712-2724(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4877.htm[doi:10.13328/j. cnki.jos.004877]
    [43] Wang XF, Xu DY. Sufficient conditions for convergence of the warning propagation algorithm. Ruan Jian Xue Bao/Journal of Software, 2016,27(12):3003-3013(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4940.htm[doi:10.13328/j. cnki.jos.004940]
    [44] Wang XF, Xu DY, Jiang JL, Tang YH. A sufficient condition for survey propagation convergence. SCIENTIA SINICA Informationis, 2017,47(12):1646-1661(in Chinese with English abstract).
    [45] Du J, Ma S, Wu YC, Kar S, Moura JMF. Convergence analysis of distributed inference with vector valued Gaussian belief propagation. Journal of Machine Learning Research, 2018,18(172):1-38.
    [46] Du J, Ma S, Wu YC, Kar S, Moura JMF. Convergence analysis of the information matrix in Gaussian belief propagation. In:Proc. of the IEEE Int'l Conf. on Acoustics, Speech and Signal Processing. 2017.4074-4078.
    [47] Du J, Ma S, Wu YC, Kar S, Moura JMF. Convergence analysis of belief propagation for pairwise linear Gaussian models. In:Proc. of the IEEE Global Conf. on Signal and Information Processing. 2017.548-552.
    [48] Su Q, Wu YC. Convergence analysis of the variance in Gaussian belief propagation. IEEE Trans. on Signal Processing, 2014, 62(19):5119-5131.
    [49] Su Q, Wu YC. On convergence conditions of Gaussian belief propagation. IEEE Trans. on Signal Processing, 2015,63(5):1144-1155.
    [50] Park S, Shin J. Convergence and correctness of max-product belief propagation for linear programming. Siam Journal on Discrete Mathematics, 2017,31(3):2228-2246.
    [51] Wang Y, Reyes MG, Neuhoff DL. Correct convergence of min-sum loopy belief propagation in a block interpolation problem. arXiv Preprint arXiv:1702.06391, 2017.
    [52] Sui T, Marelli D, Fu M. Convergence analysis for guassian belief propagation:Dynamic behaviour of marginal covariances. In:Proc. of the IEEE Int'l Conf. on Acoustics, Speech and Signal Processing. 2016.2599-2602.
    [53] Mooij JM, Kappen HJ. Sufficient conditions for convergence of the sum-product algorithm. IEEE Trans. on Information Theory, 2007,53(12):4422-4437.
    [54] Dieudonne J. Foundations of Modern Analysis. New York:Academic Press, 1960.
    附中文参考文献:
    [18] 赵春艳,郑志明.一种基于变量熵求解约束满足问题的置信传播算法.中国科学:信息科学,2012,42(9):1170-1180.
    [19] 殷明浩,周俊萍,孙吉贵,谷文祥.求解QBF问题的启发式调查传播算法.软件学报,2011,22(7):1538-1550. http://www.jos.org.cn/1000-9825/3859.htm[doi:10.3724/SP.J.1001.2011.03859]
    [41] 王晓峰,许道云,韦立.随机实例集上警示传播算法的收敛性.软件学报,2013,24(1):1-11. http://www.jos.org.cn/1000-9825/4213.htm[doi:10.3724/SP.J.1001.2013.04213]
    [42] 王晓峰,许道云.RB模型实例集上置信传播算法的收敛性.软件学报,2016,27(11):2712-2724. http://www.jos.org.cn/1000-9825/4877.htm[doi:10.13328/j.cnki.jos.004877]
    [43] 王晓峰,许道云.警示传播算法收敛的充分条件.软件学报,2016,27(12):3003-3013. http://www.jos.org.cn/1000-9825/4940.htm[doi:10.13328/j.cnki.jos.004940]
    [44] 王晓峰,许道云,姜久雷,唐延辉.调查传播算法收敛的一个充分条件.中国科学:信息科学,2017,47(12):1646-1661.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

王晓峰,许道云,杨德仁,姜久雷,李强,刘欣欣.可满足性问题中信念传播算法的收敛性分析.软件学报,2021,32(5):1360-1372

复制
分享
文章指标
  • 点击次数:1190
  • 下载次数: 3517
  • HTML阅读次数: 1590
  • 引用次数: 0
历史
  • 收稿日期:2018-06-22
  • 最后修改日期:2018-11-22
  • 在线发布日期: 2021-05-07
  • 出版日期: 2021-05-06
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19904468位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号