Aprendizagem de dicionário esparsa - Sparse dictionary learning

Parte de uma série sobre
Aprendizado de máquina e mineração de dados
Problemas Classificação Clustering Regressão Detecção de anomalia Limpeza de Dados AutoML Regras de associação Aprendizagem por reforço Previsão estruturada Engenharia de recursos Aprendizagem de recursos Aprendizagem online Aprendizagem semissupervisionada Aprendizagem não supervisionada Aprendendo a classificar Indução gramatical
Aprendizagem supervisionada ( classificação  • regressão ) Árvores de decisão Conjuntos Ensacamento Boosting Floresta aleatória k -NN Regressão linear Baías ingénuas Redes neurais artificiais Regressão logística Perceptron Máquina de vetor de relevância (RVM) Máquina de vetores de suporte (SVM)
Clustering BÉTULA CURA Hierárquico k- significa Expectativa-maximização (EM) DBSCAN ÓPTICA Mudança média
Redução de dimensionalidade Análise Fatorial CCA ICA LDA NMF PCA PGD t-SNE
Previsão estruturada Modelos gráficos Rede Bayes Campo aleatório condicional Markov Oculto
Detecção de anomalia k -NN Fator de outlier local
Rede neural artificial Autoencoder Computação cognitiva Aprendizagem profunda DeepDream Perceptron multicamadas RNN LSTM GRU ESN Máquina de Boltzmann restrita GAN SOM Rede neural convolucional U-Net Transformador Spiking rede neural Memtransistor RAM eletroquímica (ECRAM)
Aprendizagem por reforço Q-learning SARSA Diferença temporal (TD)
Teoria Compensação de polarização-variância Teoria de aprendizagem computacional Minimização de risco empírico Aprendizagem Occam Aprendizagem PAC Aprendizagem estatística Teoria VC
Locais de aprendizado de máquina NeurIPS ICML ML JMLR ArXiv: cs.LG
Artigos relacionados Glossário de inteligência artificial Lista de conjuntos de dados para pesquisa de aprendizado de máquina Esboço do aprendizado de máquina
v t e

A codificação esparsa é um método de aprendizagem de representação que visa encontrar uma representação esparsa dos dados de entrada (também conhecida como codificação esparsa ) na forma de uma combinação linear de elementos básicos, bem como os próprios elementos básicos. Esses elementos são chamados de átomos e compõem um dicionário . Os átomos no dicionário não precisam ser ortogonais e podem ser um conjunto de abrangência supercompleto. Esta configuração do problema também permite que a dimensionalidade dos sinais sendo representados seja maior do que a dos sinais sendo observados. As duas propriedades acima levam a ter átomos aparentemente redundantes que permitem várias representações do mesmo sinal, mas também fornecem uma melhoria na dispersão e flexibilidade da representação.

Uma das aplicações mais importantes do aprendizado de dicionário esparso é no campo de detecção compactada ou recuperação de sinal . No sensoriamento comprimido, um sinal de alta dimensão pode ser recuperado com apenas algumas medições lineares, desde que o sinal seja esparso ou quase esparso. Como nem todos os sinais satisfazem essa condição de esparsidade, é de grande importância encontrar uma representação esparsa desse sinal, como a transformada wavelet ou o gradiente direcional de uma matriz rasterizada. Uma vez que uma matriz ou um vetor de alta dimensão é transferido para um espaço esparso, diferentes algoritmos de recuperação como busca de base , CoSaMP ou algoritmos não iterativos rápidos podem ser usados ​​para recuperar o sinal.

Um dos princípios-chave do aprendizado de dicionário é que o dicionário deve ser inferido a partir dos dados de entrada. O surgimento de métodos de aprendizado de dicionário esparso foi estimulado pelo fato de que, no processamento de sinais, normalmente se deseja representar os dados de entrada usando o mínimo de componentes possível. Antes dessa abordagem, a prática geral era usar dicionários predefinidos (como Fourier ou transformações wavelet ). No entanto, em certos casos, um dicionário treinado para ajustar os dados de entrada pode melhorar significativamente a dispersão, que tem aplicações na decomposição, compressão e análise de dados e tem sido usado nas áreas de eliminação de ruído e classificação de imagens , processamento de vídeo e áudio . Dicionários esparsos e supercompletos têm imensas aplicações em compressão de imagens, fusão de imagens e pintura interna.

