收稿日期:20200325;修回日期:20200515 基金项目:国家自然科学基金资助项目(61462001,61762019,61862051,61962002);北方
民族大学重大专项资助项目(
ZDZX201901);宁夏自然科学基金资助项目(NZ17111,2019AAC03120,2019AAC03119);北方民族大学校级科研一般
项目(2019XYZJK05)
作者简介:牛进(1993),男,陕 西 安 康 人,硕 士 研 究 生,主 要 研 究 方 向 为 机 器 学 习、算 法 分 析 与 设 计 (20187258@ stu.nmu.edu.cn);
王晓峰(1980),男,甘肃会宁人,副教授,博士,主要研究方向为机器学习、算法分析与设计;林青文(1996),女,黑龙江牡丹江人,硕士研究生,主
要研究方向为机器学习、算法分析与设计
.
基于结构熵的警示传播算法收敛性分析
牛 进,王晓峰,林青文
(北方民族大学 计算机科学与工程学院,银川 750021)
摘 要:收敛性是评价信息传播算法性能的重要指标,信息传播算法求解可满足性问题时,命题公式的结构特
征影响算法的收敛性,具有复杂结构的命题公式,信息传播算法不总收敛。为了系统地对此现象给予理论解释,
借助于结构熵的方法和技术,提出命题公式的结构熵模型及其度量方法,计算随机可满足性实例的结构熵。警
示传播算法(WP)作为信息传播算法的基本模型,分析 WP算法的收敛性对于研究其他信息传播算法的收敛性
具有重要意义,分析了 WP算法收敛性与结构熵之间的关系,给出 WP算法收敛的判定条件。通过实验分析,该
方法有效可行。
关键词:可满足性问题;命题公式;结构熵;警示传播算法;收敛性
中图分类号:TP39304 文献标志码:A 文章编号:10013695(2021)03023076004
doi
:10.19734/j.issn.10013695.2020.03.0053
Convergenceanalysisofwarningpropagationalgorithmbasedonstructuralentropy
NiuJin,WangXiaofeng,LinQingwen
(SchoolofComputerScience&Engineering,NorthMinzuUniversity,Yinchuan750021,China)
Abstract:Convergenceisanimportantindexforevaluatingtheperformanceofinformationpropagationalgorithms.Whenthe
informationpropagationalgorithmsolvesthesatisfiabilityproblem,thestructuralcharacteristicsofthepropositionformulaaffect
theconvergenceofthealgorithm
,propositionalformulaswithcomplexstructuresdonotalwaysconvergeoninformationpropaga
tionalgorithms.Forthisphenomenon,therearefewsystematictheoreticalexplanations.Asthebasicmodeloftheinformation
propagationalgorithm,thewarningpropagation(WP)algorithmanalyzedtheconvergenceoftheWPalgorithmwasofgreatsig
nificancetostudytheconvergenceofotherinformationpropagationalgorithms.Withthehelpofstructuralentropymethodsand
techniques,thispaperproposedastructuralentropymodelofpropositionalformulaanditsmeasurementmethod.Thispapercal
culatedthestructuralentropyofarandomsatisfiabilityinstance,analyzedtherelationshipbetweentheconvergenceoftheWP
algorithmandthestructuralentropy,andgavethejudgmentconditionofconvergenceofWPalgorithm.Throughexperimental
analysis,thismethodiseffectiveandfeasible.
Keywords:satisfiabilityproblem;propositionalformula;structuralentropy;warningpropagationalgorithm;convergence
0 引言
约束可满足性问题(constraintsatisfactionproblem)普遍存
在于现实世界中,其研究目前在人工智能领域中具有广泛影
响
[1~3]
。作为一个重大子问题,布尔可满足性判定问题(sati
sfiability,SAT)作为首先被证明的 NPC问题
[4]
,任何算法都无
法在多项式时间内求得准确解,然而,现实世界中的许多问题
都可以归约为
SAT问题
[5~7]
。因此,SAT问题一直在计算机
科学界和数理逻辑界被学者广泛关注。该问题研究是否存在
一组布尔变量,赋值给指定的命题公式,能使该公式可满足,即
使公式为真。由于任何一个命题逻辑公式都可以转换为一个
等价的合取范式
[8]
,所以本文只考虑合取范式。
20世纪 80年代,物理学家提出了一种基于因子图的信息
传播算法。该算法的性能十分依赖于因子图的结构,当因子图
为单连通结构(任意两个节点之间只有一条路径)时,算法一
般能够正确收敛。虽然信息传播算法用于求解 SAT问题时往
往具有良好的性能表现,但随着因子图结构趋于复杂,尤其当
其中出现环路时,信息可能在环路中无限循环传播,该过程将
导致信息最终无法收敛于一个固定值,因此导致算法无法求
解,该现象称为算法不收敛
[9]
。WP算法作为一种最为基础的
信息传播算法,研究其收敛性可以对其他信息传播算法的研究
给出重要参考。WP算法是一种基于因子图的消息迭代算法,
通过因子图的边进行信息传递(称为警示信息),警示信息表
示变元的取值是否能够完全决定子句的可满足性,该算法利用
一种迭代策略更新警示信息,直到算法收敛时停止迭代,或达
到最大迭代步数时若算法仍不收敛,则强迫迭代过程结束,因
此收敛性是
WP算法最为核心的性质。目前,WP算法的收敛
性研究已经获得了一些成果,文献[10]证明了当因子图中只
存在一个环路时,该算法能够有效收敛,得出的值是变量边缘
分布的有效近似。文献[
11]基于高斯模型给出了算法收敛的
充分必要条件,该条件受限于两个变量不能同属于一个子句。
文献[12]基于消息矩阵分析了算法的收敛性,给出了一个充
分必要条件,但局限于消息矩阵为半正定矩阵。文献[13,14]
分析了基于高斯模型的算法的收敛性,但要求用半定规划来检
查收敛性,检查效率较低且非常困难。文献[
15]分析了求解
均值的算法的收敛性,要求估计有限尺度矩阵的谱半径,在实
际应用中可行性不高。文献[16]中分析了算法的收敛性,并
第 38卷第 3期
2021年 3月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol38No3
Mar.2021