Incremental version-space merging: A general framework for concept learning

The problem of concept learning--forming general rules from classified cases--has received much attention in artificial intelligence. Version spaces (Mitchell, 1978) provide one approach to this problem. A version space is the set of all concept definitions in a prespecified language that correctly classify training data (the positive and negative examples of the unknown concept). Although a landmark development, the version-space approach is fundamentally limited in its underlying assumption that the desired concept definition will be consistent with all the given data. This dissertation presents a general framework for concept learning based on a generalized form of version spaces that removes its assumption of strict consistency with data.;The first contribution of this work is the generalized version-space framework, which is shown to have firm theoretical underpinnings. Central to the framework is incremental version-space merging, an incremental learning method based on version-space intersection and implemented in the program IVSM. The generality of the learning method is demonstrated by its use on four very different learning tasks; two of these applications of incremental version-space merging stand as contributions in their own right.;The first application is the use of incremental version-space merging to solve the open problem of learning from inconsistent data in a computationally feasible manner using version spaces. The approach presented here succeeds in this task by identifying and addressing a subclass of the problem called "bounded inconsistency," which occurs when every nonrepresentative example has a neighboring example that is representative. The general approach is to form version spaces containing all concept definitions consistent with an instance or one of its neighbors. A larger number of concept definitions are kept in consideration to lessen the chance of removing the desired one.;The second application is the use of incremental version-space merging to combine empirical and analytical learning, solving problems they each have when used in isolation. The central idea is to apply explanation-based generalization to training data and form version spaces consistent with the generalized data. Incremental version-space merging is then used on the resulting version spaces. The result is a learning technique that exhibits behavior along a spectrum from knowledge-free to knowledge-rich learning.