Regularización por filtrado espectral

La regularización espectral es una clase de técnicas de regularización que se utilizan en el aprendizaje automático para controlar el impacto del ruido y evitar el sobreajuste . La regularización espectral se puede utilizar en una amplia gama de aplicaciones, desde la corrección de imágenes borrosas hasta la clasificación de correos electrónicos en una carpeta de correo no deseado y una carpeta de correo no deseado. Por ejemplo, en el ejemplo de clasificación de correo electrónico, la regularización espectral se puede utilizar para reducir el impacto del ruido y evitar el sobreajuste cuando se entrena un sistema de aprendizaje automático en un conjunto etiquetado de correos electrónicos para aprender a distinguir un correo electrónico no deseado de uno que no lo es.

Los algoritmos de regularización espectral se basan en métodos que se definieron y estudiaron originalmente en la teoría de problemas inversos mal planteados (por ejemplo, consulte ^[1] ) centrándose en la inversión de un operador lineal (o una matriz) que posiblemente tenga un número de condición incorrecto o una inversa ilimitada. En este contexto, la regularización equivale a sustituir el operador original por un operador acotado llamado "operador de regularización" que tiene un número de condición controlado por un parámetro de regularización, ^[2] un ejemplo clásico es la regularización de Tikhonov . Para garantizar la estabilidad, este parámetro de regularización se ajusta en función del nivel de ruido. ^[2] La idea principal detrás de la regularización espectral es que cada operador de regularización puede describirse utilizando el cálculo espectral como un filtro apropiado sobre los valores propios del operador que define el problema, y ​​el papel del filtro es "suprimir el comportamiento oscilatorio correspondiente a valores propios pequeños". ^[2] Por lo tanto, cada algoritmo en la clase de algoritmos de regularización espectral se define mediante una función de filtro adecuada (que debe derivarse para ese algoritmo en particular). Tres de los algoritmos de regularización más utilizados y cuyo filtrado espectral ha sido ampliamente estudiado son la regularización de Tikhonov, la iteración de Landweber y la descomposición en valores singulares truncados (TSVD). En cuanto a la elección del parámetro de regularización, algunos ejemplos de métodos candidatos para calcular este parámetro incluyen el principio de discrepancia, la validación cruzada generalizada y el criterio de la curva L. ^[3]

Cabe destacar que la noción de filtrado espectral estudiada en el contexto del aprendizaje automático está estrechamente relacionada con la literatura sobre aproximación de funciones (en procesamiento de señales).

Notación

El conjunto de entrenamiento se define como , donde es la matriz de entrada y es el vector de salida. Cuando corresponde, la función kernel se denota por , y la matriz kernel se denota por que tiene entradas y denota el espacio de Hilbert de kernel reproductor (RKHS) con kernel . El parámetro de regularización se denota por . ${\displaystyle S=\{(x_{1},y_{1}),\dots ,(x_{n},y_{n})\}}$ ${\displaystyle X}$ ${\displaystyle n\times d}$ ${\displaystyle Y=(y_{1},\dots ,y_{n})}$ ${\displaystyle k}$ ${\displaystyle n\times n}$ ${\displaystyle K}$ ${\displaystyle K_{ij}=k(x_{i},x_{j})}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle k}$ ${\displaystyle \lambda }$

(Nota: Para y , con y siendo espacios de Hilbert, dado un operador lineal y continuo , suponga que se cumple. En este contexto, el problema directo sería resolver para dado y el problema inverso sería resolver para dado . Si la solución existe, es única y estable, el problema inverso (es decir, el problema de resolver para ) está bien planteado; de lo contrario, está mal planteado). ${\displaystyle g\in G}$ ${\displaystyle f\in F}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle L}$ ${\displaystyle g=Lf}$ ${\displaystyle g}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f}$

Relación con la teoría de problemas inversos mal planteados

La conexión entre el problema de estimación de mínimos cuadrados regularizados (RLS) (configuración de regularización de Tikhonov) y la teoría de problemas inversos mal planteados es un ejemplo de cómo los algoritmos de regularización espectral se relacionan con la teoría de problemas inversos mal planteados.

