Learning DNF Expressions from Fourier Spectrum

By Vitaly Feldman. 2012

28 citations recorded by the source corpus.

Since its introduction by Valiant in 1984, PAC learning of DNF expressions remains one of the central problems in learning theory. We consider this problem in the setting where the underlying distribution is uniform, or more generally, a product distribution. Kalai, Samorodnitsky and Teng (2009) showed that in this setting a DNF expression can be efficiently approximated from its "heavy" low-degree Fourier coefficients alone. This is in contrast to previous approaches where boosting was used and thus Fourier coefficients of the target function modified by various distributions were needed. This property is crucial for learning of DNF expressions over smoothed product distributions, a learning model introduced by Kalai et al. (2009) and inspired by the seminal smoothed analysis model of Spielman and Teng (2001). We introduce a new approach to learning (or approximating) a polynomial threshold functions which is based on creating a function with range [-1,1] that approximately agrees with the unknown function on low-degree Fourier coefficients. We then describe conditions under which this is sufficient for learning polynomial threshold functions. Our approach yields a new, simple algorithm for approximating any polynomial-size DNF expression from its "heavy" low-degree Fourier coefficients alone. Our algorithm greatly simplifies the proof of learnability of DNF expressions over smoothed product distributions. We also describe an application of our algorithm to learning monotone DNF expressions over product distributions. Building on the work of Servedio (2001), we give an algorithm that runs in time $\poly((s \cdot \log{(s/\eps)})^{\log{(s/\eps)}}, n)$, where $s$ is the size of the target DNF expression and $\eps$ is the accuracy. This improves on $\poly((s \cdot \log{(ns/\eps)})^{\log{(s/\eps)} \cdot \log{(1/\eps)}}, n)$ bound of Servedio (2001).

Subfields: Artificial Intelligence

How researchers see this paper

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

In Artificial Intelligence

Citations in the corpus

Boolean Decision Rules via Column Generation (2018, background): “[47, 32, 24]) focuses on the ideal noiseless setting (sometimes allowing arbitrary queries) and is less relevant to the practice of learning compact models from noisy data.”
Or's of And's for Interpretable Classification, with Application to Context-Aware Recommender Systems (2015, background): “Valiant [45] showed that DNFs could be learned in polynomial time in the PAC (probably approximately correct) setting, and recent work has improved those bounds via polynomial threshold functions [23] and Fourier analysis [14].”
A Bayesian Framework for Learning Rule Sets for Interpretable Classification (2017, background): “In parallel, Valiant (1984) showed that DNFs could be learned in polynomial time in the PAC (probably approximately correct - non-noisy) setting, and recent work has improved those bounds via polynomial threshold functions (Klivans and Servedio, 2001) and Fourier analysis (Feldman, 2012).”
Learning Neural Networks with Two Nonlinear Layers in Polynomial Time (2017, methodology): “Feldman (2012) was the first to obtain a query-algorithm for PAC learning DNF formulas with respect to the uniform distribution that did not require a Boosting algorithm.”