Name
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. |
Year | Venue | Keywords |
|---|---|---|
1997 | AAAI/IAAI | concept class,infinite size,training data,theoretical approach,version space,consistency problem,machine learning,consistency problem bridge,boundary set |
Field | DocType | ISBN |
Training set,Mathematical optimization,Well-defined,Exponential function,Probably approximately correct learning,Existential quantification,Concept class,Algebra,Computer science,Equivalence (measure theory) | Conference | 0-262-51095-2 |
Citations | PageRank | References |
20 | 1.38 | 22 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Haym Hirsh | 1 | 1839 | 277.74 |
| Nina Mishra | 2 | 1205 | 72.58 |
| Leonard Pitt | 3 | 52 | 4.54 |