Version spaces and the consistency problem
| Autor: | Nina Mishra, Leonard Pitt, Haym Hirsh |
|---|---|
| Rok vydání: | 2004 |
| Předmět: |
Discrete mathematics
Linguistics and Language Efficient algorithm Consistency problem Version space Boundary (topology) 0102 computer and information sciences 02 engineering and technology Inductive learning 01 natural sciences Language and Linguistics Set (abstract data type) Monotone polygon 010201 computation theory & mathematics Artificial Intelligence If and only if Simple (abstract algebra) Boundary sets 0202 electrical engineering electronic engineering information engineering Version spaces 020201 artificial intelligence & image processing Mathematics |
| Zdroj: | Artificial Intelligence. 156:115-138 |
| ISSN: | 0004-3702 |
| DOI: | 10.1016/j.artint.2003.04.003 |
| Popis: | A version space is a collection of concepts consistent with a given set of positive and negative examples. Mitchell [Artificial Intelligence 18 (1982) 203–226] proposed representing a version space by its boundary sets: the maximally general (G) and maximally specific consistent concepts (S). For many simple concept classes, the size of G and S is known to grow exponentially in the number of positive and negative examples. This paper argues that previous work on alternative representations of version spaces has disguised the real question underlying version space reasoning. We instead show that tractable reasoning with version spaces turns out to depend on the consistency problem, i.e., determining if there is any concept consistent with a set of positive and negative examples. Indeed, we show that tractable version space reasoning is possible if and only if there is an efficient algorithm for the consistency problem. Our observations give rise to new concept classes for which tractable version space reasoning is now possible, e.g., 1-decision lists, monotone depth two formulas, and halfspaces. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect