stringtranslate.com

Aprendizaje de diccionarios dispersos

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 esos elementos básicos en sí mismos. Estos elementos se denominan átomos y componen un diccionario . No se requiere que los átomos en el diccionario sean 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 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 la flexibilidad de la representación.

Una de las aplicaciones más importantes del aprendizaje de diccionario disperso 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 se puede recuperar 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 de escasez, es de gran importancia 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 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 el diccionario debe inferirse a partir de los datos de entrada. La aparición de métodos de aprendizaje de diccionarios dispersos fue estimulada por el hecho de que en el procesamiento de señales uno normalmente quiere representar los datos de entrada usando la menor cantidad posible de componentes. Antes de este enfoque, la práctica general era usar diccionarios predefinidos (como transformadas de Fourier o wavelet ). Sin embargo, en ciertos casos un diccionario que se entrena para ajustarse a los datos de entrada puede mejorar significativamente la escasez, lo que tiene aplicaciones en la descomposición, compresión y análisis de datos y se ha utilizado en los campos de eliminación de ruido y clasificación de imágenes , procesamiento de video y audio . Los diccionarios dispersos y sobrecompletos tienen inmensas aplicaciones en la compresión de imágenes, fusión de imágenes y restauración de imágenes.

Eliminación de ruido de imágenes mediante aprendizaje por diccionario

Planteamiento del problema

Dado el conjunto de datos de entrada, deseamos encontrar un diccionario y una representación tal que ambos se minimicen y las representaciones sean lo suficientemente dispersas. Esto se puede formular como el siguiente problema de optimización :

, dónde ,

se requiere restringir de modo que sus átomos no alcancen valores arbitrariamente altos, lo que permite 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 convexo en .

Propiedades del diccionario

El diccionario definido anteriormente puede ser "subcompleto" si o "sobrecompleto" en caso de que sea este último caso una suposición típica para un problema de aprendizaje de diccionarios dispersos. El caso de un diccionario completo no proporciona ninguna mejora desde un punto de vista representacional y, por lo tanto, no se considera.

