Teoría de Vapnik-Chervonenkis

Rama de la teoría estadística del aprendizaje computacional.

La teoría de Vapnik-Chervonenkis (también conocida como teoría VC ) fue desarrollada durante 1960-1990 por Vladimir Vapnik y Alexey Chervonenkis . La teoría es una forma de teoría del aprendizaje computacional , que intenta explicar el proceso de aprendizaje desde un punto de vista estadístico.

Introducción

La teoría de VC cubre al menos cuatro partes (como se explica en La naturaleza de la teoría del aprendizaje estadístico ^[1] ):

• Teoría de la consistencia de los procesos de aprendizaje.
  • ¿Cuáles son las condiciones (necesarias y suficientes) para la coherencia de un proceso de aprendizaje basado en el principio empírico de minimización de riesgos ?
• Teoría no asintótica de la tasa de convergencia de los procesos de aprendizaje.
  • ¿Qué tan rápida es la tasa de convergencia del proceso de aprendizaje?
• Teoría del control de la capacidad de generalización de los procesos de aprendizaje.
  • ¿Cómo se puede controlar la tasa de convergencia (la capacidad de generalización ) del proceso de aprendizaje?
• Teoría de la construcción de máquinas de aprendizaje.
  • ¿Cómo se pueden construir algoritmos que puedan controlar la capacidad de generalización?

La teoría VC es una subrama importante de la teoría del aprendizaje estadístico . Una de sus principales aplicaciones en la teoría del aprendizaje estadístico es proporcionar condiciones de generalización para los algoritmos de aprendizaje. Desde este punto de vista, la teoría VC está relacionada con la estabilidad , que es un enfoque alternativo para caracterizar la generalización.

Además, la teoría de VC y la dimensión de VC son fundamentales en la teoría de procesos empíricos , en el caso de procesos indexados por clases de VC. Podría decirse que estas son las aplicaciones más importantes de la teoría VC y se emplean para demostrar la generalización. Se introducirán varias técnicas que se utilizan ampliamente en el proceso empírico y la teoría de VC. La discusión se basa principalmente en el libro Convergencia débil y procesos empíricos: con aplicaciones a la estadística . ^[2]

Descripción general de la teoría VC en procesos empíricos

Antecedentes de los procesos empíricos

