Regularización de matrices

En el campo de la teoría del aprendizaje estadístico , la regularización matricial generaliza las nociones de regularización vectorial a los casos en los que el objeto que se va a aprender es una matriz. El propósito de la regularización es hacer cumplir las condiciones, por ejemplo, escasez o suavidad, que pueden producir funciones predictivas estables. Por ejemplo, en el marco vectorial más común, la regularización de Tikhonov optimiza sobre para encontrar un vector que sea una solución estable al problema de regresión. Cuando el sistema se describe mediante una matriz en lugar de un vector, este problema se puede escribir como donde la norma vectorial que impone una penalización de regularización en se ha extendido a una norma matricial en . $${\displaystyle \min _{x}\left\|Ax-y\right\|^{2}+\lambda \left\|x\right\|^{2}}$$ ${\displaystyle x}$ $${\displaystyle \min _{X}\left\|AX-Y\right\|^{2}+\lambda \left\|X\right\|^{2},}$$ ${\displaystyle x}$ ${\displaystyle X}$

La regularización de matrices tiene aplicaciones en la terminación de matrices , la regresión multivariable y el aprendizaje multitarea . Las ideas de selección de características y grupos también se pueden extender a las matrices, y estas se pueden generalizar al caso no paramétrico del aprendizaje de múltiples núcleos .

Definición básica

Considere una matriz que se aprenderá a partir de un conjunto de ejemplos, , donde va de a , y va de a . Sea cada matriz de entrada , y sea de tamaño . Un modelo general para la salida puede plantearse como donde el producto interno es el producto interno de Frobenius . Para diferentes aplicaciones, las matrices tendrán diferentes formas, ^[1] pero para cada una de estas el problema de optimización a inferir puede escribirse como donde define el error empírico para un dado , y es una penalización de regularización de matriz. La función generalmente se elige para que sea convexa y a menudo se selecciona para imponer escasez (usando -normas) y/o suavidad (usando -normas). Finalmente, está en el espacio de matrices con producto interno de Frobenius . ${\displaystyle W}$ ${\displaystyle S=(X_{i}^{t},y_{i}^{t})}$ ${\displaystyle i}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle t}$ ${\displaystyle 1}$ ${\displaystyle T}$ ${\displaystyle X_{i}}$ ${\displaystyle \in \mathbb {R} ^{DT}}$ ${\displaystyle W}$ ${\displaystyle D\times T}$ ${\displaystyle y}$ $${\displaystyle y_{i}^{t}=\left\langle W,X_{i}^{t}\right\rangle _{F},}$$ ${\displaystyle X_{i}}$ ${\displaystyle W}$ $${\displaystyle \min _{W\in {\mathcal {H}}}E(W)+R(W),}$$ ${\displaystyle E}$ ${\displaystyle W}$ ${\displaystyle R(W)}$ ${\displaystyle R(W)}$ ${\displaystyle \ell ^{1}}$ ${\displaystyle \ell ^{2}}$ ${\displaystyle W}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle \langle \dots \rangle _{F}}$

Aplicaciones generales

Completamiento de matriz

En el problema de compleción de matrices , la matriz toma la forma donde y son la base canónica en y . En este caso, la función del producto interno de Frobenius es seleccionar elementos individuales de la matriz . Por lo tanto, la salida es una muestra de entradas de la matriz . ${\displaystyle X_{i}^{t}}$ $${\displaystyle X_{i}^{t}=e_{t}\otimes e_{i}',}$$ ${\displaystyle (e_{t})_{t}}$ ${\displaystyle (e_{i}')_{i}}$ ${\displaystyle \mathbb {R} ^{T}}$ ${\displaystyle \mathbb {R} ^{D}}$ ${\displaystyle w_{i}^{t}}$ ${\displaystyle W}$ ${\displaystyle y}$ ${\displaystyle W}$

El problema de reconstrucción a partir de un pequeño conjunto de entradas muestreadas es posible solo bajo ciertas restricciones en la matriz, y estas restricciones pueden ser impuestas por una función de regularización. Por ejemplo, se podría suponer que es de bajo rango, en cuyo caso la penalización de regularización puede tomar la forma de una norma nuclear. ^[2] donde , con de a , son los valores singulares de . ${\displaystyle W}$ ${\displaystyle W}$ $${\displaystyle R(W)=\lambda \left\|W\right\|_{*}=\lambda \sum _{i}\left|\sigma _{i}\right|,}$$ ${\displaystyle \sigma _{i}}$ ${\displaystyle i}$ ${\displaystyle 1}$ ${\displaystyle \min D,T}$ ${\displaystyle W}$

