Aprendizaje de diccionario disperso

El aprendizaje de diccionarios dispersos (también conocido como codificación dispersa o SDL ) es un método de aprendizaje de representaciones que busca encontrar una representación dispersa de los datos de entrada en forma de una combinación lineal de elementos básicos, así como los propios elementos básicos. Estos elementos se denominan átomos y componen un diccionario . Los átomos del diccionario no tienen por qué ser ortogonales y pueden ser un conjunto de expansión sobrecompleto. Esta configuración del problema también permite que la dimensionalidad de las señales representadas sea mayor que la de cualquiera de las señales observadas. Estas dos propiedades dan lugar a átomos aparentemente redundantes que permiten múltiples representaciones de la misma señal, a la vez que mejoran la dispersión y la flexibilidad de la representación.

Una de las aplicaciones más importantes del aprendizaje de diccionarios dispersos se encuentra en el campo de la detección comprimida o recuperación de señales . En la detección comprimida, una señal de alta dimensión puede recuperarse con solo unas pocas mediciones lineales, siempre que la señal sea dispersa o casi dispersa. Dado que no todas las señales satisfacen esta condición, es crucial encontrar una representación dispersa de dicha 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 diferentes algoritmos de recuperación, como la búsqueda de base , CoSaMP ^{[ 1 ]} o algoritmos rápidos no iterativos ^{[ 2 ],} para recuperar la señal.

Uno de los principios clave del aprendizaje de diccionarios es que este debe inferirse a partir de los datos de entrada. El surgimiento de los métodos de aprendizaje de diccionarios dispersos se vio impulsado por el hecho de que, en el procesamiento de señales , se suele buscar representar los datos de entrada con una cantidad mínima de componentes. Antes de este enfoque, la práctica general era utilizar diccionarios predefinidos, como las transformadas de Fourier o de ondículas . 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 la clasificación de imágenes , así como en el procesamiento de vídeo y audio . La dispersión y los diccionarios sobrecompletos tienen aplicaciones inmensas en la compresión, fusión y relleno de imágenes .

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

${\displaystyle {\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}}$, dónde ,${\displaystyle {\mathcal {C}}\equiv \{\mathbf {D} \in \mathbb {R} ^{d\times n}:\|d_{i}\|_{2}\leq 1\,\,\forall i=1,...,n\}}$${\displaystyle \lambda >0}$

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

El problema de minimización anterior no es convexo debido a la norma ℓ ₀ y resolver este problema es NP-difícil. ^{[ 3 ]} En algunos casos se sabe que la norma L ¹ garantiza la escasez ^{[ 4 ]} y por lo tanto lo anterior se convierte en un problema de optimización convexa con respecto a cada una de las variables y cuando la otra está fija, pero no es conjuntamente convexo en . ${\displaystyle \mathbf {D} }$${\displaystyle \mathbf {R} }$${\displaystyle (\mathbf {D} ,\mathbf {R} )}$

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

Los diccionarios incompletos representan la configuración en la que los datos de entrada reales se encuentran en un espacio de menor dimensión. Este caso está estrechamente relacionado con la reducción de dimensionalidad y técnicas como el análisis de componentes principales , que requieren que los átomos sean ortogonales. La elección de estos subespacios es crucial para una reducción de dimensionalidad eficiente, pero no es trivial. La reducción de dimensionalidad basada en la representación de diccionarios puede extenderse para abordar tareas específicas como el análisis o la clasificación de datos. Sin embargo, su principal desventaja es que limita la elección de átomos. ${\displaystyle d_{1},...,d_{n}}$

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 permite la representación dispersa de una señal puede ser una matriz de transformación conocida (transformada wavelet, transformada de Fourier) o puede formularse de manera que sus elementos se modifiquen para representar la señal dada de la forma más dispersa posible. Los diccionarios aprendidos son capaces de proporcionar soluciones más dispersas en comparación con las matrices de transformación predefinidas.

Dado que el problema de optimización descrito anteriormente puede resolverse como un problema convexo con respecto a la codificación por diccionario o por dispersión, mientras que la otra de las dos permanece fija, la mayoría de los algoritmos se basan en la idea de actualizar iterativamente una y luego la otra.

