Aprendizaje por diccionarios dispersos

El aprendizaje por diccionarios dispersos (también conocido como codificación dispersa o SDL) es un método de aprendizaje de representaciones cuyo objetivo es encontrar una representación dispersa de los datos de entrada en forma de combinación lineal de elementos básicos, así como de los propios elementos básicos. Estos elementos se denominan átomos y componen un diccionario. No es necesario que los átomos del diccionario sean ortogonales, y pueden ser un conjunto sobrecompleto. Esta configuración del problema también permite que la dimensionalidad de las señales representadas sea mayor que la de las señales observadas. Las dos propiedades anteriores conducen a tener átomos aparentemente redundantes que permiten múltiples representaciones de la misma señal, pero también proporcionan una mejora en la escasez y la flexibilidad de la representación.

Una de las aplicaciones más importantes del aprendizaje de diccionarios dispersos es el campo de la detección comprimida o la recuperación de señales. En la detección comprimida, una señal de alta dimensión puede recuperarse con sólo unas pocas medidas lineales, siempre que la señal sea dispersa o casi dispersa. Dado que no todas las señales satisfacen esta condición de dispersidad, es muy importante encontrar una representación dispersa de esa señal, como la transformada wavelet o el gradiente direccional de una matriz rasterizada. Una vez que una matriz o un vector de alta dimensión se transfiere a un espacio disperso, se pueden utilizar distintos algoritmos de recuperación, como la búsqueda de bases, CoSaMP​ o algoritmos rápidos no iterativos,​ para recuperar la señal.

Uno de los principios clave del aprendizaje por diccionarios es que el diccionario debe inferirse a partir de los datos de entrada. La aparición de métodos de aprendizaje por diccionarios dispersos se vio estimulada por el hecho de que, en el tratamiento de señales, normalmente se desea representar los datos de entrada utilizando el menor número posible de componentes. Antes de este enfoque, la práctica general era utilizar diccionarios predefinidos (como las transformadas de Fourier o wavelet). Sin embargo, en ciertos casos, un diccionario entrenado para ajustarse a los datos de entrada puede mejorar significativamente la dispersión, lo que tiene aplicaciones en la descomposición, compresión y análisis de datos y se ha utilizado en los campos de la eliminación de ruido y clasificación de imágenes, y el procesamiento de vídeo y audio. Los diccionarios sparsity y overcomplete tienen inmensas aplicaciones en compresión de imágenes, fusión de imágenes e inpainting.

Planteamiento del problema

Dado el conjunto de datos de entrada $X=[x_{1},...,x_{K}],x_{i}\in \mathbb {R} ^{d}$ deseamos encontrar un diccionario $\mathbf {D} \in \mathbb {R} ^{d\times n}:D=[d_{1},...,d_{n}]$ y una representación $R=[r_{1},...,r_{K}],r_{i}\in \mathbb {R} ^{n}$ de forma que ambos $\|X-\mathbf {D} R\|_{F}^{2}$ se minimiza y las representaciones $r_{i}$ son suficientemente dispersos. Esto puede formularse como el siguiente problema de optimización:

${\underset {\mathbf {D} \in {\mathcal {C}},r_{i}\in \mathbb {R} ^{n}}{\text{argmin}}}\sum _{i=1}^{K}\|x_{i}-\mathbf {D} r_{i}\|_{2}^{2}+\lambda \|r_{i}\|_{0}$, donde ${\mathcal {C}}\equiv \{\mathbf {D} \in \mathbb {R} ^{d\times n}:\|d_{i}\|_{2}\leq 1\,\,\forall i=1,...,n\}$, $\lambda >0$

${\mathcal {C}}$ es necesario para restringir $\mathbf {D}$ para que sus átomos no alcancen valores arbitrariamente altos permitiendo valores arbitrariamente bajos (pero no nulos) de $r_{i}$. $\lambda$ controla el equilibrio entre la dispersión y el error de minimización.

El problema de minimización anterior no es convexo debido a la norma ℓ₀- y resolver este problema es NP-difícil.​ En algunos casos, se sabe que la norma L¹ garantiza la dispersión,​ por lo que lo anterior se convierte en un problema de optimización convexa con respecto a cada una de las variables $\mathbf {D}$ y $\mathbf {R}$ cuando el otro es fijo, pero no es convexo conjuntamente en $(\mathbf {D} ,\mathbf {R} )$.

Propiedades del diccionario