Sea un espacio mensurable . Para cualquier medida y cualquier función medible , defina ${\displaystyle ({\mathcal {X}},{\mathcal {A}})}$ ${\displaystyle Q}$ ${\displaystyle ({\mathcal {X}},{\mathcal {A}})}$ ${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$

${\displaystyle Qf=\int fdQ}$

Aquí se ignorarán los problemas de mensurabilidad; para obtener más detalles técnicos, consulte. ^[1] Sea una clase de funciones medibles y defina: ${\displaystyle {\mathcal {F}}}$ ${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$

${\displaystyle \|Q\|_{\mathcal {F}}=\sup\{\vert Qf\vert \ :\ f\in {\mathcal {F}}\}.}$

Sean elementos aleatorios independientes e idénticamente distribuidos de . Luego define la medida empírica. ${\displaystyle X_{1},\ldots ,X_{n}}$ ${\displaystyle ({\mathcal {X}},{\mathcal {A}})}$

${\displaystyle \mathbb {P} _{n}=n^{-1}\sum _{i=1}^{n}\delta _{X_{i}},}$

donde δ aquí representa la medida de Dirac . La medida empírica induce un mapa dado por: ${\displaystyle {\mathcal {F}}\to \mathbf {R} }$

${\displaystyle f\mapsto \mathbb {P} _{n}f={\frac {1}{n}}(f(X_{1})+...+f(X_{n}))}$

Ahora supongamos que P es la verdadera distribución subyacente de los datos, que se desconoce. La teoría de los procesos empíricos tiene como objetivo identificar clases para las cuales se aplican afirmaciones como las siguientes: ${\displaystyle {\mathcal {F}}}$

• ley uniforme de grandes números :

  ${\displaystyle \|\mathbb {P} _{n}-P\|_{\mathcal {F}}{\underset {n}{\to }}0,}$

Es decir, como , ${\displaystyle n\to \infty }$

${\displaystyle \left|{\frac {1}{n}}(f(X_{1})+...+f(X_{n}))-\int fdP\right|\to 0}$

uniformemente para todos . ${\displaystyle f\in {\mathcal {F}}}$

• teorema del límite central uniforme :

${\displaystyle \mathbb {G} _{n}={\sqrt {n}}(\mathbb {P} _{n}-P)\rightsquigarrow \mathbb {G} ,\quad {\text{in }}\ell ^{\infty }({\mathcal {F}})}$

En el primer caso se llama clase Glivenko-Cantelli , y en el último caso (bajo el supuesto ) la clase se llama Donsker o P -Donsker. Una clase de Donsker es Glivenko-Cantelli en probabilidad mediante una aplicación del teorema de Slutsky . ${\displaystyle {\mathcal {F}}}$ ${\displaystyle \forall x,\sup \nolimits _{f\in {\mathcal {F}}}\vert f(x)-Pf\vert <\infty }$ ${\displaystyle {\mathcal {F}}}$

Estas afirmaciones son ciertas para un solo argumento , según el estándar LLN , CLT , bajo condiciones de regularidad, y la dificultad en los procesos empíricos surge porque se hacen afirmaciones conjuntas para todos . Intuitivamente entonces, el conjunto no puede ser demasiado grande, y resulta que la geometría juega un papel muy importante. ${\displaystyle f}$ ${\displaystyle f\in {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$

Una forma de medir el tamaño del conjunto de funciones es utilizar los llamados números de cobertura . El número de cobertura ${\displaystyle {\mathcal {F}}}$

${\displaystyle N(\varepsilon ,{\mathcal {F}},\|\cdot \|)}$

es el número mínimo de bolas necesarias para cubrir el conjunto (aquí obviamente se supone que hay una norma subyacente en ). La entropía es el logaritmo del número de cobertura. ${\displaystyle \{g:\|g-f\|<\varepsilon \}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$

A continuación se proporcionan dos condiciones suficientes bajo las cuales se puede demostrar que el conjunto es Glivenko-Cantelli o Donsker. ${\displaystyle {\mathcal {F}}}$

Una clase es P -Glivenko–Cantelli si es P -medible con envolvente F tal que y satisface: ${\displaystyle {\mathcal {F}}}$ ${\displaystyle P^{\ast }F<\infty }$

${\displaystyle \forall \varepsilon >0\quad \sup \nolimits _{Q}N(\varepsilon \|F\|_{Q},{\mathcal {F}},L_{1}(Q))<\infty .}$

La siguiente condición es una versión del célebre teorema de Dudley . Si es una clase de funciones tal que ${\displaystyle {\mathcal {F}}}$

${\displaystyle \int _{0}^{\infty }\sup \nolimits _{Q}{\sqrt {\log N\left(\varepsilon \|F\|_{Q,2},{\mathcal {F}},L_{2}(Q)\right)}}d\varepsilon <\infty }$

entonces es P -Donsker para cada medida de probabilidad P tal que . En la última integral, la notación significa ${\displaystyle {\mathcal {F}}}$ ${\displaystyle P^{\ast }F^{2}<\infty }$

${\displaystyle \|f\|_{Q,2}=\left(\int |f|^{2}dQ\right)^{\frac {1}{2}}}$.

Simetrización

La mayoría de los argumentos sobre cómo limitar el proceso empírico se basan en la simetrización, las desigualdades máximas y de concentración y el encadenamiento. La simetrización suele ser el primer paso de las pruebas y, dado que se utiliza en muchas pruebas de aprendizaje automático sobre funciones de pérdida empíricas acotadas (incluida la prueba de la desigualdad VC que se analiza en la siguiente sección), se presenta aquí.

Considere el proceso empírico:

${\displaystyle f\mapsto (\mathbb {P} _{n}-P)f={\dfrac {1}{n}}\sum _{i=1}^{n}(f(X_{i})-Pf)}$

Resulta que existe una conexión entre el proceso empírico y el siguiente proceso simetrizado:

${\displaystyle f\mapsto \mathbb {P} _{n}^{0}f={\dfrac {1}{n}}\sum _{i=1}^{n}\varepsilon _{i}f(X_{i})}$

El proceso simetrizado es un proceso de Rademacher , condicionalmente a los datos . Por tanto, se trata de un proceso subgaussiano por la desigualdad de Hoeffding . ${\displaystyle X_{i}}$

Lema (simetrización). Para cada Φ convexo no decreciente: R → R y clase de funciones medibles , ${\displaystyle {\mathcal {F}}}$

${\displaystyle \mathbb {E} \Phi (\|\mathbb {P} _{n}-P\|_{\mathcal {F}})\leq \mathbb {E} \Phi \left(2\left\|\mathbb {P} _{n}^{0}\right\|_{\mathcal {F}}\right)}$

La prueba del lema de simetrización se basa en introducir copias independientes de las variables originales (a veces denominadas muestra fantasma ) y reemplazar la expectativa interna del LHS por estas copias. Después de una aplicación de la desigualdad de Jensen se podrían introducir diferentes signos (de ahí el nombre de simetrización) sin cambiar la expectativa. La prueba se puede encontrar a continuación debido a su naturaleza instructiva. Se puede utilizar el mismo método de demostración para demostrar el teorema de Glivenko-Cantelli . ^[3] ${\displaystyle X_{i}}$

Prueba

Introduzca la "muestra fantasma" para que sean copias independientes de . Para valores fijos de uno tiene: ${\displaystyle Y_{1},\ldots ,Y_{n}}$ ${\displaystyle X_{1},\ldots ,X_{n}}$ ${\displaystyle X_{1},\ldots ,X_{n}}$

${\displaystyle \|\mathbb {P} _{n}-P\|_{\mathcal {F}}=\sup _{f\in {\mathcal {F}}}{\dfrac {1}{n}}\left|\sum _{i=1}^{n}f(X_{i})-\mathbb {E} f(Y_{i})\right|\leq \mathbb {E} _{Y}\sup _{f\in {\mathcal {F}}}{\dfrac {1}{n}}\left|\sum _{i=1}^{n}f(X_{i})-f(Y_{i})\right|}$

Por lo tanto, por la desigualdad de Jensen :

${\displaystyle \Phi (\|\mathbb {P} _{n}-P\|_{\mathcal {F}})\leq \mathbb {E} _{Y}\Phi \left(\left\|{\dfrac {1}{n}}\sum _{i=1}^{n}f(X_{i})-f(Y_{i})\right\|_{\mathcal {F}}\right)}$

Teniendo expectativa con respecto a da: ${\displaystyle X}$

${\displaystyle \mathbb {E} \Phi (\|\mathbb {P} _{n}-P\|_{\mathcal {F}})\leq \mathbb {E} _{X}\mathbb {E} _{Y}\Phi \left(\left\|{\dfrac {1}{n}}\sum _{i=1}^{n}f(X_{i})-f(Y_{i})\right\|_{\mathcal {F}}\right)}$

Tenga en cuenta que agregar un signo menos delante de un término no cambia el lado derecho, porque es una función simétrica de y . Por lo tanto, el RHS sigue siendo el mismo bajo "perturbación de signos": ${\displaystyle f(X_{i})-f(Y_{i})}$ ${\displaystyle X}$ ${\displaystyle Y}$

${\displaystyle \mathbb {E} \Phi \left(\left\|{\dfrac {1}{n}}\sum _{i=1}^{n}e_{i}\left(f(X_{i})-f(Y_{i})\right)\right\|_{\mathcal {F}}\right)}$

para cualquier . Por lo tanto: ${\displaystyle (e_{1},e_{2},\ldots ,e_{n})\in \{-1,1\}^{n}}$

${\displaystyle \mathbb {E} \Phi (\|\mathbb {P} _{n}-P\|_{\mathcal {F}})\leq \mathbb {E} _{\varepsilon }\mathbb {E} \Phi \left(\left\|{\dfrac {1}{n}}\sum _{i=1}^{n}\varepsilon _{i}\left(f(X_{i})-f(Y_{i})\right)\right\|_{\mathcal {F}}\right)}$

Finalmente, usando la desigualdad del primer triángulo y luego la convexidad de se obtiene: ${\displaystyle \Phi }$

${\displaystyle \mathbb {E} \Phi (\|\mathbb {P} _{n}-P\|_{\mathcal {F}})\leq {\dfrac {1}{2}}\mathbb {E} _{\varepsilon }\mathbb {E} \Phi \left(2\left\|{\dfrac {1}{n}}\sum _{i=1}^{n}\varepsilon _{i}f(X_{i})\right\|_{\mathcal {F}}\right)+{\dfrac {1}{2}}\mathbb {E} _{\varepsilon }\mathbb {E} \Phi \left(2\left\|{\dfrac {1}{n}}\sum _{i=1}^{n}\varepsilon _{i}f(Y_{i})\right\|_{\mathcal {F}}\right)}$

Donde las dos últimas expresiones del RHS son iguales, con lo que concluye la prueba.

Una forma típica de probar CLT empíricos es utilizar primero la simetrización para pasar el proceso empírico y luego argumentar condicionalmente sobre los datos, aprovechando el hecho de que los procesos de Rademacher son procesos simples con buenas propiedades. ${\displaystyle \mathbb {P} _{n}^{0}}$

Conexión VC

Resulta que existe una conexión fascinante entre ciertas propiedades combinatorias del conjunto y los números de entropía. Los números de cobertura uniformes pueden controlarse mediante la noción de clases de conjuntos de Vapnik-Chervonenkis , o brevemente conjuntos VC . ${\displaystyle {\mathcal {F}}}$

Considere una colección de subconjuntos del espacio muestral . se dice que selecciona un determinado subconjunto del conjunto finito si es para algunos . se dice que destruye S si selecciona cada uno de sus 2 ⁿ subconjuntos. El índice VC (similar a la dimensión VC + 1 para un conjunto de clasificadores elegido apropiadamente) de es el n más pequeño para el cual ningún conjunto de tamaño n se rompe . ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle W}$ ${\displaystyle S=\{x_{1},\ldots ,x_{n}\}\subset {\mathcal {X}}}$ ${\displaystyle W=S\cap C}$ ${\displaystyle C\in {\mathcal {C}}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle V({\mathcal {C}})}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {C}}}$

El lema de Sauer luego establece que el número de subconjuntos seleccionados por una clase VC satisface: ${\displaystyle \Delta _{n}({\mathcal {C}},x_{1},\ldots ,x_{n})}$ ${\displaystyle {\mathcal {C}}}$

${\displaystyle \max _{x_{1},\ldots ,x_{n}}\Delta _{n}({\mathcal {C}},x_{1},\ldots ,x_{n})\leq \sum _{j=0}^{V({\mathcal {C}})-1}{n \choose j}\leq \left({\frac {ne}{V({\mathcal {C}})-1}}\right)^{V({\mathcal {C}})-1}}$

Que es un número polinómico de subconjuntos en lugar de un número exponencial. Intuitivamente, esto significa que un índice VC finito implica que tiene una estructura aparentemente simplista. ${\displaystyle O(n^{V({\mathcal {C}})-1})}$ ${\displaystyle {\mathcal {C}}}$

Se puede mostrar un límite similar (con una constante diferente y la misma tasa) para las llamadas clases de subgrafos VC . Para una función, el subgrafo es un subconjunto de tal que: . Una colección de se denomina clase de subgrafo VC si todos los subgrafos forman una clase VC. ${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$ ${\displaystyle {\mathcal {X}}\times \mathbf {R} }$ ${\displaystyle \{(x,t):t<f(x)\}}$ ${\displaystyle {\mathcal {F}}}$

Considere un conjunto de funciones indicadoras para un tipo empírico discreto de medida Q (o de manera equivalente para cualquier medida de probabilidad Q ). Entonces se puede demostrar que, de manera bastante notable, para : ${\displaystyle {\mathcal {I}}_{\mathcal {C}}=\{1_{C}:C\in {\mathcal {C}}\}}$ ${\displaystyle L_{1}(Q)}$ ${\displaystyle r\geq 1}$

${\displaystyle N(\varepsilon ,{\mathcal {I}}_{\mathcal {C}},L_{r}(Q))\leq KV({\mathcal {C}})(4e)^{V({\mathcal {C}})}\varepsilon ^{-r(V({\mathcal {C}})-1)}}$

Considere además el casco convexo simétrico de un conjunto : siendo la colección de funciones de la forma con . Entonces sí ${\displaystyle {\mathcal {F}}}$ ${\displaystyle \operatorname {sconv} {\mathcal {F}}}$ ${\displaystyle \sum _{i=1}^{m}\alpha _{i}f_{i}}$ ${\displaystyle \sum _{i=1}^{m}|\alpha _{i}|\leq 1}$

${\displaystyle N\left(\varepsilon \|F\|_{Q,2},{\mathcal {F}},L_{2}(Q)\right)\leq C\varepsilon ^{-V}}$

lo siguiente es válido para el casco convexo de : ${\displaystyle {\mathcal {F}}}$

${\displaystyle \log N\left(\varepsilon \|F\|_{Q,2},\operatorname {sconv} {\mathcal {F}},L_{2}(Q)\right)\leq K\varepsilon ^{-{\frac {2V}{V+2}}}}$

La consecuencia importante de este hecho es que

${\displaystyle {\frac {2V}{V+2}}<2,}$

lo cual es suficiente para que la integral de entropía converja y, por lo tanto, la clase sea P -Donsker. ${\displaystyle \operatorname {sconv} {\mathcal {F}}}$

Finalmente se considera un ejemplo de una clase de subgrafo VC. Cualquier espacio vectorial de dimensión finita de funciones medibles es un subgrafo VC de índice menor o igual a . ${\displaystyle {\mathcal {F}}}$ ${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$ ${\displaystyle \dim({\mathcal {F}})+2}$

Prueba: toma puntos . Los vectores: ${\displaystyle n=\dim({\mathcal {F}})+2}$ ${\displaystyle (x_{1},t_{1}),\ldots ,(x_{n},t_{n})}$

${\displaystyle (f(x_{1}),\ldots ,f(x_{n}))-(t_{1},\ldots ,t_{n})}$

están en un subespacio n − 1 dimensional de R ⁿ . Tome a ≠ 0 , un vector que es ortogonal a este subespacio. Por lo tanto:

${\displaystyle \sum _{a_{i}>0}a_{i}(f(x_{i})-t_{i})=\sum _{a_{i}<0}(-a_{i})(f(x_{i})-t_{i}),\quad \forall f\in {\mathcal {F}}}$

Considere el conjunto . Este conjunto no se puede seleccionar ya que, si existe alguno , eso implicaría que el LHS es estrictamente positivo pero el RHS no es positivo. ${\displaystyle S=\{(x_{i},t_{i}):a_{i}>0\}}$ ${\displaystyle f}$ ${\displaystyle S=\{(x_{i},t_{i}):f(x_{i})>t_{i}\}}$

Existen generalizaciones de la noción de clase de subgrafo VC, por ejemplo, existe la noción de pseudodimensión. El lector interesado puede consultar. ^[4]

desigualdad de capital de riesgo

Se considera una configuración similar, que es más común para el aprendizaje automático . Sea un espacio característico y . Una función se llama clasificador. Sea un conjunto de clasificadores. De manera similar a la sección anterior, defina el coeficiente de ruptura (también conocido como función de crecimiento): ${\displaystyle {\mathcal {X}}}$ ${\displaystyle {\mathcal {Y}}=\{0,1\}}$ ${\displaystyle f:{\mathcal {X}}\to {\mathcal {Y}}}$ ${\displaystyle {\mathcal {F}}}$

${\displaystyle S({\mathcal {F}},n)=\max _{x_{1},\ldots ,x_{n}}|\{(f(x_{1}),\ldots ,f(x_{n})),f\in {\mathcal {F}}\}|}$

Tenga en cuenta aquí que hay una relación 1:1 entre cada una de las funciones y el conjunto en el que la función es 1. Por lo tanto, podemos definirlo como la colección de subconjuntos obtenidos del mapeo anterior para cada . Por lo tanto, en términos de la sección anterior el coeficiente de ruptura es precisamente ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle f\in {\mathcal {F}}}$

${\displaystyle \max _{x_{1},\ldots ,x_{n}}\Delta _{n}({\mathcal {C}},x_{1},\ldots ,x_{n})}$.

Esta equivalencia junto con el lema de Sauer implica que será polinomio en n , para n suficientemente grande , siempre que la colección tenga un índice VC finito. ${\displaystyle S({\mathcal {F}},n)}$ ${\displaystyle {\mathcal {C}}}$

Sea un conjunto de datos observado. Supongamos que los datos se generan mediante una distribución de probabilidad desconocida . Definir como la pérdida esperada 0/1 . Por supuesto, como se desconoce en general, no se tiene acceso a él . Sin embargo, el riesgo empírico , dado por: ${\displaystyle D_{n}=\{(X_{1},Y_{1}),\ldots ,(X_{n},Y_{m})\}}$ ${\displaystyle P_{XY}}$ ${\displaystyle R(f)=P(f(X)\neq Y)}$ ${\displaystyle P_{XY}}$ ${\displaystyle R(f)}$

${\displaystyle {\hat {R}}_{n}(f)={\dfrac {1}{n}}\sum _{i=1}^{n}\mathbb {I} (f(X_{i})\neq Y_{i})}$

ciertamente se puede evaluar. Entonces se tiene el siguiente teorema:

Teorema (Desigualdad VC)

Para la clasificación binaria y la función de pérdida 0/1 tenemos los siguientes límites de generalización:

${\displaystyle {\begin{aligned}P\left(\sup _{f\in {\mathcal {F}}}\left|{\hat {R}}_{n}(f)-R(f)\right|>\varepsilon \right)&\leq 8S({\mathcal {F}},n)e^{-n\varepsilon ^{2}/32}\\\mathbb {E} \left[\sup _{f\in {\mathcal {F}}}\left|{\hat {R}}_{n}(f)-R(f)\right|\right]&\leq 2{\sqrt {\dfrac {\log S({\mathcal {F}},n)+\log 2}{n}}}\end{aligned}}}$

En palabras, la desigualdad de VC dice que a medida que aumenta la muestra, siempre que tenga una dimensión de VC finita, el riesgo empírico 0/1 se convierte en un buen indicador del riesgo 0/1 esperado. Tenga en cuenta que ambos RHS de las dos desigualdades convergerán a 0, siempre que crezca polinomialmente en n . ${\displaystyle {\mathcal {F}}}$ ${\displaystyle S({\mathcal {F}},n)}$

La conexión entre este marco y el marco del Proceso Empírico es evidente. Aquí se trata de un proceso empírico modificado.

${\displaystyle \left|{\hat {R}}_{n}-R\right|_{\mathcal {F}}}$

pero no es sorprendente que las ideas sean las mismas. La prueba de la (primera parte de) la desigualdad VC se basa en la simetrización y luego se argumenta condicionalmente sobre los datos utilizando desigualdades de concentración (en particular la desigualdad de Hoeffding ). El lector interesado puede consultar el libro ^[5] Teoremas 12.4 y 12.5.

Referencias

1. Vapnik, Vladimir N (2000). La naturaleza de la teoría del aprendizaje estadístico . Ciencias de la Información y Estadística. Springer-Verlag . ISBN 978-0-387-98780-4.
2. van der Vaart, Aad W .; Wellner, Jon A. (2000). Convergencia débil y procesos empíricos: con aplicaciones a la estadística (2ª ed.). Saltador. ISBN 978-0-387-94640-5.
3. Devroye, L., Gyorfi, L. y Lugosi, G. Una teoría probabilística del reconocimiento de patrones. Matemáticas aplicadas discretas 73 , 192–194 (1997).
4. Pollard, David (1990).Procesos empíricos: teoría y aplicaciones. Serie de conferencias regionales NSF-CBMS sobre probabilidad y estadística Volumen 2. ISBN 978-0-940600-16-4.
5. Gyorfi, L.; Devroye, L.; Lugosi, G. (1996). Una teoría probabilística del reconocimiento de patrones (1ª ed.). Saltador. ISBN 978-0387946184.

• Ver referencias en artículos: Richard M. Dudley , procesos empíricos , Conjunto destrozado . ^{[ referencia circular ]}
• Bousquet, Olivier; Elisseeff, Andr´e (1 de marzo de 2002). "Estabilidad y Generalización". La revista de investigación sobre aprendizaje automático . 2 : 499–526. doi :10.1162/153244302760200704. S2CID  1157797 . Consultado el 10 de diciembre de 2022 .
• Vapnik, V.; Chervonenkis, A. (2004). "Sobre la convergencia uniforme de frecuencias relativas de eventos con respecto a sus probabilidades". Teoría probable. Aplica . 16 (2): 264–280. doi :10.1137/1116025.