Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Uniform Characterizations of Polynomial-Query Learnabilities
| Book Series | Lecture Notes in Computer Science |
| Publisher | Springer Berlin / Heidelberg |
| ISSN | 0302-9743 (Print) 1611-3349 (Online) |
| Volume | Volume 1532/1998 |
| Book | Discovey Science |
| DOI | 10.1007/3-540-49292-5 |
| Copyright | 1998 |
| ISBN | 978-3-540-65390-5 |
| DOI | 10.1007/3-540-49292-5_8 |
| Page | 571 |
| Subject Collection | Computer Science |
| SpringerLink Date | Thursday, January 01, 1998 |
| |
|
Uniform Characterizations of Polynomial-Query Learnabilities
Yosuke Hayashi3 , Satoshi Matsumoto4 , Ayumi Shinohara3 and Masayuki Takeda3 
| (3) |
Department of Informatics, Kyushu University 33, Fukuoka 812-8581, Japan |
| (4) |
Faculty of Science, Tokai University, Kanagawa 259-1291, Japan |
Abstract
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
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|