计算最大积实例的新算法  

New algorithms for computing max-product instantiations

作　　者：李超[1] 覃飙[2] 

机构地区：[1]中国政法大学商学院,北京100088 [2]中国人民大学信息学院,北京100872

出　　处：《计算机应用研究》2015年第6期1711-1715,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(61170012);国家社会科学基金资助项目(12CRK019);中国人民大学明德青年学者计划资助项目(10XNJ048);中国政法大学青年教师学术创新团队项目(2014CXTD06);江苏省未来网络创新研究院未来网络前瞻性研究项目(BY2013095-5-09)

摘　　要：最大积实例包括最大可能解释(MPE)和最大后验估计(MAP),它们是贝叶斯网络的基本问题。针对经典算法求最大积实例的时间复杂度高,提出新算法来求解该问题。该算法将求贝叶斯网络的最大积实例问题转变成一组一元一次方程,而一元一次方程很容易求解;通过临时表来缓存计算最大积概率时的中间结果,而这些临时表可以用来优化计算最大积实例而不需要过多的额外空间开销,并能够在贝叶斯查询之间共享。通过实验证实该算法计算贝叶斯网络实例时的高效性,在计算最大积实例时的有效性。The max-product problem includes the most probable explanation （MPE） and the maximum a posteriori hypothesis （ MAP）, which are basic problems of Bayesian networks. Because the time complexity of the traditional algorithms was high, this paper introduced novel techniques to solve the max-product problem. This algorithm first transformed the problem of Computing the max-product instantiations of Bayesian networks into a set of linear equations with one variable, which could be easily solved. Next this paper used factors to cache the intermediate results when computing the max-product probability. The with cached factors could be used to optimize the computation of the max-product instantiations without too much extra space overhead. Moreover, the cached factors could be shared among Bayesian network queries. Finally, the experimental results dem- onstrate the efficiencies of the algorithms in finding the max-product instantiations of Bayesian networks, and they are effective algorithms in computing the max-product instantiations.

关 键 词：贝叶斯网络 最大积实例 最大可能解释 最大后验估计 

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