Regresión multivariante

Los modelos utilizados en la regresión multivariante están parametrizados por una matriz de coeficientes. En el producto interno de Frobenius anterior, cada matriz es tal que la salida del producto interno es el producto escalar de una fila de la entrada con una columna de la matriz de coeficientes. La forma familiar de estos modelos es ${\displaystyle X}$ $${\displaystyle X_{i}^{t}=e_{t}\otimes x_{i}}$$ $${\displaystyle Y=XW+b}$$

Muchas de las normas vectoriales utilizadas en la regresión de una sola variable se pueden extender al caso multivariante. Un ejemplo es la norma de Frobenius al cuadrado, que se puede considerar como una norma que actúa sobre las entradas o sobre los valores singulares de la matriz: ${\displaystyle \ell ^{2}}$ $${\displaystyle R(W)=\lambda \left\|W\right\|_{F}^{2}=\lambda \sum _{i}\sum _{j}\left|w_{ij}\right|^{2}=\lambda \operatorname {Tr} \left(W^{*}W\right)=\lambda \sum _{i}\sigma _{i}^{2}.}$$

En el caso multivariado, el efecto de regularizar con la norma de Frobenius es el mismo que en el caso vectorial; los modelos muy complejos tendrán normas más grandes y, por lo tanto, serán más penalizados.

Aprendizaje multitarea

La configuración para el aprendizaje multitarea es casi la misma que la configuración para la regresión multivariante. La principal diferencia es que las variables de entrada también están indexadas por tarea (columnas de ). La representación con el producto interno de Frobenius es entonces ${\displaystyle Y}$ $${\displaystyle X_{i}^{t}=e_{t}\otimes x_{i}^{t}.}$$

El papel de la regularización matricial en este contexto puede ser el mismo que en la regresión multivariante, pero las normas matriciales también se pueden utilizar para acoplar problemas de aprendizaje entre tareas. En particular, observe que para el problema de optimización las soluciones correspondientes a cada columna de están desacopladas. Es decir, se puede encontrar la misma solución resolviendo el problema conjunto o resolviendo un problema de regresión aislado para cada columna. Los problemas se pueden acoplar añadiendo una penalización de regularización adicional en la covarianza de soluciones donde modela la relación entre tareas. Este esquema se puede utilizar tanto para imponer la similitud de soluciones entre tareas como para aprender la estructura específica de la similitud de tareas alternando entre optimizaciones de y . ^[3] Cuando se sabe que la relación entre tareas se encuentra en un gráfico, la matriz laplaciana del gráfico se puede utilizar para acoplar los problemas de aprendizaje. $${\displaystyle \min _{W}\left\|XW-Y\right\|_{2}^{2}+\lambda \left\|W\right\|_{2}^{2}}$$ ${\displaystyle Y}$ $${\displaystyle \min _{W,\Omega }\left\|XW-Y\right\|_{2}^{2}+\lambda _{1}\left\|W\right\|_{2}^{2}+\lambda _{2}\operatorname {Tr} \left(W^{T}\Omega ^{-1}W\right)}$$ ${\displaystyle \Omega }$ ${\displaystyle W}$ ${\displaystyle \Omega }$

Regularización espectral

La regularización por filtrado espectral se ha utilizado para encontrar soluciones estables a problemas como los que se han analizado anteriormente, abordando inversiones de matrices mal planteadas (véase, por ejemplo, la función de filtro para la regularización de Tikhonov ). En muchos casos, la función de regularización actúa sobre la entrada (o núcleo) para garantizar una inversa acotada eliminando pequeños valores singulares, pero también puede ser útil tener normas espectrales que actúen sobre la matriz que se va a aprender.

Existen varias normas matriciales que actúan sobre los valores singulares de la matriz. Entre los ejemplos más utilizados se encuentran las p-normas de Schatten , con p  = 1 o 2. Por ejemplo, la regularización de matrices con una 1-norma de Schatten, también llamada norma nuclear, se puede utilizar para imponer la escasez en el espectro de una matriz. Esto se ha utilizado en el contexto de la compleción de matrices cuando se cree que la matriz en cuestión tiene un rango restringido. ^[2] En este caso, el problema de optimización se convierte en: $${\displaystyle \min \left\|W\right\|_{*}~~{\text{ subject to }}~~W_{i,j}=Y_{ij}.}$$

