On Upper Bound of VC Dimension of Binary Decision Tree Algorithms
Nianyi Chen · Jisuanji fangzhen · 2005
VC dimension plays a central role in the Statistical Learning Theory especially for classification problems. Since there does not exist a universal method to calculate this combinatorial dimension, this value for most of the classification algorithms is still unknown. Binary decision tree algorithms for classification constitute a large family in the fields of machine learning, pattern recognition, and data mining. Investigating their VC dimension seems to be a helpful step towards further improvement of their generalization performance. For this purpose, the paper calculated, in theorem 2, an upper bound of VC dimension for binary decision tree algorithms, which rises as the complexity of resulting tree and the number of adjustable parameters at each node increases. To facilitate the calculation, only continuous attributes are considered here, and hypothesis function class of decision tree algorithms is considered as a continuously expending group of uniform Boolean formulas. As a supplement, upper bound of single non-leaf node of univariate decision tree algorithms is also calculated in theorem 3, which displays its special classification capability when compared with its multivariate counterpart. For the purpose of comparison, experiential conclusions on VC dimension of univirate decision tree algorithms are evaluated by experiments. They are found to be appropriate when complexity of the resulting tree is large enough. Based on this observation, a numerical comparison between the experiential value of VC dimension and the upper bound calculated by us was made. Although the numeric discrepancy between them is large, they display the same tendency. Possible origins of the exaggeration in the upper bound were discussed. Conclusions of the paper is helpful for us to understand the essential purpose of some techniques of improvement such as pruning a grown decision tree or imposing earlier-stop criteria in training, which are assumed to limit the VC dimension of the algorithm to a reasonable range and hence alleviate the serious problem of over training.