电子学报 ›› 2013, Vol. 41 ›› Issue (1): 98-104.DOI: 10.3969/j.issn.0372-2112.2013.01.018

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

基于混合方式的贝叶斯网络等价类学习算法

朱明敏1, 刘三阳1,2, 杨有龙1   

  1. 1. 西安电子科技大学理学院数学系,陕西西安 710071;
    2. 西安电子科技大学综合业务网国家重点实验室,陕西西安 710071
  • 收稿日期:2011-03-16 修回日期:2012-08-30 出版日期:2013-01-25
    • 作者简介:
    • 朱明敏 女,1985年生于陕西咸阳.西安电子科技大学数学系博士研究生.研究方向:最优化理论、算法及其在贝叶斯网络学习中的应用. E-mail:zmmzhu2010@126.com 杨有龙 男,1967生于陕西西安.西安电子科技大学数学系教授、博士生导师.研究方向:图模型学习及其应用. E-mail:ylyang@mail.xidian.edu.cn
    • 基金资助:
    • 国家自然科学基金 (No.60974082,No.61075055); 国家杰出青年科学基金 (No.11001214); 西安电子科技大学基本科研业务基金 (No.K5051270013)

Structural Learning Bayesian Network Equivalence Classes Based on a Hybrid Method

ZHU Ming-min1, LIU San-yang1,2, YANG You-long1   

  1. 1. Department of Mathematics, Xidian University, Xi'an, Shaanxi 710071, China;
    2. State Key Laboratory of Integrated Service Networks, Xidian University, Xi'an, Shaanxi 710071, China
  • Received:2011-03-16 Revised:2012-08-30 Online:2013-01-25 Published:2013-01-25
    • Supported by:
    • National Natural Science Foundation of China (No.60974082, No.61075055); National Natural Science Foundation of China for Distinguished Young Schoolars (No.11001214); Fundamental Research Funds for Xidian University (No.K5051270013)

摘要: 贝叶斯网络(BN)是不确定知识表示和推理的主要方法之一,是人工智能中重要的理论模型.针对现有混合方法学习BN结构不稳定、容易陷入局部最优等问题,本文将图论中的最大主子图分解理论与条件独立(CI)测试相结合,同时引入少量的局部评分搜索,提出一种新的基于混合方式的BN等价类学习算法.新算法通过确定所有变量的Markov边界构造网络的无向独立图,并对无向图进行最大主子图分解,从而将高维的结构学习问题转化为低维问题,然后利用低阶CI测试和局部评分搜索识别子图中的V结构.理论证明以及实验分析显示了新算法的正确性和有效性.

关键词: 贝叶斯网络, 最大主分解, Markov边界, 有向无环图, 条件独立

Abstract: Bayesian Network (BN) is one of the most important methods for representing and inferring with uncertainty knowledge,and also a powerful theory model within the community of artificial intelligence.To solve the drawbacks of hybrid methods for learning BNs which are easy to fall into local optimum and unreliable for learning large data set,we propose a novel hybrid algorithm for learning BN equivalence classes which combines ideas from maximal prime decomposition (MPD) of graph theory,conditional independence (CI) tests,and local search-and-score techniques in an effective way.It first reconstructs the undirected independence graph of a BN and then performs MPD to transform the undirected graph into its subgraphs.Finally,the new algorithm uses only lower-order CI tests and local BDeu score to check the v-structure of each subgraph.Theoretical and experimental results show that the proposed algorithm is correctness and effective.

Key words: Bayesian network, maximal prime decomposition, Markov boundary, directed acyclic graph, conditional independence

中图分类号: