Abstract for holden_tr155

Cambridge University Engineering Department Technical Report CUED/F-INFENG/TR155

ON THE PRACTICAL APPLICABILITY OF VC DIMENSION BOUNDS

Sean Holden and Mahesan Niranjan

October 1994

This article addresses the question of whether some recent Vapnik-Chervonenkis (VC) dimension based bounds on sample complexity can be regarded as a practical design tool. Specifically, we are interested in bounds on the sample complexity for the problem of training a pattern classifier such that we can expect it to perform valid generalization. Early results using the VC dimension, while being extremely powerful, suffered from the fact that their sample complexity predictions were rather impractical. More recent results have begun to improve the situation by attempting to take specific account of the precise algorithm used to train the classifier. We perform a series of experiments based on a task involving the classification of sets of vowel formant frequencies. The results of these experiments indicate that the more recent theories provide sample complexity predictions that are significantly more applicable in practice than those provided by earlier theories; however, we also find that the recent theories still have significant shortcomings.


(ftp:) holden_tr155.ps.Z (http:) holden_tr155.ps.Z
PDF (automatically generated from original PostScript document - may be badly aliased on screen):
  (ftp:) holden_tr155.pdf | (http:) holden_tr155.pdf

If you have difficulty viewing files that end '.gz', which are gzip compressed, then you may be able to find tools to uncompress them at the gzip web site.

If you have difficulty viewing files that are in PostScript, (ending '.ps' or '.ps.gz'), then you may be able to find tools to view them at the gsview web site.

We have attempted to provide automatically generated PDF copies of documents for which only PostScript versions have previously been available. These are clearly marked in the database - due to the nature of the automatic conversion process, they are likely to be badly aliased when viewed at default resolution on screen by acroread.