贝叶斯网络结构学习研究-论文.pdf

《贝叶斯网络结构学习研究-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第22卷第17期电子设计工程2014年9月VoI．22No．17ElectronicDesignEngineeringSep．2014贝叶斯网络结构学习研究殷陶(上海交通大学计算机系，上海200240)摘要：针对贝叶斯网络结构学习方法难以兼顾高准确率和高效率的问题，提出了一种基于MarkovChainMonteCarlo(MCMC)~-法的贝叶斯网络结构学习方法的改进。改进包括：使用依赖关系分析，利用统计学的方法对采样空间进行大幅缩减，能够在精确控制准确度的情况下大幅提高时间效率；结合先验知识，从理论角度将先验知识融

2、入评分中得到完全服从后验分布的结果；搜索最优子结构，对于特定的一些结构搜索最优子结构而不是采用贪心的方法，提高了贝叶斯网络结构学习的准确率。通过理论分析可以证明时间复杂度得到了大幅的降低。并且可以在牺牲可预知的准确率的情况下，将指数时间复杂度降为线性时间。大量的数据实验表明，经改进后的方法在时间和准确性上都具有良好的表现。关键词：贝叶斯网络学习；时间效率；独立性检测；最优子结构；先验知~．；MarkovChainMonteCarlo(MCMC)中图分类号：TP3l1文献标识码：A文章编号：1674—6236(2014

3、)17—005—04BayesiannetworkstructurelearningmethodstudyYINTao(DepartmentofComputerScienceandEngineering,ShanghaiJiaotongUniversity，Shanghai200240，China)Abstract：ForthedificultiesoflearningthestructureofBayesiannetworkbothhishaccuracyandhisheficiency,weproposedana

4、daptivemethodbasedonMarkovChainMonteCarlo(MCMC)method．ImprovementsincludeDependencyanalysis；usingstatisticalmethodstosubstantiallyreducethesamplingspace，wecancontroltheaccuracyandsubstantialincreasethetimeeficiency．Combinedwithprioriknowledge；fromthetheoretical

5、point,wecanaddprioriknowledgetothescorewhichexactlyobeytheposteriordistribution．Searchforoptimalsubstructure；searchforoptimalsubstructureofsomespecificstructurewillgetthehighaccuracyoflearningBayesiannetworkratherthangreedymethods．Bytheoreticalanalysiswecanprov

6、ethetimecomplexityissignificantlyreduced．Undertheexpenseoftheaccuracywhichcanpredict,wecanreducethetimecomplexityfromexponentiallineartime．Largeamountsofdataexperimentsshowthattheimprovedmethodhasgoodperformancebothintimeandaccuracy．Keywords：Bayesiannetworkstru

7、cturelearning；timeeficiency；independencetest；optimalsubstructure；prioriknowledge；MarkovChainMonteCarlo(MCMC)在已知数据中进行贝叶斯网络结构学习是一个重要的确性难以保证，特别是在高维的情况下很难让人信服。基于问题，在近些年中也得到了广泛和深入的研究。贝叶斯网络采样的方法中最常使用的方法就是MCMC采样，其优点在于成功的应用在多个领域，诸如：生物信息学，计算机视觉，经从理论上可以保证解的最优性。但是往往在实际应用中

8、计算济学等。贝叶斯网络是一个有向无环图(directedacyclic复杂度是不可行的，除非只有很少的结点。本文提出一种改graph，DAG)，其结构表明了数据间的条件独立性和因果关进的方法，在基于MCMC采样方法上使用一些带有启发式系。贝叶斯网络结构数随着结点个数的增长呈超指数增长。信息，在具有严格理论支持的置信度控制下大幅缩减样本空因此，无