基于条件独立测试的链图结构学习算法

doi:10.3969/j.issn.0372-2112.2017.10.019

电子学报 ›› 2017, Vol. 45 ›› Issue (10): 2443-2448.DOI: 10.3969/j.issn.0372-2112.2017.10.019

基于条件独立测试的链图结构学习算法

王静云, 刘三阳, 朱明敏

西安电子科技大学数学与统计学院, 陕西西安 710071

收稿日期:2016-01-29 修回日期:2016-08-16 出版日期:2017-10-25
- 通讯作者:
- 刘三阳
- 作者简介:
- 王静云,女,1988年生于陕西咸阳,西安电子科技大学数学与统计学院博士研究生.研究方向:最优化理论、算法及其在概率图模型学习中的应用.E-mail:wangjingyun0607@163.com
- 基金资助:
- 国家自然科学基金 (No.61373174）; 国家青年科学基金 (No.11401454）

Structure Learning of Chain Graphs Using the Conditional Independence Tests

WANG Jing-yun, LIU San-yang, ZHU Ming-min

School of Mathematics and Statistics, Xidian University, Xi'an, Shaanxi 710071, China

Received:2016-01-29 Revised:2016-08-16 Online:2017-10-25 Published:2017-10-25

摘要/Abstract

摘要： 链图是贝叶斯网络和马尔科夫网络的自然推广，具有较强的表达能力.但目前关于链图结构学习算法的研究较少.本文基于贝叶斯网络结构学习的Grow-Shrink 算法思想，提出一种链图等价类结构学习算法.该算法首先利用网络中结点的局部邻域信息，学习结点的邻接结点恢复网络骨架；然后根据链图复合体有向边的特点，利用条件独立测试确定网络的复合体有向边，从而恢复链图结构.理论分析和实验结果表明了该算法的正确性和有效性.

关键词: 链图, 结构学习, 条件独立测试, 马尔科夫性

Abstract: Chain graphs(CGs) including both Bayesian networks(BNs) and Markov networks(MNs) as special cases,can express more independence models compared to the basic probabilistic graphical models.Today there exist several researches on structure learning of chain graphs.In this paper,we propose an algorithm for learning the equivalence classes of a chain graph based on the Grow-Shrink(GS) algorithm for structure learning of Bayesian networks.The algorithm works by first learning the adjacent nodes of each node in a chain graph for recovering its skeleton,and then discovering its complexes using the conditional independence tests and the property of the complexes.Theoretical analysis and experimental results demonstrate the effectiveness and correctness of the proposed algorithm.

Key words: chain graph, structure learning, conditional independence test, Markov property

中图分类号:

TP18

王静云, 刘三阳, 朱明敏. 基于条件独立测试的链图结构学习算法[J]. 电子学报, 2017, 45(10): 2443-2448.

WANG Jing-yun, LIU San-yang, ZHU Ming-min. Structure Learning of Chain Graphs Using the Conditional Independence Tests[J]. Acta Electronica Sinica, 2017, 45(10): 2443-2448.

参考文献

[1] Dag Sonntag,J MPeña, Manuel Gomez-Olmedo.Approximate counting of graphical models via MCMC revisited[J].International Journal of Intelligence Systems,2015,30(3):384-420.
[2] M Frydenberg.The chain graph Markov property[J].Scandinavian Journal of Statistics,1990,17(4):333-353.
[3] S L Lauritzen,N Wermuth.Graphical models for associations between variables,some of which are qualitative and some quantitative[J].Annals of Statistics,1989,17(1):31-57.
[4] S A Andersson,D Madigan,M D Perlman.An alternative Markov property for chain graphs[J].Scandianavian Journal of Statistics,2001,28(1):33-85.
[5] D R Cox,N Wermuth.Linear dependencies represented by chain graphs[J].Statistical Science,1993,8(3):204-283.
[6] Dag Sonntag,J M Peña.Chain graph interpretations and their relations[J].International Journal of Approximate Reasoning,2015,58:39-56.
[7] 王飞跃,韩素青,等译.概率图模型原理与技术[M].清华大学出版社,2015.
[8] Tsamardinos I,Brown L E,Aliferis C F.The max-min hill-climbing Bayesian network structure learning algorithm[J].Machine Learning,2006,65(1):31-78.
[9] 朱明敏,刘三阳,杨有龙.基于混合方式的贝叶斯网络等价类学习算法[J].电子学报,2013,41(1):98-104. ZHU M M,Liu S Y,Yang Y L.Structural learning Bayesian network equivalence classes based on a hybrid method[J].Acta Electronica Sinica,2013,41(1):98-104.(in Chinese)
[10] Milan Studeny.On recovery algorithm for chain graphs[J].International Journal of Approximate Reasoning,1997,17(2-3):265-293.
[11] J MPeña.Learning AMP chain graphs under faithfulness[A].Proceedings of the 6^th European Workshop on Probabilistic Graphical Models[C].Granada,Spain,2012.251-258.
[12] D Sonntag,J M Peña.Learning multivariate regression chain graphs under faithfulness[A].Proceedings of the 6^th European Workshop on Probabilistic Graphical Models[C].Granada,Spain,2012.299-306.
[13] Zongming Ma,Xianchao Xie,Zhi Geng.Structure learning of chain graphs via decomposition[J].Journal of Machine Learning Research,2008,9(9):2847-2880.
[14] Xianchao Xie,Zhi Geng,Qiang Zhao.Decomposition of structure learning about directed acyclic graphs[J].Artificial Intelligence,2006,170(4-5):422-439.
[15] J M Peña,Dag Sonntag,Jens D Nielsen.An inclusion optimal algorithm for chain graph structure learning[A].Proceedings of the 17^th International Conference on Artificial Intelligence and Statistics (AISTATS)[C].Reykjavik,Iceland,2014.778-786.
[16] J D Nielsen,T Kocka,J M Peña.On local optima in learning Bayesian networks[A].Proceedings of the 19^th Conference on Uncertainty in Artificial Intelligence[C].Acapulco,Mexico,2003.435-442.
[17] Dag Sonntag,Matti Jarvisalo,J M Peña, Antti Hyttinen.Learning optimal chain graphs with answer set programming[A].Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence[C].Amsterdam,Netherlands,2015.822-831.
[18] Dimitris Margaritis,Sebastian Thrun S.Bayesian network induction via local neighborhoods[A].Advances in Neural Information Processing Systems 12[C].Denver,USA,2000.505-511.
[19] Dimitris Margaritis.Learning Bayesian network model structures from data[D].Pittsburgh:Carnegie Mellon University,2003.
[20] J M Peña.Faithfulness in chain graph:The discrete case[J].International Journal of Approximate Reasoning,2009,50:1306-1313.
[21] J M Peña.Faithfulness in chain graphs:the Gaussian case[A].Proceedings of the 14^th International Conference on Artificial Intelligence and Statistics[C].Florida,USA,2011.588-599.
[22] Richard E Neapolitan.Learning Bayesian Networks[M].Pearson Prentice Hall,2004.

基于条件独立测试的链图结构学习算法

Structure Learning of Chain Graphs Using the Conditional Independence Tests

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

[1]	谭翔元, 高晓光, 贺楚超. 基于马尔科夫毯约束的最优贝叶斯网络结构学习算法[J]. 电子学报, 2019, 47(9): 1898-1904.
[2]	陶卿, 朱烨雷, 罗强, 孔康. 一种基于Comid的非光滑损失随机坐标下降方法[J]. 电子学报, 2013, 41(4): 768-775.
[3]	贾海洋;陈娟;朱允刚;刘大有. 基于混合方式的贝叶斯网弧定向算法[J]. 电子学报, 2009, 37(8): 1842-1847.
[4]	侯彪;刘凤;焦李成;包慧东. 基于自适应窗口固定及传播的多尺度纹理图像分割[J]. 电子学报, 2009, 37(7): 1492-1500.