贝叶斯网络结构学习研究  

Bayesian network structure learning method study

作　　者：殷陶[1] 

机构地区：[1]上海交通大学计算机系,上海200240

出　　处：《电子设计工程》2014年第17期5-8,共4页Electronic Design Engineering

基　　金：国家自然科学基金(61073087)

摘　　要：针对贝叶斯网络结构学习方法难以兼顾高准确率和高效率的问题,提出了一种基于Markov Chain Monte Carlo(MCMC)方法的贝叶斯网络结构学习方法的改进。改进包括:使用依赖关系分析,利用统计学的方法对采样空间进行大幅缩减,能够在精确控制准确度的情况下大幅提高时间效率;结合先验知识,从理论角度将先验知识融入评分中得到完全服从后验分布的结果;搜索最优子结构,对于特定的一些结构搜索最优子结构而不是采用贪心的方法,提高了贝叶斯网络结构学习的准确率。通过理论分析可以证明时间复杂度得到了大幅的降低。并且可以在牺牲可预知的准确率的情况下,将指数时间复杂度降为线性时间。大量的数据实验表明,经改进后的方法在时间和准确性上都具有良好的表现。For the difficulties of learning the structure of Bayesian network both high accuracy and high efficiency, we proposed an adaptive method based on Markov Chain Monte Carlo （MCMC） method. Improvements include Dependency analysis; using statistical methods to substantially reduce the sampling space, we can control the accuracy and substantial increase the time efficiency. Combined with priori knowledge; from the theoretical point, we can add priori knowledge to the score which exactly obey the posterior distribution. Search for optimal substructure; search for optimal substructure of some specific structure will get the high accuracy of learning Bayesian network rather than greedy methods. By theoretical analysis we can prove the time complexity is significantly reduced. Under the expense of the accuracy which can predict, we can reduce the time complexity from exponential linear time. Large amounts of data experiments show that the improved method has good performance both in time and accuracy.

关 键 词：贝叶斯网络学习 时间效率 独立性检测 最优子结构 先验知识 MARKOV CHAIN MONTE Carlo(MCMC) 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]