论文标题
MPE推理使用增量建筑范围的范式
MPE inference using an Incremental Build-Infer-Approximate Paradigm
论文作者
论文摘要
已知贝叶斯网络中最可能的解释（MPE）的精确推断已知NP完整。在本文中，我们提出了一种基于增量构建 - 与众不同（IBIA）框架的近似MPE推理的算法。我们使用此框架来获取贝叶斯网络和相应的最大校准集团树的有序分区。我们表明，最后一个分区中的最大信念给出了MPE分配概率的估计。我们提出了一种用于解码的迭代算法，其中保证获得分配的变量子集可确保每次迭代中增加。没有融合问题，我们也不会对解决方案进行搜索。即使是单个射击算法，我们也可以在用于测试的117个基准中获得100个有效的作业。我们解决方案的准确性可与大多数基准的分支和绑定搜索相媲美，并具有竞争性运行时间。
Exact inference of the most probable explanation (MPE) in Bayesian networks is known to be NP-complete. In this paper, we propose an algorithm for approximate MPE inference that is based on the incremental build-infer-approximate (IBIA) framework. We use this framework to obtain an ordered set of partitions of the Bayesian network and the corresponding max-calibrated clique trees. We show that the maximum belief in the last partition gives an estimate of the probability of the MPE assignment. We propose an iterative algorithm for decoding, in which the subset of variables for which an assignment is obtained is guaranteed to increase in every iteration. There are no issues of convergence, and we do not perform a search for solutions. Even though it is a single shot algorithm, we obtain valid assignments in 100 out of the 117 benchmarks used for testing. The accuracy of our solution is comparable to a branch and bound search in majority of the benchmarks, with competitive run times.