Declaração do problema

Dado o conjunto de dados de entrada , desejamos encontrar um dicionário e uma representação de forma que ambos sejam minimizados e as representações sejam esparsas o suficiente. Isso pode ser formulado como o seguinte problema de otimização : ${\ 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}}$, onde ,${\ 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}}}$é necessário restringir de modo que seus átomos não alcancem valores arbitrariamente altos, permitindo valores arbitrariamente baixos (mas diferentes de zero) de . controla a compensação entre a dispersão e o erro de minimização. ${\ displaystyle \ mathbf {D}}$${\ displaystyle r_ {i}}$${\ displaystyle \ lambda}$

O problema de minimização acima não é convexo por causa da ℓ ₀ - "norma" e resolver este problema é NP-difícil. Em alguns casos, a norma L ¹ é conhecida por garantir a esparsidade e, portanto, o acima se torna um problema de otimização convexo em relação a cada uma das variáveis e quando a outra é fixa, mas não é convexa em conjunto . ${\ displaystyle \ mathbf {D}}$${\ displaystyle \ mathbf {R}}$${\ displaystyle (\ mathbf {D}, \ mathbf {R})}$

Propriedades do dicionário

O dicionário definido acima pode ser "incompleto" se ou "incompleto" no caso de o último ser uma suposição típica para um problema de aprendizado de dicionário esparso. O caso de um dicionário completo não oferece nenhuma melhoria do ponto de vista representacional e, portanto, não é considerado. ${\ displaystyle \ mathbf {D}}$${\ displaystyle n <d}$${\ displaystyle n> d}$

Dicionários incompletos representam a configuração na qual os dados de entrada reais estão em um espaço de dimensão inferior. Este caso está fortemente relacionado à redução de dimensionalidade e técnicas como a análise de componentes principais, que requerem que os átomos sejam ortogonais. A escolha desses subespaços é crucial para uma redução eficiente da dimensionalidade, mas não é trivial. E a redução da dimensionalidade com base na representação do dicionário pode ser estendida para tratar de tarefas específicas, como análise ou classificação de dados. No entanto, sua principal desvantagem é limitar a escolha dos átomos. ${\ displaystyle d_ {1}, ..., d_ {n}}$

Dicionários supercompletos, no entanto, não exigem que os átomos sejam ortogonais (eles nunca serão uma base de qualquer maneira), permitindo, assim, dicionários mais flexíveis e representações de dados mais ricas.

Um dicionário supercompleto que permite a representação esparsa do sinal pode ser uma famosa matriz de transformação (transformada de wavelets, transformada de Fourier) ou pode ser formulada de modo que seus elementos sejam alterados de forma a representar esparsamente o sinal dado da melhor maneira. Dicionários aprendidos são capazes de fornecer soluções mais esparsas em comparação com matrizes de transformação predefinidas.

Algoritmos

Como o problema de otimização descrito acima pode ser resolvido como um problema convexo com relação ao dicionário ou à codificação esparsa enquanto o outro dos dois é fixo, a maioria dos algoritmos é baseada na ideia de atualizar iterativamente um e depois o outro.

O problema de encontrar uma codificação esparsa ideal com um determinado dicionário é conhecido como aproximação esparsa (ou, às vezes, apenas problema de codificação esparsa). Vários algoritmos foram desenvolvidos para resolvê-lo (como a busca de correspondência e LASSO ) e são incorporados aos algoritmos descritos abaixo. ${\ displaystyle R}$${\ displaystyle \ mathbf {D}}$

Método das direções ideais (MOD)

O método das direções ótimas (ou MOD) foi um dos primeiros métodos introduzidos para lidar com o problema de aprendizado de dicionário esparso. A ideia central disso é resolver o problema de minimização sujeito ao número limitado de componentes diferentes de zero do vetor de representação:

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

Aqui, denota a norma Frobenius . MOD alterna entre obter a codificação esparsa usando um método como a busca de correspondência e atualizar o dicionário computando a solução analítica do problema dado por onde está um pseudoinverso de Moore-Penrose . Depois que essa atualização é renormalizada para se ajustar às restrições, a nova codificação esparsa é obtida novamente. O processo é repetido até a convergência (ou até um resíduo suficientemente pequeno). ${\ displaystyle F}$${\ displaystyle \ mathbf {D} = XR ^ {+}}$${\ displaystyle R ^ {+}}$${\ displaystyle \ mathbf {D}}$

