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.