Regularización de variedades

En el aprendizaje automático , la regularización de variedades es una técnica para usar la forma de un conjunto de datos para restringir las funciones que se deben aprender en ese conjunto de datos. En muchos problemas de aprendizaje automático, los datos que se deben aprender no cubren todo el espacio de entrada. Por ejemplo, un sistema de reconocimiento facial puede no necesitar clasificar ninguna imagen posible, sino solo el subconjunto de imágenes que contienen caras. La técnica de aprendizaje de variedades supone que el subconjunto relevante de datos proviene de una variedad , una estructura matemática con propiedades útiles. La técnica también supone que la función que se debe aprender es suave : no es probable que los datos con diferentes etiquetas estén juntos, por lo que la función de etiquetado no debería cambiar rápidamente en áreas donde es probable que haya muchos puntos de datos. Debido a esta suposición, un algoritmo de regularización de variedades puede usar datos sin etiquetar para informar dónde se permite que la función aprendida cambie rápidamente y dónde no, utilizando una extensión de la técnica de regularización de Tikhonov . Los algoritmos de regularización de variedades pueden extender los algoritmos de aprendizaje supervisado en entornos de aprendizaje semisupervisado y aprendizaje transductivo , donde hay datos no etiquetados disponibles. La técnica se ha utilizado para aplicaciones que incluyen imágenes médicas, imágenes geográficas y reconocimiento de objetos.

La regularización de variedades es un tipo de regularización , una familia de técnicas que reduce el sobreajuste y garantiza que un problema esté bien planteado al penalizar las soluciones complejas. En particular, la regularización de variedades extiende la técnica de regularización de Tikhonov aplicada a los espacios de Hilbert de núcleo reproductor (RKHS). Bajo la regularización de Tikhonov estándar en RKHS, un algoritmo de aprendizaje intenta aprender una función de entre un espacio de hipótesis de funciones . El espacio de hipótesis es un RKHS, lo que significa que está asociado con un núcleo , y por lo tanto cada función candidata tiene una norma , que representa la complejidad de la función candidata en el espacio de hipótesis. Cuando el algoritmo considera una función candidata, tiene en cuenta su norma para penalizar las funciones complejas. ${\estilo de visualización f}$${\displaystyle {\mathcal {H}}}$ ${\estilo de visualización K}$${\estilo de visualización f}$ ${\displaystyle \left\|f\right\|_{K}}$

Formalmente, dado un conjunto de datos de entrenamiento etiquetados con y una función de pérdida , un algoritmo de aprendizaje que utilice la regularización de Tikhonov intentará resolver la expresión ${\displaystyle (x_{1},y_{1}),\ldots ,(x_{\ell },y_{\ell })}$${\displaystyle x_{i}\in X,y_{i}\in Y}$ ${\displaystyle V}$

${\displaystyle {\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }V(f(x_{i}),y_{i})+\gamma \left\|f\right\|_{K}^{2}}$

donde es un hiperparámetro que controla en qué medida el algoritmo preferirá funciones más simples sobre funciones que se ajusten mejor a los datos. ${\displaystyle \gamma }$

La regularización de variedades agrega un segundo término de regularización, el regularizador intrínseco , al regularizador ambiental utilizado en la regularización estándar de Tikhonov. Bajo el supuesto de variedad en el aprendizaje automático, los datos en cuestión no provienen de todo el espacio de entrada , sino de una variedad no lineal . La geometría de esta variedad, el espacio intrínseco, se utiliza para determinar la norma de regularización. ^[1]${\displaystyle X}$ ${\displaystyle M\subset X}$

Hay muchas opciones posibles para el regularizador intrínseco . Muchas opciones naturales involucran el gradiente en la variedad , que puede proporcionar una medida de cuán suave es una función objetivo. Una función suave debería cambiar lentamente donde los datos de entrada son densos; es decir, el gradiente debería ser pequeño donde la densidad de probabilidad marginal , la densidad de probabilidad de un punto de datos extraído aleatoriamente que aparece en , es grande. Esto da una opción apropiada para el regularizador intrínseco: ${\displaystyle \left\|f\right\|_{I}}$ ${\displaystyle \nabla _{M}}$${\displaystyle \nabla _{M}f(x)}$ ${\displaystyle {\mathcal {P}}_{X}(x)}$${\displaystyle x}$

${\displaystyle \left\|f\right\|_{I}^{2}=\int _{x\in M}\left\|\nabla _{M}f(x)\right\|^{2}\,d{\mathcal {P}}_{X}(x)}$

En la práctica, esta norma no se puede calcular directamente porque se desconoce la distribución marginal, pero se puede estimar a partir de los datos proporcionados. ${\displaystyle {\mathcal {P}}_{X}}$

Cuando las distancias entre los puntos de entrada se interpretan como un gráfico, entonces la matriz laplaciana del gráfico puede ayudar a estimar la distribución marginal. Suponga que los datos de entrada incluyen ejemplos etiquetados (pares de una entrada y una etiqueta ) y ejemplos no etiquetados (entradas sin etiquetas asociadas). Defina como una matriz de pesos de aristas para un gráfico, donde es una medida de distancia entre los puntos de datos y . Defina como una matriz diagonal con y como la matriz laplaciana . Luego, a medida que aumenta el número de puntos de datos , converge al operador de Laplace-Beltrami , que es la divergencia del gradiente . ^{[2] [3]} Luego, si es un vector de los valores de en los datos, , se puede estimar la norma intrínseca: ${\displaystyle \ell }$${\displaystyle x}$${\displaystyle y}$${\displaystyle u}$${\displaystyle W}$${\displaystyle W_{ij}}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle D}$${\displaystyle D_{ii}=\sum _{j=1}^{\ell +u}W_{ij}}$${\displaystyle L}$${\displaystyle D-W}$${\displaystyle \ell +u}$${\displaystyle L}$ ${\displaystyle \Delta _{M}}$${\displaystyle \nabla _{M}}$${\displaystyle \mathbf {f} }$${\displaystyle f}$${\displaystyle \mathbf {f} =[f(x_{1}),\ldots ,f(x_{l+u})]^{\mathrm {T} }}$

${\displaystyle \left\|f\right\|_{I}^{2}={\frac {1}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f} }$

A medida que aumenta el número de puntos de datos , esta definición empírica de converge a la definición cuando se conoce. ^[1]${\displaystyle \ell +u}$${\displaystyle \left\|f\right\|_{I}^{2}}$${\displaystyle {\mathcal {P}}_{X}}$

Utilizando los pesos y para los regularizadores ambientales e intrínsecos, la expresión final a resolver queda: ${\displaystyle \gamma _{A}}$${\displaystyle \gamma _{I}}$

${\displaystyle {\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }V(f(x_{i}),y_{i})+\gamma _{A}\left\|f\right\|_{K}^{2}+{\frac {\gamma _{I}}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f} }$

Al igual que con otros métodos de kernel , puede ser un espacio de dimensión infinita, por lo que si la expresión de regularización no se puede resolver explícitamente, es imposible buscar una solución en todo el espacio. En cambio, un teorema de representación muestra que bajo ciertas condiciones en la elección de la norma , la solución óptima debe ser una combinación lineal del kernel centrado en cada uno de los puntos de entrada: para algunos pesos , ${\displaystyle {\mathcal {H}}}$${\displaystyle \left\|f\right\|_{I}}$${\displaystyle f^{*}}$${\displaystyle \alpha _{i}}$

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell +u}\alpha _{i}K(x_{i},x)}$

Utilizando este resultado, es posible buscar la solución óptima buscando en el espacio de dimensión finita definido por las posibles opciones de . ^[1]${\displaystyle f^{*}}$${\displaystyle \alpha _{i}}$

La idea más allá del laplaciano gráfico es usar vecinos para estimar el laplaciano. Este método es similar a los métodos de promedio local , que se sabe que escalan mal en problemas de alta dimensión. De hecho, se sabe que el laplaciano gráfico sufre la maldición de la dimensionalidad . ^[2] Afortunadamente, es posible aprovechar la suavidad esperada de la función para estimar gracias a un análisis funcional más avanzado. Este método consiste en estimar el operador laplaciano gracias a las derivadas del kernel leyendo donde denota las derivadas parciales de acuerdo con la coordenada j -ésima de la primera variable. ^[4] Este segundo enfoque de la norma laplaciana se pone en relación con los métodos sin malla , que contrastan con el método de diferencias finitas en PDE. ${\displaystyle \partial _{1,j}K(x_{i},x)}$${\displaystyle \partial _{1,j}}$

