Efficient distribution-free learning of probabilistic concepts

Michael J. Kearns, Robert E. Schapire

Research output: Contribution to journalArticlepeer-review

197 Scopus citations


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
Issue number3
StatePublished - Jun 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


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

Cite this