Toward efficient agnostic learning
Published 1 July 1992Open access
Michael Kearns, Robert E. Schapire, Linda Sellie
Citations347
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
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.
Keywords
Computer Science
Pattern classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
Springer series in statisticsProbability Inequalities for sums of Bounded Random Variables
6,947 Citations1994Wassily Hoeffding
A theory of the learnable
4,242 Citations1984Leslie G. Valiant
This paper regards learning as the phenomenon of knowledge acquisition in the absence of explicit programming, and gives a precise methodology for studying this phenomenon from a computational viewpoint.
Machine LearningThe Strength of Weak Learnability
3,293 Citations1990Robert E. Schapire
In this paper, a method is described for converting a weak learning algorithm into one that achieves arbitrarily high accuracy, and it is shown that these two notions of learnability are equivalent.
Communications of the ACMA theory of the learnable
3,268 Citations1984Leslie G. Valiant
This paper regards learning as the phenomenon of knowledge acquisition in the absence of explicit programming, and gives a precise methodology for studying this phenomenon from a computational viewpoint.
Information science and statisticsEstimation of Dependences Based on Empirical Data
2,238 Citations2006Vladimir Vapnik
Journal of the ACMLearnability and the Vapnik-Chervonenkis dimension
1,852 Citations1989Anselm Blumer, Andrzej Ehrenfeucht +2 more
This paper shows that the essential condition for distribution-free learnability is finiteness of the Vapnik-Chervonenkis dimension, a simple combinatorial parameter of the class of concepts to be learned.
Neural ComputationLearning in Artificial Neural Networks: A Statistical Perspective
922 Citations1989Halbert White
Concepts and analytical results from the literatures of mathematical statistics, econometrics, systems identification, and optimization theory relevant to the analysis of learning in artificial neural networks are reviewed.
Information and ComputationDecision theoretic generalizations of the PAC model for neural net and other learning applications
871 Citations1992David Haussler
Theorems on the uniform convergence of empirical loss estimates to true expected loss rates for certain hypothesis spaces H are given, and it is shown how this implies learnability with bounded sample size, disregarding computational complexity.
Journal of the ACMCryptographic limitations on learning Boolean formulae and finite automata
744 Citations1994Michael Kearns, Leslie G. Valiant
It is proved that a polynomial-time learning algorithm for Boolean formulae, deterministic finite automata or constant-depth threshold circuits would have dramatic consequences for cryptography and number theory and is applied to obtain strong intractability results for approximating a generalization of graph coloring.
Journal of the ACMConstant depth circuits, Fourier transform, and learnability
585 Citations1993Nathan Linial, Yishay Mansour +1 more
An O(n/sup polylog(/ /sup sup)/ /sup (n)/)-time algorithm for learning functions in AC/sup O/ is obtained and derives a good approximation for the Fourier transform of the function.
Journal of the ACMComputational limitations on learning from examples
532 Citations1988Leonard Pitt, Leslie G. Valiant
It is shown for various classes of concept representations that these cannot be learned feasibly in a distribution-free sense unless R = NP, and relationships between learning of heuristics and finding approximate solutions to NP-hard optimization problems are given.
Journal of the American Statistical AssociationRecent Developments in Nonparametric Density Estimation
471 Citations1991Alan Julian Izenman
A method of multivariate density estimation that did not spring from a univariate generalization is described, namely, projection pursuit density estimation, in which both dimensionality reduction and density estimation can be pursued at the same time.
Journal of Computer and System SciencesEfficient distribution-free learning of probabilistic concepts
377 Citations1994Michael Kearns, Robert E. Schapire
SIAM Journal on ComputingLearning in the Presence of Malicious Errors
350 Citations1993Michael Kearns, Ming Li
On the learnability of Boolean formulae
293 Citations1987Michael Kearns, M. Li +2 more
The goals are to prove results and develop general techniques that shed light on the boundary between the classes of expressions that are learnable in polynomial time and those that are apparently not, and to employ the distribution-free model of learning.
Journal of the American Statistical AssociationReview Papers: Recent Developments in Nonparametric Density Estimation
283 Citations1991Alan Julian Izenman
The early density estimation methods, such as the histogram, kernel estimators, and orthogonal series estimators are still very popular, and recent research on them is described, as well as different types of restricted maximum likelihood density estimators.
Crytographic limitations on learning Boolean formulae and finite automata
273 Citations1989Michael Kearns, Leslie G. Valiant
It is proved that for Boolean formulae, finite automata, and constant depth threshold circuits (simplified neural nets), this problem is computationally as difficult as the quadratic residue problem, inverting the RSA function and factoring Blum integers.
Learning disjunction of conjunctions
167 Citations1985Leslie G. Valiant
Positive results are shown for significant subclasses that allow not only propositional predicates but also some relations and under certain restrictions on these subclasses the learning algorithms are well suited to implementation on neural networks of threshold elements.
Machine LearningTracking Drifting Concepts By Minimizing Disagreements
146 Citations1994David P. Helmbold, Philip M. Long
Constant depth circuits, Fourier transform, and learnability
134 Citations1989Nathan Linial, Yishay Mansour +1 more
Learning in the presence of malicious errors
128 Citations1988Michael Kearns, Ming Li
General methods for bounding the rate of error tolerable by any learning algorithm, efficient algorithms tolerating nontrivial rates of malicious errors, and equivalences between problems of learning with errors and standard combinatorial optimization problems are studied.
IEEE Transactions on Information TheoryDensity estimation by stochastic complexity
115 Citations1992J. Rissanen, Terence P. Speed +1 more
Two theoresms are proved, which together extend the universal coding theorems to a large class of data generating densities and give an asymptotic upper bound for the code redundancy in the order of magnitude, achieved with a special predictive type of histogram estimator, which sharpens a related bound.
Conference on Learning TheoryA learning criterion for stochastic rules
85 Citations1990Kenji Yamanishi
An improved boosting algorithm and its implications on learning complexity
66 Citations1992Yoav Freund
The main result is an improvement of the boosting-by-majority algorithm, which shows that the majority rule is the optimal rule for combining general weak learners and extends the boosting algorithm to concept classes that give multi-valued labels and real-valuedlabel.
A Markovian extension of Valiant's learning model
32 Citations2002David Aldous, Umesh Vazirani
A model of learning that expands on the Valiant model is introduced, and the learner is placed in a Markovian environment where the examples reside on the vertices of the graph, one example on each vertex.
Learning switching concepts
29 Citations1992Avrim Blum, Prasad Chalasani
This work considers learning in situations where the function used to classify examples may switch back and forth between a small number of different concepts during the course of learning, and describes a randomized query algorithm for such adversarial switches between two monotone disjunctions.
Conference on Learning TheoryTracking drifting concepts using random examples
25 Citations1991David P. Helmbold, Philip M. Long