Learnability and Automatizability
Authors:
- 23 December 2004
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 621-630
Abstract
We consider the complexity of properly learning concept classes, i.e. when the learner must output a hypothesis of the same form as the unknown concept. We present the following upper and lower bounds on well-known concept classes: 1) We show that unless NP = RP, there is no polynomial-time PAC learning algorithm for DNF formulae where the hypothesis is an OR-of-thresholds. Note that as special cases, we show that neither DNF nor OR-of-thresholds are properly learnable unless NP = RP. Previous hardness results have required strong restrictions on the size of the output DNF formula. We also prove that it is NP-hard to learn the intersection of /spl lscr/ /spl ges/ 2 halfspaces by the intersection of k halfspaces for any constant k > 0. Previous work held for the case when k = /spl lscr/; 2) Assuming that NP /spl nsube/ DTIME(2/sup n/spl epsi//) for a certain constant /spl epsiv/ < 1 we show that it is not possible to learn size s decision trees by size s/sup k/ decision trees for any k /spl ges/ 0. Previous hardness results for learning decision trees held for k /spl les/ 2; 3) We present the first nontrivial upper bounds on properly learning DNF formulae and decision trees. In particular we show how to learn size s DNF by DNF in time 2/sup O~/(/spl radic/(n log s)), and how to learn size s decision trees by decision trees in time n/sup O(log s)/. The hardness results for DNF formulae and intersections of halfspaces are obtained via specialized graph products for amplifying the hardness of approximating the chromatic number as well as applying work on the hardness of approximate hypergraph coloring. The hardness results for decision trees, as well as the upper bounds, are obtained by developing a connection between automatizability in proof complexity and learnability, which may have other applications.Keywords
This publication has 28 references indexed in Scilit:
- Hardness results for neural network approximation problemsTheoretical Computer Science, 2002
- Lower bounds for cutting planes proofs with small coefficientsThe Journal of Symbolic Logic, 1997
- A subexponential exact learning algorithm for DNF using equivalence queriesInformation Processing Letters, 1996
- Cryptographic limitations on learning Boolean formulae and finite automataJournal of the ACM, 1994
- Training a 3-node neural network is NP-completeNeural Networks, 1992
- Learning decision trees from random examplesInformation and Computation, 1989
- Computational limitations on learning from examplesJournal of the ACM, 1988
- Occam's RazorInformation Processing Letters, 1987
- A theory of the learnableCommunications of the ACM, 1984
- Complexity of automaton identification from given dataInformation and Control, 1978