O MOD provou ser um método muito eficiente para dados de entrada de baixa dimensão que requerem apenas algumas iterações para convergir. No entanto, devido à alta complexidade da operação de inversão de matriz, calcular o pseudoinverso em casos de alta dimensão é, em muitos casos, intratável. Essa deficiência inspirou o desenvolvimento de outros métodos de aprendizagem de dicionário. ${\ displaystyle X}$

K-SVD

K-SVD é um algoritmo que executa SVD em seu núcleo para atualizar os átomos do dicionário um por um e basicamente é uma generalização de K-means . Ele impõe que cada elemento dos dados de entrada seja codificado por uma combinação linear de não mais do que elementos de uma forma idêntica à abordagem 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}}$

A essência deste algoritmo é primeiro fixar o dicionário, encontrar o melhor possível sob a restrição acima (usando Orthogonal Matching Pursuit ) e então atualizar iterativamente os átomos do dicionário da seguinte maneira: ${\ 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}}$

As próximas etapas do algoritmo incluem a aproximação de classificação 1 da matriz residual , atualizando e reforçando a dispersão de após a atualização. Este algoritmo é considerado padrão para aprendizagem de dicionário e é usado em uma variedade de aplicações. No entanto, ele compartilha pontos fracos com o MOD, sendo eficiente apenas para sinais com dimensionalidade relativamente baixa e tendo a possibilidade de ficar preso em mínimos locais. ${\ displaystyle E_ {k}}$${\ displaystyle d_ {k}}$${\ displaystyle x_ {k}}$

Descida do gradiente estocástico

Pode-se também aplicar um método difundido de descida gradiente estocástico com projeção iterativa para resolver esse problema. A ideia deste método é atualizar o dicionário usando o gradiente estocástico de primeira ordem e projetá-lo no conjunto de restrições . A etapa que ocorre na i-ésima iteração é descrita por esta expressão: ${\ 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 \}}$, onde é um subconjunto aleatório de e é uma etapa de gradiente. ${\ displaystyle S}$${\ displaystyle \ {1 ... K \}}$${\ displaystyle \ delta _ {i}}$

Método dual de Lagrange

Um algoritmo baseado na solução de um problema Lagrangeano dual fornece uma maneira eficiente de resolver o dicionário, sem complicações induzidas pela função de esparsidade. Considere o seguinte 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)}$, onde há uma restrição na norma dos átomos e são as chamadas variáveis ​​duais que formam a matriz diagonal . ${\ displaystyle c}$${\ displaystyle \ lambda _ {i}}$${\ displaystyle \ Lambda}$

Podemos, então, fornecer uma expressão analítica para o dual de Lagrange após a minimização 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)}$.

Depois de aplicar um dos métodos de otimização ao valor do dual (como o método de Newton ou gradiente conjugado ), obtemos o valor de : ${\ displaystyle \ mathbf {D}}$

${\ displaystyle \ mathbf {D} ^ {T} = (RR ^ {T} + \ Lambda) ^ {- 1} (XR ^ {T}) ^ {T}}$

Resolver este problema é menos difícil computacionalmente porque a quantidade de variáveis ​​duais é muitas vezes muito menor do que a quantidade de variáveis ​​no problema primordial. ${\ displaystyle n}$

LAÇO

Nesta abordagem, o problema de otimização é formulado como:

${\ displaystyle \ min _ {r \ in \ mathbb {R} ^ {n}} \ {\, \, \ | r \ | _ {1} \} \, \, {\ text {sujeito a}} \ , \, \ | X- \ mathbf {D} R \ | _ {F} ^ {2} <\ epsilon}$, onde está o erro permitido na reconstrução LASSO. ${\ displaystyle \ epsilon}$

Ele encontra uma estimativa de minimizando o erro mínimo quadrado sujeito a uma restrição da norma L ¹ no vetor de solução, formulado como: ${\ displaystyle r_ {i}}$

${\ displaystyle \ min _ {r \ in \ mathbb {R} ^ {n}} \, \, {\ dfrac {1} {2}} \, \, \ | X- \ mathbf {D} r \ | _ {F} ^ {2} + \ lambda \, \, \ | r \ | _ {1}}$, onde controla a compensação entre a dispersão e o erro de reconstrução. Isso dá a solução ótima global. Veja também Aprendizagem de dicionário online para codificação esparsa${\ displaystyle \ lambda> 0}$

