TY - JOUR
T1 - Version spaces and the consistency problem
AU - Hirsh, Haym
AU - Mishra, Nina
AU - Pitt, Leonard
N1 - Funding Information:
✩ This paper expands and updates the results presented by Hirsh, Mishra, and Pitt (1997). * Corresponding author. E-mail addresses: [email protected] (H. Hirsh), [email protected] (N. Mishra), [email protected] (L. Pitt). 1 Supported in part by NSF Grant IRI-9209795. 2 Supported in part by NSF Grant EIA-0137761. 3 Supported in part by NSF Grant IIS-9907483.
PY - 2004/7
Y1 - 2004/7
N2 - 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.
AB - 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.
KW - Boundary sets
KW - Consistency problem
KW - Inductive learning
KW - Version spaces
UR - http://www.scopus.com/inward/record.url?scp=2442676919&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=2442676919&partnerID=8YFLogxK
U2 - 10.1016/j.artint.2003.04.003
DO - 10.1016/j.artint.2003.04.003
M3 - Article
AN - SCOPUS:2442676919
SN - 0004-3702
VL - 156
SP - 115
EP - 138
JO - Artificial Intelligence
JF - Artificial Intelligence
IS - 2
ER -