微分MPE问题的联合树算法
|
摘要
贝叶斯网络的最大可能解释(MPE)就是在给定一些变量的值时求使这些变量的概率达到最大值时其它变量的最可能取值,本文提出用联合树来求MPE问题的一阶微分并在此基础上求MPE实例.本文先通过观察和积问题的微分提出了一个微分表,并在此基础上提出求MPE问题一阶微分的方法和用联合树求MPE问题微分的公式,同时给出了求MPE问题二阶微分的公式;接着给出了一个策略来用一阶微分的结论求MPE实例,并通过贝叶斯网络的数据特性来优化MPE实例的求解;在此基础上提出一个算法来用联合树微分MPE问题和求MPE实例.最后,通过实验证实该算法计算MPE实例时的高效性.
In Bayesian networks,a most probable explanation( MPE) is to find the most probable instantiationsof all other network variables,which will compute the biggest probability of a set of given evidence. This paper proposes to use the jointree for the first derivative of the MPE problem and the MPE instantiation. In this paper,a differential table is introduced by observing the differentiation of the sumproduct problem. Using the differential table,a strategy is proposed to compute the first derivative of the MPE problem and a formula is introduced to differentiate the MPE problem by the jointree. In addition,we give the formulas for computing the second derivative of the MPE problem by the differential table. Another method is proposed to compute the MPE instantiation by the result of the differentiation of the MPE Problem. Moreover,our strategy can be optimized by the data properties of Bayesian networks. Based on the above strategy,a jointree-based algorithm is devised to differentiate the MPE problem and compute the MPE instantiation as well. Finally,we present the experimental results to demonstrate the efficiency and effectiveness of our algorithm in finding the MPE instantiation.
In Bayesian networks,a most probable explanation( MPE) is to find the most probable instantiationsof all other network variables,which will compute the biggest probability of a set of given evidence. This paper proposes to use the jointree for the first derivative of the MPE problem and the MPE instantiation. In this paper,a differential table is introduced by observing the differentiation of the sumproduct problem. Using the differential table,a strategy is proposed to compute the first derivative of the MPE problem and a formula is introduced to differentiate the MPE problem by the jointree. In addition,we give the formulas for computing the second derivative of the MPE problem by the differential table. Another method is proposed to compute the MPE instantiation by the result of the differentiation of the MPE Problem. Moreover,our strategy can be optimized by the data properties of Bayesian networks. Based on the above strategy,a jointree-based algorithm is devised to differentiate the MPE problem and compute the MPE instantiation as well. Finally,we present the experimental results to demonstrate the efficiency and effectiveness of our algorithm in finding the MPE instantiation.
引文
[1]Darwiche A.Modeling and reasoing with bayesian networks[M].Cambridge University Press,2009.
[2]Darwiche A.A differential approach to inference in bayesian netw orks[J].Journal of the ACM,2003,50(3):280-305.
[3]Park J,Darwiche A.A differential semantics for jointree algorithms[J].Artificial Intelligence,2004,156(1):197-216.
[4]Chan H,Darwiche A.On the robustness of most probable explanations[C].Proc of the 22th Conference on Uncertainty in Artificial Intelligence.Arlington,Virginia,2006:63-71.
[5]Dechter R.Bucket elimination:a unifying framework for reasoning[J].Artificial Intelligence,1999,113(1-2):41-85.
[6]Shenoy P,Shafer G.Propagating belief functions with local computations[J].IEEE Expert,1986,1(3):43-52.
[7]Qin B.Differential semantics of intervention in bayesian networks[C].Proc of the 24th International Joint Conference on Artificial Intelligence.Buenos Aires,Argentina,2015:710-716.
[8]Jensen F,Andersen S.Approximations in bayesianbelief universes for know ledge based systems[C].Proc of the 6th Conference on Uncertainty in Artificial Intelligence.Cambridge,MA,1990:162-169.
[9]Li Chao,Qin Biao.New algorithms for computing max-product instantiations[J].Application Research of Computers,2015,32(6):1711-1715.
[10]Qin Biao,Wang Qiu-yue,Li Chao.An effective strategy for sensitivity analysis of bayesian netw orks[J].Journal of Chinese Computer Systems,2016,37(4):732-737.
[11]Darwiche A.http://reasoning.cs.ucla.edu/ace,2011.
[12]http://sourceforge.net/projects/bnj/,2012.
[9]李超,覃飙.计算最大积实例的新算法[J].计算机应用研究,2015,32(6):1711-1715.
[10]覃飙,王秋月,李超.一种高效的贝叶斯网络敏感性分析方法[J].小型微型计算机系统,2016,37(4):732-737.
[2]Darwiche A.A differential approach to inference in bayesian netw orks[J].Journal of the ACM,2003,50(3):280-305.
[3]Park J,Darwiche A.A differential semantics for jointree algorithms[J].Artificial Intelligence,2004,156(1):197-216.
[4]Chan H,Darwiche A.On the robustness of most probable explanations[C].Proc of the 22th Conference on Uncertainty in Artificial Intelligence.Arlington,Virginia,2006:63-71.
[5]Dechter R.Bucket elimination:a unifying framework for reasoning[J].Artificial Intelligence,1999,113(1-2):41-85.
[6]Shenoy P,Shafer G.Propagating belief functions with local computations[J].IEEE Expert,1986,1(3):43-52.
[7]Qin B.Differential semantics of intervention in bayesian networks[C].Proc of the 24th International Joint Conference on Artificial Intelligence.Buenos Aires,Argentina,2015:710-716.
[8]Jensen F,Andersen S.Approximations in bayesianbelief universes for know ledge based systems[C].Proc of the 6th Conference on Uncertainty in Artificial Intelligence.Cambridge,MA,1990:162-169.
[9]Li Chao,Qin Biao.New algorithms for computing max-product instantiations[J].Application Research of Computers,2015,32(6):1711-1715.
[10]Qin Biao,Wang Qiu-yue,Li Chao.An effective strategy for sensitivity analysis of bayesian netw orks[J].Journal of Chinese Computer Systems,2016,37(4):732-737.
[11]Darwiche A.http://reasoning.cs.ucla.edu/ace,2011.
[12]http://sourceforge.net/projects/bnj/,2012.
[9]李超,覃飙.计算最大积实例的新算法[J].计算机应用研究,2015,32(6):1711-1715.
[10]覃飙,王秋月,李超.一种高效的贝叶斯网络敏感性分析方法[J].小型微型计算机系统,2016,37(4):732-737.