Redução de dimensão escalável

9

Considerando o número de recursos constante, o Barnes-Hut t-SNE possui uma complexidade de , projeções aleatórias e PCA têm uma complexidade de tornando-os "acessíveis" para conjuntos de dados muito grandes.O(nlogn)O(n)

Por outro lado, os métodos baseados no dimensionamento multidimensional têm uma complexidade .O(n2)

Existem outras técnicas de redução de dimensão (além das triviais, como observar as primeiras colunas, é claro) cuja complexidade é menor que ?kO(nlogn)

RUser4512
fonte

Respostas:

5

Uma opção interessante seria explorar a redução de dimensionalidade com base neural. O tipo de rede mais comumente usado para redução de dimensionalidade, o autoencoder, pode ser treinado ao custo de , em que representa as iterações de treinamento (é um hiperparâmetro independente dos dados de treinamento) . Portanto, a complexidade do treinamento simplifica para .O(in)iO(n)

Você pode começar dando uma olhada no trabalho do seminário de 2006 por Hinton e Salakhutdinov [1]. Desde então, as coisas evoluíram muito. Agora, a maioria das atenções é alcançada pelos Autoencodificadores Variacionais [2], mas a idéia básica (uma rede que reconstrói a entrada em sua camada de saída com uma camada de gargalo no meio) permanece a mesma. Observe que, ao contrário de PCA e RP, os auto-codificadores executam uma redução de dimensionalidade não linear. Além disso, ao contrário do t-SNE, os autoencodificadores podem transformar amostras invisíveis sem a necessidade de treinar novamente o modelo inteiro.

No lado prático, recomendo dar uma olhada neste post , que fornece detalhes sobre como implementar diferentes tipos de codificadores automáticos com a maravilhosa biblioteca Keras.

[1] Hinton, GE e Salakhutdinov, RR (2006). Reduzindo a dimensionalidade dos dados com redes neurais. science, 313 (5786), 504-507.

[2] Kingma, DP, & Welling, M. (2013). Bayes variacionais de codificação automática. pré-impressão do arXiv arXiv: 1312.6114.

Daniel López
fonte
11
tecnicamente, você não precisa treinar novamente o modelo para novas amostras com t-SNE usando esta abordagem específica: lvdmaaten.github.io/publications/papers/AISTATS_2009.pdf
bibliolytic
Certo. O autor também sugeriu o treinamento de um regressor multivariado para prever a localização do mapa nas amostras de dados de entrada como uma abordagem potencial. No artigo mencionado, o autor treina uma rede neural para minimizar diretamente a perda de t-SNE. No entanto, em ambos os casos, é necessário definir um modelo ou função explícita para mapear pontos de dados para o espaço resultante, portanto, ele deve ser poderoso o suficiente (camadas / neurônios suficientes) para aprender a incorporação, mas não muito para evitar ajustes excessivos. ... Isso sacrifica parte da usabilidade do t-SNE padrão.
22617 Daniel López
Nenhum desacordo lá, eu só acho que é um pouco impreciso autoencoders contraste e t-SNE como você faz em sua resposta, vendo como t-PND pode ser usado como uma perda para redução de dimensionalidade
bibliolytic
Embora agora que eu li novamente, uma pergunta: podemos realmente dizer que as redes neurais são , visto que elas não garantem a convergência? A notação Big-O tem os piores casos, certo? O(n)
bibliolytic
Eu não queria incluir isso na resposta, pois o cálculo da perda de t-SNE ao treinar uma rede leva tempo em que é o tamanho do minilote. O(m2)m
22617 Daniel López
0

Além dos autoencodificadores mencionados, pode-se tentar explorar o lema de Johnson-Lindenstrauss com projeções aleatórias ou métodos aleatórios de subespaço. Saliências aleatórias são , com o número de amostras de dimensão e a dimensão alvo, CF [1].O(kdN)Ndk

Um pouco de pesquisa no Google fornece resultados muito recentes, principalmente para conjuntos de dados esparsos.

[1] Projeção aleatória na redução de dimensionalidade: aplicações em dados de imagem e texto .

Miguel
fonte