Fakultät für Mathematik

Lehrstuhl Mathematik & Informatik

On the Number of Examples and Stages Needed for Learning Decision Trees

Abstract.  We show that VCDIM(r-DT_n)=\sum _i=0 ^r {n \choose i }, where r-DT_n denotes the set of all boolean functions on n variables defined by decision trees of rank at most r, and VCDIM(r-DT_n) denotes its Vapnik-Chervonenkis dimension. It follows that the number of examples needed for learning r-DT_n can be determined modulo a small factor. We show furthermore that \Omega(log log log(