Learning Random Log-Depth Decision Trees under the Uniform Distribution

Learning Random Log-Depth Decision Trees under the Uniform Distribution.
J. Jackson and R. Servedio.
SIAM Journal on Computing 34(5), 2005, pp. 1107-1128.
Preliminary version appeared in Sixteenth Annual Conference on Computational Learning Theory (COLT), 2003, pp. 610-624.

Abstract:

We consider three natural models of random log-depth decision trees. We give an efficient algorithm that for each of these models learns---as a decision tree---all but an inverse polynomial fraction of such trees using only uniformly distributed random examples.

pdf of conference version

Postscript or pdf of journal version

Back to main papers page