K-SVD - K-SVD

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

En matemáticas aplicadas , K-SVD es un algoritmo de aprendizaje de diccionario para crear un diccionario para representaciones dispersas , a través de un enfoque de descomposición de valores singulares . K-SVD es una generalización del método de agrupación de k-means y funciona alternando iterativamente entre la codificación dispersa de los datos de entrada basados ​​en el diccionario actual y la actualización de los átomos en el diccionario para que se ajusten mejor a los datos. Está relacionado estructuralmente con el algoritmo de maximización de expectativas (EM). K-SVD se puede encontrar ampliamente en aplicaciones como procesamiento de imágenes, procesamiento de audio, biología y análisis de documentos.

Descripción del problema

El objetivo del aprendizaje del diccionario es aprender una matriz de diccionario demasiado completa que contiene átomos de señal (en esta notación, columnas de ). Un vector de señal puede representarse, en forma escasa , como una combinación lineal de estos átomos; Para representar , el vector de representación debe satisfacer la condición exacta , o la condición aproximada , precisada al requerir que para algún valor pequeño ε y alguna norma L _p . El vector contiene los coeficientes de representación de la señal . Normalmente, la norma se selecciona como L ₁ , L ₂ o L _∞ . ${\displaystyle D\in \mathbb {R} ^{n\times K}}$${\displaystyle K}$${\displaystyle D}$${\displaystyle y\in \mathbb {R} ^{n}}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y=Dx}$${\displaystyle y\approx Dx}$${\displaystyle \|y-Dx\|_{p}\leq \epsilon }$${\displaystyle x\in \mathbb {R} ^{K}}$${\displaystyle y}$${\displaystyle p}$

Si y D es una matriz de rango completo, hay un número infinito de soluciones disponibles para el problema de representación. Por lo tanto, se deben establecer restricciones en la solución. Además, para garantizar la escasez, se prefiere la solución con el menor número de coeficientes distintos de cero. Por tanto, la representación de la escasez es la solución de ${\displaystyle n<K}$

${\displaystyle (P_{0})\quad \min \limits _{x}\|x\|_{0}\qquad {\text{subject to }}y=Dx}$

o

${\displaystyle (P_{0,\epsilon })\quad \min \limits _{x}\|x\|_{0}\qquad {\text{subject to }}\|y-Dx\|_{2}\leq \epsilon }$

donde cuenta las entradas distintas de cero en el vector . (Ver la "norma" cero ). ${\displaystyle \|x\|_{0}}$${\displaystyle x}$

Algoritmo K-SVD

K-SVD es una especie de generalización de K-medias, como sigue. La agrupación de k-medias también se puede considerar como un método de representación dispersa . Es decir, encontrar el mejor libro de códigos posible para representar las muestras de datos por vecino más cercano , resolviendo ${\displaystyle \{y_{i}\}_{i=1}^{M}}$

${\displaystyle \quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\forall i,x_{i}=e_{k}{\text{ for some }}k.}$

que es equivalente a

${\displaystyle \quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\quad \forall i,\|x_{i}\|_{0}=1}$.

La letra F denota la norma Frobenius . El término de representación dispersa obliga al algoritmo K-means a usar solo un átomo (columna) en el diccionario . Para relajar esta restricción, el objetivo del algoritmo K-SVD es representar la señal como una combinación lineal de átomos en . ${\displaystyle x_{i}=e_{k}}$${\displaystyle D}$${\displaystyle D}$

El algoritmo K-SVD sigue el flujo de construcción del algoritmo K-means. Sin embargo, a diferencia de las K-medias, para lograr una combinación lineal de átomos en , el término de escasez de la restricción se relaja de modo que el número de entradas distintas de cero de cada columna puede ser mayor que 1, pero menor que un número . ${\displaystyle D}$${\displaystyle x_{i}}$${\displaystyle T_{0}}$

Entonces, la función objetivo se convierte en

${\displaystyle \quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\quad \forall i\;,\|x_{i}\|_{0}\leq T_{0}.}$

o en otra forma objetiva

${\displaystyle \quad \min \limits _{D,X}\sum _{i}\|x_{i}\|_{0}\qquad {\text{subject to }}\quad \forall i\;,\|Y-DX\|_{F}^{2}\leq \epsilon .}$

