Version Spaces Without Boundary Sets

Abstract

This paper shows that it is not necessary to maintain boundary sets to reason using version spaces. Rather, most of the operations typically performed on version spaces for a concept class can be tractably executed directly on the training data, as long as it is tractable to solve the consistency problem for that concept class -- to determine whether there exists any concept in the concept class that correctly classifies the data. The equivalence of version-space learning to the consistency problem bridges a gap between empirical and theoretical approaches to machine learning, since the consistency problem is already known to be critical to learning in the PAC (Probably Approximately Correct) sense. By exhibiting this link to the consistency problem, we broaden the class of problems to which version spaces can be applied to include concept classes where boundary sets can have exponential or infinite size and cases where boundary sets are not even well defined.