A theory of the learnable
A theory of the learnable
复制标题
DOI：
10.1145/800057.808710
复制
发表时间：
1984-11
期刊：
影响因子：
--
通讯作者：
L. Valiant
中科院分区：
文献类型：
--
作者：
L. Valiant
人类似乎能够学习新的概念，而不需要在任何传统意义上明确编程。在本文中，我们认为学习是在没有明确规划的情况下获得知识的现象。我们给出了一个精确的方法，从计算的角度来研究这种现象。它包括选择一个适当的信息收集机制，学习协议，并探索类的概念，可以学习使用它在一个合理的（多项式）的步骤。我们发现，固有的算法的复杂性似乎设置了严重的限制，可以这样学习的概念的范围。的方法和结果提出了具体的原则，设计现实的学习系统。
Humans appear to be able to learn new concepts without needing to be programmed explicitly in any conventional sense. In this paper we regard learning as the phenomenon of knowledge acquisition in the absence of explicit programming. We give a precise methodology for studying this phenomenon from a computational viewpoint. It consists of choosing an appropriate information gathering mechanism, the learning protocol, and exploring the class of concepts that can be learnt using it in a reasonable (polynomial) number of steps. We find that inherent algorithmic complexity appears to set serious limits to the range of concepts that can be so learnt. The methodology and results suggest concrete principles for designing realistic learning systems.