Toward efficient agnostic learning

Michael J. Kearns, Robert E. Schapire, Linda M. Sellie

Research output: Chapter in Book/Report/Conference proceedingConference contribution

58 Scopus citations

Abstract

In this paper we initiate an investigation of generalizations of the Probably Approximately Correct (PAC) learning model that attempt to significantly weaken the target function assumptions. The ultimate goal in this direction is informally termed agnostic learning, in which we make virtually no assumptions on the target function. The name derives from the fact that as designers of learning algorithms, we give up the belief that Nature (as represented by the target function) has a simple or succinct explanation. We give a number of both positive and negative results that provide an initial outline of the possibilities for agnostic learning. Our results include hardness results for the most obvious generalization of the PAC model to an agnostic setting, an efficient and general agnostic learning method based on dynamic programming, relationships between loss functions for agnostic learning, and an algorithm for learning in a model for problems involving hidden variables.

Original languageEnglish (US)
Title of host publicationProceedings of the Fifth Annual ACM Workshop on Computational Learning Theory
PublisherPubl by ACM
Pages341-352
Number of pages12
ISBN (Print)089791497X, 9780897914970
DOIs
StatePublished - Jan 1 1992
Externally publishedYes
EventProceedings of the Fifth Annual ACM Workshop on Computational Learning Theory - Pittsburgh, PA, USA
Duration: Jul 27 1992Jul 29 1992

Publication series

NameProceedings of the Fifth Annual ACM Workshop on Computational Learning Theory

Other

OtherProceedings of the Fifth Annual ACM Workshop on Computational Learning Theory
CityPittsburgh, PA, USA
Period7/27/927/29/92

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Toward efficient agnostic learning'. Together they form a unique fingerprint.

  • Cite this

    Kearns, M. J., Schapire, R. E., & Sellie, L. M. (1992). Toward efficient agnostic learning. In Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory (pp. 341-352). (Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory). Publ by ACM. https://doi.org/10.1145/130385.130424