贝叶斯网结构学习搜索空间分析  

Analysis on the Searching Space of the Bayesian Networks Structure Learning

作　　者：贾海洋[1] 陈娟[1] 刘大有[1] 

机构地区：[1]吉林大学计算机科学与技术学院,符号计算与知识工程教育部重点实验室,吉林长春130012

出　　处：《计算机工程与科学》2010年第9期122-126,共5页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(60496321;60573073;60603030;60773099;60703022);国家863计划资助项目(2006AA10Z245);教育部博士点基金资助项目(20070183057);中央高校基本科研业务费专项资金资助--吉林大学(421032041421)

摘　　要：贝叶斯网结构学习是一个NP难题,提高学习效率是重要研究问题之一。贝叶斯网结构空间的规模随节点(随机变量)数呈指数增加,选择适当的结构空间可以提高学习效率。本文对贝叶斯网结构空间进行定性和定量分析,对比有向图空间、贝叶斯网空间和马尔科夫等价类空间的规模和特点。通过实验数据分析先验结构空间约束对降低结构空间规模的效率,给出约束参数的选择区间。为贝叶斯网结构学习选择搜索空间和确定约束参数提供理论支持,从而提高学习效率。Structure learning of the Bayesian networks is a NP hard problem,and improving the efficiency of structure learning is one of the most important problems. The size of a searching space increases exponentially with the number of vertexes,and choosing and limiting the searching space of structure learning can improve the efficiency of a learning algorithm. This paper gives a qualitative and quantitive analysis on the searching space,compares the sizes and characteristics of the directed graph,the directed acyclic graph and the Markov equivalence class space. Based on the experiment data,we analyse the efficiency of constraining the prior structure space,and give an advice on choosing the parameters. These analyses are helpful when choosing the searching space and defining the parameters of constraints,thus improving the efficiency of structure learning.

关 键 词：贝叶斯网 结构学习 搜索空间 马尔可夫等价 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]