Learning the Fourier spectrum of probabilistic lists and trees
William A. Aiello, Milena Mihail · 1991
method of learning boolean concepts (under uni-form sampling distribution) by reconstructing their Fourier represent ation [LMN89] extends when the concepts are probabilistic in the sense of Kearns and Shapire [KS90]. We show that probabilistic decision lists, and more generally probabilistic decision trees with at most one occurrence of each literal, can be approx-imate ed by polynomially small Fourier represent a-tions, and that the non-negligible Fourier coeffi-cients can be efficiently identified and estimated. Hence, all such concepts are learnable in polynomial time under uniform sampling distribution. This is the first instance where Fourier methods result in polynomial learning algorithms: the polynomiality of our results should be contrasted to the np”lylogn complexities in the analogous cases of [LMN89] and [M90]. The new ingredient of our work that allows us to achieve this polynomiality is that via refined Fourier analysis we are able to isolate the polynomi-ally small set of non-negligible Fourier coefficients that reside in a super-polynomially large area of the spectrum. We further observe that several more gen-eral concept classes have slightly super-polynomial (npolyk)gn) learning algorithms. These classes include all polynomial-size probabilistic decision trees, their convex combinations, etc. A concrete special case which results in polynomial learnabil-