La minimización de riesgos empíricos (ERM) es un principio de la teoría del aprendizaje estadístico que define una familia de algoritmos de aprendizaje y se utiliza para dar límites teóricos a su desempeño. La idea central es que no podemos saber exactamente qué tan bien funcionará un algoritmo en la práctica (el verdadero "riesgo") porque no conocemos la verdadera distribución de los datos con los que funcionará el algoritmo, pero podemos medir su rendimiento en un conjunto conocido de datos de entrenamiento (el riesgo "empírico").
Fondo
Considere la siguiente situación, que es un escenario general de muchos problemas de aprendizaje supervisado . Tenemos dos espacios de objetos y y me gustaría aprender una función (a menudo llamado hipótesis ) que genera un objeto, dado . Para ello, tenemos a nuestra disposición un conjunto de formación de ejemplos dónde es una entrada y es la respuesta correspondiente que deseamos obtener de .
Para decirlo de manera más formal, asumimos que existe una distribución de probabilidad conjunta encima y , y que el conjunto de entrenamiento consta de instancias dibujado iid de. Tenga en cuenta que el supuesto de una distribución de probabilidad conjunta nos permite modelar la incertidumbre en las predicciones (por ejemplo, a partir del ruido en los datos) porque no es una función determinista de , sino más bien una variable aleatoria con distribución condicional por un fijo .
También asumimos que se nos da una función de pérdida de valor real no negativa que mide qué tan diferente es la predicción de una hipótesis es del resultado verdadero El riesgo asociado a la hipótesisEntonces se define como la expectativa de la función de pérdida:
Una función de pérdida comúnmente utilizada en teoría es la función de pérdida 0-1 :.
El objetivo final de un algoritmo de aprendizaje es encontrar una hipótesis entre una clase fija de funciones por el cual el riesgo es mínimo:
Minimización de riesgos empíricos
En general, el riesgo no se puede calcular porque la distribución es desconocido para el algoritmo de aprendizaje (esta situación se conoce como aprendizaje agnóstico ). Sin embargo, podemos calcular una aproximación, llamada riesgo empírico , promediando la función de pérdida en el conjunto de entrenamiento:
El principio empírico de minimización del riesgo [1] establece que el algoritmo de aprendizaje debe elegir una hipótesis que minimiza el riesgo empírico:
Así, el algoritmo de aprendizaje definido por el principio ERM consiste en resolver el problema de optimización anterior .
Propiedades
Complejidad computacional
Se sabe que la minimización del riesgo empírico para un problema de clasificación con una función de pérdida de 0-1 es un problema NP-difícil incluso para una clase de funciones tan relativamente simple como los clasificadores lineales . [2] Sin embargo, se puede resolver de manera eficiente cuando el riesgo empírico mínimo es cero, es decir, los datos se pueden separar linealmente .
En la práctica, los algoritmos de aprendizaje automático se las arreglan empleando una aproximación convexa a la función de pérdida 0-1 (como la pérdida de bisagra para SVM ), que es más fácil de optimizar, o imponiendo supuestos en la distribución (y así dejar de ser algoritmos de aprendizaje agnósticos a los que se aplica el resultado anterior).
Ver también
Referencias
- ^ V. Vapnik (1992). [ http://papers.nips.cc/paper/506-principles-of-risk-minimization-for-learning-theory.pdf Principios de minimización de riesgos para la teoría del aprendizaje. ]
- ^ V. Feldman, V. Guruswami, P. Raghavendra y Yi Wu (2009). El aprendizaje agnóstico de monomios por medio espacio es difícil. (Consulte el artículo y las referencias que contiene)
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.