ON THE PRACTICAL APPLICABILITY OF VC-DIMENSION BOUNDS

This article addresses the question of whether some recent Vapnik-Cher vonenkis (VC) dimension-based bounds on sample complexity can be regar ded as a practical design tool. Specifically, we are interested in bou nds on the sample complexity for the problem of training a pattern cla ssifier such that we can expect it to perform valid generalization. Ea rly results using the VC dimension, while being extremely powerful, su ffered from the fact that their sample complexity predictions were rat her impractical. More recent results have begun to improve the situati on by attempting to take specific account of the precise algorithm use d to train the classifier. We perform a series of experiments based on a task involving the classification of sets of vowel formant frequenc ies. The results of these experiments indicate that the more recent th eories provide sample complexity predictions that are significantly mo re applicable in practice than those provided by earlier theories; how ever, we also find that the recent theories still have significant sho rtcomings.