This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)(Learn how and when to remove this template message)
- Leave-one-out cross-validation (CVloo) Stability An algorithm f has CVloo stability β with respect to the loss function V if the following holds:
- Expected-to-leave-one-out error () Stability An algorithm f has stability if for each n there exists a and a such that:
, with and going to zero for
X and Y ⊂ R being respectively an input and an output space, we consider a training set
of size m in drawn i.i.d. from an unknown distribution D. A learning algorithm is a function from into which maps a learning set S onto a function from X to Y. To avoid complex notation, we consider only deterministic algorithms. It is also assumed that the algorithm is symmetric with respect to S, i.e. it does not depend on the order of the elements in the training set. Furthermore, we assume that all functions are measurable and all sets are countable which does not limit the interest of the results presented here.
The loss of an hypothesis f with respect to an example is then defined as . The empirical error of f is .
The true error of f is
Given a training set S of size m, we will build, for all i = 1....,m, modified training sets as follows:
- By removing the i-th element
- By replacing the i-th element
- S. Mukherjee, P. Niyogi, T. Poggio, and R. M. Rifkin. Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization. Adv. Comput. Math., 25(1-3):161–193, 2006