Regularización de variedades

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 penalizando 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 con núcleo reproductor (RKHS). Bajo la regularización de Tikhonov estándar en RKHS, un algoritmo de aprendizaje intenta aprender una función${\displaystyle f}$de entre un espacio de hipótesis de funciones${\displaystyle {\mathcal {H}}}$El espacio de hipótesis es un RKHS, lo que significa que está asociado con un núcleo .${\displaystyle K}$y por lo tanto cada función candidata${\displaystyle f}$tiene una norma${\displaystyle \left\|f\right\|_{K}}$, 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.

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

${\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}}$

dónde${\displaystyle \gamma }$es un hiperparámetro que controla cuánto dará preferencia el algoritmo a las funciones más simples sobre las funciones que se ajustan mejor a los datos.

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

Existen muchas opciones posibles para el regularizador intrínseco.${\displaystyle \left\|f\right\|_{I}}$Muchas elecciones naturales implican el gradiente en la variedad .${\displaystyle \nabla _{M}}$, 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${\displaystyle \nabla _{M}f(x)}$debería ser pequeño donde la densidad de probabilidad marginal${\displaystyle {\mathcal {P}}_{X}(x)}$, la densidad de probabilidad de que un punto de datos extraído aleatoriamente aparezca en${\displaystyle x}$, es grande. Esto proporciona una opción adecuada para el regularizador intrínseco:

${\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 debido a la distribución marginal.${\displaystyle {\mathcal {P}}_{X}}$Se desconoce, pero se puede estimar a partir de los datos proporcionados.

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

${\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${\displaystyle \ell +u}$aumenta, esta definición empírica de${\displaystyle \left\|f\right\|_{I}^{2}}$converge a la definición cuando${\displaystyle {\mathcal {P}}_{X}}$es conocido. ^{[ 1 ]}

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

${\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 ,${\displaystyle {\mathcal {H}}}$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 del representante muestra que bajo ciertas condiciones sobre la elección de la norma${\displaystyle \left\|f\right\|_{I}}$la solución óptima${\displaystyle f^{*}}$debe ser una combinación lineal del núcleo centrado en cada uno de los puntos de entrada: para algunos pesos${\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.${\displaystyle f^{*}}$mediante la búsqueda en el espacio de dimensión finita definido por las posibles elecciones de${\displaystyle \alpha _{i}}$. ^{[ 1 ]}

La idea más allá del laplaciano de grafos es utilizar 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 de grafos 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 utilizando derivadas de la lectura del núcleo${\displaystyle \partial _{1,j}K(x_{i},x)}$dónde${\displaystyle \partial _{1,j}}$denota las derivadas parciales según la j -ésima coordenada de la primera variable. ^{[ 4 ]} Este segundo enfoque de la norma laplaciana es ponerla en relación con los métodos sin malla , que contrastan con el método de diferencias finitas en EDP.

Los mínimos cuadrados regularizados (RLS) son una familia de algoritmos de regresión : algoritmos que predicen un valor${\displaystyle y=f(x)}$por sus insumos${\displaystyle x}$con el objetivo de que los valores predichos se aproximen a las etiquetas reales de los datos. En particular, RLS está diseñado para minimizar el error cuadrático medio entre los valores predichos y las etiquetas reales, 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 del núcleo . El planteamiento del problema para RLS resulta de la elección de la función de pérdida.${\displaystyle V}$en la regularización de Tikhonov para ser el error cuadrático medio:

${\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 representante , la solución se puede escribir como una suma ponderada del núcleo evaluado en los puntos de datos:

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

y resolver para${\displaystyle \alpha ^{*}}$da:

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

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

Agregar un término laplaciano para la regularización de la variedad da como resultado 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 nuevamente da

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

y esto produce una expresión para el vector${\displaystyle \alpha ^{*}}$Alquiler${\displaystyle K}$Sea la matriz del núcleo como se indicó anteriormente,${\displaystyle Y}$sea ​​el vector de etiquetas de datos, y${\displaystyle J}$ser el${\displaystyle (\ell +u)\times (\ell +u)}$matriz de bloques${\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 vídeos. ^{[ 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 manera que los ejemplos etiquetados más cercanos al límite estén lo más lejos 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 de 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 representante 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, dejando${\displaystyle K}$sea ​​la matriz del núcleo y${\displaystyle J}$sea ​​la matriz de bloques${\displaystyle {\begin{bmatrix}I_{\ell }&0\\0&0_{u}\end{bmatrix}}}$, se puede demostrar que la solución es

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

dónde${\displaystyle \beta ^{*}}$es la solución al problema dual

${\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${\displaystyle Q}$se define por

${\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 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.