En el algoritmo K-SVD, primero se fija y se encuentra la mejor matriz de coeficientes . Como es imposible encontrar lo verdaderamente óptimo , utilizamos un método de búsqueda por aproximación. Cualquier algoritmo como OMP, la búsqueda de emparejamiento ortogonal se puede utilizar para el cálculo de los coeficientes, siempre que pueda proporcionar una solución con un número fijo y predeterminado de entradas distintas de cero . ${\displaystyle D}$${\displaystyle X}$${\displaystyle X}$${\displaystyle T_{0}}$

Después de la tarea de codificación escasa, lo siguiente es buscar un diccionario mejor . Sin embargo, es imposible encontrar todo el diccionario a la vez, por lo que el proceso consiste en actualizar solo una columna del diccionario cada vez, mientras se corrige . La actualización de la -ésima columna se realiza reescribiendo el término de penalización como ${\displaystyle D}$${\displaystyle D}$${\displaystyle X}$${\displaystyle k}$

${\displaystyle \|Y-DX\|_{F}^{2}=\left\|Y-\sum _{j=1}^{K}d_{j}x_{j}^{T}\right\|_{F}^{2}=\left\|\left(Y-\sum _{j\neq k}d_{j}x_{j}^{T}\right)-d_{k}x_{k}^{T}\right\|_{F}^{2}=\|E_{k}-d_{k}x_{k}^{T}\|_{F}^{2}}$

donde denota el k fila -ésimo de X . ${\displaystyle x_{k}^{T}}$

Al descomponer la multiplicación en la suma de las matrices de rango 1, podemos asumir que los otros términos se suponen fijos y la -ésima permanece desconocida. Después de este paso, podemos resolver el problema de minimización aproximando el término con una matriz usando la descomposición de valores singulares y luego actualizar con ella. Sin embargo, es muy probable que se complete la nueva solución de vector porque no se aplica la restricción de esparcimiento. ${\displaystyle DX}$${\displaystyle K}$${\displaystyle K-1}$${\displaystyle k}$${\displaystyle E_{k}}$${\displaystyle rank-1}$${\displaystyle d_{k}}$${\displaystyle x_{k}^{T}}$

Para curar este problema, defina como ${\displaystyle \omega _{k}}$

${\displaystyle \omega _{k}=\{i\mid 1\leq i\leq N,x_{k}^{T}(i)\neq 0\},}$

que apunta a ejemplos que usan atom (también las entradas de eso son distintas de cero). Luego, defina como una matriz de tamaño , con unos en las entradas y ceros en caso contrario. Al multiplicar , esto reduce el vector de fila descartando las entradas cero. De manera similar, la multiplicación es el subconjunto de los ejemplos que están usando el átomo. El mismo efecto se puede ver en . ${\displaystyle \{y_{i}\}_{i=1}^{N}}$${\displaystyle d_{k}}$${\displaystyle x_{i}}$${\displaystyle \Omega _{k}}$${\displaystyle N\times |\omega _{k}|}$${\displaystyle (i,\omega _{k}(i)){\text{-th}},}$${\displaystyle {\tilde {x}}_{k}^{T}=x_{k}^{T}\Omega _{k}}$${\displaystyle x_{k}^{T}}$${\displaystyle {\tilde {Y}}_{k}=Y\Omega _{k}}$${\displaystyle d_{k}}$${\displaystyle {\tilde {E}}_{k}=E_{k}\Omega _{k}}$

Entonces el problema de minimización como se mencionó anteriormente se convierte en

${\displaystyle \|E_{k}\Omega _{k}-d_{k}x_{k}^{T}\Omega _{k}\|_{F}^{2}=\|{\tilde {E}}_{k}-d_{k}{\tilde {x}}_{k}^{T}\|_{F}^{2}}$

y se puede hacer directamente usando SVD. SVD se descompone en . La solución para es la primera columna de U, el vector de coeficientes como la primera columna de . Después de actualizar todo el diccionario, el proceso pasa a resolver iterativamente X, luego resolver iterativamente D. ${\displaystyle {\tilde {E}}_{k}}$${\displaystyle U\Delta V^{T}}$${\displaystyle d_{k}}$${\displaystyle {\tilde {x}}_{k}^{T}}$${\displaystyle V\times \Delta (1,1)}$

Limitaciones

La elección de un "diccionario" apropiado para un conjunto de datos es un problema no convexo, y K-SVD opera mediante una actualización iterativa que no garantiza encontrar el óptimo global. Sin embargo, esto es común a otros algoritmos para este propósito, y K-SVD funciona bastante bien en la práctica.

Ver también

• Aproximación escasa
• Valor singular de descomposición
• Norma de matriz
• Agrupación de K-medias
• Aproximación de rango bajo

Referencias