Uniform characterizations of polynomial-query learnabilities

作     者：Hayashi, Y Matsumoto, S Shinohara, A Takeda, M 

作者机构：Kyushu Univ 33 Dept Informat Fukuoka 8128581 Japan Tokai Univ Dept Math Sci Kanagawa 2591292 Japan 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2003年第292卷第2期

页      面：377-385页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：polynomial-query learning learning from examples concept learning 

摘      要：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 W using queries and the existence of a good query for any subset H of W 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. (C) 2002 Elsevier Science B.V. All rights reserved.