Learning decision trees using the Fourier spectrum

By Eyal Kushilevitz, Yishay Mansour. 1991

This work gives apolynomial 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 L2) by a polynomially sparse function (i.e., a function with only polynomially many nonzero Fourier coefficients). The authors demonstrate that any functionf 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 a and n. This result implies that trees of logarithmic depth can be identified in polynomial time.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Stealing Machine Learning Models via Prediction APIs (2016, background): “, PAC learning [53] and other previous works [3, 7, 8, 15, 30, 33, 36].”
Local, Private, Efficient Protocols for Succinct Histograms (2015, background): “For example, the use of hashing to isolate unique “heavy” items appears in the context of sparse approximations to a vector’s Fourier representation [12] (and arguably that idea has roots in learning algorithms for Fourier coefficients such as [18]).”
Learning Neural Networks with Two Nonlinear Layers in Polynomial Time (2017, methodology): “Here we give an algorithm, KMtron, which combines isotonic regression with the KM algorithm (Kushilevitz and Mansour (1993)) for finding large Fourier coefficients of a function (given query access to the function).”
Weakly learning DNF and characterizing statistical query learning using Fourier analysis (1994, methodology): “All of our results rely heavily on the Fourier representation of functions on the hypercube [18, 16, 20], demonstrating once again the utility of spectral analysis tools in computational learning theory.”
Near-optimal sparse fourier representations via sampling (2002, methodology): “In [10], authors presented a polynomial time algorithm to nd all the large coe cients for this Fourier basis for given Boolean functions.”
The Power of Amnesia: Learning Probabilistic Automata with Variable Memory Length (2005, methodology): “A similar type of branch-and-bound technique (with various bounding criteria) is applied in many algorithms which use trees as data structures (cf ( Kushilevitz & Mansour, 1993 )).”
Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals (2009, methodology): “The earliest work in this area was due to Kushilevitz and Mansour [55], while the method was perfected by Gilbert et al. [56], [57].”
An efficient membership-query algorithm for learning DNF with respect to the uniform distribution (1994, methodology): “For example, every Boolean function f has a TOP representation that is at most polynomially larger then the smallest representation of f as either a CNF or a DNF [36] or as a decision tree with parity functions at the internal nodes [37].”
Learning DNF Expressions from Fourier Spectrum (2012, methodology): “…the Fourier transform-based learning technique (Linial et al., 1993) and combines the Kushilevitz-Mansour algorithm for finding a “heavy” Fourier coefficient of a boolean function (Goldreich and Levin, 1989, Kushilevitz and Mansour, 1993) with the Boosting-by-Majority algorithm of Freund (1995).”
Universal approximation bounds for superpositions of a sigmoidal function (1993, background): “(that is, L(f) :::: de for some fixed c � 1), is examined in [5] and [ 27 ].3 In particular, Siu and Bruck [5] show, among examples, that the Boolean function on {O, 1 Fd defined by the comparison of two d-bit”
Agnostically learning decision trees (2008, background): “It is well-known that decision trees with t leaves are t -sparse [15].”
Distribution-Specific Agnostic Boosting (2009, methodology): “Proof: As it has been shown by Kushilevitz and Mansour, the L1 norm of the Fourier representation of a decision tree of size s is at most s [28].”