基于飞蛾-烛火优化算法的贝叶斯网络结构学习

,, ,

(中国科学技术大学 自动化系,合肥 230027)

0 概述

贝叶斯网络又称信度网络,自1988年在文献[1]中被提出以来,已经广泛运用于各个领域,是不确定知识表达和推理领域最有效的理论模型之一。贝叶斯网络的构建包含结构学习和参数学习,其中结构学习是基础和核心,其结果直接影响参数学习。

完备数据集下的结构学习方法主要有2类:基于依赖分析的方法及基于评分搜索的方法。基于依赖分析的方法[2-4]根据节点间的条件相关性,利用互信息等准则获取贝叶斯网络结构。基于评分搜索的方法通过定义评分函数,利用有效的搜索算法,寻找评分最高的网络结构。相比于前者,后者通常能够获取到更好的网络结构。

采用评分搜索的方法来学习贝叶斯网络结构是一个NP-Hard问题[5],通常用启发式算法来解决此类问题。文献[6]给出一种基于贪婪搜索的K2算法,算法需要预先输入节点顺序且无法进行全局搜索。文献[7]给出了基于爬山算法(Hill Climbing,HC)的结构学习算法,通过选择不同操作,改变网络结构,但容易陷入局部最优。进化计算也广泛应用于结构学习中,文献[8]给出基于遗传算法(Genetic Algorithm,GA)的结构学习算法,利用交叉变异算子对网络更新迭代,取得了良好的效果。文献[9]根据粒子群的搜索策略,结合遗传算法交叉变异算子,给出了贝叶斯网络结构学习算法(BNC-PSO),仿真结果表明,BNC-PSO能够搜寻到较优的结构。蜂群算法[10]、蚁群算法[11]等进化计算方法已经应用于贝叶斯网络结构学习中,然而存在收敛性较差、易陷入局部最优或不稳定等问题。

2015年文献[12]给出了仿生优化算法:飞蛾烛火优化算法(Moth-flame Optimization,MFO),该算法模拟了飞蛾围绕烛火等角螺线飞行,最终扑向烛火这一曲线运动过程,很好地平衡了解空间的全局探索和潜在最优解的局部探索,能够快速有效地找到最优解,该算法在连续域问题求解中得到了广泛运用[13-14]。然而,结构学习是二值离散问题,不能模拟曲线位置更新,算法无法直接运用到贝叶斯网络结构学习中。

本文将MFO算法引入到贝叶斯网络结构学习这一离散问题中,保留了原有MFO的排序框架,通过借鉴遗传算法的相关操作,在变异时参考节点间互信息,解决二值离散问题中无法模拟曲线位置更新的问题,提出用于贝叶斯网络结构学习的BN-MFO算法。

1 贝叶斯网络及其结构学习

贝叶斯网络N(G,θ)包含两部分:结构矩阵G和参数θ。其中,矩阵G=〈V,E〉为有向无环图(Directed Acyclic Graph,DAG),V={V1,V2,…,Vn}是贝叶斯网络的节点集,E={Vk→Vl,Vi→Vj,…}则代表节点间的依赖关系,其中k,l,i,j∈[1,n];参数θ={θ1,θ2,…,θn}是一组节点的条件分布的集合,其中θi=P(Vi|π(Vi))为节点Vi的条件概率分布,若Vi没有父节点则该分布为其边缘分布。贝叶斯网络结构学习问题可描述为:

OM=(D,G′,C,f)

(1)

其中,G′是V构成的所有网络结构的集合,C是合法结构的约束条件,矩阵D是样本数据,f是描述结构矩阵G∈G′对于数据矩阵D的匹配程度的评分函数。

结构学习的过程就是在所有符合约束条件的结构中搜索评分最优的结构,即:

(2)

其中,G|=C表示结构矩阵G满足约束条件C。常用的评分函数f有K2评分函数[15]、BDe评分函数[16]、BIC评分函数[17]等,它们各有特点。本文采用BIC评分函数:

(3)

2 MFO算法

NP-Hard问题的启发式求解方法一般包含两个关键环节:全局搜索和局部搜索。优秀的启发式算法能够在两者之间合理地平衡,提高算法性能。MFO是一种优秀的启发式算法,成功运用在了连续优化问题的求解过程中。

MFO算法中,飞蛾是解的搜索者,烛火是当前最优解,飞蛾数量和烛火数量在初始时相同。向量Mi是矩阵M中的一行,代表一只飞蛾,其适应值在适应值矩阵OM中对应为OMi。

(4)

其中,n是飞蛾的数量,d是解的维数。算法另一重要组成部分是烛火的描述矩阵F,每一行代表一支烛火向量Fi,且其对应的适应值不劣于Fi+1的适应值,矩阵F对应的适应值矩阵为矩阵OF:

(5)

MFO将飞蛾和烛火均视为解,不同的是迭代过程中更新方式:飞蛾作为搜索的行动者,沿曲线朝着烛火进行搜索;飞蛾搜索到的解若更优,则将其标记为烛火,吸引飞蛾进行搜索。飞蛾的曲线位置更新函数如下:

Mi=Diebtcos(2πt)+Fj

(6)

其中,矩阵Mi代表第i只飞蛾,矩阵Fj代表第j支烛火,Di=|Fj-Mi|是距离,常量b决定了等角螺线形状,t∈[-1,1]是随机变量。

MFO人为地使每只飞蛾都绕着对应的烛火飞,即:第i只飞蛾绕着第g(i)优的烛火进行位置更新。每一轮迭代都会根据适应值对烛火进行排序,在下一轮迭代中,飞蛾再绕着对应的烛火飞。烛火的数量FN是变化的:

(7)

其中,l是当前迭代次数,N是最大烛火数,T是最大迭代次数。后期将只有一支烛火,所有飞蛾都会在最优的烛火附近飞,算法结束时返回剩下的烛火位置即为问题的最优解。

3 BN-MFO算法

3.1 初始化

本文贝叶斯网络的结构矩阵G用邻接矩阵A表示:

(8)

若节点Vj是Vi的子节点,则aij=1,否则aij=0。相应地,为适应结构学习问题的描述方式,重新定义矩阵M和矩阵F,如式(9)、式(10)所示。

(9)

(10)

其中,M和F分别为原算法飞蛾矩阵和烛火矩阵,Mi和Fi均为有向无环图DAG对应的邻接矩阵,其余定义均保持不变。需要指出的是,初始时,向量M和向量F包含完全相同的DAG,只是DAG排列不同。

初始化时,随机生成n个合法DAG作为向量M并求出对应的适应值矩阵OM,对矩阵OM排序得到矩阵OF及其对应的向量F。初始化时,还从数据中求得节点间的互信息矩阵MI。DAG生成算法为算法1,该算法不同于一般DAG生成算法,它能够返回一个与节点顺序无关的随机合法DAG,使得初始飞蛾在解空间中的分布更为均匀,其中随机数k≤size(Q)。

算法1生成DAG

输入节点个数n

输出随机的合法DAG对应的邻接矩阵A

步骤1将n个节点随机排列为队列Q,A=0。

步骤2Q出队节点Vx。从Q中随机选择k个节点为Vx的子节点。将矩阵A相应位置置1。

步骤3若Q非空,转至步骤2。

步骤4返回矩阵A。

3.2 非法结构及其更正

本文定义贝叶斯网络的非法结构为存在有向环的结构,如图1所示,图中节点2、3、5构成了有向环。除非法结构之外的其他结构都是合法结构,它们构成了飞蛾的飞行空间。当飞蛾位置非法时,需要有机制对位置进行更正,使其重新回到搜索空间。

图1 非法结构

根据图论知识设计了算法2实现检测并更正,若输入的矩阵合法则不处理,否则更正,该算法更正时能够保持DAG的大部分结构不变。本文标记检测更正算子为CC(Check and Correct)。

算法2DAG合法检测及更正

输入DAG的邻接矩阵A

输出保证合法的邻接矩阵A

步骤1矩阵A的副本矩阵C,i=1。

步骤2矩阵C对角线不含非零元素,则C=C*C,i=i+1;否则转至步骤4。

步骤3若i

步骤4随机选择矩阵C非零元素对应的2个节点Vx、Vy,将矩阵A中Vx、Vy对应的边删除或反向,将新矩阵作为输入,递归调用本算法,返回值赋给矩阵A并返回矩阵A。

3.3 位置更新

贝叶斯网络结构学习的解空间离散,MFO中的曲线移动策略无法实施。位置更新本质是继承烛火和飞蛾的部分信息,飞蛾的下一个位置和当前位置、目标位置相关。通过借鉴遗传算法,可以定义贝叶斯网络结构学习问题中杂交、变异、选择等操作,实现飞蛾的位置移动。

3.3.1 杂交操作

如图2所示,随机选择飞蛾矩阵Mi和对应烛火矩阵Fg(i)的若干列进行交换,生成新的2个子代,考虑到效率问题,列数与网络节点总数相关。该操作可能会产生非法的DAG,暂时不做处理,本文标记杂交算子为CO(Crossover)。

图2 杂交操作

3.3.2 变异操作

在结构学习中,变异操作(如图3所示)包含3种行为,即增加边、删除边、反向边。通常3种操作是随机的,事实上,在贝叶斯网络中,若节点间互信息较大,说明该对节点有较大相关性,可以认为它们之间存在有向边[3]。在BN-MFO变异过程中,选择若干节点对,参考对节点间的标准互信息,采取不同的操作:对于互信息值较大的节点对,若节点间有边存在,倾向于将边反向,若没有边,倾向于加边;对于互信息较小的节点对,倾向于删边。同样,选择的节点对数和网络节点总数相关。本文标记变异算子为V(Variation)。