El problema de encontrar una codificación dispersa óptima con un diccionario dado se conoce como aproximación dispersa (o a veces simplemente problema de codificación dispersa). Se han desarrollado varios algoritmos para resolverlo (como Matching Pursuit y LASSO ), los cuales se incorporan en los algoritmos que se describen a continuación. ${\displaystyle R}$${\displaystyle \mathbf {D} }$

El método de direcciones óptimas (o MOD) fue uno de los primeros métodos introducidos para abordar el problema del aprendizaje de diccionarios dispersos. ^{[ 5 ]} La idea central es resolver el problema de minimización sujeto al número limitado de componentes no nulas del vector de representación:

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

Aquí, 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 dada por donde es una pseudoinversa de Moore-Penrose . Después de esta actualización , se renormaliza para ajustarse a las restricciones y se obtiene de nuevo la nueva codificación dispersa. El proceso se repite hasta la convergencia (o hasta que el residuo sea suficientemente pequeño). ${\displaystyle F}$${\displaystyle \mathbf {D} =XR^{+}}$${\displaystyle R^{+}}$${\displaystyle \mathbf {D} }$

MOD ha demostrado ser un método muy eficiente para datos de entrada de baja dimensión, requiriendo solo unas pocas iteraciones para converger. Sin embargo, debido a la alta complejidad de la operación de inversión de matrices, el cálculo de la pseudoinversa en casos de alta dimensión resulta, en muchos casos, intratable. Esta limitación ha impulsado el desarrollo de otros métodos de aprendizaje de diccionarios. ${\displaystyle X}$

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

