Not Logged In

Theory and Applications of Agnostic PAC-Learning With Small Decision Trees

We exhibit a theoretically founded algorithm T2 for agnostic PAC­learning of decision trees of at most 2 levels, whose computation time is almost linear in the size of the training set. We evalu­ ate the performance of this learning algorithm T2 on 15 common ``real­world'' datasets, and show that for most of these datasets T2 provides simple decision trees with little or no loss in predictive power (compared with C4.5). In fact, for datasets with continuous attributes its error rate tends to be lower than that of C4.5. To the best of our knowl­ edge this is the first time that a PAC­learning al­ gorithm is shown to be applicable to ``real­world'' classification problems. Since one can prove that T2 is an agnostic PAC­ learning algorithm, T2 is guaranteed to produce close to optimal 2­level decision trees from suffi­ ciently large training sets for any (!) distribution of data. In this regard T2 differs strongly from all other learning algorithms that are considered in applied machine learning, for which no guaran­ tee can be given about their performance on new datasets. We also demonstrate that this algorithm T2 can be used as a diagnostic tool for the investigation of the expressive limits of 2­level decision trees. Finally, T2, in combination with new bounds on the VC­dimension of decision trees of bounded depth that we derive, provides us now for the first time with the tools necessary for comparing learning curves of decision trees for ``real­world'' datasets with the theoretical estimates of PAC­ learning theory.

Citation

P. Auer, R. Holte, W. Maass. "Theory and Applications of Agnostic PAC-Learning With Small Decision Trees". International Conference on Machine Learning (ICML), pp 21-29, January 1995.

Keywords: agnostic, PAC-learning, decision, machine learning
Category: In Conference

BibTeX

@incollection{Auer+al:ICML95,
  author = {Peter Auer and Robert Holte and Wolfgang Maass},
  title = {Theory and Applications of Agnostic PAC-Learning With Small Decision
    Trees},
  Pages = {21-29},
  booktitle = {International Conference on Machine Learning (ICML)},
  year = 1995,
}

Last Updated: June 18, 2007
Submitted by Staurt H. Johnson

University of Alberta Logo AICML Logo