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

CAO Fu-yuan; YANG Shu-jing; WANG Yun-xia; YU Kui

doi:10.12263/DZXB.20210134

您当前的位置：

首页 >

文章列表页 >

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

PAPERS | 更新时间：2025-12-08

- Local-Global LWF Chain Graph Structure Learning Algorithm Based on Constraints
- ACTA ELECTRONICA SINICA Vol. 51, Issue 6, Pages: 1458-1467(2023)
- 作者机构：
  
  1.山西大学计算机与信息技术学院，山西太原 030006
  2.合肥工业大学计算机与信息学院，安徽合肥 230601
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(61976128)
- DOI：10.12263/DZXB.20210134
  CLC： TP18;
- Received：20 January 2021，
  
  Revised：2022-12-28，
  
  Published：25 June 2023
- 稿件说明：
移动端阅览
曹付元,杨淑晶,王雲霞等.基于约束的局部-全局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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Optimal BN Structure Learning Algorithm Based on Double Constraints

Structure Learning of Chain Graphs Using the Conditional Independence Tests

Learning Optimal Bayesian Network Structure Constrained with Markov Blanket

Related Author

ZHANG Xin-lan

DI Ruo-hai

CHEN Yi-wei

WANG Peng

ZHANG Huan

XU Wen

ZHU Ming-min

WANG Jing-yun

Related Institution

School of Electronics and Information Engineering, Xi'an Technological University, , Shannxi

Aerospace Research Institute of Materials & Processing Technology

School of Mathematics and Statistics, Xidian University

School of Electronic and Information, Northwestern Polytechnical University

⁰