Métodos de treinamento paramétrico

Os métodos de treinamento paramétrico visam incorporar o melhor dos dois mundos - o reino dos dicionários construídos analiticamente e os aprendidos. Isso permite construir dicionários generalizados mais poderosos que podem ser potencialmente aplicados aos casos de sinais de tamanho arbitrário. Abordagens notáveis ​​incluem:

• Dicionários invariantes de tradução. Esses dicionários são compostos pelas traduções dos átomos originados do dicionário construído para um patch de sinal de tamanho finito. Isso permite que o dicionário resultante forneça uma representação para o sinal de tamanho arbitrário.
• Dicionários multiescala. Este método se concentra na construção de um dicionário que é composto de dicionários com escalas diferentes para melhorar a dispersão.
• Dicionários esparsos. Este método se concentra não apenas em fornecer uma representação esparsa, mas também em construir um dicionário esparso que é reforçado pela expressão onde está algum dicionário analítico predefinido com propriedades desejáveis, como computação rápida e é uma matriz esparsa. Tal formulação permite combinar diretamente a implementação rápida de dicionários analíticos com a flexibilidade de abordagens esparsas.${\ displaystyle \ mathbf {D} = \ mathbf {B} \ mathbf {A}}$${\ displaystyle \ mathbf {B}}$${\ displaystyle \ mathbf {A}}$

Aprendizagem de dicionário online ( abordagem LASSO )

Muitas abordagens comuns para o aprendizado de dicionário esparso dependem do fato de que todos os dados de entrada (ou pelo menos um conjunto de dados de treinamento grande o suficiente) estão disponíveis para o algoritmo. No entanto, pode não ser o caso no cenário do mundo real, pois o tamanho dos dados de entrada pode ser muito grande para caber na memória. O outro caso em que essa suposição não pode ser feita é quando os dados de entrada vêm na forma de um fluxo . Esses casos situam-se no campo de estudo da aprendizagem online, o que sugere essencialmente a atualização iterativa do modelo após a disponibilização de novos pontos de dados . ${\ displaystyle X}$${\ displaystyle x}$

Um dicionário pode ser aprendido online da seguinte maneira:

1. Para ${\ displaystyle t = 1 ... T:}$
2. Desenhe uma nova amostra ${\ displaystyle x_ {t}}$
3. Encontre uma codificação esparsa 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. Atualize o dicionário usando a abordagem de coordenada de bloco :${\ 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 atualizar gradualmente o dicionário à medida que novos dados se tornam disponíveis para o aprendizado de representação esparsa e ajuda a reduzir drasticamente a quantidade de memória necessária para armazenar o conjunto de dados (que geralmente tem um tamanho enorme).

Formulários

A estrutura de aprendizagem de dicionário, ou seja, a decomposição linear de um sinal de entrada usando alguns elementos básicos aprendidos a partir dos próprios dados, levou a resultados de última geração em várias tarefas de processamento de imagem e vídeo. Essa técnica pode ser aplicada a problemas de classificação de forma que, se tivermos construído dicionários específicos para cada classe, o sinal de entrada pode ser classificado encontrando o dicionário correspondente à representação mais esparsa.

Ele também tem propriedades que são úteis para a redução de ruído do sinal, uma vez que normalmente se pode aprender um dicionário para representar a parte significativa do sinal de entrada de uma forma esparsa, mas o ruído na entrada terá uma representação muito menos esparsa.

O aprendizado de dicionário esparso foi aplicado com sucesso a várias tarefas de processamento de imagem, vídeo e áudio, bem como à síntese de textura e agrupamento não supervisionado. Em avaliações com o modelo Bag-of-Words , a codificação esparsa foi encontrada empiricamente para superar outras abordagens de codificação nas tarefas de reconhecimento de categoria de objeto.

O aprendizado do dicionário é usado para analisar os sinais médicos em detalhes. Esses sinais médicos incluem aqueles de eletroencefalografia (EEG), eletrocardiografia (ECG), ressonância magnética (MRI), MRI funcional (fMRI), monitores de glicose contínuos e tomografia computadorizada de ultrassom (USCT), onde diferentes suposições são usadas para analisar cada sinal.

Veja também

• Aproximação esparsa
• PCA esparso
• K-SVD
• Fatoração de matriz
• Codificação esparsa neural

Referências