La regularización de variedades puede extender una variedad de algoritmos que pueden expresarse utilizando la regularización de Tikhonov, eligiendo una función de pérdida y un espacio de hipótesis adecuados . Dos ejemplos comúnmente utilizados son las familias de máquinas de vectores de soporte y algoritmos de mínimos cuadrados regularizados . (Los mínimos cuadrados regularizados incluyen el algoritmo de regresión de cresta; los algoritmos relacionados de LASSO y la regularización de red elástica pueden expresarse como máquinas de vectores de soporte. ^{[5] [6]} ) Las versiones extendidas de estos algoritmos se denominan Mínimos Cuadrados Regularizados Laplacianos (abreviados LapRLS) y Máquinas de Vectores de Soporte Laplacianos (LapSVM), respectivamente. ^[1]${\displaystyle V}$${\displaystyle {\mathcal {H}}}$

Los mínimos cuadrados regularizados (RLS) son una familia de algoritmos de regresión : algoritmos que predicen un valor para sus entradas , con el objetivo de que los valores predichos sean cercanos a las etiquetas verdaderas de los datos. En particular, RLS está diseñado para minimizar el error cuadrático medio entre los valores predichos y las etiquetas verdaderas, sujeto a regularización. La regresión de cresta es una forma de RLS; en general, RLS es lo mismo que la regresión de cresta combinada con el método kernel . ^{[ cita requerida ]} El enunciado del problema para RLS resulta de elegir la función de pérdida en la regularización de Tikhonov como el error cuadrático medio: ${\displaystyle y=f(x)}$${\displaystyle x}$${\displaystyle V}$

${\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }(f(x_{i})-y_{i})^{2}+\gamma \left\|f\right\|_{K}^{2}}$

Gracias al teorema del representador , la solución se puede escribir como una suma ponderada del kernel evaluado en los puntos de datos:

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell }\alpha _{i}^{*}K(x_{i},x)}$

y resolviendo obtenemos: ${\displaystyle \alpha ^{*}}$

${\displaystyle \alpha ^{*}=(K+\gamma \ell I)^{-1}Y}$

donde se define como la matriz del núcleo, con , y es el vector de etiquetas de datos. ${\displaystyle K}$${\displaystyle K_{ij}=K(x_{i},x_{j})}$${\displaystyle Y}$

Al agregar un término laplaciano para la regularización de variedades se obtiene la declaración RLS laplaciana:

${\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }(f(x_{i})-y_{i})^{2}+\gamma _{A}\left\|f\right\|_{K}^{2}+{\frac {\gamma _{I}}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f} }$

El teorema del representante para la regularización de variedades da nuevamente

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell +u}\alpha _{i}^{*}K(x_{i},x)}$

y esto produce una expresión para el vector . Sea la matriz del núcleo como se indica arriba, el vector de etiquetas de datos y la matriz de bloques : ${\displaystyle \alpha ^{*}}$${\displaystyle K}$${\displaystyle Y}$${\displaystyle J}$${\displaystyle (\ell +u)\times (\ell +u)}$${\displaystyle {\begin{bmatrix}I_{\ell }&0\\0&0_{u}\end{bmatrix}}}$

${\displaystyle \alpha ^{*}={\underset {\alpha \in \mathbf {R} ^{\ell +u}}{\arg \!\min }}{\frac {1}{\ell }}(Y-JK\alpha )^{\mathrm {T} }(Y-JK\alpha )+\gamma _{A}\alpha ^{\mathrm {T} }K\alpha +{\frac {\gamma _{I}}{(\ell +u)^{2}}}\alpha ^{\mathrm {T} }KLK\alpha }$

con una solución de

${\displaystyle \alpha ^{*}=\left(JK+\gamma _{A}\ell I+{\frac {\gamma _{I}\ell }{(\ell +u)^{2}}}LK\right)^{-1}Y}$^[1]

LapRLS se ha aplicado a problemas que incluyen redes de sensores, ^[7] imágenes médicas , ^{[8] [9]} detección de objetos, ^[10] espectroscopia , ^[11] clasificación de documentos , ^[12] interacciones fármaco-proteína, ^[13] y compresión de imágenes y videos. ^[14]

Las máquinas de vectores de soporte (SVM) son una familia de algoritmos que se utilizan a menudo para clasificar datos en dos o más grupos o clases . Intuitivamente, una SVM traza un límite entre clases de modo que los ejemplos etiquetados más cercanos al límite estén lo más alejados posible. Esto se puede expresar directamente como un programa lineal , pero también es equivalente a la regularización de Tikhonov con la función de pérdida de bisagra : ${\displaystyle V(f(x),y)=\max(0,1-yf(x))}$

${\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }\max(0,1-y_{i}f(x_{i}))+\gamma \left\|f\right\|_{K}^{2}}$^{[15] [16]}

Al agregar el término de regularización intrínseca a esta expresión se obtiene el enunciado del problema LapSVM:

${\displaystyle f^{*}={\underset {f\in {\mathcal {H}}}{\arg \!\min }}{\frac {1}{\ell }}\sum _{i=1}^{\ell }\max(0,1-y_{i}f(x_{i}))+\gamma _{A}\left\|f\right\|_{K}^{2}+{\frac {\gamma _{I}}{(\ell +u)^{2}}}\mathbf {f} ^{\mathrm {T} }L\mathbf {f} }$

Nuevamente, el teorema del representador permite expresar la solución en términos del núcleo evaluado en los puntos de datos:

${\displaystyle f^{*}(x)=\sum _{i=1}^{\ell +u}\alpha _{i}^{*}K(x_{i},x)}$

${\displaystyle \alpha }$se puede encontrar escribiendo el problema como un programa lineal y resolviendo el problema dual . Nuevamente, siendo la matriz del núcleo y la matriz de bloques , se puede demostrar que la solución es ${\displaystyle K}$${\displaystyle J}$${\displaystyle {\begin{bmatrix}I_{\ell }&0\\0&0_{u}\end{bmatrix}}}$

${\displaystyle \alpha =\left(2\gamma _{A}I+2{\frac {\gamma _{I}}{(\ell +u)^{2}}}LK\right)^{-1}J^{\mathrm {T} }Y\beta ^{*}}$

¿Dónde está la solución al problema dual? ${\displaystyle \beta ^{*}}$

${\displaystyle {\begin{aligned}&&\beta ^{*}=\max _{\beta \in \mathbf {R} ^{\ell }}&\sum _{i=1}^{\ell }\beta _{i}-{\frac {1}{2}}\beta ^{\mathrm {T} }Q\beta \\&{\text{subject to}}&&\sum _{i=1}^{\ell }\beta _{i}y_{i}=0\\&&&0\leq \beta _{i}\leq {\frac {1}{\ell }}\;i=1,\ldots ,\ell \end{aligned}}}$

y se define por ${\displaystyle Q}$

${\displaystyle Q=YJK\left(2\gamma _{A}I+2{\frac {\gamma _{I}}{(\ell +u)^{2}}}LK\right)^{-1}J^{\mathrm {T} }Y}$^[1]

LapSVM se ha aplicado a problemas que incluyen imágenes geográficas, ^{[17] [18] [19]} imágenes médicas, ^{[20] [21] [22]} reconocimiento facial, ^[23] mantenimiento de máquinas, ^[24] e interfaces cerebro-computadora . ^[25]

• La regularización de variedades supone que no es probable que los datos con etiquetas diferentes estén muy juntos. Esta suposición es lo que permite que la técnica extraiga información de datos no etiquetados, pero solo se aplica a algunos dominios problemáticos. Dependiendo de la estructura de los datos, puede ser necesario utilizar un algoritmo de aprendizaje transductivo o semisupervisado diferente. ^[26]
• En algunos conjuntos de datos, la norma intrínseca de una función puede ser muy cercana a la norma ambiental : por ejemplo, si los datos consisten en dos clases que se encuentran en líneas perpendiculares, la norma intrínseca será igual a la norma ambiental. En este caso, los datos no etiquetados no tienen efecto en la solución aprendida por la regularización de variedades, incluso si los datos se ajustan al supuesto del algoritmo de que el separador debe ser suave. Se han propuesto enfoques relacionados con el co-entrenamiento para abordar esta limitación. ^[27]${\displaystyle \left\|f\right\|_{I}}$${\displaystyle \left\|f\right\|_{K}}$
• Si hay una gran cantidad de ejemplos sin etiquetar, la matriz del núcleo se vuelve muy grande y un algoritmo de regularización de variedades puede volverse prohibitivamente lento de calcular. Los algoritmos en línea y las aproximaciones dispersas de la variedad pueden ayudar en este caso. ^[28]${\displaystyle K}$

• Aprendizaje múltiple
• Hipótesis de colectores
• Aprendizaje semisupervisado
• Transducción (aprendizaje automático)
• Teoría de grafos espectrales
• Reproducción del espacio de Hilbert del núcleo
• Regularización de Tikhonov
• Geometría diferencial

• La biblioteca ManifoldLearn y la biblioteca Primal LapSVM implementan LapRLS y LapSVM en MATLAB .
• La biblioteca Dlib para C++ incluye una función de regularización de variedades lineales.