La regularización espectral también se utiliza para aplicar una matriz de coeficientes de rango reducido en la regresión multivariante. ^[4] En este contexto, se puede encontrar una matriz de coeficientes de rango reducido manteniendo solo los valores singulares superiores, pero esto se puede ampliar para mantener cualquier conjunto reducido de valores singulares y vectores. ${\displaystyle n}$

Escasez estructurada

La optimización dispersa se ha convertido en el foco de interés de muchas investigaciones como una forma de encontrar soluciones que dependen de un pequeño número de variables (véase, por ejemplo, el método Lasso ). En principio, la escasez por entrada se puede imponer penalizando la norma por entrada de la matriz, pero la norma no es convexa. En la práctica, esto se puede implementar mediante la relajación convexa de la norma. Si bien la regularización por entrada con una norma encontrará soluciones con un pequeño número de elementos distintos de cero, la aplicación de una norma a diferentes grupos de variables puede imponer una estructura en la escasez de soluciones. ^[5] ${\displaystyle \ell ^{0}}$ ${\displaystyle \ell ^{0}}$ ${\displaystyle \ell ^{1}}$ ${\displaystyle \ell ^{1}}$ ${\displaystyle \ell ^{1}}$

El ejemplo más sencillo de escasez estructurada utiliza la norma con y : ${\displaystyle \ell _{p,q}}$ ${\displaystyle p=2}$ ${\displaystyle q=1}$ $${\displaystyle \left\|W\right\|_{2,1}=\sum _{i}\left\|w_{i}\right\|_{2}.}$$

Por ejemplo, la norma se utiliza en el aprendizaje multitarea para agrupar características en las distintas tareas, de modo que todos los elementos de una fila determinada de la matriz de coeficientes se puedan convertir en cero como grupo. ^[6] El efecto de agrupación se logra tomando la norma de cada fila y, a continuación, tomando la penalización total como la suma de estas normas por fila. Esta regularización da como resultado filas que tenderán a ser todas ceros o densas. El mismo tipo de regularización se puede utilizar para aplicar la escasez por columna tomando las normas de cada columna. ${\displaystyle \ell _{2,1}}$ ${\displaystyle \ell ^{2}}$ ${\displaystyle \ell ^{2}}$

De manera más general, la norma se puede aplicar a grupos arbitrarios de variables: donde el índice abarca todos los grupos de variables e indica la cardinalidad del grupo . ${\displaystyle \ell _{2,1}}$ $${\displaystyle R(W)=\lambda \sum _{g}^{G}{\sqrt {\sum _{j}^{|G_{g}|}\left|w_{g}^{j}\right|^{2}}}=\lambda \sum _{g}^{G}\left\|w_{g}\right\|_{g}}$$ ${\displaystyle g}$ ${\displaystyle |G_{g}|}$ ${\displaystyle g}$

Los algoritmos para resolver estos problemas de escasez de grupos extienden los métodos Lasso y Lasso de grupo más conocidos al permitir grupos superpuestos, por ejemplo, y se han implementado a través de búsqueda de coincidencias : ^[7] y métodos de gradiente proximal . ^[8] Al escribir el gradiente proximal con respecto a un coeficiente dado, , se puede ver que esta norma impone un umbral suave para todos los grupos ^[1] donde es la función indicadora para las normas de grupo . ${\displaystyle w_{g}^{i}}$ $${\displaystyle \operatorname {prox} _{\lambda ,R_{g}}\left(w_{g}\right)^{i}=\left(w_{g}^{i}-\lambda {\frac {w_{g}^{i}}{\left\|w_{g}\right\|_{g}}}\right)\mathbf {1} _{\|w_{g}\|_{g}\geq \lambda }.}$$ ${\displaystyle \mathbf {1} _{\|w_{g}\|_{g}\geq \lambda }}$ ${\displaystyle \geq \lambda }$

