Explanation-Based Learning: Finding Better Explanations Via Partial Evaluation

控制搜索是人工智能的核心问题。在现实的规划、设计和推理问题中克服组合搜索需要大量的领域特定搜索控制知识。基于解释的学习（EBL）已经成为一种获取搜索控制知识的标准技术。以前的EBL工作已经产生了令人印象深刻的演示，但也发现了一个基本问题，EBL经常构建过于复杂的解释，从而产生无效的控制知识。本文提出了一种解决方案：将EBL与部分评价相结合，以改进EBL的解释。在标准的EBL系统中，问题解决者在训练示例上的行为决定了EBL解释什么以及如何解释。相反，部分评估执行全局分析，通常产生更简单和更一般的解释。在以前的工作中，STATIC（由PI编写的部分评估器）与PRODIGY/EBL（最先进的EBL系统）进行了竞争。当在PRODIGY/EBL的基准问题空间中进行测试时，STATIC生成的搜索控制知识的效率是PRODIGY/EBL的三倍，并且速度快了26到77倍。但是，由于STATIC的分析不是集中在训练示例上，因此在面对大型和复杂的问题空间时，它可能会陷入困境。PI打算设计并建立一个称为DYNAMIC的混合系统，它将克服这两种方法的弱点。DYNAMIC将像PRODIGY/EBL那样识别学习机会，但像STATIC那样生成解释。对这两个系统的详细研究表明，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? //