Explanation-Based Learning: Finding Better Explanations Via Partial Evaluation

控制搜索是人工智能的核心问题。在现实的规划、设计和推理问题中克服组合搜索需要大量的领域特定搜索控制知识。基于解释的学习(EBL)已经成为获取搜索控制知识的标准技术。以前的EBL工作已经产生了令人印象深刻的示范，但也揭示了一个根本问题EBL经常构建过于复杂的解释，从而产生无效的控制知识。本研究描述了一种解决方案：将EBL与部分评估相结合，以提高EBL的解释能力。在标准的EBL系统中，问题解决者在训练实例上的行为决定了EBL解释什么以及如何解释。相比之下，局部评估执行的是全局分析，通常会产生更简单、更笼统的解释。在以前的工作中，Static(由PI编写的部分赋值器)与最先进的EBL系统Prodigy/EBL进行了竞争。当在Prodigy/EBL的基准问题空间中测试时，Static生成的搜索控制知识的有效性是Prodigy/EBL的三倍，并且速度快26到77倍。然而，由于静态分析不以训练实例为重点，在面对庞大而复杂的问题空间时，它可能会步履蹒跚。PI打算设计和构建一种名为Dynamic的混合系统，该系统将克服这两种方法的弱点。Dynamic将像神童/EBL一样识别学习机会，但会像静态一样产生解释。对这两个系统的详细研究表明，Dynamic将显著超过这两个系统，并在两个基本问题上产生见解：如何改进机器生成的解释，以及训练示例在基于解释的学习中的适当角色是什么？

Controlling search is a central concern for AI. Overcoming combinatorial search in realistic planning, design, and reasoning problems requires large doses of domain specific search control knowledge. Explanation Based Learning (EBL) has emerged as a standard technique for acquiring search control knowledge. Previous EBL work has produced impressive demonstrations but has also uncovered a fundamental problem EBL frequently constructs overlycomplex explanations that yield ineffective control knowledge. This research describes a solution: integrating EBL with partial evaluation to improve EBL's explanations. In standard EBL systems, the problem solver's behavior on a training example determines what EBL explains and how. Partial evaluation, in contrast, performs a global analysis that often yields simpler and more general explanations. In previous work, STATIC (a partial evaluator written by the PI) was pitted against PRODIGY/EBL, a state of the art EBL system. When tested in PRODIGY/EBL's benchmark problem spaces, STATIC generated search control knowledge that was up to three times a effective as PRODIGY/EBL's, and did so twenty six to seventy seven times faster. Since STATIC's analysis in not focused by training examples, however, it may flounder when confronted with large and complex problem spaces. The PI intends to design and build a hybrid system , called DYNAMIC, that will overcome the weaknesses of both approaches. DYNAMIC will identify learning opportunities a la PRODIGY/EBL, BUT GENERATE EXPLANATIONS a la STATIC. The detailed studies of the two systems suggest that DYNAMIC will significantly out perform both, and yield insights in two fundamental questions: how to improve machine generated explanations, and what is the appropriate role of training examples in explanation based learning? //