Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0587.68077
Valiant, L.G.
A theory of the learnable. (English)
[J] Commun. ACM 27, 1134-1142 (1984). ISSN 0001-0782

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, learning protocol, and exploring the class of concepts that can be learned using it in a reasonable (polynomial) number of steps. Although inherent algorithmic complexity appears to set serious limits to the range of concepts that can be learned, we show that there are some important nontrivial classes of propositional concepts that can be learned in a realistic sense.

MSC 2000:: *68T05 Learning and adaptive systems

Keywords: learning; knowledge acquisition in the absence of explicit programming; information gathering

Cited in: Zbl 1181.68192 Zbl 0968.68126 Zbl 0870.68061 Zbl 0898.68066 Zbl 0872.93075 Zbl 0870.94021 Zbl 0789.92002 Zbl 0789.68118 Zbl 0764.68139 Zbl 0766.68116 Zbl 0761.68082 Zbl 0761.68080 Zbl 0747.68041 Zbl 0747.68050 Zbl 0678.68084 Zbl 0659.68072 Zbl 0649.68080 Zbl 0649.68067 Zbl 0653.68084 Zbl 0635.68096

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]