图3 变异操作

变异操作之后,需要检查DAG的合法性,若该DAG非法,需要按照3.2节中的方法对其进行更正,保证结构合法。由于该步骤参考了节点间的互信息,这使得飞蛾更倾向飞向样本数据的潜在结构,保证了学习结果的稳定性。

3.3.3 选择操作

飞蛾矩阵Mi与对应的烛火矩阵Fg(i)杂交后生成2个子代矩阵ChAi、ChBi,子代经过变异、纠正之后,通过评分函数对其进行评分,选出评分较优的子代为飞蛾的下一位置,所有的子代加上全部烛火排序之后,选择合前R优的为新的烛火,过程如图4所示。

图4 排序选择框架

(11)

事实上,可以采用其他的函数关系来描述烛火数量和迭代代数的关系,不同的关系也会有不同的性能效果。

本文算法描述见算法3,算法将n只飞蛾按编号对R取余分配目标烛火,即g(i)=i%R+1;判断是否需要淘汰飞蛾取决于当前迭代代数和飞蛾的适应值。

算法3BN-MFO

输入数据矩阵D,飞蛾数量n,迭代次数T

输出贝叶斯网络结构邻接矩阵A

步骤1初始化向量M,求对应的矩阵OM,对矩阵OM排序得到矩阵OF,根据对应关系得到向量F,求互信息矩阵MI,矩阵ChA=0、矩阵ChB=0用于放置子代。

步骤2根据式(11)更新R。

步骤3对n只飞蛾矩阵Mi均按如下流程移动位置[ChAi,ChBi] =CO(Mi,Fg(i)),ChAi=V(ChAi),ChBi=V(ChBi),ChAi=CC(ChAi),ChBi=CC(ChBi),Mi=BiggerOne(ChAi,ChBi),更新OMi。

步骤4对向量F、矩阵ChA、矩阵ChB按照适应值排序,取前R优为新的向量F,同时更新矩阵OF,根据算法1生成新飞蛾替换需要淘汰飞蛾同时更新向量M和矩阵OM;若迭代未完成,转至步骤2。

步骤5返回向量F(此时最优烛火即为所求矩阵A)。

4 实验及分析

4.1 实验设置及结果

本文采用经典的8个节点Asia网和5个节点Cancer网检验算法的有效性。首先,对网络进行采样,分别获得3个数据集。算法有效性有4个评价指标:1)反向边数量;2)缺失边数量;3)多余边数量;4)求得的结构的评分。实验中,飞蛾数量设为30只,迭代次数分别为200(Cancer)、250(Asia)。实验对比算法为经典算法HC和同样基于群的优化算法BNC-PSO,其粒子群数为50,迭代次数和BN-MFO相同,每个实验均做10次,实验结果如表1、表2所示。

表1 Cancer网络实验结果

表2 Asia网络实验结果

对于Cancer网络BN-MFO能够保持和HC一样的效果,且返回的结果稳定,虽然BNC-PSO能够返回评分最优的结构,但是每次返回的结果和标准Cancer网有较大差别。对于Asia网络,3种算法中BN-MFO能够找到和标准Asia网最为相近的结构,且10次实验返回的结构基本相同、结果稳定、评分普遍优于标准Asia网;HC算法返回结构的评分有时甚至不如标准Asia网的评分优,BNC-PSO返回的结构评分普遍优于标准Asia网,但是每次返回的结构均有较大差别、不稳定。

图5和图6分别是BN-MFO算法在Cancer1000和Asia2000数据集下的迭代记录,其中,粗线表示了10次实验的平均值,细线表示单次的收敛曲线。对于Cancer网,算法在30代左右就找到了潜在结构,Asia网络的解空间较大,找到潜在结构的迭代次数较大。

图5 Cancer1000收敛曲线

图6 Asia2000收敛曲线

实验结果表明,3种算法均能学习到网络结构的大部分结构,仍有部分结构和标准结构不同。BN-MFO返回的结果稳定且最接近标准结构;HC算法能够快速学习出网络结构,但是有时不能学到最优的结构;BNC-PSO普遍能够学到评分最优的结构,但每次学到的都有较大差别,不够稳定。

4.2 结果分析

