Aprendizaje escaso de diccionario - Sparse dictionary learning

Parte de una serie sobre
Aprendizaje automático y minería de datos
Problemas Clasificación Agrupación Regresión Detección de anomalías Limpieza de datos AutoML reglas de asociación Aprendizaje reforzado Predicción estructurada Ingeniería de características Aprendizaje de funciones Aprender en línea Aprendizaje semi-supervisado Aprendizaje sin supervisión Aprendiendo a clasificar Inducción gramatical
Aprendizaje supervisado ( clasificación  • regresión ) Árboles de decisión Conjuntos Harpillera Impulsando Bosque aleatorio k -NN Regresión lineal Bayes ingenuo Redes neuronales artificiales Regresión logística Perceptrón Máquina de vectores de relevancia (RVM) Máquina de vectores de soporte (SVM)
Agrupación ABEDUL CURA Jerárquico k -significa Expectativa-maximización (EM) DBSCAN ÓPTICA Cambio medio
Reducción de dimensionalidad Análisis factorial CCA ICA LDA NMF PCA PGD t-SNE
Predicción estructurada Modelos graficos Red de Bayes Campo aleatorio condicional Markov oculto
Detección de anomalías k -NN Factor de valor atípico local
Red neuronal artificial Autoencoder Computación cognitiva Aprendizaje profundo DeepDream Perceptrón multicapa RNN LSTM GRU ESN Máquina de Boltzmann restringida GAN SOM Red neuronal convolucional U-Net Transformador Red neuronal en aumento Memtransistor RAM electroquímica (ECRAM)
Aprendizaje reforzado Q-aprendizaje SARSA Diferencia temporal (TD)
Teoría Compensación entre sesgo y varianza Teoría del aprendizaje computacional Minimización de riesgos empíricos Aprendizaje de Occam Aprendizaje PAC Aprendizaje estadístico Teoría de VC
Lugares de aprendizaje automático NeurIPS ICML ML JMLR ArXiv: cs.LG
Artículos relacionados Glosario de inteligencia artificial Lista de conjuntos de datos para la investigación de aprendizaje automático Esquema del aprendizaje automático
v t mi

La codificación dispersa es un método de aprendizaje de representación que tiene como objetivo encontrar una representación dispersa de los datos de entrada (también conocida como codificación dispersa ) 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 demasiado completo. Esta configuración problemática también permite que la dimensionalidad de las señales que se representan sea más alta 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 escaso de diccionarios se encuentra en 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 se puede recuperar con solo 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 se transfiere una matriz o un vector de alta dimensión a un espacio disperso, se pueden usar diferentes 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 de diccionarios es que el diccionario debe inferirse de los datos de entrada. La aparición de métodos de aprendizaje de diccionario dispersos fue estimulada por el hecho de que en el procesamiento de señales uno normalmente quiere representar los datos de entrada utilizando la menor cantidad posible de componentes. Antes de este enfoque, la práctica general era utilizar diccionarios predefinidos (como transformadas de Fourier o wavelet ). Sin embargo, en ciertos casos, un diccionario capacitado para ajustarse a los datos de entrada puede mejorar significativamente la dispersión, 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, la fusión de imágenes y la pintura.

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 escasas. 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}}$, donde ,${\ 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}}}$se requiere restringir para que sus átomos no alcancen valores arbitrariamente altos, lo que permite valores arbitrariamente bajos (pero distintos de cero) de . controla la compensación 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. En algunos casos L ¹ -norma es conocida para asegurar escasez y lo que lo anterior se convierte en una optimización convexa problema con respecto a cada una de las variables y cuando el otro es fijo, pero no es convexa en forma conjunta . ${\ Displaystyle \ mathbf {D}}$${\ Displaystyle \ mathbf {R}}$${\ Displaystyle (\ mathbf {D}, \ mathbf {R})}$

Propiedades del diccionario

El diccionario definido anteriormente puede estar "incompleto" si o "demasiado completo" en caso de que este último sea una suposición típica para un problema de aprendizaje de diccionario escaso. El caso de un diccionario completo no aporta ninguna mejora desde el punto de vista de la representación y, por 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á 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 la 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 limitar la elección de átomos. ${\ Displaystyle d_ {1}, ..., d_ {n}}$

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

