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.
My Menu
Saved Items

Uniform Characterizations of Polynomial-Query Learnabilities

Yosuke HayashiContact Information, Satoshi MatsumotoContact Information, Ayumi ShinoharaContact Information and Masayuki TakedaContact Information

(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

Contact Information Yosuke Hayashi
Email: yosuke@i.kyushu-u.ac.jp

Contact Information Satoshi Matsumoto
Email: matumoto@ss.u-tokai.ac.jp

Contact Information Ayumi Shinohara
Email: ayumi@i.kyushu-u.ac.jp

Contact Information Masayuki Takeda
Email: takeda@i.kyushu-u.ac.jp
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.106 • Server: mpweb17
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)