El diccionario $\mathbf {D}$ definido anteriormente puede ser "incompleto" si $n<d$ o "sobrecompleto" en caso de $n>d$ siendo este último un supuesto típico para un problema de aprendizaje de diccionario disperso. El caso de un diccionario completo no aporta ninguna mejora desde el punto de vista de la representación, por lo que no se tiene en cuenta.

Los diccionarios incompletos representan la situación en la que los datos de entrada reales se encuentran en un espacio de dimensiones inferiores. Este caso está muy relacionado con la reducción de la dimensionalidad y técnicas como el análisis de componentes principales, que requieren átomos $d_{1},...,d_{n}$ sean ortogonales. La elección de estos subespacios es crucial para una reducción eficaz de la dimensionalidad, pero no es trivial. Y la reducción de la dimensionalidad basada en la representación de diccionarios puede ampliarse para abordar tareas específicas como el análisis de datos o la clasificación. Sin embargo, su principal inconveniente es la limitación en la elección de los átomos.

Sin embargo, los diccionarios sobrecompletos no requieren que los átomos sean ortogonales (de todos modos, nunca tendrán una base), lo que permite diccionarios más flexibles y representaciones de datos más ricas.

Un diccionario sobrecompleto que permita una representación dispersa de la señal puede ser una famosa matriz de transformación (transformada wavelets, transformada de Fourier) o puede formularse de forma que sus elementos se modifiquen de tal manera que represente de forma dispersa la señal dada de la mejor manera posible. Los diccionarios aprendidos son capaces de ofrecer soluciones más dispersas que las matrices de transformación predefinidas.

Algoritmos

Como el problema de optimización descrito anteriormente puede resolverse como un problema convexo con respecto al diccionario o a la codificación dispersa mientras que el otro de los dos es fijo, la mayoría de los algoritmos se basan en la idea de actualizar iterativamente uno y luego el otro.

El problema de encontrar una codificación dispersa óptima $R$ con un diccionario determinado $\mathbf {D}$ se conoce como problema de aproximación dispersa (o a veces simplemente problema de codificación dispersa). Se han desarrollado varios algoritmos para resolverlo (como búsqueda de coincidencia y LASSO) que se incorporan a los algoritmos descritos a continuación.

Método de direcciones óptimas (MOD)

El método de direcciones óptimas (o MOD)​ fue uno de los primeros métodos introducidos para abordar el problema del aprendizaje por diccionarios dispersos.​ La idea central del mismo es resolver el problema de minimización sujeto al número limitado de componentes distintos de cero del vector de representación:

$\min _{\mathbf {D} ,R}\{\|X-\mathbf {D} R\|_{F}^{2}\}\,\,{\text{s.t.}}\,\,\forall i\,\,\|r_{i}\|_{0}\leq T$

En este caso, $F$ denota la norma de Frobenius. MOD alterna entre obtener la codificación dispersa mediante un método como la búsqueda de coincidencias y actualizar el diccionario calculando la solución analítica del problema dado por $\mathbf {D} =XR^{+}$, donde $R^{+}$ es un pseudoinverso de Moore-Penrose. Después de esta actualización, $\mathbf {D}$ se renormaliza para ajustarse a las restricciones y se vuelve a obtener la nueva codificación dispersa. El proceso se repite hasta la convergencia (o hasta un residuo suficientemente pequeño).

MOD ha demostrado ser un método muy eficaz para datos de entrada de baja dimensión $X$ ya que sólo requiere unas pocas iteraciones. Sin embargo, debido a la gran complejidad de la operación de inversión de matrices, el cálculo del pseudoinverso en casos de alta dimensionalidad es en muchos casos intratable. Esta deficiencia ha inspirado el desarrollo de otros métodos de aprendizaje de diccionarios.

K-SVD

K-SVD es un algoritmo que realiza SVD​ en su núcleo para actualizar los átomos del diccionario uno a uno y básicamente es una generalización de K-means. Obliga a que cada elemento de los datos de entrada $x_{i}$ se codifica mediante una combinación lineal de no más de $T_{0}$ elementos de forma idéntica al enfoque MOD:

$\min _{\mathbf {D} ,R}\{\|X-\mathbf {D} R\|_{F}^{2}\}\,\,{\text{s.t.}}\,\,\forall i\,\,\|r_{i}\|_{0}\leq T_{0}$

La esencia de este algoritmo es fijar primero el diccionario, encontrar el mejor $R$ bajo la restricción anterior (utilizando búsqueda de coincidencias ortogonales) y luego actualizar iterativamente los átomos del diccionario $\mathbf {D}$ de la siguiente forma:

