Theoretical Underpinnings of Version Spaces

Abstract

Mitchell's version-space approach to inductive concept learning has been highly influential in machine learning, as it formalizes inductive concept learning as a search problem-to identify some concept definition out of a space of possible definitions. This paper lays out some theoretical underpinnings of version spaces. It presents the conditions under which an arbitrary set of concept definitions in a concept description language can be represented by boundary sets, which is a necessary condition for a set of concept definitions to be a version space. Furthermore, although version spaces can be intersected and unioned (version spaces are simply sets, albeit with special structure), the result need not be a version space; this paper also presents the conditions under which such intersection and union of two version spaces yields a version space (i.e., representable by boundary sets). Finally, the paper shows how the resulting boundary sets after intersections and unions can be computed from the initial boundary sets, and proves the algorithms correct.