微分MPE问题的联合树算法

贝叶斯网络的最大可能解释(MPE)就是在给定一些变量的值时求使这些变量的概率达到最大值时其它变量的最可能取值,本文提出用联合树来求MPE问题的一阶微分并在此基础上求MPE实例.本文先通过观察和积问题的微分提出了一个微分表,并在此基础上提出求MPE问题一阶微分的方法和用联合树求MPE问题微分的公式,同时给出了求MPE问题二阶微分的公式;接着给出了一个策略来用一阶微分的结论求MPE实例,并通过贝叶斯网络的数据特性来优化MPE实例的求解;在此基础上提出一个算法来用联合树微分MPE问题和求MPE实例.最后,通过实验证实该算法计算MPE实例时的高效性.

高效计算因果网中的最大可能解释

在因果网中,高效计算的最大可能解释(Most Probable Explanations,MPE)是一个关键问题。从有向无环图的角度,研究者们发现每一个因果网都有一个与之对应的贝叶斯网络。文中通过比较干预和微分的语义,揭示了MPE完全原子干预的微分语义。根据微分语义,因果网中原子干预MPE实例的计算可以归约为贝叶斯网络中的MPE实例的计算。接着,提出了一个联合树算法(Best JoinTree,BJT),它通过在因果网中只构建一个联合树来计算最好的原子干预,原子干预的结果包含一个BMPE(Best MPE)概率和它对应的实例。其中,BMPE概率是对MPE所有结点分别进行原子干预后得到的最高概率。BJT可以采用干预的效果来计算对应贝叶斯网络的MPE概率和MPE实例。最后,实验证实了绝大多数因果网在计算最好原子干预时,BJT的速度比目前最好的算法快了超过10倍。