TY - GEN
T1 - Uniform characterizations of Polynomial-Query learnabilities
AU - Hayashi, Yosuke
AU - Matsumoto, Satoshi
AU - Shinohara, Ayumi
AU - Takeda, Masayuki
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1998.
PY - 1998
Y1 - 1998
N2 - We consider the exact learning in the query model. We deal with all types of queries introduced by Angluin: membership, equivalence, superset, subset, disjointness and exhaustiveness queries, and their weak (or restricted) versions where no counterexample is returned. For each of all possible combinations of these queries, we uniformly give complete characterizations of boolean concept classes that are learnable using a polynomial number of polynomial sized queries. Our characterizations show the equivalence between the learnability of a concept class C using queries and the existence of a good query for any subset H of C which is guaranteed to reject a certain fraction of candidate concepts in H regardless of the answer. As a special case for equivalence queries alone, our characterizations directly correspond to the lack of the approximate fingerprint property, which is known to be a sufficient and necessary condition for the learnability using equivalence queries.
AB - We consider the exact learning in the query model. We deal with all types of queries introduced by Angluin: membership, equivalence, superset, subset, disjointness and exhaustiveness queries, and their weak (or restricted) versions where no counterexample is returned. For each of all possible combinations of these queries, we uniformly give complete characterizations of boolean concept classes that are learnable using a polynomial number of polynomial sized queries. Our characterizations show the equivalence between the learnability of a concept class C using queries and the existence of a good query for any subset H of C which is guaranteed to reject a certain fraction of candidate concepts in H regardless of the answer. As a special case for equivalence queries alone, our characterizations directly correspond to the lack of the approximate fingerprint property, which is known to be a sufficient and necessary condition for the learnability using equivalence queries.
UR - http://www.scopus.com/inward/record.url?scp=84949211417&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84949211417&partnerID=8YFLogxK
U2 - 10.1007/3-540-49292-5_8
DO - 10.1007/3-540-49292-5_8
M3 - Conference contribution
AN - SCOPUS:84949211417
SN - 3540653902
SN - 9783540653905
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 84
EP - 92
BT - Discovery Science - 1st International Conference, DS 1998, Proceedings
A2 - Arikawa, Setsuo
A2 - Motoda, Hiroshi
PB - Springer Verlag
T2 - 1st International Conference on Discovery Science, DS 1998
Y2 - 14 December 1998 through 16 December 1998
ER -