TY - GEN

T1 - Toward efficient agnostic learning

AU - Kearns, Michael J.

AU - Schapire, Robert E.

AU - Sellie, Linda M.

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 1992

Y1 - 1992

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0026965935&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026965935&partnerID=8YFLogxK

U2 - 10.1145/130385.130424

DO - 10.1145/130385.130424

M3 - Conference contribution

AN - SCOPUS:0026965935

SN - 089791497X

SN - 9780897914970

T3 - Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory

SP - 341

EP - 352

BT - Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory

PB - Publ by ACM

T2 - Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory

Y2 - 27 July 1992 through 29 July 1992

ER -