实例结构限制下信息传播算法的收敛性研究

Message passing algorithms are very effective in finding satisfying assignments for SAT instances, and hard region become narrower. However, the message passing algorithms do not always converge for factor graph with cycles. Unfortunately, rigorous theory proof of this phenomenon is still lacking. In this project,we study the performance and convergence of message passing algorithms for regular structures instances.The RB(k,n,a,r,p) instances and (3,4)-SAT instances have regular structures,the factor graph of those instances are regular structure bipartite graphs.So we study the convergence of the message passing algorithms on regular structures RB(k,n,a,r,p) and (3,4)-SAT instances, and give convergence conditions of message passing algorithms .It includes (1)Presenting random models producing (3,4)-CNF formulas and analyzing critical properties of random (3,4)-SAT based on properties of regular bigaphes from regular formulas. (2)Investigating the factor graph structures and controls parameters of RB(k,n,a,r,p) and (3,4)-SAT instances. (3)Investigating the convergence of the message passing algorithms for solving (3,4)-SAT instances and RB(k,n,a,r,p) instances,and estimating bounds of iterations number of message passing algorithms. (4)According to Markov chain theory, investigating probability convergence conditions and unique fixed point of the warning propagation algorithm. (5)Improving the performance of message passing algorithms and analyzing the message passing algorithms principle.

信息传播算法求解可满足性问题时具有良好的有效性，能使难解区域变窄。然而，对于因子图含有回路的可满足性实例，信息传播算法不总有效，常表现为不收敛。对于这种现象，至今缺少系统的理论解释。本项目主要研究实例结构限制下信息传播算法的收敛性。RB(k,n,a,r,p)实例和(3,4)-SAT实例具有一定的结构限制(如，子句长度均等是一种最简单和常见的限制），其对应的因子图是一个规则结构的二部图。基于该实例的规则结构性质，研究信息传播算法在这种结构限制下的收敛性，并给出算法收敛的条件。研究内容包括：(3,4)-SAT实例产生模型、相变分析及测试算法；RB(k,n,a,r,p)实例和(3,4)-SAT实例的因子图结构性质及相应的控制参数；RB(k,n,a,r,p)实例和(3,4)-SAT实例上信息传播算法的收敛性及算法迭代步数的上界估计；警示传播算法存在唯一固定点的条件；信息传播算法的原理及性能改进。

命题公式的可满足性（SAT）问题是计算机科学中最为著名的NP-完全问题，其理论及其应用研究，是计算机与数理逻辑界共同关注的一个重大问题。最近几年，随着人工智能的迅速发展，人们对SAT问题的研究进入了新的阶段，特别是大数据的到来，对SAT问题原有的求解算法需要重新审视和设计，这为研究SAT问题提供了新的机遇和挑战。信息传播算法求解SAT问题时有良好的有效性，使得难解区域变窄。然而，对于因子图含有回路的可满足性实例，信息传播算法不总有效，常表现为不收敛。对于这种现象，至今缺少系统的理论解释。通过我们近年来的不断深入研究，给出了信息传播算法收敛的有效条件，构建了信息传播算法收敛的一个基本框架，从而形成了一整套关于信息传播算法收敛的理论体系，这为信息传播算法的进一步应用提供了理论依据。具体地讲，主要有两个方面的工作：信息传播算法的收敛性和信息传播算法在组合优化问题中的应用。一方面，我们给出了信息传播算法收敛的有效条件，包括警示传播算法的收敛性、置信传播算法的收敛性、调查传播算法的收敛性。(1)通过随机实例的公式结构，利用一阶矩和二阶矩证明了公式的因子图具备某种结构性质时警示传播算法收敛的概率条件；(2)根据压缩映射原理，利用迭代方程系数矩阵的谱半径，给出了警示传播算法收敛的一个充分条件；(3)基于RB模型实例产生特征，利用一阶矩和二阶矩及函数的压缩映射原理，并结合迭代方程系数矩阵的谱半径，给出基于这种实例集上置信传播算法收敛的一个概率条件；(4)根据压缩映射原理，利用迭代方程系数矩阵的谱半径，给出了信念传播算法收敛的一个充分条件；(5)根据压缩映射原理，利用迭代方程系数矩阵的谱半径，给出了调查传播算法收敛的一个充分条件；(6)利用骨干集和后门集的相关概念，定义了WP-可解公式，基于植入指派的WP-可解公式，给出警示传播算法概率收敛的充分必要条件；(7)利用马尔科夫链模型存在平稳分布的相关性质，给出基于(3,4)-SAT实例集上警示传播算法收敛的一个概率条件。另一方面，我们给出了求解组合优化问题的信息传播算法。(1)设计求解MAX-3-SAT问题的警示传播算法，并分析了算法的近似度；(2)设计了一种求解最小连通控制集的警示传播算法，实验结果表明算法非常有效；(3)设计一种求解最小顶点覆盖集的置信传播算法；......等等。