El aprendizaje de diccionario disperso (también conocido como codificación dispersa o SDL ) es un método de aprendizaje de representación que tiene como objetivo encontrar una representación dispersa de los datos de entrada en forma de una combinación lineal de elementos básicos, así como de esos elementos básicos mismos. Estos elementos se llaman átomos y componen un diccionario . No es necesario que los átomos del diccionario sean ortogonales y pueden ser un conjunto abarcador demasiado completo. Esta configuración del problema también permite que la dimensionalidad de las señales que se representan sea mayor que la de las señales que se observan. 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 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 la recuperación de señales . En la detección comprimida, se puede recuperar una señal de alta dimensión con sólo unas pocas mediciones lineales, siempre que la señal sea escasa o casi escasa. Dado que no todas las señales satisfacen esta condición de escasez, es de gran importancia encontrar una representación escasa 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 diferentes algoritmos de recuperación como búsqueda de bases , 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 el diccionario debe inferirse de los datos de entrada. La aparición de métodos dispersos de aprendizaje de diccionarios fue estimulada por el hecho de que en el procesamiento de señales normalmente se quiere representar los datos de entrada utilizando la menor cantidad de componentes posible. 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 escasez, lo que tiene aplicaciones en descomposición, compresión y análisis de datos y se ha utilizado en los campos de clasificación y eliminación de ruido de imágenes , procesamiento de video y audio . Los diccionarios dispersos y sobrecompletos tienen inmensas aplicaciones en la compresión y fusión de imágenes y en la pintura.
Dado el conjunto de datos de entrada, deseamos encontrar un diccionario y una representación tal que ambos estén minimizados y las representaciones sean lo suficientemente escasas. Esto se puede formular como el siguiente problema de optimización :
, dónde ,
se requiere restringir para que sus átomos no alcancen valores arbitrariamente altos que permitan valores arbitrariamente bajos (pero distintos de cero) de . controla el equilibrio entre la escasez y el error de minimización.
El problema de minimización anterior no es convexo debido a la "norma" ℓ 0 y resolver este problema es NP-difícil. [3] En algunos casos se sabe que la norma L 1 garantiza la escasez [4] y, por lo tanto, lo anterior se convierte en un problema de optimización convexo con respecto a cada una de las variables y cuando la otra es fija, pero no es conjuntamente convexa en .
El diccionario definido anteriormente puede estar "insuficientemente completo" si o "sobrecompleto" en el caso de que este último sea una suposición típica para un problema de aprendizaje de diccionario disperso. El caso de un diccionario completo no aporta ninguna mejora desde el punto de vista representacional y por tanto no se considera.
Los diccionarios incompletos representan la configuración en la que los datos de entrada reales se encuentran en un espacio de dimensiones inferiores. Este caso está fuertemente 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 eficiente de la dimensionalidad, pero no es trivial. Y la reducción de dimensionalidad basada en la representación del diccionario se puede ampliar para abordar tareas específicas como el análisis o la clasificación de datos. Sin embargo, su principal desventaja es la limitación de la elección de á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 permite una representación escasa de la señal puede ser una famosa matriz de transformación (transformada de wavelets, transformada de Fourier) o puede formularse de manera que sus elementos se cambien de tal manera que represente escasamente la señal dada de la mejor manera. Los diccionarios aprendidos son capaces de ofrecer soluciones más dispersas en comparación con las matrices de transformación predefinidas.
Como el problema de optimización descrito anteriormente se puede resolver como un problema convexo con respecto al diccionario o a la codificación dispersa mientras 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 con un diccionario determinado se conoce como aproximación dispersa (o, a veces, simplemente problema de codificación dispersa). Se han desarrollado varios algoritmos para resolverlo (como búsqueda de coincidencias y LASSO ) y se incorporan en los algoritmos que se describen a continuación.
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 distintos de cero del vector de representación:
Aquí, denota la norma de Frobenius . MOD alterna entre obtener la codificación dispersa utilizando un método como la búsqueda de coincidencias y actualizar el diccionario calculando la solución analítica del problema dado por dónde está un pseudoinverso de Moore-Penrose . Después de esta actualización, se vuelve a normalizar para ajustarse a las restricciones y se obtiene nuevamente la nueva codificación dispersa. El proceso se repite hasta la convergencia (o hasta que quede un residuo suficientemente pequeño).
MOD ha demostrado ser un método muy eficiente para datos de entrada de baja dimensión que requieren solo unas pocas iteraciones para converger. Sin embargo, debido a la alta complejidad de la operación de inversión de matrices, calcular la pseudoinversa en casos de alta dimensión es en muchos casos intratable. Esta deficiencia ha inspirado el desarrollo de otros métodos de aprendizaje de diccionarios.
K-SVD es un algoritmo que realiza SVD en su núcleo para actualizar los átomos del diccionario uno por uno y básicamente es una generalización de K-means . Obliga a que cada elemento de los datos de entrada esté codificado mediante una combinación lineal de no más de elementos de una manera idéntica al enfoque MOD:
La esencia de este algoritmo es primero arreglar el diccionario, encontrar lo mejor posible bajo la restricción anterior (usando Orthogonal Matching Pursuit ) y luego actualizar iterativamente los átomos del diccionario de la siguiente manera:
Los siguientes pasos del algoritmo incluyen la aproximación de rango 1 de la matriz residual , la actualización y el cumplimiento de la escasez después de la actualización. Este algoritmo se considera estándar para el aprendizaje de diccionarios y se utiliza en una variedad de aplicaciones. Sin embargo, comparte debilidades con MOD, ya que es eficiente solo para señales con dimensionalidad relativamente baja y tiene la posibilidad de quedarse estancado en mínimos locales.
También se puede aplicar un método generalizado de descenso de gradiente estocástico con proyección iterativa 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 en el conjunto de restricciones . El paso que ocurre en la i-ésima iteración se describe mediante esta expresión:
, donde es un subconjunto aleatorio de y es un paso de gradiente.
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. [7] Considere el siguiente lagrangiano:
, donde es una restricción a la norma de los átomos y son las llamadas variables duales que forman la matriz diagonal .
Luego podemos proporcionar una expresión analítica para el dual de Lagrange después de la minimización sobre :
.
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 :
Resolver este problema es menos difícil desde el punto de vista computacional porque la cantidad de variables duales es muchas veces menor que la cantidad de variables en el problema primario.
En este enfoque, el problema de optimización se formula como:
, donde está el error permitido en la reconstrucción LASSO.
Encuentra una estimación minimizando el error de mínimos cuadrados sujeto a una restricción de norma L 1 en el vector de solución, formulada como:
, donde controla el equilibrio entre la escasez y el error de reconstrucción. Esto da la solución óptima global. [8] Véase también Aprendizaje de diccionarios en línea para codificación dispersa.
Los métodos de entrenamiento paramétrico tienen como objetivo 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. Los enfoques notables incluyen:
Muchos enfoques comunes para el aprendizaje disperso de diccionarios se basan en el hecho de que todos los datos de entrada (o al menos un conjunto de datos de entrenamiento lo suficientemente grande) están disponibles para el algoritmo. Sin embargo, este podría no ser el caso en el mundo real, ya que el tamaño de los datos de entrada podría 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 medida que nuevos puntos de datos estén disponibles.
Un diccionario se puede aprender en línea de la siguiente manera: [13]
Este método nos permite actualizar gradualmente el diccionario a medida que hay nuevos datos disponibles 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 algunos elementos básicos aprendidos de los propios datos, ha dado lugar a resultados de última generación en diversas tareas de procesamiento de imágenes y vídeos. Esta técnica se puede aplicar a problemas de clasificación de manera que si hemos creado diccionarios específicos para cada clase, la señal de entrada se puede clasificar encontrando el diccionario correspondiente a la representación más escasa.
También tiene propiedades que son útiles para eliminar el 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 escasa, pero el ruido en la entrada tendrá una representación mucho menos escasa. [14]
El aprendizaje disperso de diccionarios 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 la agrupación en clústeres 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 la electroencefalografía (EEG), la electrocardiografía (ECG), la resonancia magnética (MRI), la MRI funcional (fMRI), los monitores continuos de glucosa [19] y la tomografía computarizada por ultrasonido (USCT), donde se utilizan diferentes suposiciones para analizar cada señal.