Efficient distribution-free learning of probabilistic concepts

Michael J. Kearns, Robert E. Schapire

Research output: Contribution to journalArticle

148 Scopus citations

Abstract

In this paper we investigate a new formal model of machine learning in which the concept (Boolean function) to be learned may exhibit uncertain or probabilistic behavior-thus, the same input may sometimes be classified as a positive example and sometimes as a negative example. Such probabilistic concepts (or p-concepts) may arise in situations such as weather prediction, where the measured variables and their accuracy are insufficient to determine the outcome with certainty. We adopt from the Valiant model of learining [28] the demands that learning algorithms be efficient and general in the sense that they perform well for a wide class of p-concepts and for any distribution over the domain. In addition to giving many efficient algorithms for learning natural classes of p-concepts, we study and develop in detail an underlying theory of learning p-concepts.

Original languageEnglish (US)
Pages (from-to)464-497
Number of pages34
JournalJournal of Computer and System Sciences
Volume48
Issue number3
DOIs
StatePublished - Jun 1994

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Efficient distribution-free learning of probabilistic concepts'. Together they form a unique fingerprint.

Cite this