2002 · 57 citations · 38 references
ComputingComputer ScienceMachine LearningNatural Language ProcessingDeep LearningPattern RecognitionRepresentation Learning
We present a membership-query algorithm for efficiently learning DNF with respect to the uniform distribution. In fact, the algorithm properly learns the more general class of functions that are computable as a majority of polynomially-many parity functions. We also describe extensions of this algorithm for learning DNF over certain nonuniform distributions and from noisy examples as well as for learning a class of geometric concepts that generalizes DNF. The algorithm utilizes one of Freund's boosting techniques and relies on the fact that boosting does not require a completely distribution-independent weak learner. The boosted weak learner is a nonuniform extension of a Fourier-based algorithm due to Kushilevitz and Mansour (1991).< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
38
Leslie G. Valiant · 1984 · 4.2K citations
The Strength of Weak Learnability
Robert E. Schapire · Machine Learning · 1990 · 3.3K citations · Full text
Leslie G. Valiant · Communications of the ACM · 1984 · 3.3K citations · Full text
The strength of weak learnability
Robert E. Schapire · Machine Learning · 1990 · 2.5K citations · Full text