<abstract xml:lang="en" xmlns="http://www.w3.org/1999/xhtml"><p>Two known approaches to complexity selection are taken under consideration: <italic>n</italic>-fold cross-validation and structural risk minimization. Obviously, in either approach, a discrepancy between the indicated optimal complexity (indicated as the minimum of a generalization error estimate or a bound) and the genuine minimum of <italic>unknown true risks</italic> is possible. In the paper, this problem is posed in a novel quantitative way. We state and prove theorems demonstrating how one can calculate pessimistic probabilities of discrepancy between these minima for given for given conditions of an experiment. The probabilities are calculated in terms of all relevant constants: the sample size, the number of cross-validation folds, the capacity of the set of approximating functions and bounds on this set. We report experiments carried out to validate the results.</p></abstract>

Two known approaches to complexity selection are taken under consideration: n-fold cross-validation and structural risk minimization. Obviously, in either approach, a discrepancy between the indicated optimal complexity (indicated as the minimum of a generalization error estimate or a bound) and the genuine minimum of unknown true risks is possible. In the paper, this problem is posed in a novel quantitative way. We state and prove theorems demonstrating how one can calculate pessimistic probabilities of discrepancy between these minima for given for given conditions of an experiment. The probabilities are calculated in terms of all relevant constants: the sample size, the number of cross-validation folds, the capacity of the set of approximating functions and bounds on this set. We report experiments carried out to validate the results.

Probabilities of discrepancy between minima of cross-validation, Vapnik bounds and true risks

Department of Methods of Artificial Intelligence and Applied Mathematics, Westpomeranian University of Technology, ul. Żołnierska 49, 71-210 Szczecin, Poland

International Journal of Applied Mathematics and Computer Science

Two known approaches to complexity selection are taken under consideration: n-fold cross-validation and structural risk minimization. Obviously, in either...

Probabilities of discrepancy between minima of cross-validation, Vapnik bounds and true risks

Published Online: Sep 27, 2010

Page range: 525 - 544

DOI: https://doi.org/10.2478/v10006-010-0039-x

Keywords
regression estimation, model comparison, complexity selection, cross-validation, generalization, statistical learning theory, generalization bounds, structural risk minimization

This content is open access.

Probabilities of discrepancy between minima of cross-validation, Vapnik bounds and true risks

Published Online: Sep 27, 2010

Page range: 525 - 544

DOI: https://doi.org/10.2478/v10006-010-0039-x

Keywordsregression estimation, model comparison, complexity selection, cross-validation, generalization, statistical learning theory, generalization bounds, structural risk minimization

This content is open access.

Keywords
regression estimation, model comparison, complexity selection, cross-validation, generalization, statistical learning theory, generalization bounds, structural risk minimization