计算最大积实例的新算法

New algorithms for computing max-product instantiations

最大积实例包括最大可能解释(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.