BN-MFO保留了MFO的整体框架,从而继承了MFO的优良性质。由于飞蛾和烛火间的动态对应关系g(i)和数量变化的烛火数量R的综合作用,在算法初期飞蛾与对应烛火的位置距离较远,飞蛾将有更大概率探索到更多区域,保证了全局探索性;在中期,一支烛火将会对应多只飞蛾,保证了对烛火邻域的局部探索,后期产生的新生飞蛾也使得算法有机会发现新的潜在最优解。可见BN-MFO很好地平衡了对解空间的全局探索和局部探索。同时,在飞蛾通过杂交、变异等操作具有随机性,使得飞蛾位置能够较为均匀地分布;另一方面,在变异时参考节点间的互信息,使变异有更大概率向数据潜在结构发生,保障了对潜在结构的充分探索,使得返回的结构更为稳定。

3种算法均为基于评分搜索的算法,影响结果的自然是搜索的过程和评分函数,实验已经表明,3种算法的搜索方式甚至能够学到评分优于标准网的网络结构,验证了搜索过程的正确性。可见,评分函数是导致实验中的3种算法不能学到与原结构完全一致的结构的主要原因。BNC-PSO和BN-MFO得到的结果表明,不同的结构能够获得相同的BIC评分,这一现象进一步表明评分函数的选择能够影响结构学习的过程。

5 结束语

本文将MFO引入到贝叶斯网络结构学习离散问题领域,借鉴遗传算法,替换原算法的位置更新方式,在移动的过程中参考网络节点的互信息,提出BN-MFO。该算法继承了原算法的优良性能,同时,因为互信息的运用,保证了BN-MFO的稳定性。在标准贝叶斯网络Cancer网和Asia网上,与经典结构学习算法及同类型结构学习算法进行实验对比,验证了算法的有效性和优越性。

[1] PEARL J.Probabilistic Reasoning in Intelligent Systems[J].Computer Science Artificial Intelligence,1988,70(2):1022-1027.

[2] 胡学钢,胡春玲.一种基于依赖分析的贝叶斯网络结构学习算法[J].模式识别与人工智能,2006,19(4):445-449.

[3] 李冰寒,高晓利,刘三阳,等.利用互信息学习贝叶斯网络结构[J].智能系统学报,2011,6(1):68-72.

[4] SPIRTES P G C,SCHEINES R,TILLMAN R.Automated Search for Causal Relations——Theory and Practice[EB/OL].(2010-11-21).http://repository.cmu.edu/philosophy/435/.

[5] CHICKERING D M.Learning Bayesian Networks is NP-Complete[J].Networks,1996,112(2):121-130.

[6] COOPER G F,HERSKOVITS E.A Bayesian Method for the Induction of Probabilistic Networks from Data[J].Machine Learning,1992,9(4):309-347.

[7] ALCOBé J R.Incremental Hill-climbing Search Applied to Bayesian Network Structure Learning[C]//Proceedings of the 15th European Conference on Machine Learning.Pisa,Italy:Springer,2004:301-311.

[8] LARRANAGA P,KUIJPERS C M H,MURGA R H,et al.Learning Bayesian Network Structures by Searching for the Best Ordering with Genetic Algorithms[J].IEEE Transactions on Systems Man & Cybernetics Part A Systems & Humans,1996,26(4):487-493.

[9] GHEISARI S,MEYBODI M R.BNC-PSO:Structure Learning of Bayesian Networks by Particle Swarm Optimization[J].Information Sciences,2016,348:272-289.

[10] 郭 童,林 峰.基于混合差分蜂群算法的贝叶斯网络结构学习[J].模式识别与人工智能,2014,27(6):540-545.

[11] CAMPOS L M D,FERNNDEZ-LUNA J M,GMEZ J A,et al.Ant Colony Optimization for Learning Bayesian Networks[J].International Journal of Approximate Reasoning,2002,31(3):291-311.

[12] MIRJALILI S.Moth-flame Optimization Algorithm:A Novel Nature-inspired Heuristic Paradigm[J].Knowledge-based Systems,2015,89:228-249.

[13] ALLAM D,YOUSRI D A,ETEIBA M B.Parameters Extraction of the Three Diode Model for the Multi-crystalline Solar Cell/module Using Moth-flame Optimization Algorithm[J].Energy Conversion & Management,2016,123:535-548.

[14] YAMANY W,FAWZY M,THARWAT A,et al.Moth-flame Optimization for Training Multi-layer Perceptrons[C]//Proceedings of International Computer Engineering Conference.Washington D.C.,USA:IEEE Press,2015:267-272.

[15] COOPER G F,HERSKOVITS E.A Bayesian Method for the Induction of Probabilistic Networks from Data[J].Machine Learning,1992,9(4):309-347.

[16] HECKERMAN D,DAN G,CHICKERING D M.Learning Bayesian Networks:The Combination of Knowledge and Statistical Data[J].Machine Learning,1995,20(3):197-243.

[17] LAM W,BACCHUS F.Learning Bayesian Belief Networks:An Approach Based on the MDL Principle[J].Computational Intelligence,1994,10(3):269-293.