期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2002
卷号：2002
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We study the proper learnability of axis parallel concept classes in the PAC learning model and in the exact learning model with membership and equivalence queries. These classes include union of boxes, DNF, decision trees and multivariate polynomials. For the {\it constant} dimensional axis parallel concepts C we show that the following problems have the same time complexity \begin{enumerate} \item C is -properly exactly learnable (with hypotheses of size at most times the target size) from membership and equivalence queries. \item C is -properly PAC learnable (without membership queries) under any product distribution. \item There is an -approximation algorithm for the \MinEqui C problem. (given a g C find a minimal size f C that is equivalent to g ). \end{enumerate} In particular, C is -properly learnable in polynomial time from membership and equivalence queries {\bf if and only if} C is -properly PAC learnable in polynomial time under the product distribution {\bf if and only if} \MinEqui C has a polynomial time -approximation algorithm. Using this result we give the first proper learning algorithm of decision trees over the constant dimensional domain and the first negative results in proper learning from membership and equivalence queries for many classes. For the non-constant dimensional axis parallel concepts we show that with the equivalence oracle (1) ( 3) . We use this to show that (binary) decision trees are not properly learnable in polynomial time (assuming P = NP) and DNF is not s -properly learnable ( 1 ) in polynomial time even with an NP-oracle (assuming p 2 = P N P ).
-properly exactly learnable (with hypotheses of size at most 
