Learning Decision Trees Using the Fourier Spectrum

This work gives a polynomial time algorithm for learning decision trees with respect to the uniform distribution. (This algorithm uses membership queries.) The decision tree model that is considered is an extension of the traditional boolean decision tree model that allows linear operations in each node (i.e., summation of a subset of the input variables over $GF(2)$). This paper shows how to learn in polynomial time any function that can be approximated (in norm L₂) by a polynomially sparse function (i.e., a function with only polynomially many nonzero Fourier coefficients). The authors demonstrate that any function f whose L₁-norm (i.e., the sum of absolute value of the Fourier coefficients) is polynomial can be approximated by a polynomially sparse function, and prove that boolean decision trees with linear operations are a subset of this class of functions. Moreover, it is shown that the functions with polynomial L₁-norm can be learned deterministically. The algorithm can also exactly identify a decision tree of depth d in time polynomial in 2ᵈ and n. This result implies that trees of logarithmic depth can be identified in polynomial time.