Learning Random Log-Depth Decision Trees under Uniform Distribution
Jeffrey C. Jackson, Rocco A. Servedio · SIAM Journal on Computing · 2005
We consider three natural models of random logarithmic depth decision trees over Boolean variables. We give an efficient algorithm that for each of these models learns all but an inverse polynomial fraction of such trees using only uniformly distributed random examples from {0,1} n . The learning algorithm constructs a decision tree as its hypothesis.