ON THE VC-DIMENSION OF UNIVARIATE DECISION TREES

Olcay Taner Yildiz

2012

Abstract

In this paper, we give and prove lower bounds of the VC-dimension of the univariate decision tree hypothesis class. The VC-dimension of the univariate decision tree depends on the VC-dimension values of its subtrees and the number of inputs. In our previous work (Aslan et al., 2009), we proposed a search algorithm that calculates the VC-dimension of univariate decision trees exhaustively. Using the experimental results of that work, we show that our VC-dimension bounds are tight. To verify that the VC-dimension bounds are useful, we also use them to get VC-generalization bounds for complexity control using SRM in decision trees, i.e., pruning. Our simulation results shows that SRM-pruning using the VC-dimension bounds finds trees that are more accurate as those pruned using cross-validation.

Paper Citation

in Harvard Style

Taner Yildiz O. (2012). ON THE VC-DIMENSION OF UNIVARIATE DECISION TREES . In Proceedings of the 1st International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM, ISBN 978-989-8425-98-0, pages 205-210. DOI: 10.5220/0003777202050210

in Bibtex Style

@conference{icpram12,
author={Olcay Taner Yildiz},
title={ON THE VC-DIMENSION OF UNIVARIATE DECISION TREES},
booktitle={Proceedings of the 1st International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM,},
year={2012},
pages={205-210},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003777202050210},
isbn={978-989-8425-98-0},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 1st International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM,
TI - ON THE VC-DIMENSION OF UNIVARIATE DECISION TREES
SN - 978-989-8425-98-0
AU - Taner Yildiz O.
PY - 2012
SP - 205
EP - 210
DO - 10.5220/0003777202050210