Minimización empírica del riesgo

Principio de la teoría del aprendizaje estadístico.

La minimización empírica del riesgo es un principio de la teoría del aprendizaje estadístico que define una familia de algoritmos de aprendizaje basados ​​en la evaluación del rendimiento de un conjunto de datos fijo y conocido. La idea central se basa en una aplicación de la ley de los grandes números ; más específicamente, no podemos saber exactamente qué tan bien funcionará un algoritmo predictivo en la práctica (es decir, el verdadero "riesgo") porque no conocemos la verdadera distribución de los datos, pero en cambio podemos estimar y optimizar el rendimiento del algoritmo en un conjunto conocido de datos de entrenamiento. El rendimiento sobre el conjunto conocido de datos de entrenamiento se denomina "riesgo empírico".

Fondo

La siguiente situación es un escenario general de muchos problemas de aprendizaje supervisado . Hay dos espacios de objetos y me gustaría aprender una función (a menudo llamada hipótesis ) que genera un objeto , dado . Para hacerlo, existe un conjunto de ejemplos de entrenamiento donde hay una entrada y la respuesta correspondiente que se desea . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle \ h:X\to Y}$ ${\displaystyle y\in Y}$ ${\displaystyle x\in X}$ ${\displaystyle n}$ ${\displaystyle \ (x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$ ${\displaystyle x_{i}\in X}$ ${\displaystyle y_{i}\in Y}$ ${\displaystyle h(x_{i})}$

Para decirlo más formalmente, suponiendo que existe una distribución de probabilidad conjunta sobre y y que el conjunto de entrenamiento consta de instancias extraídas de iid . El supuesto de una distribución de probabilidad conjunta permite modelar la incertidumbre en las predicciones (por ejemplo, del ruido en los datos) porque no es una función determinista de , sino más bien una variable aleatoria con distribución condicional para un valor fijo . ${\displaystyle P(x,y)}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle n}$ ${\displaystyle \ (x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$ ${\displaystyle P(x,y)}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle P(y|x)}$ ${\displaystyle x}$

También se supone que existe una función de pérdida de valor real no negativa que mide qué tan diferente es la predicción de una hipótesis del resultado real . Para tareas de clasificación, estas funciones de pérdida pueden ser reglas de puntuación . El riesgo asociado con la hipótesis se define entonces como la expectativa de la función de pérdida: ${\displaystyle L({\hat {y}},y)}$ ${\displaystyle {\hat {y}}}$ ${\displaystyle y}$ ${\displaystyle h(x)}$

${\displaystyle R(h)=\mathbf {E} [L(h(x),y)]=\int L(h(x),y)\,dP(x,y).}$

Una función de pérdida comúnmente utilizada en teoría es la función de pérdida 0-1 : . ${\displaystyle L({\hat {y}},y)={\begin{cases}1&{\mbox{ if }}\quad {\hat {y}}\neq y\\0&{\mbox{ if }}\quad {\hat {y}}=y\end{cases}}}$

El objetivo final de un algoritmo de aprendizaje es encontrar una hipótesis entre una clase fija de funciones para las cuales el riesgo sea mínimo: ${\displaystyle h^{*}}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle R(h)}$

${\displaystyle h^{*}={\underset {h\in {\mathcal {H}}}{\operatorname {arg\,min} }}\,{R(h)}.}$

Para problemas de clasificación, el clasificador de Bayes se define como el clasificador que minimiza el riesgo definido con la función de pérdida 0-1.

Minimización empírica del riesgo

En general, el riesgo no se puede calcular porque el algoritmo de aprendizaje desconoce la distribución (esta situación se conoce como aprendizaje agnóstico ^{[ cita necesaria ]} ). Sin embargo, dada una muestra de puntos de datos de entrenamiento de iid , podemos calcular una estimación , llamada riesgo empírico , calculando el promedio de la función de pérdida sobre el conjunto de entrenamiento; más formalmente, calculando la expectativa con respecto a la medida empírica : ${\displaystyle R(h)}$ ${\displaystyle P(x,y)}$

${\displaystyle \!R_{\text{emp}}(h)={\frac {1}{n}}\sum _{i=1}^{n}L(h(x_{i}),y_{i}).}$

El principio de minimización del riesgo empírico ^[1] establece que el algoritmo de aprendizaje debe elegir una hipótesis que minimice el riesgo empírico sobre la clase de hipótesis : ${\displaystyle {\hat {h}}}$ ${\displaystyle {\mathcal {H}}}$

${\displaystyle {\hat {h}}={\underset {h\in {\mathcal {H}}}{\operatorname {arg\,min} }}\,R_{\text{emp}}(h).}$

Así, el algoritmo de aprendizaje definido por el principio empírico de minimización de riesgos consiste en resolver el problema de optimización anterior .

Propiedades

Las garantías para el desempeño de la minimización empírica del riesgo dependen en gran medida de la clase de función seleccionada, así como de los supuestos distributivos realizados. ^[2] En general, los métodos sin distribución son demasiado toscos y no conducen a límites prácticos. Sin embargo, siguen siendo útiles para derivar propiedades asintóticas de algoritmos de aprendizaje, como la coherencia . En particular, los límites libres de distribución sobre el desempeño de la minimización empírica del riesgo dada una clase de función fija se pueden derivar utilizando límites sobre la complejidad VC de la clase de función.

Por simplicidad, considerando el caso de tareas de clasificación binaria, es posible acotar la probabilidad del clasificador seleccionado, siendo mucho peor que el mejor clasificador posible . Considere el riesgo definido sobre la clase de hipótesis con función de crecimiento dado un conjunto de datos de tamaño . Entonces, para cada : ^[3] ${\displaystyle \phi _{n}}$ ${\displaystyle \phi ^{*}}$ ${\displaystyle L}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {S}}({\mathcal {C}},n)}$ ${\displaystyle n}$ ${\displaystyle \epsilon >0}$

$${\displaystyle \mathbb {P} \left(L(\phi _{n})-L(\phi ^{*})\right)\leq {\mathcal {8}}S({\mathcal {C}},n)\exp\{-n\epsilon ^{2}/32\}}$$

Resultados similares se aplican a las tareas de regresión. ^[2] Estos resultados a menudo se basan en leyes uniformes de grandes números , que controlan la desviación del riesgo empírico del riesgo real, de manera uniforme en toda la clase de hipótesis. ^[3]

Resultados de imposibilidad

También es posible mostrar límites inferiores en el rendimiento del algoritmo si no se hacen suposiciones distributivas. ^[4] Esto a veces se conoce como el teorema del almuerzo gratis . Aunque un algoritmo de aprendizaje específico puede proporcionar el rendimiento asintóticamente óptimo para cualquier distribución, el rendimiento de la muestra finita siempre es deficiente para al menos una distribución de datos. Esto significa que ningún clasificador puede proporcionar el error para un tamaño de muestra determinado para todas las distribuciones. ^[3]

Específicamente, consideremos un tamaño de muestra y una regla de clasificación , existe una distribución con riesgo (lo que significa que es posible una predicción perfecta) tal que: ^[3] ${\displaystyle \epsilon >0}$ ${\displaystyle n}$ ${\displaystyle \phi _{n}}$ ${\displaystyle (X,Y)}$ ${\displaystyle L^{*}=0}$

$${\displaystyle \mathbb {E} L_{n}\geq 1/2-\epsilon .}$$

Además, es posible demostrar que la tasa de convergencia de un algoritmo de aprendizaje es deficiente para algunas distribuciones. Específicamente, dada una secuencia de números positivos decrecientes que convergen a cero, es posible encontrar una distribución tal que: ${\displaystyle a_{i}}$

$${\displaystyle \mathbb {E} L_{n}\geq a_{i}}$$

para todos . Este resultado muestra que no existen reglas de clasificación universalmente buenas, en el sentido de que la regla debe ser de baja calidad para al menos una distribución. ^[3] ${\displaystyle n}$

Complejidad computacional

Se sabe que la minimización empírica del riesgo para un problema de clasificación con una función de pérdida 0-1 es un problema NP-difícil incluso para una clase de funciones relativamente simple, como los clasificadores lineales . ^[5] Sin embargo, se puede resolver eficientemente cuando el riesgo empírico mínimo es cero, es decir, los datos son linealmente separables . ^{[ cita necesaria ]}

En la práctica, los algoritmos de aprendizaje automático abordan este problema empleando una aproximación convexa a la función de pérdida 0-1 (como la pérdida bisagra para SVM ), que es más fácil de optimizar, o imponiendo suposiciones sobre la distribución (y así dejar de ser agnóstico). algoritmos de aprendizaje a los que se aplica el resultado anterior). ${\displaystyle P(x,y)}$

En el caso de la convexificación, el lema de Zhang aumenta el exceso de riesgo del problema original utilizando el exceso de riesgo del problema convexificado. ^[6] Minimizar este último mediante optimización convexa también permite controlar el primero.

Minimización empírica inclinada del riesgo

La minimización del riesgo empírico inclinado es una técnica de aprendizaje automático que se utiliza para modificar funciones de pérdida estándar como el error al cuadrado, mediante la introducción de un parámetro de inclinación. Este parámetro ajusta dinámicamente el peso de los puntos de datos durante el entrenamiento, lo que permite que el algoritmo se centre en regiones o características específicas de la distribución de datos. La minimización empírica inclinada del riesgo es particularmente útil en escenarios con datos desequilibrados o cuando es necesario enfatizar errores en ciertas partes del espacio de predicción.

Ver también

• estimador m
• Estimación de máxima verosimilitud

Referencias

1. V. Vapnik (1992). Principios de minimización de riesgos para la teoría del aprendizaje.
2. Györfi, László; Kohler, Michael; Krzyzak, Adán; Camina, Harro (1 de diciembre de 2010). Una teoría de la regresión no paramétrica sin distribución (reimpresión en tapa blanda de la primera edición original). Nueva York: Springer. ISBN 978-1-4419-2998-3.
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. Devroye, Luc; Györfi, László; Lugosi, Gábor (1996). "Una teoría probabilística del reconocimiento de patrones". Modelado estocástico y probabilidad aplicada . doi :10.1007/978-1-4612-0711-5. ISSN  0172-4568.
5. V. Feldman, V. Guruswami, P. Raghavendra y Yi Wu (2009). El aprendizaje agnóstico de monomios mediante medios espacios es difícil. (Ver el artículo y las referencias que contiene)
6. "Notas de la conferencia 9 sobre Matemáticas del aprendizaje automático | Matemáticas del aprendizaje automático | Matemáticas". MIT OpenCourseWare . Consultado el 28 de octubre de 2023 .

Otras lecturas

• Vapnik, V. (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.