Learning Decision Trees Using the Fourier Spectrum

Citations Over TimeTop 1% of 1993 papers

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.

Related Papers

• → Logarithm Difference Based Illumination Invariant Feature for Severe Illumination Variation Face Recognition(2019)1 cited
• Characteristics of the binary decision diagrams of Boolean Bent Functions(2009)
• → Functional equations of higher logarithms(2002)1 cited
• → Appendix A: Uses of Exponents and Logarithms(2010)
• → A numerical algorithm for taking the logarithm of a complex function with a minimum width of the logarithm spectrum(2000)