Theory and Applications of Agnostic PAC-Learning With Small Decision Trees
- Peter Auer, Institute for Theoretical Computer Science, Graz, Austria
- Robert Holte, Department of Computing Science, University of Alberta
- Wolfgang Maass, Institute for Theoretical Computer Science, Graz, Austria
We exhibit a theoretically founded algorithm T2
for agnostic PAClearning 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 ``realworld'' 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 PAClearning al
gorithm is shown to be applicable to ``realworld''
classification problems.
Since one can prove that T2 is an agnostic PAC
learning algorithm, T2 is guaranteed to produce
close to optimal 2level 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 2level decision trees.
Finally, T2, in combination with new bounds on
the VCdimension 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 ``realworld''
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