$\|X-\mathbf {D} R\|_{F}^{2}=\left|X-\sum _{i=1}^{K}d_{i}x_{T}^{i}\right|_{F}^{2}=\|E_{k}-d_{k}x_{T}^{k}\|_{F}^{2}$

Los siguientes pasos del algoritmo incluyen la aproximación de rango 1 de la matriz residual $E_{k}$, actualizando $d_{k}$ e imponiendo la dispersión de $x_{k}$ después de la actualización. Este algoritmo se considera estándar para el aprendizaje de diccionarios y se utiliza en diversas aplicaciones. Sin embargo, comparte debilidades con MOD al ser eficiente sólo para señales con una dimensionalidad relativamente baja y tener la posibilidad de quedarse atascado en mínimos locales.

Descenso de gradiente estocástico

También se puede aplicar un método generalizado de descenso de gradiente estocástico con proyección iterativa para resolver este problema.​ La idea de este método es actualizar el diccionario utilizando el gradiente estocástico de primer orden y proyectarlo sobre el conjunto de restricciones ${\mathcal {C}}$. El paso que se produce en la iteración i-ésima se describe mediante esta expresión:​

$\mathbf {D} _{i}={\text{proj}}_{\mathcal {C}}\left\{\mathbf {D} _{i-1}-\delta _{i}\nabla _{\mathbf {D} }\sum _{i\in S}\|x_{i}-\mathbf {D} r_{i}\|_{2}^{2}+\lambda \|r_{i}\|_{1}\right\}$, donde $S$ es un subconjunto aleatorio de $\{1...K\}$ y $\delta _{i}$ es un paso de gradiente.

Método dual de Lagrange

Un algoritmo basado en la resolución de un problema lagrangiano dual proporciona una forma eficiente de resolver el diccionario sin complicaciones inducidas por la función de dispersión.​ Consideremos el siguiente lagrangiano:

${\mathcal {L}}(\mathbf {D} ,\Lambda )={\text{tr}}\left((X-\mathbf {D} R)^{T}(X-\mathbf {D} R)\right)+\sum _{j=1}^{n}\lambda _{j}\left({\sum _{i=1}^{d}\mathbf {D} _{ij}^{2}-c}\right)$, donde $c$ es una restricción de la norma de los átomos y $\lambda _{i}$ son las denominadas variables duales que forman la matriz diagonal $\Lambda$.

Podemos entonces proporcionar una expresión analítica para el dual de Lagrange tras la minimización sobre $\mathbf {D}$:

${\mathcal {D}}(\Lambda )=\min _{\mathbf {D} }{\mathcal {L}}(\mathbf {D} ,\Lambda )={\text{tr}}(X^{T}X-XR^{T}(RR^{T}+\Lambda )^{-1}(XR^{T})^{T}-c\Lambda )$

Tras aplicar uno de los métodos de optimización al valor del dual (como el método de Newton o el gradiente conjugado) obtenemos el valor de $\mathbf {D}$:

$\mathbf {D} ^{T}=(RR^{T}+\Lambda )^{-1}(XR^{T})^{T}$

Resolver este problema es menos difícil computacionalmente porque la cantidad de variables duales $n$ es muchas veces mucho menor que la cantidad de variables del problema primal.

LASSO

En este enfoque, el problema de optimización se formula como:

$\min _{r\in \mathbb {R} ^{n}}\{\,\,\|r\|_{1}\}\,\,{\text{subject to}}\,\,\|X-\mathbf {D} R\|_{F}^{2}<\epsilon$, donde $\epsilon$ es el error permitido en la reconstrucción LASSO.

Se encuentra una estimación de $r_{i}$ minimizando el error mínimo cuadrático sujeto a una restricción de norma L¹ en el vector solución, formulada como:

$\min _{r\in \mathbb {R} ^{n}}\,\,{\dfrac {1}{2}}\,\,\|X-\mathbf {D} r\|_{F}^{2}+\lambda \,\,\|r\|_{1}$, donde $\lambda >0$ controla el equilibrio entre la dispersión y el error de reconstrucción. Así se obtiene la solución óptima global.​

Métodos de formación paramétrica

Los métodos de formación paramétrica pretenden incorporar lo mejor de ambos mundos: el ámbito de los diccionarios construidos analíticamente y el de los aprendidos,​ lo que permite construir diccionarios generalizados más potentes que pueden aplicarse potencialmente a los casos de señales de tamaño arbitrario. Entre los enfoques más destacados se incluyen:

• Diccionarios invariantes de traducción.​ Estos diccionarios están compuestos por las traducciones de los átomos procedentes del diccionario construido para un parche de señal de tamaño finito. Esto permite que el diccionario resultante proporcione una representación para la señal de tamaño arbitrario.
• Diccionarios multiescala.​ Este método se centra en la construcción de un diccionario compuesto por diccionarios de diferentes escalas para mejorar la dispersión.
• Diccionarios dispersos.​ Este método se centra no sólo en proporcionar una representación dispersa, sino también en construir un diccionario disperso que se impone mediante la expresión $\mathbf {D} =\mathbf {B} \mathbf {A}$, donde $\mathbf {B}$ es un diccionario analítico predefinido con propiedades deseables, como un cálculo rápido y $\mathbf {A}$ es una matriz dispersa. Esta formulación permite combinar directamente la rápida aplicación de los diccionarios analíticos con la flexibilidad de los enfoques dispersos.

Aprendizaje por diccionarios en línea

Muchos enfoques comunes para el aprendizaje por diccionarios dispersos se basan en el hecho de que todos los datos de entrada $X$ o al menos un conjunto de datos de entrenamiento lo suficientemente grande). Sin embargo, esto puede no ser así en el mundo real, ya que el tamaño de los datos de entrada puede ser demasiado grande para caber en la memoria. El otro caso en el que no se puede hacer esta suposición es cuando los datos de entrada vienen en forma de flujo. Estos casos se encuentran en el campo de estudio del aprendizaje en línea, que esencialmente sugiere actualizar iterativamente el modelo a partir de los nuevos puntos de datos $x$ que están disponibles.

Un diccionario puede aprenderse en línea de la siguiente manera:​

1. Para $t=1...T:$
2. Dibujar una nueva muestra $x_{t}$
3. Encuentra una codificación dispersa utilizando LARS: $r_{t}={\underset {r\in \mathbb {R} ^{n}}{\text{argmin}}}\left({\frac {1}{2}}\|x_{t}-\mathbf {D} _{t-1}r\|+\lambda \|r\|_{1}\right)$
4. Actualización del diccionario mediante un enfoque de coordenadas de bloque: $\mathbf {D} _{t}={\underset {\mathbf {D} \in {\mathcal {C}}}{\text{argmin}}}{\frac {1}{t}}\sum _{i=1}^{t}\left({\frac {1}{2}}\|x_{i}-\mathbf {D} r_{i}\|_{2}^{2}+\lambda \|r_{i}\|_{1}\right)$

Este método nos permite actualizar gradualmente el diccionario a medida que se dispone de nuevos datos para el aprendizaje de la representación dispersa y ayuda a reducir drásticamente la cantidad de memoria necesaria para almacenar el conjunto de datos (que a menudo tiene un tamaño enorme).

Aplicaciones

El marco del aprendizaje por diccionario, es decir, la descomposición lineal de una señal de entrada utilizando unos pocos elementos base aprendidos a partir de los propios datos, ha dado lugar a resultados innovadores en diversas tareas de procesamiento de imágenes y vídeo. Esta técnica puede aplicarse a problemas de clasificación de forma que, si hemos construido diccionarios específicos para cada clase, la señal de entrada puede clasificarse encontrando el diccionario correspondiente a la representación más escasa.

También tiene propiedades útiles para la eliminación de ruido de señales, ya que normalmente se puede aprender un diccionario para representar la parte significativa de la señal de entrada de forma dispersa, pero el ruido de entrada tendrá una representación mucho menos dispersa.​

El aprendizaje de diccionarios dispersos se ha aplicado con éxito a diversas tareas de procesamiento de imágenes, vídeo y audio, así como a la síntesis de texturas​ y a la agrupación no supervisada.​ En evaluaciones con el modelo Bag-of-Words,​​ se observó empíricamente que la codificación dispersa superaba a otros enfoques de codificación en las tareas de reconocimiento de categorías de objetos.

El aprendizaje por diccionarios se utiliza para analizar en detalle las señales médicas. Dichas señales médicas incluyen las procedentes de la electroencefalografía (EEG), la electrocardiografía (ECG), la resonancia magnética (RM), la resonancia magnética funcional (RMf), los monitores continuos de glucosa​ y la tomografía computarizada (USCT), en las que se utilizan distintos supuestos para analizar cada señal.

Véase también

• Análisis de componentes principales
• Descomposición en valores singulares (K-SVD)
• Factorización de matrices
• Codificación neural