基于约束的局部-全局LWF链图结构学习算法  

Local-Global LWF Chain Graph Structure Learning Algorithm Based on Constraints

作　　者：曹付元[1] 杨淑晶 王雲霞 俞奎[2] CAO Fu-yuan;YANG Shu-jing;WANG Yun-xia;YU Kui(School of Computer and Information Technology,Shanxi University,Taiyuan,Shanxi 030006,China;School of Computer Science and Information Engineering,Hefei University of Technology,Hefei,Anhui 230601,China)

机构地区：[1]山西大学计算机与信息技术学院,山西太原030006 [2]合肥工业大学计算机与信息学院,安徽合肥230601

出　　处：《电子学报》2023年第6期1458-1467,共10页Acta Electronica Sinica

基　　金：国家自然科学基金(No.61976128)。

摘　　要：LWF链图结构学习旨在发现链图中所有节点的父节点、子节点、邻居节点以及配偶节点.然而,目前最新的LWF链图结构学习算法是基于Growing-Shrinking(GS)思想得到节点的局部结构(即节点的马尔科夫毯)来学习全局网络结构,该类算法的条件独立测试是以整个马尔科夫毯为条件集的,为了保证条件独立测试的可靠性,算法要求样本数量是马尔科夫毯大小的指数级,从而使得算法的数据效率较差.针对该问题,本文提出了一种基于约束的局部-全局LWF链图结构学习算法.该算法通过迭代的学习邻接集和配偶集来降低对数据样本量的要求;与此同时,在学习邻接集时采用后向策略保障了条件独立测试的正确性.算法的基本思想如下:首先学习网络中每个节点的马尔科夫毯,将节点马尔科夫毯学习拆分为学习邻接集和学习配偶集;然后利用节点的马尔科夫毯信息恢复网络骨架,根据链图复合体有向边的特点,利用条件独立测试确定网络复合体有向边,从而恢复链图结构.理论分析证明了该算法的正确性,在仿真数据集和标准数据集上的实验测试验证了算法的有效性.LWF chain graph structure learning aims to find the parents,children,neighbours and spouses of all nodes in the chain graph.Currently,the state-of-the-art LWF chain graph structure learning algorithms obtain the local structure of nodes to learn the global network structure based on Growing-Shrinking(GS)idea.The conditional independence test of these algorithms takes the whole Markov blanket(MB)as the condition set.In order to ensure the reliability of conditional independence test,the number of samples is required to be exponential level of the size of Markov blanket,which makes the data efficiency of the algorithm poor.To alleviate this problem,we propose a Local-Global LWF chain graph structure learning algorithm based on constraints,which reduces the requirement of sample size of data by iterative learning adjacen⁃cies and spouses;while learning adjacencies,it further improves the accuracy of the conditional independence test by back⁃ward strategy.The basic idea of the algorithm as follows:firstly,the Markov blanket of each node in the network is learned,and the Markov blanket learning of node is divided into learning the adjacencies and the spouses;secondly,we use the Markov blanket information of nodes to recover the network skeleton and take advantage of conditional independent test to discover its complexes,which restores the chain graph structure,according to the characteristics of directed edges of chain graph complexes.Theoretical analysis demonstrates the correctness of the algorithm.Moreover,experiments on the generated datasets and standard datasets show the effectiveness of the algorithm.

关 键 词：LWF链图 马尔科夫毯 条件独立测试 数据效率 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]