Version spaces without boundary sets

Haym Hirsh, Nina Mishra, Leonard Pitt

Research output: Contribution to conferencePaperpeer-review


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.

Original languageEnglish (US)
Number of pages6
StatePublished - 1997
EventProceedings of the 1997 14th National Conference on Artificial Intelligence, AAAI 97 - Providence, RI, USA
Duration: Jul 27 1997Jul 31 1997


OtherProceedings of the 1997 14th National Conference on Artificial Intelligence, AAAI 97
CityProvidence, RI, USA

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence


Dive into the research topics of 'Version spaces without boundary sets'. Together they form a unique fingerprint.

Cite this