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



PDF全文下载地址:

http://jos.org.cn/jos/article/pdf/5844