Por lo tanto, el uso de normas permite aplicar una estructura sencilla en la escasez de una matriz, ya sea por filas, por columnas o en bloques arbitrarios. Al aplicar normas de grupo en bloques en una regresión multivariada o multitarea, por ejemplo, es posible encontrar grupos de variables de entrada y de salida, de modo que los subconjuntos definidos de variables de salida (columnas de la matriz ) dependan del mismo conjunto disperso de variables de entrada. ${\displaystyle \ell _{2,1}}$ ${\displaystyle Y}$

Selección de kernel múltiple

Las ideas de escasez estructurada y selección de características se pueden extender al caso no paramétrico de aprendizaje de múltiples núcleos . ^[9] Esto puede ser útil cuando hay múltiples tipos de datos de entrada (color y textura, por ejemplo) con diferentes núcleos apropiados para cada uno, o cuando se desconoce el núcleo apropiado. Si hay dos núcleos, por ejemplo, con mapas de características y que se encuentran en espacios de Hilbert de núcleos de reproducción correspondientes , entonces se puede crear un espacio más grande, , como la suma de dos espacios: suponiendo independencia lineal en y . En este caso, la -norma es nuevamente la suma de normas: ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle {\mathcal {H_{A}}},{\mathcal {H_{B}}}}$ ${\displaystyle {\mathcal {H_{D}}}}$ $${\displaystyle {\mathcal {H_{D}}}:f=h+h';h\in {\mathcal {H_{A}}},h'\in {\mathcal {H_{B}}}}$$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \ell _{2,1}}$ $${\displaystyle \left\|f\right\|_{{\mathcal {H_{D}}},1}=\left\|h\right\|_{\mathcal {H_{A}}}+\left\|h'\right\|_{\mathcal {H_{B}}}}$$

Por lo tanto, al elegir una función de regularización matricial como este tipo de norma, es posible encontrar una solución que sea dispersa en términos de qué núcleos se utilizan, pero densa en el coeficiente de cada núcleo utilizado. El aprendizaje de múltiples núcleos también se puede utilizar como una forma de selección de variables no lineales o como una técnica de agregación de modelos (por ejemplo, tomando la suma de normas al cuadrado y relajando las restricciones de dispersión). Por ejemplo, cada núcleo puede tomarse como el núcleo gaussiano con un ancho diferente.

Véase también

• Regularización (matemáticas)

Referencias

1. Rosasco, Lorenzo; Poggio, Tomaso (diciembre de 2014). "Un recorrido de regularización por el aprendizaje automático". Notas de clase de MIT-9.520 (manuscrito).
2. Candès, Emmanuel J. ; Recht, Benjamin (2009). "Completado exacto de matrices mediante optimización convexa". Fundamentos de las matemáticas computacionales . 9 (6): 717–772. doi : 10.1007/s10208-009-9045-5 .
3. Zhang; Yeung (2012). "Una formulación convexa para el aprendizaje de relaciones de tareas en el aprendizaje multitarea". Actas de la Vigésima Sexta Conferencia sobre Incertidumbre en Inteligencia Artificial (UAI2010) . arXiv : 1203.3536 . Código Bibliográfico :2012arXiv1203.3536Z.
4. Izenman, Alan J. (1975). "Regresión de rango reducido para el modelo lineal multivariante". Revista de análisis multivariante . 5 (2): 248–264. doi : 10.1016/0047-259X(75)90042-1 .
5. Kakade; Shalev-Shwartz; Tewari (2012). "Técnicas de regularización para el aprendizaje con matrices". Revista de investigación en aprendizaje automático . 13 : 1865–1890.
6. Argyriou, A.; Evgeniou, T.; Pontil, M. (2008). "Aprendizaje de características multitarea convexas". Aprendizaje automático . 73 (3): 243–272. doi : 10.1007/s10994-007-5040-8 .
7. Huang; Zhang; Metaxas (2011). "Aprendizaje con escasez estructurada". Revista de investigación en aprendizaje automático . 12 : 3371–3412.
8. Chen, Xi; et al. (2012). "Método de suavizado de gradiente proximal para regresión dispersa estructurada general". Anales de estadística aplicada . 6 (2): 719–752. arXiv : 1005.4717 . doi : 10.1214/11-AOAS514 .
9. Sonnenburg; Ratsch; Schafer; Scholkopf (2006). "Aprendizaje de núcleos múltiples a gran escala". Revista de investigación en aprendizaje automático . 7 : 1531–1565.