Streeter–Phelps equation

2013-11-12T18:14:37Z

122.164.225.79:

{{Multiple issues|
{{confusing|date=November 2011}}
{{context|date=November 2011}}
}}
* '''Leave-one-out cross-validation (CVloo) Stability''' An [[algorithm]] f has CVloo stability β with respect to the [[loss function]] V if the following holds:

<math>\forall i\in\{1,...,m\}, \mathbb{P}_S\{\sup_{z\in Z}|V(f_S,z_i)-V(f_{S^{|i}},z_i)|\leq\beta_{CV}\}\geq1-\delta_{CV}</math>
* '''Expected-to-leave-one-out error (<math>Eloo_{err}</math>) Stability''' An algorithm f has <math>Eloo_{err}</math> stability if for each n there exists a<math>\beta_{EL}^m</math> and a <math>\delta_{EL}^m</math> such that:

<math>\forall i\in\{1,...,m\}, \mathbb{P}_S\{|I[f_S]-\frac{1}{m}\sum_{i=1}^m V(f_{S^{|i}},z_i)|\leq\beta_{EL}^m\}\geq1-\delta_{EL}^m</math>, with <math>\beta_{EL}^m</math>and <math>\delta_{EL}^m</math> going to zero for <math>n\rightarrow\inf</math>

==Preliminary Notations==
X and Y ⊂ R being respectively an input and an output space, we consider a [[training set]]

<math>S = \{z_1 = (x_1,\ y_1)\ ,..,\ z_m = (x_m,\ y_m)\}</math>
of size m in <math>Z = X \times Y</math> drawn i.i.d. from an unknown distribution D. A [[Learning algorithms|learning algorithm]] is a function <math>f </math> from <math>Z_m</math> into <math> F \subset YX </math>which maps a learning set S onto a function <math>f_S</math> from X to Y. To avoid complex notation, we consider only [[deterministic algorithm]]s. It is also assumed that the algorithm <math>f</math> 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 '''<big>f</big>''' with respect to an example <math>z = (x,y)</math> is then defined as <math>V(f,z) = V(f(x),y)</math>.
The empirical error of '''<big>f</big>''' is <math>I_S[f] = \frac{1}{n}\sum V(f,z_i)</math>.

The true error of '''<big>f</big>''' is <math>I[f] = \mathbb{E}_z V(f,z)</math>

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
<math>S^{|i} = \{z_1 ,...,\ z_{i-1},\ z_{i+1},...,\ z_m\}</math>
* By replacing the i-th element
<math>S^i = \{z_1 ,...,\ z_{i-1},\ z_i',\ z_{i+1},...,\ z_m\}</math>

==References==
S. Mukherjee, P. Niyogi, T. Poggio, and R. M. Rifkin. Learning theory: stability is sufficient for generaliza- tion and necessary and sufficient for consistency of empirical risk minimization. Adv. Comput. Math., 25(1-3):161–193, 2006

[[Category:Machine learning]]

formulasearchengine - User contributions [en]

Streeter–Phelps equation