Clase de función aprendible

En la teoría del aprendizaje estadístico , una clase de funciones aprendibles es un conjunto de funciones para las cuales se puede diseñar un algoritmo que minimice asintóticamente el riesgo esperado , de forma uniforme sobre todas las distribuciones de probabilidad. El concepto de clases aprendibles está estrechamente relacionado con la regularización en el aprendizaje automático y proporciona justificaciones con muestras grandes para ciertos algoritmos de aprendizaje.

Si la verdadera relación entre${\displaystyle y}$y${\displaystyle x}$es${\displaystyle y\sim f^{*}(x)}$, luego seleccionando la función de pérdida apropiada,${\displaystyle f^{*}}$Siempre se puede expresar como el minimizador de la pérdida esperada en todas las funciones posibles. Es decir,

${\displaystyle f^{*}=\arg \min _{f\in {\mathcal {F}}^{*}}I_{P}(f)}$

Aquí dejamos${\displaystyle {\mathcal {F}}^{*}}$sea ​​la colección de todas las funciones posibles mapeo${\displaystyle {\mathcal {X}}}$sobre${\displaystyle {\mathcal {Y}}}$.${\displaystyle f^{*}}$puede interpretarse como el mecanismo real de generación de datos. Sin embargo, el teorema de que no hay almuerzo gratis nos dice que, en la práctica, con muestras finitas no podemos esperar buscar el minimizador de riesgo esperado sobre${\displaystyle {\mathcal {F}}^{*}}$. Por lo tanto, a menudo consideramos un subconjunto de${\displaystyle {\mathcal {F}}^{*}}$,${\displaystyle {\mathcal {F}}}$, para realizar búsquedas sobre. Al hacerlo, corremos el riesgo de que${\displaystyle f^{*}}$podría no ser un elemento de${\displaystyle {\mathcal {F}}}$Esta compensación puede expresarse matemáticamente como

En la descomposición anterior, parte${\displaystyle (b)}$no depende de los datos y no es estocástico. Describe cuán lejos están nuestras suposiciones (${\displaystyle {\mathcal {F}}}$) son de la verdad (${\displaystyle {\mathcal {F}}^{*}}$).${\displaystyle (b)}$será estrictamente mayor que 0 si hacemos suposiciones demasiado fuertes (${\displaystyle {\mathcal {F}}}$demasiado pequeño). Por otro lado, no imponer suficientes restricciones${\displaystyle {\mathcal {F}}}$hará que no sea aprendible y parte${\displaystyle (a)}$no convergerá estocásticamente a 0. Este es el conocido problema de sobreajuste en la literatura sobre estadística y aprendizaje automático.

Un buen ejemplo donde se utilizan clases aprendibles es la llamada regularización de Tikhonov en el espacio de Hilbert de núcleo reproductor (RKHS). Específicamente, sea${\displaystyle {\mathcal {F^{*}}}}$ser un RKHS y${\displaystyle ||\cdot ||_{2}}$ser la norma en${\displaystyle {\mathcal {F^{*}}}}$^{dado por su producto interno. En [ 3 ]} se muestra que${\displaystyle {\mathcal {F}}=\{f:||f||_{2}\leq \gamma \}}$es una clase aprendible para cualquier finito, positivo${\displaystyle \gamma }$El algoritmo de minimización empírica para la forma dual de este problema es:

${\displaystyle \arg \min _{f\in {\mathcal {F}}^{*}}\left\{\sum _{i=1}^{n}L(f(x_{i}),y_{i})+\lambda ||f||_{2}\right\}}$

Esto fue introducido por primera vez por Tikhonov ^{[ 4 ]} para resolver problemas mal condicionados. Muchos algoritmos de aprendizaje estadístico pueden expresarse de esta forma (por ejemplo, la conocida regresión de cresta ).

La disyuntiva entre${\displaystyle (a)}$y${\displaystyle (b)}$en ( 2 ) es geométricamente más intuitivo con la regularización de Tikhonov en RKHS. Podemos considerar una secuencia de${\displaystyle \{{\mathcal {F}}_{\gamma }\}}$, que son esencialmente bolas en ${\displaystyle {\mathcal {F^{*}}}}$con centros en 0. Como${\displaystyle \gamma }$se hace más grande,${\displaystyle {\mathcal {F}}_{\gamma }}$se acerca a todo el espacio, y${\displaystyle (b)}$es probable que se vuelva más pequeño. Sin embargo, también sufriremos tasas de convergencia más pequeñas en${\displaystyle (a)}$La forma de elegir un óptimo${\displaystyle \gamma }$En entornos con muestras finitas, generalmente se utiliza la validación cruzada .

Parte${\displaystyle (a)}$en ( 2 ) está estrechamente vinculado a la teoría de procesos empíricos en estadística, donde el riesgo empírico${\displaystyle \{\sum _{i=1}^{n}L(y_{i},f(x_{i})),f\in {\mathcal {F}}\}}$se conocen como procesos empíricos. ^{[ 5 ]} En este campo, la clase de función${\displaystyle {\mathcal {F}}}$que satisface la convergencia estocástica

se conocen como clases uniformes de Glivenko-Cantelli . Se ha demostrado que bajo ciertas condiciones de regularidad, las clases aprendibles y las clases uniformemente Glivenko-Cantelli son equivalentes. ^{[ 1 ]} Interacción entre${\displaystyle (a)}$y${\displaystyle (b)}$En la literatura estadística, a menudo se la conoce como la compensación entre sesgo y varianza .

Sin embargo, tenga en cuenta que en ^{[ 2 ]} los autores dieron un ejemplo de optimización convexa estocástica para un entorno general de aprendizaje donde la capacidad de aprendizaje no es equivalente a la convergencia uniforme .