An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
Jeffrey C. Jackson · 2002
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).>