Los diccionarios incompletos representan una 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. Y la reducción de dimensionalidad basada en la representación de diccionarios se puede ampliar para abordar tareas específicas como el análisis o la clasificación de datos. Sin embargo, su principal desventaja es limitar 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 dispersa de la señal puede ser una matriz de transformación famosa (transformación wavelet, transformación de Fourier) o puede formularse de modo 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 proporcionar 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 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 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 ) 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 de aprendizaje del diccionario disperso. [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 donde es una pseudoinversa de Moore-Penrose . Después de esta actualización se renormaliza para ajustarse a las restricciones y se obtiene nuevamente 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 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 matriz, 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 ejecuta SVD en su núcleo para actualizar los átomos del diccionario uno por uno y básicamente es una generalización de K-means . Implica que cada elemento de los datos de entrada esté codificado por 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 el 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 la aplicación de la escasez de 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 una dimensionalidad relativamente baja y tiene la posibilidad de quedarse atascado en mínimos locales.

Descenso de gradiente estocástico

También se puede aplicar un método de descenso de gradiente estocástico generalizado 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 sobre el conjunto de restricciones . El paso que ocurre en la iteración i-ésima 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 solución de un problema lagrangiano dual proporciona una forma eficiente de resolver el diccionario sin complicaciones inducidas por la función de escasez. [7] Considere el siguiente lagrangiano:

, donde es una restricción en la norma de los átomos y son las llamadas variables duales que forman la matriz diagonal .

Podemos entonces 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 complicado computacionalmente porque la cantidad de variables duales es muchas veces mucho menor que la cantidad de variables en el problema primal.

LAZO

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

, donde es el error permitido en la reconstrucción LASSO.

Se obtiene una estimación de minimizando el error de mínimos cuadrados sujeto a una restricción de norma L 1 en el vector solución, formulado como:

, 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

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 el de los aprendidos. [9] Esto permite construir diccionarios generalizados más potentes que pueden aplicarse potencialmente a los casos de señales de tamaño arbitrario. Entre los enfoques destacados se incluyen:

Aprendizaje de diccionarios en línea (enfoque LASSO)

Muchos enfoques comunes para el aprendizaje de diccionarios dispersos 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, esto podría no ser el caso en el escenario del mundo real, ya que el tamaño de los datos de entrada podría ser demasiado grande para que quepan en la memoria. El otro caso en el que esta suposición no se puede realizar 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 se disponga de nuevos puntos de datos .

Se puede aprender un diccionario de forma online de la siguiente manera: [13]

  1. Para
  2. Extraer una nueva muestra
  3. Encuentre una codificación dispersa usando LARS :
  4. Actualizar 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 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 de aprendizaje de diccionarios, es decir, la descomposición lineal de una señal de entrada utilizando unos pocos elementos básicos aprendidos de los propios datos, ha dado lugar a resultados de última generación [ cita requerida ] en diversas tareas de procesamiento de imágenes y vídeos. Esta técnica se puede aplicar a problemas de clasificación de forma 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 dispersa. También tiene propiedades que son ú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 en la entrada tendrá una representación mucho menos dispersa. [14]

El aprendizaje de diccionario disperso se ha aplicado con éxito a varias tareas de procesamiento de imágenes, videos y audio, así como a la síntesis de texturas [15] y al agrupamiento no supervisado. [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 por diccionario se utiliza para analizar señales médicas en detalle. Entre estas señales médicas se incluyen las de electroencefalografía (EEG), electrocardiografía (ECG), resonancia magnética (RM), resonancia magnética funcional (RMf), monitorización continua de glucosa [19] y tomografía computarizada por ultrasonido (USCT), donde se utilizan diferentes supuestos para analizar cada señal.

Véase también

Referencias

  1. ^ Needell, D.; Tropp, JA (2009). "CoSaMP: Recuperación iterativa de señales a partir de muestras incompletas e inexactas". Análisis armónico computacional y aplicado . 26 (3): 301–321. arXiv : 0803.2392 . doi :10.1016/j.acha.2008.07.002.
  2. ^ Lotfi, M.; Vidyasagar, M. "Un algoritmo rápido y no iterativo para detección compresiva utilizando matrices de medición binarias"
  3. ^ AM Tillmann, "Sobre la intratabilidad computacional del aprendizaje de diccionarios exactos y aproximados", 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". Communications on Pure and Applied Mathematics . 59 (6): 797–829. doi :10.1002/cpa.20132. ISSN  1097-0312. S2CID  8510060.
  5. ^ Engan, K. ; Aase, SO; Hakon Husoy, J. (1999-01-01). "Método de direcciones óptimas para el diseño de marcos". Conferencia internacional IEEE de 1999 sobre acústica, habla y procesamiento de señales. Actas. ICASSP99 (Cat. No.99CH36258) . Vol. 5. págs. 2443–2446 vol.5. doi :10.1109/ICASSP.1999.760624. ISBN 978-0-7803-5041-0. Número de identificación del sujeto  33097614.
  6. ^ Aharon, Michal ; Elad, Michael (2008). "Modelado disperso y redundante del contenido de imágenes mediante un diccionario de firmas de imágenes". Revista SIAM sobre ciencias de la imagen . 1 (3): 228–247. CiteSeerX 10.1.1.298.6982 . doi :10.1137/07070156x. 
  7. ^ Lee, Honglak, et al. "Algoritmos de codificación dispersa eficientes". Avances en 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 representación dispersa". 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 la 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 escasez: aprendizaje de diccionarios dispersos para la aproximación de señales dispersas". IEEE Transactions on Signal Processing . 58 (3): 1553–1564. Bibcode :2010ITSP...58.1553R. CiteSeerX 10.1.1.183.992 . doi :10.1109/TSP.2009.2036477. ISSN  1053-587X. S2CID  7193037. 
  13. ^ Mairal, Julien; Bach, Francis; Ponce, Jean; Sapiro, Guillermo (1 de marzo de 2010). "Aprendizaje en línea para factorización de matrices y codificación dispersa". J. Mach. Learn. Res . 11 : 19–60. arXiv : 0908.0050 . Código Bibliográfico :2009arXiv0908.0050M. ISSN  1532-4435.
  14. ^ Aharon, M , M Elad y A Bruckstein. 2006. "K-SVD: Un algoritmo para diseñar diccionarios sobrecompletos para representación dispersa". 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 imágenes y visión matemática . 34 (1): 17–31. doi :10.1007/s10851-008-0120-3. ISSN  0924-9907. S2CID  15994546.
  16. ^ Ramirez, Ignacio; Sprechmann, Pablo; Sapiro, Guillermo (1 de enero de 2010). "Clasificación y agrupamiento mediante aprendizaje de diccionarios con incoherencia estructurada y características compartidas". Conferencia de la IEEE Computer Society sobre visión artificial y reconocimiento de patrones de 2010. Los Alamitos, CA, EE. UU.: IEEE Computer Society. pp. 3501–3508. doi :10.1109/CVPR.2010.5539964. ISBN 978-1-4244-6984-0.S2CID206591234  .​
  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). "Agrupamiento de ocurrencias de orden superior para bolsas de palabras: detección visual de conceptos" (PDF) . IEEE Transactions on Pattern Analysis and Machine Intelligence . 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, Carlo; Ivana, Rabbone; Vincent, Tyrone (15 de marzo de 2019). "Reconstrucción dispersa de flujos de glucosa utilizando monitores de glucosa continuos". 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.