Decision trees are PAC-learnable from most product distributions: a smoothed analysis

2008/12/04 by Kalai, Adam Tauman, Teng, Shang-Hua · 1 citation
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.0812.0933

Abstract

We consider the problem of PAC-learning decision trees, i.e., learning a decision tree over the n-dimensional hypercube from independent random labeled examples. Despite significant effort, no polynomial-time algorithm is known for learning polynomial-sized decision trees (even trees of any super-constant size), even when examples are assumed to be drawn from the uniform distribution on 0,1ⁿ. We give an algorithm that learns arbitrary polynomial-sized decision trees for \em most product distributions. In particular, consider a random product distribution where the bias of each bit is chosen independently and uniformly from, say, [.49,.51]. Then with high probability over the parameters of the product distribution and the random examples drawn from it, the algorithm will learn any tree. More generally, in the spirit of smoothed analysis, we consider an arbitrary product distribution whose parameters are specified only up to a [-c,c] accuracy (perturbation), for an arbitrarily small positive constant c.

Cited by

• Smoothed Agnostic Learning of Halfspaces over the Hypercube

Related

• Lifting uniform learners via distributional decomposition
• Superpolynomial Lower Bounds for Decision Tree Learning and Testing
• Open Problem: Properly learning decision trees in polynomial time?
• Properly Learning Decision Trees with Queries Is NP-Hard
• Universal guarantees for decision tree induction via a higher-order splitting criterion