stringtranslate.com

Mínimos cuadrados regularizados

Mínimos cuadrados regularizados ( RLS ) es una familia de métodos para resolver el problema de mínimos cuadrados mientras se utiliza la regularización para restringir aún más la solución resultante.

RLS 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 ordinario 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 forma única la solución.

La segunda razón para utilizar RLS surge cuando el modelo aprendido adolece de una generalización deficiente . RLS se puede utilizar en tales casos para mejorar la generalización del modelo restringiéndolo en el momento del entrenamiento. Esta restricción puede forzar que la solución sea "escasa" de alguna manera o que refleje otros conocimientos previos sobre el problema, como información sobre correlaciones entre características. Se puede llegar a una comprensión bayesiana de esto mostrando que los métodos RLS a menudo son equivalentes a aproximaciones en la solución del problema de mínimos cuadrados.

formulación general

Considere un entorno de aprendizaje dado por un espacio probabilístico . Denotemos un conjunto de entrenamiento de pares iid con respecto a . Sea una función de pérdida. Defina como el espacio de las funciones tal que el riesgo esperado:

Como normalmente se desconoce la distribución conjunta , se asume el riesgo empírico. Para mínimos cuadrados regularizados se introduce la función de pérdida de cuadrados:

Sin embargo, si las funciones provienen de un espacio relativamente no restringido, como el conjunto de funciones integrables al cuadrado en , este enfoque puede sobreajustar los datos de entrenamiento y conducir a una generalización deficiente. Por lo tanto, debería limitar 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 reproductor (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 del grano

Definición de RKHS

Un RKHS se puede definir mediante una función kernel simétrica definida positiva con la propiedad de reproducción:

completar

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 a la regresión del vector de soporte .

Núcleo arbitrario

El teorema del representante garantiza que la solución se puede escribir como:

El problema de minimización se puede expresar como:

Para tal función,

Se puede obtener el siguiente problema de minimización:

Como la suma de funciones convexas es convexa, la solución es única y su mínimo se puede encontrar estableciendo el gradiente con respecto a :

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. Sea una matriz, donde las filas son vectores de entrada, y un vector donde las entradas son las 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 residual de cuadrados . El segundo término es un término de regularización, no presente en OLS, que penaliza los valores grandes. Como se considera un problema suave de dimensiones finitas y es posible aplicar herramientas de cálculo estándar. Para minimizar la función objetivo, el gradiente se calcula con respecto a y se establece en 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 varianza mínima, según el teorema de Gauss-Markov . Por tanto, el término 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 de los valores es proporcional a y, por lo tanto, valores grandes de conducirán a una varianza más baja. Por lo tanto, manipular corresponde a un sesgo y una varianza de compensación. Para problemas con estimaciones de alta varianza, como casos con regresores relativamente pequeños o 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 raro que en el aprendizaje automático haya casos en los que , en cuyo caso el rango es deficiente y es necesario un valor distinto de cero para calcular .

Complejidad

El parámetro controla la invertibilidad de la matriz . Se pueden utilizar varios métodos para resolver el sistema lineal anterior, siendo probablemente la descomposición de Cholesky el método elegido, ya que la matriz es simétrica y definida positiva . La complejidad de este método es para entrenamiento y prueba. El costo es esencialmente el de calcular , 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 núcleo K en reproducción. En lugar de un núcleo lineal, se considera un mapa de características para algún 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 , donde , o el -ésimo componente de .

Este enfoque se conoce como el truco del kernel . Esta técnica puede simplificar significativamente las operaciones computacionales. Si es de alta dimensión, la informática puede ser bastante intensiva. Si se conoce la forma explícita de la función del núcleo, sólo necesitamos calcular y almacenar la matriz del núcleo .

De hecho, el espacio de Hilbert no necesita ser isomorfo y puede tener dimensiones infinitas. Esto se desprende del teorema de Mercer , que establece que una función nuclear definida positiva, simétrica y continua se puede expresar como

base ortonormal

Interpretación bayesiana

Los mínimos cuadrados pueden verse como una maximización de 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, al igual que la función objetivo de mínimos cuadrados. En este marco, se puede entender que los términos de regularización de RLS codifican anteriores en . Por ejemplo, la regularización de Tikhonov corresponde a una distribución anterior centrada en 0. Para ver esto, primero observe que el objetivo de MCO es proporcional a la función de probabilidad logarítmica cuando cada muestra se distribuye normalmente alrededor de . Luego observe que un prior normal centrado en 0 tiene una probabilidad logarítmica de la forma

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 que satisfacen las restricciones obtenidas de los datos, pero como 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 antecedentes diferentes. Consulte la lista a continuación para obtener más detalles.

Ejemplos específicos

Regresión de crestas (o regularización de Tikhonov)

Una elección particularmente común para la función de penalización es la norma al cuadrado , es decir,

regularización de Tikhonovregresión de crestas
matriz de covarianza

Cuando , es decir, en el caso de mínimos cuadrados ordinarios , la condición que hace que la matriz de covarianza muestral no tenga rango completo y, por lo tanto, no pueda invertirse 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 ordinario 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 garantiza 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 imparcial. Acepta sesgo para reducir la varianza y el error cuadrático medio .

regresión de lazo

El método de selección y contracción menos absoluta (LASSO) es otra opción popular. En la regresión de lazo , la función de penalización de lazo es la 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 de forma cerrada conveniente: en cambio, la solución generalmente se encuentra usando 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 con lazo y la regularización de Tikhonov es que la regresión con lazo obliga a que más entradas de sean iguales a 0 de lo que serían de otro modo. Por el contrario, si bien la regularización de Tikhonov obliga a que las entradas de sean pequeñas, no obliga a que más de ellas sean 0 de lo que serían de otro modo. Por lo tanto, la regularización LASSO es más apropiada que la regularización de Tikhonov en los casos en los que esperamos que el número de entradas de distintas de cero sea pequeño, y la regularización de Tikhonov es más apropiada cuando esperamos que las entradas de generalmente sean pequeñas 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 mayor precisión en el caso de variables altamente correlacionadas. [1] En otro caso, LASSO selecciona como máximo las 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

normaconvexa

Red elástica

Para cualquier no negativo y el objetivo tiene la siguiente forma:

Sea , entonces la solución del problema de minimización se describe como:

Considérelo como una función de penalización de Elastic Net.

Cuando , la red elástica se convierte en regresión de crestas, 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 tomando las propiedades tanto de regresión de lazo como de regresión de 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 viene dada por:

[2]

Si y están altamente correlacionados ( ), los vectores de peso están muy cerca. En el caso de muestras correlacionadas negativamente ( ) , se pueden tomar las muestras . En resumen, para variables altamente correlacionadas los vectores de peso tienden a ser iguales hasta un signo en el caso de 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 una, el anterior correspondiente si es simple y las formas de calcular la solución al problema de optimización resultante.

Ver también

Referencias

  1. ^ Tibshirani Robert (1996). "Regresión, contracción y selección mediante el lazo" (PDF) . Revista de la Royal Statistical Society, Serie B. 58 : págs. 266–288.
  2. ^ Hui, Zou ; Hastie, Trevor (2003). «Regularización y Selección de Variables vía Red Elástica» (PDF) . Revista de la Royal Statistical Society, Serie B. 67 (2): págs. 301–320.

enlaces externos