Regularización por filtrado espectral.

La regularización espectral pertenece a una clase de técnicas de regularización utilizadas 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 desenfocar imágenes hasta clasificar correos electrónicos en una carpeta de spam y una carpeta que no es spam. 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 de correos electrónicos etiquetados para aprender a distinguir un correo electrónico no deseado de uno no deseado. aparte.

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] ) y se centran en la inversión de un operador lineal (o una matriz) que posiblemente tenga un} número de condición incorrecto. o un inverso ilimitado. 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 se puede describir usando el cálculo espectral como un filtro apropiado sobre los valores propios del operador que define el problema, y ​​la función del filtro es "suprimir el comportamiento oscilatorio correspondiente a pequeños valores propios". ^[2] Por lo tanto, cada algoritmo de 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 para los cuales el filtrado espectral está bien estudiado son la regularización de Tikhonov, la iteración de Landweber y la descomposición de valores singulares truncados (TSVD). En cuanto a la elección del parámetro de regularización, ejemplos de métodos candidatos para calcular este parámetro incluyen el principio de discrepancia, la validación cruzada generalizada y el criterio de curva L. ^[3]

Es de 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 el 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 corresponda, la función del núcleo se indica con , y la matriz del núcleo se indica con entradas y denota el espacio de reproducción del núcleo de Hilbert (RKHS) con núcleo . El parámetro de regularización se indica con . ${\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 , siendo y espacios de Hilbert, dado un operador lineal y continuo , supongamos que se cumple. En este escenario, el problema directo sería resolver para dado y el problema inverso sería resolver para dado . Si la solución existe, es único 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 los 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

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

^[4][5] ${\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 entorno de aprendizaje, la matriz del núcleo se puede descomponer como , con ${\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 tanto, para valores propios pequeños, incluso pequeñas perturbaciones en los datos pueden provocar 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, indicada aquí por . Si la matriz Kernel se denota por , entonces se debe 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 hacerlo, se define una función de filtro escalar utilizando la descomposición propia de la matriz del núcleo: ${\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 debería tener las siguientes propiedades: ^[5]

1. Cuando llega 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 ,. De este modo, ${\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 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 esta configuración, 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 equivale a minimizar (es decir, el riesgo empírico) mediante el descenso de gradiente; Usando inducción, se puede demostrar que en la -ésima iteración, la solución viene 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 está definida por:

$${\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, tenga en cuenta que la relación , aún se mantendría si se reemplaza por una matriz; por lo tanto, si se considera (la matriz del núcleo), o mejor dicho , 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 esta configuración, el número de iteraciones proporciona el parámetro de regularización; Mas o menos, . ^[5] Si es grande, el sobreajuste puede ser una preocupación. Si es pequeño, el suavizado excesivo puede ser motivo de preocupación. Por lo tanto, elegir un momento apropiado para detener anticipadamente 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 del núcleo 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 sobre los datos proyectados (sin regularización). ^[5] Tenga en cuenta que el número de componentes conservados 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. Eliminación de imágenes borrosas: matrices, espectros y filtrado , Fundamentos de algoritmos 3, SIAM, Filadelfia, 2006.
4. L. Rosasco. Clase 6 de las notas de la clase 9.520: Teoría y aplicaciones del aprendizaje estadístico. Instituto de Tecnología de Massachusetts, otoño de 2013. Disponible en https://www.mit.edu/~9.520/fall13/slides/class06/class06_RLSSVM.pdf
5. L. Rosasco. Clase 7 de las notas de la clase 9.520: Teoría y aplicaciones del aprendizaje estadístico. Instituto de Tecnología de Massachusetts, otoño de 2013. Disponible en https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf