Using Determinations in EBL: A Solution to the Incomplete Theory Problem

Abstract

This paper proposes a solution to the incomplete theory problem[3] for the case when the domain theory contains determinations, a form of incomplete knowledge[1]. We weaken the requirement made in explanation-based learning (EBL) that the learning procedure return an operational description that implies the target concept, to computing an operational description that determines the concept. The fact that the training example is an instance of the target concept is assumed (rather than proved), and used to complete missing information in the domain theory. A key assumption made by this approach is that the incompleteness of the domain theory is restricted to determinations, and that a neccessary and sufficient definition of the target concept exists. We discuss how this can be approximated in horn theories by making the closed world assumption. We present a prototype implementation of our solution using a PROLOG-based implementation of EBL, and illustrate how it can incrementally refine an incomplete theory using training examples.