A RELATIONSHIP BETWEEN CROSS-VALIDATION AND VAPNIK BOUNDS ON GENERALIZATION OF LEARNING MACHINES

Przemysław Klęsk

2011

Abstract

Typically, the n-fold cross-validation is used both to: (1) estimate the generalization properties of a model of fixed complexity, (2) choose from a family of models of different complexities, the one with the best complexity, given a data set of certain size. Obviously, it is a time-consuming procedure. A different approach — the Structural Risk Minimization is based on generalization bounds of learning machines given by Vapnik (Vapnik, 1995a; Vapnik, 1995b). Roughly speaking, SRM is O(n) times faster than n-fold cross-validation but less accurate. We state and prove theorems, which show the probabilistic relationship between the two approaches. In particular, we show what e-difference between the two, one may expect without actually performing the crossvalidation. We conclude the paper with results of experiments confronting the probabilistic bounds we derived.

Download


Paper Citation


in Harvard Style

Klęsk P. (2011). A RELATIONSHIP BETWEEN CROSS-VALIDATION AND VAPNIK BOUNDS ON GENERALIZATION OF LEARNING MACHINES . In Proceedings of the 3rd International Conference on Agents and Artificial Intelligence - Volume 1: ICAART, ISBN 978-989-8425-40-9, pages 5-17. DOI: 10.5220/0003121000050017

in Bibtex Style

@conference{icaart11,
author={Przemysław Klęsk},
title={A RELATIONSHIP BETWEEN CROSS-VALIDATION AND VAPNIK BOUNDS ON GENERALIZATION OF LEARNING MACHINES},
booktitle={Proceedings of the 3rd International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,},
year={2011},
pages={5-17},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003121000050017},
isbn={978-989-8425-40-9},
}


in EndNote Style

TY - CONF
JO - Proceedings of the 3rd International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,
TI - A RELATIONSHIP BETWEEN CROSS-VALIDATION AND VAPNIK BOUNDS ON GENERALIZATION OF LEARNING MACHINES
SN - 978-989-8425-40-9
AU - Klęsk P.
PY - 2011
SP - 5
EP - 17
DO - 10.5220/0003121000050017