El estimador RLS resuelve y el RKHS permite expresar este estimador RLS como donde con . ^[4] El término de penalización se utiliza para controlar la suavidad y evitar el sobreajuste. Dado que la solución de minimización de riesgo empírico se puede escribir como tal que , agregar la función de penalización equivale al siguiente cambio en el sistema que necesita ser resuelto: ^[5] $${\displaystyle \min _{f\in {\mathcal {H}}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}+\lambda \left\|f\right\|_{\mathcal {H}}^{2}}$$ ${\displaystyle f_{S}^{\lambda }(X)=\sum _{i=1}^{n}c_{i}k(x,x_{i})}$ ${\displaystyle (K+n\lambda I)c=Y}$ ${\displaystyle c=(c_{1},\dots ,c_{n})}$ ${\displaystyle \min _{f\in {\mathcal {H}}}{\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-f(x_{i}))^{2}}$ ${\displaystyle f_{S}^{\lambda }(X)=\sum _{i=1}^{n}c_{i}k(x,x_{i})}$ ${\displaystyle Kc=Y}$ $${\displaystyle \left\{\min _{f\in {\mathcal {H}}}{\frac {1}{n}}\sum _{i=1}^{n}\left(y_{i}-f(x_{i})\right)^{2}\rightarrow \min _{f\in {\mathcal {H}}}{\frac {1}{n}}\sum _{i=1}^{n}\left(y_{i}-f(x_{i})\right)^{2}+\lambda \left\|f\right\|_{\mathcal {H}}^{2}\right\}\equiv {\biggl \{}Kc=Y\rightarrow \left(K+n\lambda I\right)c=Y{\biggr \}}.}$$

En este contexto de aprendizaje, la matriz kernel se puede descomponer como , donde y son los vectores propios correspondientes. Por lo tanto, en el contexto de aprendizaje inicial, se cumple lo siguiente: ${\displaystyle K=Q\Sigma Q^{T}}$ $${\displaystyle \sigma =\operatorname {diag} (\sigma _{1},\dots ,\sigma _{n}),~\sigma _{1}\geq \sigma _{2}\geq \cdots \geq \sigma _{n}\geq 0}$$ ${\displaystyle q_{1},\dots ,q_{n}}$ $${\displaystyle c=K^{-1}Y=Q\Sigma ^{-1}Q^{T}Y=\sum _{i=1}^{n}{\frac {1}{\sigma _{i}}}\langle q_{i},Y\rangle q_{i}.}$$

Por lo tanto, para valores propios pequeños, incluso pequeñas perturbaciones en los datos pueden llevar a cambios considerables en la solución. Por lo tanto, el problema está mal condicionado, y resolver este problema RLS equivale a estabilizar un problema de inversión de matrices posiblemente mal condicionado, que se estudia en la teoría de problemas inversos mal planteados; en ambos problemas, una preocupación principal es abordar la cuestión de la estabilidad numérica.

Implementación de algoritmos

Cada algoritmo de la clase de algoritmos de regularización espectral se define mediante una función de filtro adecuada, denotada aquí por . Si la matriz Kernel se denota por , entonces debería controlar la magnitud de los valores propios más pequeños de . En una configuración de filtrado, el objetivo es encontrar estimadores donde . Para ello, se define una función de filtro escalar utilizando la descomposición propia de la matriz kernel: que produce ${\displaystyle G_{\lambda }(\cdot )}$ ${\displaystyle K}$ ${\displaystyle \lambda }$ ${\displaystyle G_{\lambda }(K)}$ ${\displaystyle f_{S}^{\lambda }(X):=\sum _{i=1}^{n}c_{i}k(x,x_{i})}$ ${\displaystyle c=G_{\lambda }(K)Y}$ ${\displaystyle G_{\lambda }(\sigma )}$ $${\displaystyle G_{\lambda }(K)=QG_{\lambda }(\Sigma )Q^{T},}$$ $${\displaystyle G_{\lambda }(K)Y~=~\sum _{i=1}^{n}G_{\lambda }(\sigma _{i})\langle q_{i},Y\rangle q_{i}.}$$

Normalmente, una función de filtro adecuada debe tener las siguientes propiedades: ^[5]

1. A medida que va llegando a cero, . ${\displaystyle \lambda }$ ${\displaystyle G_{\lambda }(\sigma )~\rightarrow ~1/\sigma }$
2. La magnitud de los valores propios (más pequeños) de está controlada por . ${\displaystyle G_{\lambda }}$ ${\displaystyle \lambda }$

Si bien los elementos anteriores brindan una caracterización aproximada de las propiedades generales de las funciones de filtro para todos los algoritmos de regularización espectral, la derivación de la función de filtro (y, por lo tanto, su forma exacta) varía según el método de regularización específico al que se aplica el filtrado espectral.

Función de filtro para la regularización de Tikhonov

En la configuración de regularización de Tikhonov, la función de filtro para RLS se describe a continuación. Como se muestra en ^[4] en esta configuración, . Por lo tanto, ${\displaystyle c=\left(K+n\lambda I\right)^{-1}Y}$ $${\displaystyle c=(K+n\lambda I)^{-1}Y=Q(\Sigma +n\lambda I)^{-1}Q^{T}Y=\sum _{i=1}^{n}{\frac {1}{\sigma _{i}+n\lambda }}<q_{i},Y>q_{i}.}$$

Los componentes no deseados se filtran mediante regularización:

