Learning Decision Trees Using the Fourier Spectrum

TLDR

The decision tree model considered extends the traditional Boolean decision tree by allowing linear operations (sums of input subsets over GF(2)) at each node. The study presents a polynomial‑time algorithm for learning such decision trees under the uniform distribution. The algorithm uses membership queries and learns any function that can be approximated by a polynomially sparse Fourier representation in polynomial time. It shows that any function with polynomial L1‑norm, including linear‑operation decision trees, can be approximated by a polynomially sparse function, learned deterministically, and that depth‑d trees can be exactly identified in time polynomial in 2^d and n, so logarithmic‑depth trees are learnable in polynomial time.

Abstract

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_2 $) 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_1 $-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_1 $-norm can be learned deterministically. The algorithm can also exactly identify a decision tree of depth d in time polynomial in $2^d $ and n. This result implies that trees of logarithmic depth can be identified in polynomial time.