Un diccionario demasiado completo 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 modo 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 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 escasa óptima con un diccionario dado se conoce como aproximación escasa (o, a veces, simplemente un problema de codificación escasa). Se han desarrollado varios algoritmos para resolverlo (como la búsqueda de coincidencias y LASSO ) y se incorporan en los algoritmos que se describen a continuación. ${\ Displaystyle R}$${\ Displaystyle \ mathbf {D}}$

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 escaso problema de aprendizaje del diccionario. 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:

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

Aquí, denota la norma Frobenius . MOD alterna entre obtener la codificación escasa utilizando un método como búsqueda de coincidencias y actualizar el diccionario calculando la solución analítica del problema dada por dónde está un pseudoinverso de Moore-Penrose . Después de que 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). ${\ 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 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. ${\ Displaystyle X}$

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 . Hace cumplir 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: ${\ Displaystyle x_ {i}}$${\ Displaystyle T_ {0}}$

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

La esencia de este algoritmo es primero arreglar el diccionario, encontrar lo mejor posible bajo la restricción anterior (usando Ortogonal 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 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 siendo eficiente solo para señales con dimensionalidad relativamente baja y con la posibilidad de quedarse atascado en mínimos locales. ${\ Displaystyle E_ {k}}$${\ Displaystyle d_ {k}}$${\ Displaystyle x_ {k}}$

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. La idea de este método es actualizar el diccionario usando 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 con 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}}$

Método dual de Lagrange

Un algoritmo basado en la resolución de un problema lagrangiano dual proporciona una manera eficiente de resolver que el diccionario no tenga complicaciones inducidas por la función de dispersión. 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}$

Luego podemos 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 de calcular porque la cantidad de variables duales es muchas veces mucho menor que la cantidad de variables en el problema primario. ${\ Displaystyle n}$

LAZO

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

${\ Displaystyle \ min _ {r \ in \ mathbb {R} ^ {n}} \ {\, \, \ | r \ | _ {1} \} \, \, {\ text {sujeto a}} \ , \, \ | 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 L ¹ en el vector de solución, formulado 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 la compensación entre la escasez y el error de reconstrucción. Esto proporciona la solución óptima global. Consulte también Aprendizaje de diccionario en línea para codificación dispersa${\ Displaystyle \ lambda> 0}$

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. Esto permite construir diccionarios generalizados más potentes que se pueden aplicar potencialmente a los casos de señales de tamaño arbitrario. Los enfoques notables incluyen:

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

Aprendizaje de diccionarios en línea ( enfoque LASSO )

Muchos enfoques comunes para el aprendizaje escaso 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 escenario del 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 . Tales casos se encuentran en el campo de estudio del aprendizaje en línea, que esencialmente sugiere actualizar iterativamente el modelo a medida que los nuevos puntos de datos estén disponibles. ${\ Displaystyle X}$${\ Displaystyle x}$

Un diccionario se puede aprender en línea de la siguiente manera:

1. Para ${\ Displaystyle t = 1 ... T:}$
2. Dibujar una nueva muestra ${\ Displaystyle x_ {t}}$
3. Encuentre una codificación escasa 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. Actualice el diccionario usando el enfoque de bloques de coordenadas :${\ 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 hay nuevos datos disponibles para el aprendizaje de representación escasa 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 del diccionario, es decir, la descomposición lineal de una señal de entrada utilizando algunos elementos básicos aprendidos de los datos mismos, ha dado lugar a resultados de vanguardia en diversas tareas de procesamiento de imágenes y vídeo. Esta técnica se puede aplicar a problemas de clasificación de manera que si hemos construido 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 dispersa, pero el ruido en la entrada tendrá una representación mucho menos dispersa.

El aprendizaje escaso del diccionario 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 la agrupación en clústeres sin supervisión. En evaluaciones con el modelo Bag-of-Words , se encontró empíricamente que la codificación escasa supera a otros enfoques de codificación en las tareas de reconocimiento de categorías de objetos.

El aprendizaje de diccionario se utiliza para analizar las señales médicas en detalle. Dichas señales médicas incluyen las de electroencefalografía (EEG), electrocardiografía (ECG), resonancia magnética (MRI), resonancia magnética funcional (fMRI), monitores continuos de glucosa y tomografía computarizada por ultrasonido (USCT), donde se utilizan diferentes suposiciones para analizar cada señal.

Ver también

• Aproximación escasa
• PCA escasa
• K-SVD
• Factorización de matrices
• Codificación neural escasa

Referencias