• Si , entonces . ${\displaystyle \sigma \gg \lambda n}$ ${\displaystyle {\frac {1}{\sigma _{i}+n\lambda }}\sim {\frac {1}{\sigma _{i}}}}$
• Si , entonces . ${\displaystyle \sigma \ll \lambda n}$ ${\displaystyle {\frac {1}{\sigma _{i}+n\lambda }}\sim {\frac {1}{\lambda n}}}$

Por lo tanto, la función de filtro para la regularización de Tikhonov se define como: ^[5] $${\displaystyle G_{\lambda }(\sigma )={\frac {1}{\sigma +n\lambda }}.}$$

Función de filtro para la iteración de Landweber

La idea detrás de la iteración de Landweber es el descenso de gradiente : ^[5]

c 0  := 0 para  i = 1, ..., t − 1 c i  := c i −1 + η ( Y − Kc i −1 ) fin

En este contexto, si es mayor que el valor propio más grande de , la iteración anterior converge eligiendo como tamaño de paso:. ^[5] La iteración anterior es equivalente a minimizar (es decir, el riesgo empírico) a través del descenso de gradiente; utilizando la inducción, se puede demostrar que en la iteración -ésima, la solución está dada por ^[5] ${\displaystyle n}$ ${\displaystyle K}$ ${\displaystyle \eta =2/n}$ ${\displaystyle {\frac {1}{n}}\left\|Y-Kc\right\|_{2}^{2}}$ ${\displaystyle t}$ $${\displaystyle c=\eta \sum _{i=0}^{t-1}\left(I-\eta K\right)^{i}Y.}$$

Por tanto, la función de filtro adecuada se define mediante: $${\displaystyle G_{\lambda }(\sigma )=\eta \sum _{i=0}^{t-1}\left(I-\eta \sigma \right)^{i}.}$$

Se puede demostrar que esta función de filtro corresponde a una expansión de potencia truncada de ; ^[5] para ver esto, note que la relación , todavía se cumpliría si se reemplaza por una matriz; por lo tanto, si se considera (la matriz kernel), o más bien , se cumple lo siguiente: ${\displaystyle K^{-1}}$ ${\displaystyle \sum _{i\geq 0}x^{i}=1/(1-x)}$ ${\displaystyle x}$ ${\displaystyle K}$ ${\displaystyle I-\eta K}$ $${\displaystyle K^{-1}=\eta \sum _{i=0}^{\infty }\left(I-\eta K\right)^{i}\sim \eta \sum _{i=0}^{t-1}\left(I-\eta K\right)^{i}.}$$

En este contexto, el número de iteraciones proporciona el parámetro de regularización; en términos generales, . ^[5] Si es grande, el sobreajuste puede ser un problema. Si es pequeño, el sobresuavizado puede ser un problema. Por lo tanto, elegir un momento apropiado para detener temprano las iteraciones proporciona un efecto de regularización. ${\displaystyle t\sim 1/\lambda }$ ${\displaystyle t}$ ${\displaystyle t}$

Función de filtro para TSVD

En la configuración TSVD, dada la descomposición propia y utilizando un umbral prescrito , se puede formar una inversa regularizada para la matriz kernel descartando todos los valores propios que sean menores que este umbral. ^[5] Por lo tanto, la función de filtro para TSVD se puede definir como ${\displaystyle K=Q\Sigma Q^{T}}$ ${\displaystyle \lambda n}$ $${\displaystyle G_{\lambda }(\sigma )={\begin{cases}1/\sigma ,&{\text{if }}\sigma \geq \lambda n\\[1ex]0,&{\text{otherwise}}\end{cases}}}$$

Se puede demostrar que TSVD es equivalente a la proyección (no supervisada) de los datos utilizando el Análisis de Componentes Principales (PCA) (kernel), y que también es equivalente a minimizar el riesgo empírico en los datos proyectados (sin regularización). ^[5] Nótese que el número de componentes mantenidos para la proyección es el único parámetro libre aquí.

Referencias

1. HW Engl , M. Hanke y A. Neubauer. Regularización de problemas inversos . Kluwer, 1996.
2. L. Lo Gerfo, L. Rosasco, F. Odone, E. De Vito y A. Verri. Algoritmos espectrales para aprendizaje supervisado, computación neuronal , 20 (7), 2008.
3. PC Hansen, JG Nagy y DP O'Leary. Cómo desenfocar imágenes: matrices, espectros y filtrado , Fundamentos de algoritmos 3, SIAM, Filadelfia, 2006.
4. L. Rosasco. Lección 6 de las Notas de la lección de 9.520: Teoría y aplicaciones del aprendizaje estadístico. Instituto Tecnológico de Massachusetts, otoño de 2013. Disponible en https://www.mit.edu/~9.520/fall13/slides/class06/class06_RLSSVM.pdf
5. L. Rosasco. Lección 7 de las Notas de la lección de 9.520: Teoría y aplicaciones del aprendizaje estadístico. Instituto Tecnológico de Massachusetts, otoño de 2013. Disponible en https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf