stringtranslate.com

Aprendizaje escaso del diccionario

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.

Eliminación de ruido de imágenes mediante el aprendizaje de diccionarios

Planteamiento del problema

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 .

Propiedades del diccionario

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.

Algoritmos

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.

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 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

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.

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. [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.

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. [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.

LAZO

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.

Métodos de entrenamiento paramétrico.

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:

Aprendizaje de diccionarios en línea (enfoque LASSO)

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]

  1. Para
  2. dibujar una nueva muestra
  3. Encuentre una codificación dispersa usando LARS :
  4. Actualice el diccionario utilizando el enfoque de coordenadas de bloque :

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).

Aplicaciones

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.

Ver también

Referencias

  1. ^ Needell, D.; Tropp, JA (2009). "CoSaMP: recuperación iterativa de señales de muestras incompletas e inexactas". Análisis Armónico Aplicado y Computacional . 26 (3): 301–321. arXiv : 0803.2392 . doi :10.1016/j.acha.2008.07.002.
  2. ^ Lotfi, M.; Vidyasagar, M."Un algoritmo rápido no iterativo para la detección de compresión utilizando matrices de medición binarias"
  3. ^ AM Tillmann, "Sobre la intratabilidad computacional del aprendizaje de diccionarios exacto y aproximado", IEEE Signal Processing Letters 22(1), 2015: 45–49.
  4. ^ Donoho, David L. (1 de junio de 2006). "Para la mayoría de los grandes sistemas indeterminados de ecuaciones lineales, la solución mínima de norma 𝓁1 es también la solución más dispersa". Comunicaciones sobre Matemática Pura y Aplicada . 59 (6): 797–829. doi :10.1002/cpa.20132. ISSN  1097-0312. S2CID  8510060.
  5. ^ Engan, K .; Aase, SO; Hakon Husoy, J. (1 de enero de 1999). "Método de direcciones óptimas para el diseño de marcos". 1999 Conferencia internacional IEEE sobre acústica, habla y procesamiento de señales. Actas. ICASSP99 (Nº de catálogo 99CH36258) . vol. 5. págs. 2443–2446 vol.5. doi :10.1109/ICASSP.1999.760624. ISBN 978-0-7803-5041-0. S2CID  33097614.
  6. ^ Aarón, Mical ; Elad, Michael (2008). "Modelado escaso y redundante de contenido de imagen utilizando un diccionario de firmas de imágenes". Revista SIAM de Ciencias de la Imagen . 1 (3): 228–247. CiteSeerX 10.1.1.298.6982 . doi :10.1137/07070156x. 
  7. ^ Lee, Honglak y col. "Algoritmos de codificación dispersos eficientes". Avances en los sistemas de procesamiento de información neuronal . 2006.
  8. ^ Kumar, Abhay; Kataria, Saurabh. "Aplicaciones basadas en aprendizaje de diccionarios en el procesamiento de imágenes mediante optimización convexa" (PDF) .
  9. ^ Rubinstein, R.; Bruckstein, AM; Elad, M. (1 de junio de 2010). "Diccionarios para modelado de representaciones dispersas". Actas del IEEE . 98 (6): 1045-1057. CiteSeerX 10.1.1.160.527 . doi :10.1109/JPROC.2010.2040551. ISSN  0018-9219. S2CID  2176046. 
  10. ^ Engan, Kjersti ; Skretting, Karl; Husøy, John Haakon (1 de enero de 2007). "Familia de algoritmos de aprendizaje de diccionarios iterativos basados ​​en LS, ILS-DLA, para representación de señales dispersas". Dígito. Proceso de señal . 17 (1): 32–49. doi :10.1016/j.dsp.2006.02.002. ISSN  1051-2004.
  11. ^ Mairal, J.; Sapiro, G.; Elad, M. (1 de enero de 2008). "Aprendizaje de representaciones dispersas multiescala para restauración de imágenes y vídeos". Modelado y simulación multiescala . 7 (1): 214–241. CiteSeerX 10.1.1.95.6239 . doi : 10.1137/070697653. ISSN  1540-3459. 
  12. ^ Rubinstein, R.; Zibulevsky, M.; Elad, M. (1 de marzo de 2010). "Doble dispersión: aprendizaje de diccionarios dispersos para la aproximación de señales dispersas". Transacciones IEEE sobre procesamiento de señales . 58 (3): 1553-1564. Código Bib : 2010ITSP...58.1553R. CiteSeerX 10.1.1.183.992 . doi :10.1109/TSP.2009.2036477. ISSN  1053-587X. S2CID  7193037. 
  13. ^ Mairal, Julien; Bach, Francisco; Ponce, Jean; Sapiro, Guillermo (1 de marzo de 2010). "Aprendizaje en línea para factorización matricial y codificación dispersa". J. Mach. Aprender. Res . 11 : 19–60. arXiv : 0908.0050 . Código Bib : 2009arXiv0908.0050M. ISSN  1532-4435.
  14. ^ Aharon, M , M Elad y A Bruckstein. 2006. "K-SVD: un algoritmo para diseñar diccionarios supercompletos para una representación escasa". Procesamiento de señales, transacciones IEEE en 54 (11): 4311-4322
  15. ^ Peyré, Gabriel (6 de noviembre de 2008). "Modelado disperso de texturas" (PDF) . Revista de visión y imágenes matemáticas . 34 (1): 17–31. doi :10.1007/s10851-008-0120-3. ISSN  0924-9907. S2CID  15994546.
  16. ^ Ramírez, Ignacio; Sprechmann, Pablo; Sapiro, Guillermo (1 de enero de 2010). "Clasificación y agrupación mediante aprendizaje de diccionario con incoherencia estructurada y características compartidas". Conferencia de la IEEE Computer Society de 2010 sobre visión por computadora y reconocimiento de patrones. Los Alamitos, CA, EE.UU.: IEEE Computer Society. págs. 3501–3508. doi :10.1109/CVPR.2010.5539964. ISBN 978-1-4244-6984-0. S2CID  206591234.
  17. ^ Koniusz, Piotr; Yan, Fei; Mikolajczyk, Krystian (1 de mayo de 2013). "Comparación de enfoques de codificación de características de nivel medio y estrategias de agrupación en la detección de conceptos visuales". Visión por computadora y comprensión de imágenes . 117 (5): 479–492. CiteSeerX 10.1.1.377.3979 . doi :10.1016/j.cviu.2012.10.010. ISSN  1077-3142. 
  18. ^ Koniusz, Piotr; Yan, Fei; Gosselin, Philippe Henri; Mikolajczyk, Krystian (24 de febrero de 2017). "Agrupación de ocurrencias de orden superior para bolsas de palabras: detección de conceptos visuales" (PDF) . Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 39 (2): 313–326. doi :10.1109/TPAMI.2016.2545667. hdl : 10044/1/39814 . ISSN  0162-8828. PMID  27019477. S2CID  10577592.
  19. ^ AlMatouq, Ali; LalegKirati, TaousMeriem; Novara, Carlos; Ivana, Rabona; Vicente, Tyrone (15 de marzo de 2019). "Reconstrucción escasa de flujos de glucosa mediante monitores continuos de glucosa". Transacciones IEEE/ACM sobre biología computacional y bioinformática . 17 (5): 1797–1809. doi :10.1109/TCBB.2019.2905198. hdl : 10754/655914 . ISSN  1545-5963. PMID  30892232. S2CID  84185121.