基于约束的局部-全局LWF链图结构学习算法
Local-Global LWF Chain Graph Structure Learning Algorithm Based on Constraints
- 电子学报 2023年51卷第6期 页码：1458-1467
- 作者机构：
1.山西大学计算机与信息技术学院，山西太原 030006
2.合肥工业大学计算机与信息学院，安徽合肥 230601
- 作者简介：
[ "曹付元 男，1974年5月出生于山西省阳高县.现为山西大学计算机与信息技术学院教授.主要研究方向为数据挖掘、机器学习与因果推断.在国内外发表学术论文70余篇.E⁃mail: cfy@sxu.edu.cn" ]
[ "杨淑晶 女，1996年1月出生于山西省临汾市.现为山西大学计算机与信息技术学院博士研究生.主要研究方向为数据挖掘、机器学习与因果推断.E⁃mail: ysjzuibang@126.com" ]
- 基金信息：国家自然科学基金(61976128)
DOI：10.12263/DZXB.20210134
中图分类号： TP18;收稿：2021-01-20，
修回：2022-12-28，
纸质出版：2023-06-25
- 稿件说明：
移动端阅览
曹付元,杨淑晶,王雲霞等.基于约束的局部-全局LWF链图结构学习算法[J].电子学报,2023,51(06):1458-1467.
CAO Fu-yuan,YANG Shu-jing,WANG Yun-xia,et al.Local-Global LWF Chain Graph Structure Learning Algorithm Based on Constraints[J].ACTA ELECTRONICA SINICA,2023,51(06):1458-1467.
曹付元,杨淑晶,王雲霞等.基于约束的局部-全局LWF链图结构学习算法[J].电子学报,2023,51(06):1458-1467. DOI： 10.12263/DZXB.20210134.
CAO Fu-yuan,YANG Shu-jing,WANG Yun-xia,et al.Local-Global LWF Chain Graph Structure Learning Algorithm Based on Constraints[J].ACTA ELECTRONICA SINICA,2023,51(06):1458-1467. DOI： 10.12263/DZXB.20210134.
摘要
LWF链图结构学习旨在发现链图中所有节点的父节点、子节点、邻居节点以及配偶节点.然而，目前最新的LWF链图结构学习算法是基于Growing-Shrinking（GS）思想得到节点的局部结构（即节点的马尔科夫毯）来学习全局网络结构，该类算法的条件独立测试是以整个马尔科夫毯为条件集的，为了保证条件独立测试的可靠性，算法要求样本数量是马尔科夫毯大小的指数级，从而使得算法的数据效率较差.针对该问题，本文提出了一种基于约束的局部-全局LWF链图结构学习算法.该算法通过迭代的学习邻接集和配偶集来降低对数据样本量的要求；与此同时，在学习邻接集时采用后向策略保障了条件独立测试的正确性.算法的基本思想如下：首先学习网络中每个节点的马尔科夫毯，将节点马尔科夫毯学习拆分为学习邻接集和学习配偶集；然后利用节点的马尔科夫毯信息恢复网络骨架，根据链图复合体有向边的特点，利用条件独立测试确定网络复合体有向边，从而恢复链图结构.理论分析证明了该算法的正确性，在仿真数据集和标准数据集上的实验测试验证了算法的有效性.
Abstract
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 adjacencies and spouses; while learning adjacencies
it further improves the accuracy of the conditional independence test by backward 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.
关键词
Keywords
references
FEIZI S , MAKHDOUMI A , DUFFY K , et al . Network maximal correlation [J]. IEEE Transactions on Network Science and Engineering , 2017 , 4 ( 4 ): 229 - 247 .
张宏毅 , 王立威 , 陈瑜希 . 概率图模型研究进展综述 [J]. 软件学报 , 2013 , 24 ( 11 ): 2476 - 2497 .
ZHANG H Y , WANG L W , CHEN Y X . Research progress of probabilistic graphical models: A survey [J]. Journal of Software , 2013 , 24 ( 11 ): 2476 - 2497 . (in Chinese)
LAPPENSCHAAR M , HOMMERSOM A , LUCAS P J F . Qualitative chain graphs and their application [J]. International Journal of Approximate Reasoning , 2014 , 55 ( 4 ): 957 - 976 .
LAURITZEN S L , WERMUTH N . Graphical models for associations between variables, some of which are qualitative and some quantitative [J]. The Annals of Statistics , 1989 , 17 ( 1 ): 31 - 57 .
FRYDENBERG M . The chain graph Markov proporty [J]. Scandinavian Journal of Statistics , 1990 , 17 ( 4 ): 333 - 353 .
ANDERSSON S A , MADIGAN D , PERLMAN M D . An alternative Markov property for chain graphs [C]// Proceedings of the Twelfth International Conference on Uncertainty in Artificial Intelligence . Portland : ACM , 1996 : 40 - 48 .
COX D R , WERMUTH N . Linear dependencies represented by chain graphs [J]. Statistical Science , 1993 , 8 ( 3 ): 204 - 218 .
COX D R , WERMUTH N . Multivariate Dependencies: Models, Analysis and Interpretation [M]. New York : Chapman and Hall/CRC , 2014 .
SONNTAG D , PEÑA J M . Chain graph interpretations and their relations revisited [J]. International Journal of Approximate Reasoning , 2015 , 58 : 39 - 56 .
BHATTACHARYA R , MALINSKY D , SHPITSER I . Causal inference under interference and network uncertainty [J]. Uncertainty in Artificial Intelligence , 2019 , 2019 : 372 .
ZHANG L , ZENG Z , JI Q . Probabilistic image modeling with an extended chain graph for human activity recognition and image segmentation [J]. IEEE Transactions on Image Processing: A Publication of the IEEE Signal Processing Society , 2011 , 20 ( 9 ): 2401 - 2413 .
MA Z M , XIE X C , GENG Z . Structural learning of chain graphs via decomposition [J]. Journal of Machine Learning Research , 2008 , 9 : 2847 - 2880 .
王静云 , 刘三阳 , 朱明敏 . 基于条件独立测试的链图结构学习算法 [J]. 电子学报 , 2017 , 45 ( 10 ): 2443 - 2448 .
WANG J Y , LIU S Y , ZHU M M . Structure learning of chain graphs using the conditional independence tests [J]. Acta Electronica Sinica , 2017 , 45 ( 10 ): 2443 - 2448 . (in Chinese)
JAVIDIAN M ALI , VALTORTA M , JAMSHIDI P . Learning LWF chain graphs: A Markov blanket discovery approach [J]. Uncertainty in Artificial Intelligence , 2020 , 124 : 1069 - 1078 .
DAPHNE KOLLER . 概率图模型:原理与技术 [M]. 王飞跃, 韩素青, 译. 北京 : 清华大学出版社 , 2015 .
VERMA T , PEARL J . Equivalence and synthesis of causal models [C]// Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence . New York : ACM , 1990 : 255 - 270 .
STUDENÝ M . A recovery algorithm for chain graphs [J]. International Journal of Approximate Reasoning , 1997 , 17 ( 2/3 ): 265 - 293 .
PEÑA J M . Learning AMP chain graphs under faithfulness [C]// Proceedings of the 6th European Workshop on Probabilistic Graphical Models . Granada : PGM , 2012 : 251 - 258 .
SONNTAG D , PEÑA J M . Learning multivariate regression chain graph under faithfulness [C]// Proceedings of the 6th European Workshop on Probabilistic Graphical Models . Granada : PGM , 2012 : 299 - 306 .
XIE X C , GENG Z , ZHAO Q . Decomposition of structural learning about directed acyclic graphs [J]. Artificial Intelligence , 2006 , 170 ( 4/5 ): 422 - 439 .
PEÑA J M , SONNTAG D , NIELSEN J D . An inclusion optimal algorithm for chain graph structure learning [C]// Proceedings of the 17th International Conference on Artificial Intelligence and Statistics . Reykjavik : PMLR , 2014 : 778 - 786 .
NIELSEN J D , KOCKA T , PEÑA J M . On local optima in learning bayesian networks [C]// Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence . Acapulco : Morgan Kaufmann , 2003 : 435 - 442 .
PEÒA J M , NILSSON R , BJÖRKEGREN J , et al . Towards scalable and data efficient learning of Markov boundaries [J]. International Journal of Approximate Reasoning , 2007 , 45 ( 2 ): 211 - 232 .
WANG J Y , LIU S Y , ZHU M M . Local structure learning of chain graphs with the false discovery rate control [J]. Artificial Intelligence Review , 2019 , 52 ( 1 ): 293 - 321 .
PEÑA J M . Faithfulness in chain graphs: The Gaussian case [C]// Proceedings of the 14th International Conference on Artificial Intelligence and Statistics . Fort Lauderdale : JMLR , 2011 , 15 : 588 - 599 .
LING Z L , YU K , ZHANG Y W , et al . Causal learner: A toolbox for causal structure and Markov blanket learning [J]. Pattern Recognition Letters , 2022 , 163 ( C ): 92 - 95 .
0
浏览量
11
下载量
0
CSCD
- 网络PDF下载
- Meta-XML下载
- BibTeX下载
- Endnote下载
- RefMan 下载
- NoteExpress下载
- NoteFirst下载
关联资源
相关文章
相关作者
相关机构
- 技术支持由北京北大方正电子有限公司提供 京ICP备09064830号-19
京公网安备11010802024621 - 本系统建议在Chrome、 IE9+ 以上版本浏览器阅读本站内容，360浏览器请切换至极速模式
- Cookies帮助我们提供服务并提供个性化体验。使用本网站，即表示您同意我们使用Cookies