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

• 作者: 李超 覃飙
• 来源期刊: 计算机科学
• 关键词: 因果网 贝叶斯网络 干预 微分MPE MPE实例
• 年，卷（期）: 2021,（4）
• 所属期刊栏目: 计算机科学理论|Computer Science Theory
• 页码范围: 14-19
• 页数: 6页
• 分类号: TP311
• 语种: 中文
• DOI: 10.11896/jsjkx.200500155

摘要

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