发帖
雷达卡
摘要翻译：
本文评价了贝叶斯网络中最佳优先搜索和/或搜索空间在求解最可能解释(MPE)任务时的能力。搜索空间的和/或表示的主要优点是它对问题结构的敏感性，这可以转化为显着的时间节省。近年来，深度优先和/或分支定界算法被证明在探索此类搜索空间时非常有效，尤其是在使用缓存时。由于已知最佳优先策略在内存利用时优于深度优先策略，因此需要探索最佳优先控制策略。本文的主要贡献在于证明了在贝叶斯网络中，AND/OR搜索算法从深度优先的分支定界到最佳优先的扩展确实是非常有效的。我们用经验证明了最佳优先搜索方法在各种概率网络上的优越性。
---
英文标题：
《Best-First AND/OR Search for Most Probable Explanations》
---
作者：
Radu Marinescu, Rina Dechter
---
最新提交年份：
2012
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要：
The paper evaluates the power of best-first search over AND/OR search spaces for solving the Most Probable Explanation (MPE) task in Bayesian networks. The main virtue of the AND/OR representation of the search space is its sensitivity to the structure of the problem, which can translate into significant time savings. In recent years depth-first AND/OR Branch-and- Bound algorithms were shown to be very effective when exploring such search spaces, especially when using caching. Since best-first strategies are known to be superior to depth-first when memory is utilized, exploring the best-first control strategy is called for. The main contribution of this paper is in showing that a recent extension of AND/OR search algorithms from depth-first Branch-and-Bound to best-first is indeed very effective for computing the MPE in Bayesian networks. We demonstrate empirically the superiority of the best-first search approach on various probabilistic networks.
---
PDF链接：
https://arxiv.org/pdf/1206.5268
京公网安备 11010802022788号