${\displaystyle \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 consiste en primero corregir el diccionario, encontrar la mejor opción posible bajo la restricción anterior (utilizando Orthogonal Matching Pursuit ) y luego actualizar iterativamente los átomos del diccionario de la siguiente manera: ${\displaystyle R}$${\displaystyle \mathbf {D} }$

${\displaystyle \|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 , la actualización y la imposición de la escasez tras 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, ya que solo es eficiente para señales de dimensionalidad relativamente baja y puede quedarse atascado en mínimos locales. ${\displaystyle E_{k}}$${\displaystyle d_{k}}$${\displaystyle x_{k}}$

También se puede aplicar un método de descenso de gradiente estocástico con proyección iterativa, ampliamente utilizado, para resolver este problema. ^{[ 6 ]} 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 . El paso que ocurre en la i-ésima iteración se describe mediante esta expresión: ${\displaystyle {\mathcal {C}}}$

${\displaystyle \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 es un subconjunto aleatorio de y es un paso de gradiente. ${\displaystyle S}$${\displaystyle \{1...K\}}$${\displaystyle \delta _{i}}$

Un algoritmo basado en la resolución de un problema lagrangiano dual proporciona una forma eficiente de resolver el diccionario sin las complicaciones inducidas por la función de escasez. ^{[ 7 ]} Considere el siguiente lagrangiano:

${\displaystyle {\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 es una restricción sobre la norma de los átomos y son las llamadas variables duales que forman la matriz diagonal . ${\displaystyle c}$${\displaystyle \lambda _{i}}$${\displaystyle \Lambda }$

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

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

Después de 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 : ${\displaystyle \mathbf {D} }$

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

Resolver este problema es menos difícil desde el punto de vista computacional porque la cantidad de variables duales es muchas veces mucho menor que la cantidad de variables en el problema primal. ${\displaystyle n}$

En este enfoque, el problema de optimización se formula de la siguiente manera:

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

Encuentra una estimación de minimizando el error de mínimos cuadrados sujeto a una restricción de norma ^L1 en el vector solución, formulada como: ${\displaystyle r_{i}}$

${\displaystyle \min _{r\in \mathbb {R} ^{n}}\,\,{\dfrac {1}{2}}\,\,\|X-\mathbf {D} r\|_{F}^{2}+\lambda \,\,\|r\|_{1}}$donde controla el equilibrio entre la escasez y el error de reconstrucción. Esto proporciona la solución óptima global. ^{[ 8 ]} Véase también Aprendizaje de diccionarios en línea para codificación dispersa${\displaystyle \lambda >0}$

Los métodos de entrenamiento paramétrico buscan incorporar lo mejor de ambos mundos: el ámbito de los diccionarios construidos analíticamente y los aprendidos. ^{[ 9 ]} Esto permite construir diccionarios generalizados más potentes que potencialmente pueden aplicarse a casos de señales de tamaño arbitrario. Algunos enfoques destacados incluyen:

• Diccionarios invariantes a la traslación. ^{[ 10 ]} Estos diccionarios se componen de las traslaciones de los átomos que se originan a partir 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. ^{[ 11 ]} 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. ^{[ 12 ]} Este método se centra no solo en proporcionar una representación dispersa, sino también en construir un diccionario disperso, lo cual se impone mediante la expresión donde es un diccionario analítico predefinido con propiedades deseables como un cálculo rápido y es una matriz dispersa. Esta formulación permite combinar directamente la rápida implementación de diccionarios analíticos con la flexibilidad de los enfoques dispersos.${\displaystyle \mathbf {D} =\mathbf {B} \mathbf {A} }$${\displaystyle \mathbf {B} }$${\displaystyle \mathbf {A} }$

Muchos enfoques comunes para el aprendizaje de diccionarios dispersos se basan en la suposición de que el algoritmo dispone de todos los datos de entrada (o al menos de un conjunto de datos de entrenamiento suficientemente grande). Sin embargo, esto podría no ser así en la práctica, ya que el tamaño de los datos de entrada podría ser demasiado grande para caber en la memoria. Otro caso en el que esta suposición no se cumple es cuando los datos de entrada se presentan en forma de flujo . Estos casos se dan en el ámbito del aprendizaje en línea, que consiste en actualizar el modelo iterativamente a medida que se dispone de nuevos datos .${\displaystyle X}$${\displaystyle x}$

Se puede aprender un diccionario en línea de la siguiente manera: ^{[ 13 ]}

1. Para${\displaystyle t=1...T:}$
2. Dibuja una nueva muestra${\displaystyle x_{t}}$
3. Encuentra una codificación dispersa usando LARS :${\displaystyle 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. Actualizar el diccionario utilizando el enfoque de coordenadas de bloque :${\displaystyle \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 representaciones dispersas 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).

El marco de aprendizaje de diccionarios, 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 de vanguardia 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 se han construido diccionarios específicos para cada clase, la señal de entrada puede clasificarse encontrando el diccionario que corresponde a la representación más dispersa. También posee propiedades útiles para la eliminación de ruido de la señal, 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. ^{[ 14 ]}

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 ^{[ 15 ]} y a la agrupación no supervisada. ^{[ 16 ]} En evaluaciones con el modelo Bag-of-Words , ^{[ 17 ] [ 18 ]} se encontró empíricamente que la codificación dispersa supera a otros enfoques de codificación en las tareas de reconocimiento de categorías de objetos.

El aprendizaje de diccionarios se utiliza para analizar señales médicas en detalle. Dichas señales médicas incluyen las de electroencefalografía (EEG), electrocardiografía (ECG), resonancia magnética (RM), resonancia magnética funcional (RMf), monitores continuos de glucosa ^{[ 19 ]} y tomografía computarizada por ultrasonido (TCUS), donde se utilizan diferentes supuestos para analizar cada señal.

El aprendizaje de diccionarios también se ha aplicado a la detección pasiva de señales desconocidas en entornos complejos. En particular, permite la detección ciega de señales en canales con distorsión de dispersión temporal (TSD), sin conocimiento previo de la señal de origen. ^{[ 20 ]} Este enfoque ha demostrado su eficacia tanto en condiciones simuladas como experimentales, ofreciendo un rendimiento robusto en escenarios con baja relación señal-ruido.

• aproximación dispersa
• PCA disperso
• K-SVD
• Factorización matricial
• codificación dispersa neuronal