Los mínimos cuadrados regularizados ( RLS ) son una familia de métodos para resolver el problema de mínimos cuadrados mientras se usa la regularización para restringir aún más la solución resultante.
El SPI se utiliza por dos razones principales. El primero surge cuando el número de variables en el sistema lineal excede el número de observaciones. En tales situaciones, el problema de mínimos cuadrados ordinarios está mal planteado y, por lo tanto, es imposible de ajustar porque el problema de optimización asociado tiene infinitas soluciones. RLS permite la introducción de restricciones adicionales que determinan de manera única la solución.
La segunda razón por la que se utiliza RLS ocurre cuando el número de variables no excede el número de observaciones, pero el modelo aprendido adolece de una mala generalización . RLS se puede utilizar en tales casos para mejorar la generalización del modelo al restringirlo en el momento del entrenamiento. Esta restricción puede obligar a la solución a ser "escasa" de alguna manera o reflejar otros conocimientos previos sobre el problema, como información sobre correlaciones entre características. A Bayesiano comprensión de este se puede llegar por lo que demuestra que los métodos de RLS a menudo son equivalentes a distribuciones previas en la solución para el problema de mínimos cuadrados.
Formulación general
Considere un entorno de aprendizaje dado por un espacio probabilístico , . Dejar denotar un conjunto de entrenamiento de pares iid con respecto a . Dejarser una función de pérdida. Definir como el espacio de las funciones tal que el riesgo esperado:
está bien definido. El objetivo principal es minimizar el riesgo esperado:
Dado que el problema no se puede resolver exactamente, es necesario especificar cómo medir la calidad de una solución. Un buen algoritmo de aprendizaje debería proporcionar un estimador con un pequeño riesgo.
Como la distribución conjunta normalmente se desconoce, se asume el riesgo empírico. Para mínimos cuadrados regularizados se introduce la función de pérdida cuadrada:
Sin embargo, si las funciones provienen de un espacio relativamente libre, como el conjunto de funciones integrables cuadradas en , este enfoque puede sobreajustarse a los datos de entrenamiento y conducir a una mala generalización. Por lo tanto, debería restringir o penalizar de alguna manera la complejidad de la función.. En RLS, esto se logra eligiendo funciones de un espacio de Hilbert del núcleo de reproducción (RKHS), y agregando un término de regularización a la función objetivo, proporcional a la norma de la función en :
Formulación de grano
Definición de RKHS
Un RKHS puede definirse mediante una función de núcleo simétrica positiva definida con la propiedad de reproducción:
dónde . El RKHS para un kernelConsiste en completar el espacio de funciones abarcadas por: , donde todos son números reales. Algunos núcleos de uso común incluyen el núcleo lineal, que induce el espacio de funciones lineales:
el núcleo polinomial, que induce el espacio de funciones polinomiales de orden :
y el kernel gaussiano:
Tenga en cuenta que para una función de pérdida arbitraria , este enfoque define una clase general de algoritmos denominada regularización de Tikhonov. Por ejemplo, el uso de la pérdida de bisagra conduce al algoritmo de la máquina de vectores de soporte , y el uso de la pérdida insensible a épsilon conduce al soporte de la regresión vectorial .
Kernel arbitrario
El teorema del representador garantiza que la solución se puede escribir como:
- para algunos .
El problema de minimización se puede expresar como:
- ,
donde, con algún abuso de notación, el entrada de la matriz del núcleo (a diferencia de la función del kernel ) es .
Para tal función,
Se puede obtener el siguiente problema de minimización:
- .
Como la suma de las funciones convexas es convexa, la solución es única y su mínimo se puede encontrar estableciendo el gradiente wrt a :
- ,
dónde .
Complejidad
La complejidad del entrenamiento es básicamente el costo de calcular la matriz del núcleo más el costo de resolver el sistema lineal que es aproximadamente . El cálculo de la matriz del núcleo para el núcleo lineal o gaussiano es. La complejidad de las pruebas es.
Predicción
La predicción en un nuevo punto de prueba es:
Núcleo lineal
Por conveniencia, se introduce una notación vectorial. Dejar frijol matriz, donde las filas son vectores de entrada, y a vector donde las entradas son salidas correspondientes. En términos de vectores, la matriz del núcleo se puede escribir como. La función de aprendizaje se puede escribir como:
Aquí definimos . La función objetivo se puede reescribir como:
El primer término es la función objetivo de la regresión de mínimos cuadrados ordinarios (MCO), correspondiente a la suma de cuadrados residual . El segundo término es un término de regularización, no presente en OLS, que penaliza a grandesvalores. Como se considera un problema de dimensión finita uniforme y es posible aplicar herramientas de cálculo estándar. Para minimizar la función objetivo, el gradiente se calcula con respecto a y ponerlo a cero:
Esta solución se parece mucho a la de la regresión lineal estándar, con un término adicional . Si se cumplen los supuestos de la regresión MCO, la solución, con , es un estimador insesgado y es el estimador insesgado lineal de mínima varianza, de acuerdo con el teorema de Gauss-Markov . El terminopor lo tanto conduce a una solución sesgada; sin embargo, también tiende a reducir la varianza. Esto es fácil de ver, ya que la matriz de covarianza del-valores es proporcional a , y por lo tanto grandes valores de conducirá a una menor variación. Por tanto, manipulandocorresponde al sesgo de compensación y la varianza. Para problemas con alta varianza estimaciones, como los casos con relativamente pequeñas o con regresores correlacionados, la precisión de predicción óptima se puede obtener utilizando un valor distinto de cero e introduciendo así algún sesgo para reducir la varianza. Además, no es infrecuente en el aprendizaje automático tener casos en los que, en ese caso tiene un rango deficiente y un valor distinto de cero es necesario calcular .
Complejidad
El parámetro controla la invertibilidad de la matriz . Se pueden usar varios métodos para resolver el sistema lineal anterior, siendo probablemente la descomposición de Cholesky el método de elección, ya que la matrizes simétrica y definida positiva . La complejidad de este método es para entrenamiento y para las pruebas. El costo es esencialmente el de la informática , mientras que el cálculo inverso (o más bien la solución del sistema lineal) es aproximadamente .
Mapas de características y teorema de Mercer
En esta sección se mostrará cómo extender RLS a cualquier tipo de kernel de reproducción K. En lugar de kernel lineal, se considera un mapa de características. por un poco de espacio de Hilbert , llamado espacio de características. En este caso, el núcleo se define como: La matriz ahora se reemplaza por la nueva matriz de datos , dónde , o el -th componente de la .
Significa que para un conjunto de entrenamiento dado . Por tanto, la función objetivo se puede escribir como:
Este enfoque se conoce como el truco del kernel . Esta técnica puede simplificar significativamente las operaciones computacionales. Si es de alta dimensión, informática puede ser bastante intensivo. Si se conoce la forma explícita de la función del kernel, solo necesitamos calcular y almacenar la matriz del núcleo .
De hecho, el espacio de Hilbert no necesita ser isomorfo para y puede ser de dimensión infinita. Esto se sigue del teorema de Mercer , que establece que una función de núcleo definida positiva, simétrica y continua se puede expresar como:
dónde forman una base ortonormal para, y . Si se definen mapas de características con componentes , resulta que . Esto demuestra que cualquier núcleo puede asociarse con un mapa de características y que RLS generalmente consiste en RLS lineal realizado en algún espacio de características posiblemente de mayor dimensión. Si bien el teorema de Mercer muestra cómo un mapa de características que se puede asociar con un kernel, de hecho, se pueden asociar múltiples mapas de características con un kernel de reproducción dado. Por ejemplo, el mapa satisface la propiedad para un kernel de reproducción arbitraria.
Interpretación bayesiana
Los mínimos cuadrados pueden verse como una maximización de la probabilidad bajo el supuesto de residuos distribuidos normalmente. Esto se debe a que el exponente de la distribución gaussiana es cuadrático en los datos, y también lo es la función objetivo de mínimos cuadrados. En este marco, los términos de regularización de RLS pueden entenderse como codificación previa en. Por ejemplo, la regularización de Tikhonov corresponde a una distribución anterior enque está centrado en 0. Para ver esto, primero tenga en cuenta que el objetivo de MCO es proporcional a la función logarítmica de verosimilitud cuando cada muestra se distribuye normalmente alrededor . Luego observe que una previa normal centrado en 0 tiene una probabilidad logarítmica de la forma
dónde y son constantes que dependen de la varianza del anterior y son independientes de . Por lo tanto, minimizar el logaritmo de la probabilidad multiplicada por el anterior equivale a minimizar la suma de la función de pérdida de MCO y el término de regularización de regresión de cresta.
Esto da una interpretación más intuitiva de por qué la regularización de Tikhonov conduce a una solución única al problema de mínimos cuadrados: hay infinitos vectores satisfaciendo las restricciones obtenidas de los datos, pero dado que llegamos al problema con una creencia previa de que se distribuye normalmente alrededor del origen, terminaremos eligiendo una solución con esta restricción en mente.
Otros métodos de regularización corresponden a diferentes anteriores. Consulte la lista a continuación para obtener más detalles.
Ejemplos específicos
Regresión de crestas (o regularización de Tikhonov)
Una opción particularmente común para la función de penalización es el cuadrado norma , es decir,
Los nombres más comunes para esto se denominan regularización de Tikhonov y regresión de crestas . Admite una solución de forma cerrada para:
El nombre de regresión de la cresta alude al hecho de que la término agrega entradas positivas a lo largo de la "cresta" diagonal de la matriz de covarianza de muestra .
Cuándo , es decir, en el caso de mínimos cuadrados ordinarios , la condición de queprovoca la matriz de covarianza de la muestra no tener rango completo y, por lo tanto, no se puede invertir para producir una solución única. Esta es la razón por la que puede haber una infinidad de soluciones al problema de mínimos cuadrados ordinarios cuando. Sin embargo cuando, es decir, cuando se utiliza la regresión de crestas, la adición de a la matriz de covarianza de la muestra asegura que todos sus valores propios serán estrictamente mayores que 0. En otras palabras, se vuelve invertible y la solución se vuelve única.
En comparación con los mínimos cuadrados ordinarios, la regresión de crestas no es insesgada. Acepta poco sesgo para reducir la varianza y el error cuadrático medio , y ayuda a mejorar la precisión de la predicción. Por lo tanto, el estimador de crestas produce soluciones más estables al reducir los coeficientes, pero adolece de la falta de sensibilidad a los datos.
Regresión de lazo
El método de selección y contracción mínima absoluta (LASSO) es otra opción popular. En la regresión de lazo , la función de penalización de lazo es el norma , es decir
Tenga en cuenta que la función de penalización del lazo es convexa pero no estrictamente convexa. A diferencia de la regularización de Tikhonov , este esquema no tiene una solución conveniente de forma cerrada: en cambio, la solución generalmente se encuentra utilizando programación cuadrática o métodos de optimización convexa más generales , así como mediante algoritmos específicos como el algoritmo de regresión de ángulo mínimo .
Una diferencia importante entre la regresión de lazo y la regularización de Tikhonov es que la regresión de lazo fuerza más entradas de para ser realmente igual a 0 de lo que sería de otra manera. Por el contrario, mientras que la regularización de Tikhonov fuerza la entrada depara ser pequeño, no obliga a que más de ellos sean 0 de lo que sería de otra manera. Por lo tanto, la regularización LASSO es más apropiada que la regularización de Tikhonov en los casos en los que esperamos el número de entradas distintas de cero de ser pequeño, y la regularización de Tikhonov es más apropiada cuando esperamos que las entradas de generalmente será pequeño pero no necesariamente cero. Cuál de estos regímenes es más relevante depende del conjunto de datos específicos disponibles.
Además de la selección de funciones descrita anteriormente, LASSO tiene algunas limitaciones. La regresión de crestas proporciona una mejor precisión en el casopara variables altamente correlacionadas. [1] En otro caso,, LASSO selecciona como máximo variables. Además, LASSO tiende a seleccionar algunas variables arbitrarias de un grupo de muestras altamente correlacionadas, por lo que no hay efecto de agrupación.
ℓ 0 Penalización
La forma más extrema de imponer la escasez es decir que la magnitud real de los coeficientes de no importa; más bien, lo único que determina la complejidad dees el número de entradas distintas de cero. Esto corresponde a la configuración ser el ℓ 0 {\ Displaystyle \ ell _ {0}} norma de. Esta función de regularización, aunque atractiva por la escasez que garantiza, es muy difícil de resolver porque hacerlo requiere la optimización de una función que ni siquiera es débilmente convexa . La regresión de lazo es la relajación mínima posible de penalización que produce un problema de optimización débilmente convexo.
Red elástica
Para cualquier no negativo y el objetivo tiene la siguiente forma:
Dejar , entonces la solución del problema de minimización se describe como:
- para algunos .
Considerar como una función de penalización de Elastic Net.
Cuándo , la red elástica se convierte en regresión de la cresta, mientras que se convierte en Lasso. La función de penalización de Elastic Net no tiene la primera derivada en 0 y es estrictamente convexa teniendo las propiedades tanto lasso de regresión y regresión cresta .
Una de las principales propiedades de Elastic Net es que puede seleccionar grupos de variables correlacionadas. La diferencia entre los vectores de peso de las muestras. y es dado por:
- , dónde . [2]
Si y están altamente correlacionados ), los vectores de peso están muy cerca. En el caso de muestras correlacionadas negativamente () Las muestras puede ser tomado. En resumen, para las variables altamente correlacionadas, los vectores de ponderación tienden a ser iguales hasta un signo en el caso de las variables correlacionadas negativamente.
Lista parcial de métodos RLS
La siguiente es una lista de posibles opciones de la función de regularización. , junto con el nombre de cada uno, el previo correspondiente si es sencillo, y las formas de calcular la solución al problema de optimización resultante.
Nombre | Función de regularización | Correspondiente anterior | Métodos para resolver |
---|---|---|---|
Regularización de Tikhonov | Normal | Forma cerrada | |
Regresión de lazo | Laplace | Descenso de gradiente proximal , regresión de ángulo mínimo | |
castigo | - | Selección hacia adelante , eliminación hacia atrás , uso de anteriores como picos y losas | |
Redes elásticas | Mezcla normal y de Laplace | Descenso de gradiente proximal | |
Regularización de variación total | - | Método Split-Bregman , entre otros |
Ver también
- Mínimos cuadrados
- Regularización en matemáticas.
- Error de generalización , una de las razones por las que se utiliza la regularización.
- Regularización de Tikhonov
- Regresión de lazo
- Regularización de red elástica
- Regresión de ángulo mínimo
Referencias
- ^ Tibshirani Robert (1996). "Contracción de regresión y selección a través del lazo" (PDF) . Revista de la Sociedad Real de Estadística, Serie B . 58 : págs. 266–288.
- ^ Hui, Zou ; Hastie, Trevor (2003). "Regularización y selección de variables vía Elastic Net" (PDF) . Revista de la Sociedad Real de Estadística, Serie B . 67 (2): págs. 301–320.
enlaces externos
- http://www.stanford.edu/~hastie/TALKS/enet_talk.pdf Regularización y selección de variables a través de Elastic Net (presentación)
- Mínimos cuadrados regularizados y máquinas de vectores de soporte (presentación)
- Mínimos cuadrados regularizados (presentación)