可满足性问题中信念传播算法的收敛性分析
作者:
作者单位:

作者简介:

王晓峰(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:
Affiliation:

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)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    信念传播算法是基于因子图模型的消息传递算法,通过图中的边,将消息从一个结点传递给另一个结点,以高概率地确定部分变量的取值,这种方法被实验证明在求解可满足性问题时非常有效.然而,目前还未对其有效性从理论角度给予解释.通过对信念传播算法的收敛性分析,试图从理论上解释算法的有效性.在信息传播算法的信息迭代方程中,参数的取值范围为(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.

    参考文献
    相似文献
    引证文献
引用本文

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

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2018-06-22
  • 最后修改日期:2018-11-22
  • 录用日期:
  • 在线发布日期: 2021-05-07
  • 出版日期: 2021-05-06
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号