6533b7d7fe1ef96bd1267c1f
RESEARCH PRODUCT
On the Intrinsic Complexity of Learning
Rusins FreivaldsEfim KinberCarl Smithsubject
HierarchyTheoretical computer scienceBasis (linear algebra)business.industryMachine learningcomputer.software_genreComputer Science ApplicationsTheoretical Computer ScienceReduction (complexity)Computational Theory and MathematicsCompleteness (order theory)Concept learningRecursive functionsNatural (music)Artificial intelligencebusinesscomputerInformation SystemsMathematicsdescription
AbstractA new view of learning is presented. The basis of this view is a natural notion of reduction. We prove completeness and relative difficulty results. An infinite hierarchy of intrinsically more and more difficult to learn concepts is presented. Our results indicate that the complexity notion captured by our new notion of reduction differs dramatically from the traditional studies of the complexity of the algorithms performing learning tasks.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1995-11-01 | Information and Computation |