An efficient membership-query algorithm for learning DNF with respect to the uniform distribution

By Jeffrey C. Jackson. 1994

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

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Stealing Machine Learning Models via Prediction APIs (2016, background): “Our setting thus differs from traditional learning-theory settings [3,7,8,15,30,33,36,53] that assume only membership queries, outputs consisting of a class label only.”
Learning DNF Expressions from Fourier Spectrum (2012, methodology): “Such an algorithm is necessary since, in the boosting-based approach of Jackson (1997), the weak learner needs to learn with respect to distributions which depend on previous weak hypotheses.”
Learning DNF in time 2 Õ(n 1/3 ) . (2001, background): “[8, 9, 21, 23, 24, 26, 27, 32, 37, 38]), the di culty of the unrestricted DNF learning problem is evidenced by the fact that, prior to the current work, only two algorithms were known which improve on the naive 2n time bound [11, 35].”
Agnostically learning halfspaces (2005, methodology): “The approach that establishes Theorem 10 is similar to Jackson’s Harmonic Sieve [15]: we apply a boosting algorithm, using the polynomial regression algorithm at each stage to identify a low-degree polynomial which, after thresholding, has advantage at least Ω(1/k) on the target function.”
Learning Neural Networks with Two Nonlinear Layers in Polynomial Time (2017, background): “The main application of KMtron is a generalization of celebrated results for PAC learning DNF formulas (Jackson (1997)) to the setting of probabilistic concepts.”
Pseudorandom Functions: Three Decades Later (2017, background): “PRFs cannot be implemented by polynomial-size formulas in disjunctive normal form (DNF), as these can be learned efficiently (under the uniform distribution) by Jackson’s harmonic sieve algorithm [81].”
Hardness results for agnostically learning low-degree polynomial threshold functions (2010, background): “[21] and its variants [12, 22], including some algorithms for distributionspecific agnostic learning [14, 20, 3, 6].”
Boosting and Hard-Core Set Construction (2003, methodology): “The main result of Jackson (1997) is the following theorem:”
On Agnostic Learning of Parities, Monomials, and Halfspaces (2009, methodology): “Jackson [ Jac97 ] proved that DNFs are learnable under the uniform distribution if the learning algorithm is allowed to ask membership queries.”
Learning and Smoothed Analysis (2009, unknown): “In a stronger interactive model, Jackson [6] showed how to learn DNFs over product distributions using membership queries, black-box evaluations of the target function f at polynomially many arbitrary inputs x, chosen by the algorithm.”
Agnostic active learning (2006, background): “The membership-query setting (Angluin, 1998; An-gluin, 2001; Bshouty & Eiron, 2002; Jackson, 1997) is similar to active learning considered here except that no unlabeled data is given.”