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(nlog⁡n)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(nlog⁡n)

pca dimensionality-reduction large-data multidimensional-scaling tsne 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(i⋅n)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