Calculating the VC-Dimension of Decision Trees

被引：5

作者：

Aslan, Oezlem ^{[1
]}

Yildiz, Olcay Taner ^{[2
]}

Alpaydin, Ethem ^{[1
]}

机构：

[1] Bogazici Univ, Dept Comp Engn, TR-34342 Istanbul, Turkey

[2] Isik Univ, Dept Comp Engn, TR-34980 Istanbul, Turkey

来源：

2009 24TH INTERNATIONAL SYMPOSIUM ON COMPUTER AND INFORMATION SCIENCES | 2009年

关键词：

REGRESSION; MACHINE;

D O I：

10.1109/ISCIS.2009.5291847

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We propose an exhaustive search algorithm that calculates the VC-dimension of univariate decision trees with binary features. The VC-dimension of the univariate decision tree with binary features depends on (i) the VC-dimension values of the left and right subtrees, (ii) the number of inputs, and (iii) the number of nodes in the tree. From a training set of example trees whose VC-dimensions are calculated by exhaustive search, we fit a general regressor to estimate the VC-dimension of any binary tree. These VC-dimension estimates are then used 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 estimated VC-dimensions finds trees that are as accurate as those pruned using cross-validation.

引用

页码：193 / +

页数：2

共 10 条

[1]

[Anonymous], 1993, C4.5: Programs for machine learning

[2] Comparison of model selection for regression [J].

Cherkassky, V ;

Ma, YQ .

NEURAL COMPUTATION, 2003, 15 (07) :1691-1714

[3]

Cherkassky V, 2007, LEARNING DATA CONCEP

[4]

Quinlan J. R., 1986, Machine Learning, V1, P81, DOI 10.1023/A:1022643204877

[5] Empirical measure of multiclass generalization performance: The K-winner machine case [J].

Ridella, S ;

Zunino, R .

IEEE TRANSACTIONS ON NEURAL NETWORKS, 2001, 12 (06) :1525-1529

[6] Measuring the VC-dimension using optimized experimental design [J].

Shao, XH ;

Cherkassky, V ;

Li, W .

NEURAL COMPUTATION, 2000, 12 (08) :1969-1986

[7] MEASURING THE VC-DIMENSION OF A LEARNING-MACHINE [J].

VAPNIK, V ;

LEVIN, E ;

LECUN, Y .

NEURAL COMPUTATION, 1994, 6 (05) :851-876

[8]

Vapnik Vladimir, 1999, The nature of statistical learning theory

[9]

Yang Z, 2006, LECT NOTES COMPUT SC, V3971, P895

[10] Omnivariate decision trees [J].

Yildiz, OT ;

Alpaydin, E .

IEEE TRANSACTIONS ON NEURAL NETWORKS, 2001, 12 (06) :1539-1546

← 1 →