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

• 学术论文 • 上一篇    下一篇

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

王静云, 刘三阳, 朱明敏   

  1. 西安电子科技大学数学与统计学院, 陕西西安 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   

  1. 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

摘要: 链图是贝叶斯网络和马尔科夫网络的自然推广,具有较强的表达能力.但目前关于链图结构学习算法的研究较少.本文基于贝叶斯网络结构学习的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

中图分类号: