Use Of Vapnik-Chervonenkis Dimension in Model Selection
This work addresses model selection for machine learning practitioners by providing a method with high-probability performance guarantees, though it appears incremental as it builds on existing Vapnik et al. techniques.
The paper tackles model selection by deriving a new method to estimate the Vapnik-Chervonenkis Dimension (VCD) for linear functions, resulting in bounds for true risk that perform as good as or better than other methods on simulated and real datasets.
In this dissertation, I derive a new method to estimate the Vapnik-Chervonenkis Dimension (VCD) for the class of linear functions. This method is inspired by the technique developed by Vapnik et al. Vapnik et al. (1994). My contribution rests on the approximation of the expected maximum difference between two empirical Losses (EMDBTEL). In fact, I use a cross-validated form of the error to compute the EMDBTEL, and I make the bound on the EMDBTEL tighter by minimizing a constant in of its right upper bound. I also derive two bounds for the true unknown risk using the additive (ERM1) and the multiplicative (ERM2) Chernoff bounds. These bounds depend on the estimated VCD and the empirical risk. These bounds can be used to perform model selection and to declare with high probability, the chosen model will perform better without making strong assumptions about the data generating process (DG). I measure the accuracy of my technique on simulated datasets and also on three real datasets. The model selection provided by VCD was always as good as if not better than the other methods under reasonable conditions.