Bucket and Mini-bucket Schemes for M Best Solutions over Graphical Models
Bucket and Mini-bucket Schemes for M Best Solutions over Graphical Models
复制标题
基于图形模型的 M 最佳解决方案的桶和迷你桶方案
DOI：
10.1007/978-3-642-29449-5_4
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
R. Dechter
中科院分区：
文献类型：
--
作者：
N. Flerova;E. Rollon;R. Dechter
本文的重点是为在图形模型上定义的组合优化问题生成前m个最佳解决方案的任务（例如，贝叶斯网络的m个最可能的解释）。我们证明了m-best任务可以在半环的统一框架内表示，从而定义了已知的推理算法，并立即暗示了m-best任务的正确性和完备性。随后，我们描述了求解m-最优任务的一种新的桶消除算法elimo -m-opt，提供了其定义组合和边缘化算子的算法，并分析了其最坏情况性能。将该算法扩展到迷你桶框架，为m个最佳解决方案中的每一个提供边界。提供了算法的经验证明，重点是它们的逼近潜力。
The paper focuses on the task of generating the first m best solutions for a combinatorial optimization problem defined over a graphical model (e.g., the m most probable explanations for a Bayesian network). We show that the m-best task can be expressed within the unifying framework of semirings making known inference algorithms defined and their correctness and completeness for the m-best task immediately implied. We subsequently describe elim-m-opt, a new bucket elimination algorithm for solving the m-best task, provide algorithms for its defining combination and marginalization operators and analyze its worst-case performance. An extension of the algorithm to the mini-bucket framework provides bounds for each of the m best solutions. Empirical demonstrations of the algorithms with emphasis on their potential for approximations are provided.
影响因子：
14.4
作者：
Aljazzar, Husain;Leue, Stefan
通讯作者：
Leue, Stefan