植入指派实例集上信息传播算法的收敛性
发布时间：2021-08-10 03:51
命题公式的可满足性（SAT）问题作为一类重要的NP完全问题,与人工智能中许多复杂性问题密切相关。然而,随着人工智能领域的快速发展,为了满足新的需求,需要重新审视和设计SAT问题原有的求解算法,因此,SAT问题在当下面临新的机遇和挑战。上世纪八十年代,物理学家提出了一种基于消息传递的信息传播算法,将该算法用于SAT问题的求解得到的效果十分显著,因此一直被学者广泛应用和研究。然而,由于该算法在相变区域有时不收敛,算法表现为失效。而对于这种现象,目前仍缺少系统的理论解释。因此本文基于WP-可解公式展开对信息传播算法的收敛性研究,力图从理论上给予对于算法收敛性现象的解释。主要研究内容如下:（1）分析信息传播算法的原理,找出信息传播算法下的骨干集和后门集之间的关系,并给出WP-可解公式的定义;（2）基于WP-可解公式的特点,借助于植入指派实例产生模型,研究信息传播算法在WP-可解公式上的收敛性,给出信息传播算法收敛的一个有效条件:信息传播算法在公式F上高概率收敛,当且仅当公式F是WP-可解公式。本文给出了信息传播算法收敛的条件,为信息传播算法的基础研究以及在人工智能领域的应用提供了理论支持。
【文章来源】：北方民族大学宁夏回族自治区
【文章页数】：54 页
【学位级别】：硕士
【部分图文】：
复杂性类图
北方民族大学2020届硕士学位论文第二章理论知识9图2-1复杂性类图2.1.2因子图从系谱学上讲，因子图是对Wiberg等人的“Tanner图”的直接概括[58,59]。Tanner[60]引入了二部图来描述Gallager的低密度校验码(LDPC)的推广码族，并基于此情况描述了合积算法。在Tanner的原始公式中，所有变量都是码字符号，由此可见，Wiberg等人介绍了隐藏状态变量，并提出了编码之外的应用，因子图将这些图论模型进一步应用于函数中。因子图可以用函数因子分解的二分图表示，所以若给定一个函数12(,,...,)nbMMM，则可以对其进行因式分解，121(,,...,)()mnjjjbMMMcS(2-1)其中，12{,,...,}jnSMMM，变量顶点12{,,...,}nIMMM构成相应的因子图G(I,C，E)，因子顶点12{,,...,}mCccc和边为E。因子图可以与消息传递算法相结合，有效地计算函数12(,,...,)nbMMM的某些特征，如边缘分布。假设12345b(m,m,m,m,m)是具有五个变量的函数，b可以表示五个变量的乘积12345121233435(,,,,)()()(,,)(,)(,)ABCDEbmmmmmcmcmcmmmcmmcmm(2-2)将符号记为：1212334{,,,,}{},{},{,,},{,}ABCDJABCDE，MmMmMmmmMmm和35{,}EMmm，则图2-2表示公式2-2对应的因子图。图2-2121233435()()(,,)(,)(,)ABCDEcmcmcmmmcmmcmm乘积的因子图
北方民族大学2020届硕士学位论文第二章理论知识10设一个CNF公式为12{,,...,}mFCCC，12,,..nxxx代表有n个变元，i代表变元ix。因子图是G{CX,E}能够描述公式F。其中，用X{1,2,...,n}来表示变量结点集，功能结点集为12{,,...,}mCCCC。图G中的边分为两类：实连接和虚连接。实连接：(,)iCjE子句iC含正文字jx；虚连接：(,)iCjE子句iC含负文字jx。由于WP算法使用于因子图上，因此在求解SAT问题时，需要将一个SAT问题转化为因子图，如下图2-3所示。在因子图中包含两种节点，变量节点和功能节点。在图中用圆圈表示的是变量节点，或称为变量，每个变量都与图中的顶点相关；在图中用方框表示的是功能节点，或称为子句，每个子句都与图中的另外顶点相关联。当子句A中包含变量ix时，功能节点A通过边的方式与变量节点相连，当子句中出现的变量为ix时，a和i之间用实线（1aiJ），当子句中出现的变量为ix时，a和i之间用虚线（1aiJ）。变量节点构成的集合X（XN），功能节点的集合A（AM）。如果因子图中有6个变量节点i1,...,6和6个功能节点a,b,c,d,e,f，则这个公式可以写为：13124353452466F(xx)(xxx)(xx)(xxx)(xxx)(x)图2-3因子图2.2信息传播算法若SAT问题中因子图是树形结构(树形问题)，可满足性问题可以用多种方法求解。本节将描述两种消息传播算法。第一种称为警示传播，它确定树形问题是否为SAT问题；如果是SAT问题，WP算法会找到一个可满足性赋值；第二种算法称为信念传播(BP)，它计算可满足赋值的数量，以及给定变量为真时赋值的比例。这些算法对树型问题是精确的，但它们可以作为一般问题的启发。
【参考文献】：
期刊论文
[1]警示传播算法收敛的充分条件[J]. 王晓峰,许道云. 软件学报. 2016(12)
[2]随机可满足实例集上警示传播算法的收敛性[J]. 王晓峰,许道云,韦立. 软件学报. 2013(01)
[3]求解公式关键文字集的信息传播算法[J]. 王晓峰,许道云,秦永彬. 山东大学学报(工学版). 2011(03)
本文编号：3333397
【文章来源】：北方民族大学宁夏回族自治区
【文章页数】：54 页
【学位级别】：硕士
【部分图文】：
复杂性类图
北方民族大学2020届硕士学位论文第二章理论知识9图2-1复杂性类图2.1.2因子图从系谱学上讲，因子图是对Wiberg等人的“Tanner图”的直接概括[58,59]。Tanner[60]引入了二部图来描述Gallager的低密度校验码(LDPC)的推广码族，并基于此情况描述了合积算法。在Tanner的原始公式中，所有变量都是码字符号，由此可见，Wiberg等人介绍了隐藏状态变量，并提出了编码之外的应用，因子图将这些图论模型进一步应用于函数中。因子图可以用函数因子分解的二分图表示，所以若给定一个函数12(,,...,)nbMMM，则可以对其进行因式分解，121(,,...,)()mnjjjbMMMcS(2-1)其中，12{,,...,}jnSMMM，变量顶点12{,,...,}nIMMM构成相应的因子图G(I,C，E)，因子顶点12{,,...,}mCccc和边为E。因子图可以与消息传递算法相结合，有效地计算函数12(,,...,)nbMMM的某些特征，如边缘分布。假设12345b(m,m,m,m,m)是具有五个变量的函数，b可以表示五个变量的乘积12345121233435(,,,,)()()(,,)(,)(,)ABCDEbmmmmmcmcmcmmmcmmcmm(2-2)将符号记为：1212334{,,,,}{},{},{,,},{,}ABCDJABCDE，MmMmMmmmMmm和35{,}EMmm，则图2-2表示公式2-2对应的因子图。图2-2121233435()()(,,)(,)(,)ABCDEcmcmcmmmcmmcmm乘积的因子图
北方民族大学2020届硕士学位论文第二章理论知识10设一个CNF公式为12{,,...,}mFCCC，12,,..nxxx代表有n个变元，i代表变元ix。因子图是G{CX,E}能够描述公式F。其中，用X{1,2,...,n}来表示变量结点集，功能结点集为12{,,...,}mCCCC。图G中的边分为两类：实连接和虚连接。实连接：(,)iCjE子句iC含正文字jx；虚连接：(,)iCjE子句iC含负文字jx。由于WP算法使用于因子图上，因此在求解SAT问题时，需要将一个SAT问题转化为因子图，如下图2-3所示。在因子图中包含两种节点，变量节点和功能节点。在图中用圆圈表示的是变量节点，或称为变量，每个变量都与图中的顶点相关；在图中用方框表示的是功能节点，或称为子句，每个子句都与图中的另外顶点相关联。当子句A中包含变量ix时，功能节点A通过边的方式与变量节点相连，当子句中出现的变量为ix时，a和i之间用实线（1aiJ），当子句中出现的变量为ix时，a和i之间用虚线（1aiJ）。变量节点构成的集合X（XN），功能节点的集合A（AM）。如果因子图中有6个变量节点i1,...,6和6个功能节点a,b,c,d,e,f，则这个公式可以写为：13124353452466F(xx)(xxx)(xx)(xxx)(xxx)(x)图2-3因子图2.2信息传播算法若SAT问题中因子图是树形结构(树形问题)，可满足性问题可以用多种方法求解。本节将描述两种消息传播算法。第一种称为警示传播，它确定树形问题是否为SAT问题；如果是SAT问题，WP算法会找到一个可满足性赋值；第二种算法称为信念传播(BP)，它计算可满足赋值的数量，以及给定变量为真时赋值的比例。这些算法对树型问题是精确的，但它们可以作为一般问题的启发。
【参考文献】：
期刊论文
[1]警示传播算法收敛的充分条件[J]. 王晓峰,许道云. 软件学报. 2016(12)
[2]随机可满足实例集上警示传播算法的收敛性[J]. 王晓峰,许道云,韦立. 软件学报. 2013(01)
[3]求解公式关键文字集的信息传播算法[J]. 王晓峰,许道云,秦永彬. 山东大学学报(工学版). 2011(03)
本文编号：3333397
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/3333397.html
