Donald Bren School of Information and Computer Sciences

This dissertation addresses the problem of theory revision in machine learning. The task requires the learner to minimally revise an initial incorrect theory such that the revised theory explains a given set of training data. A learning system, A3, is presented that solves this task.

The main contributions of this dissertation include the learning system A3 that can revise theories containing multiple concepts expressed as function-free first-order Horn clauses, an approach to repairing theories containing negation, and the introduction of a distance metric between theories to evaluate the degree of revision performed. Experimental evidence is presented that demonstrates A3's ability to solve the theory revision task.

Assumptions commonly made by other approaches to theory revision such as whether a theory needs to be generalized or specialized with respect to misclassified examples are shown to be incorrect for theories containing negation. A3 is able to repair theories containing negation and demonstrates a simple, general approach to identifying types of errors in a theory using a single mechanism for handling positive and negative examples as well as examples of multiple concepts.

The syntactic distance between two theories is proposed as an evaluation metric for theory revision systems. This distance is defined in terms of the minimum number of edit operations required to transform one theory into another. This allows for a precise measurement of how much a theory has been revised and allows for comparison of different systems' abilities to perform minimal revisions. This distance metric is also used by A3 in order to bias it towards finding minimal revisions that accurately explain the data.

The distance metric also leads to insights about the theory revision task. In particular, it is shown that the theory revision task is underconstrained if the additional goal of learning a particular correct theory is to be met. Without additional constraints, there are potentially many accurate revisions that are far apart syntactically. It is shown that providing examples of multiple concepts in the theory can provide some of these constraints.