1984 ATheoryoftheLearnable

(Valiant, 1984) ⇒ Leslie Valiant. (1984). “A Theory of the Learnable.” In: Communications of the ACM Journal, 27(11). doi:10.1145/1968.1972

Subject Headings:

Notes

Co-Cited With

http://citeseerx.ist.psu.edu/viewdoc/similar?doi=10.1.1.135.9814&type=cc

(Blumer et al., 1989) ⇒ A. Blumer, A. Ehrenfeucht, D. Haussler, Warmuth. (1989). “M.: Learnability and the vapnik-chervonenkis dimension"
The strength of weak learnability – Robert E. Schapire - 1990
Estimation of Dependencies Based on Empirical Data – V. Vapnik - 1982
Induction of Decision Trees – J. R. Quinlan - 1986

Cited By

Quotes

Abstract

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.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
1984 ATheoryoftheLearnable	Leslie G. Valiant			A Theory of the Learnable				10.1145/1968.1972		1984