Optimizations and applications of the t-distributed stochastic neighbor embedding algorithm : an approach based on high scalability solutions

Abstract

Resumo: O t-Distributed Stochastic Neighbor Embedding (t-SNE) é uma técnica amplamente usada para redução de dimensionalidade, mas é limitada por sua escalabilidade quando aplicada a grandes conjuntos de dados. Uma aproximação bem-sucedida do t-SNE chamada BH-tSNE foi recentemente proposta, a qual transforma uma etapa do algoritmo original em um problema de simulação de N-Corpos, que pode ser resolvido pelo algoritmo Barnes-Hut. No entanto, essa melhoria ainda tem limitações para processar grandes volumes de dados (milhões de registros). Estudos posteriores como t-SNE-CUDA usaram GPUs para paralelizar a execução do BH-tSNE. A pesquisa desta dissertação desenvolveu uma nova implementação em GPU do BH-tSNE que produz resultados em duas e três dimensões. Examinamos os problemas de escalabilidade em duas das etapas mais caras do GPU BH-tSNE usando estratégias eficientes de acesso à memória, técnicas de aceleração recentes para GPU e uma nova abordagem para calcular a estrutura de grafos de K-Vizinhos mais próximos (KNN Graph) usada no GPU BH-tSNE. Nosso design permite uma aceleração do tempo de execução em até 460% quando comparado à implementação t-SNE-CUDA. Considerando as tecnologias emergentes de Inteligência Artificial (IA) aplicadas a conjuntos de dados em grande escala, vários estudos focam ou usam a redução de dimensionalidade como t-SNE para visualizar os dados. A literatura conta com vários métodos de redução de dimensionalidade para processar grandes conjuntos de dados. Esta pesquisa também comparou diferentes técnicas para realizar a redução de dimensionalidade usando conjuntos de dados em grande escala obtidos de aplicações do mundo real. A comparação enfocou na relação entre as características dos algoritmos, a qualidade dos resultados e a interpretação dos pontos de dados de baixa dimensão. Nossos experimentos concluíram que estratégias como o método denominado AtSNE podem melhorar a qualidade da redução de dimensionalidade, considerando a preservação da informação global. No entanto, não pode obter resultados melhores do que outras práticas, como usar a Análise de Componentes Principais na inicialização do t-SNE. Ainda assim, as idéias de ambos os métodos podem ser combinadas em uma única técnica por estudos futuros. Comparamos sete métodos considerando duas aplicações de IA: Aprendizagem por Reforço e Redes Adversariais Gerativas (GAN). As principais contribuições desta pesquisa consistem na proposta de duas técnicas denominadas SWW-tSNE (Simulated Wide-Warp t-SNE) e SWW-AtSNE (Simulated Wide-Warp AtSNE) para realizar a redução da dimensionalidade em duas ou três dimensões. Esta dissertação também propôs um algoritmo denominado RSFK (Random Sample Forest KNN) que utiliza GPU para calcular uma estrutura denominada Approximate KNN Graph, necessária no algoritmo BH t-SNE. A preservação de estruturas globais foi medida com uma nova métrica chamada Preservação de Vizinhança Média.

Abstract: The t-Distributed Stochastic Neighbor Embedding (t-SNE) is a widely used technique for dimensionality reduction but is limited by its scalability when applied to large datasets. A successful approximation of t-SNE called BH-tSNE was recently proposed, which transforms a step of the original algorithm into an N-Body simulation problem that a modified Barnes-Hut algorithm can solve. However, this improvement still has limitations to process large data volumes (millions of records). Late studies such as t-SNE-CUDA have used GPUs to implement highly parallel BH-tSNE. The research of this thesis has developed a new GPU BH-tSNE implementation that produces the embedding of multidimensional data points into three-dimensional space. We examine scalability issues in two of the most expensive steps of GPU BH-tSNE by using efficient memory access strategies, recent acceleration techniques, and a new approach to compute the KNN graph structure used in BH-tSNE with GPU. Our design allows an acceleration of the execution time in up to 460% when compared to the t-SNE-CUDA implementation. Considering the emergent technologies of Artificial Intelligence (AI) applied to large-scale datasets, numerous studies focus on or use dimensionality reduction like t-SNE to visualize the data. The literature counts with various dimensionality reduction methods to process large datasets. This research also compared different techniques to perform dimensionality reduction using large-scale datasets obtained from real-world applications. The comparison focused on the relation between the characteristics of the algorithms, the quality of the results, and the interpretation of the low dimensional data points. Our experiments conclude that strategies like a method called AtSNE could improve dimensionality reduction quality, considering global information preservation. However, it cannot achieve better results than other practices like using the Principal Component Analysis in the initialization of t-SNE. Still, the ideas of both methods could be merged into a unique technique in future studies. We have compared seven methods considering two AI applications: Reinforcement Learning and Generative Adversarial Networks (GAN). The major contributions of this research consist in the proposal of two techniques named SWW-tSNE (Simulated Wide-Warp t-SNE) and SWW-AtSNE (Simulated Wide-Warp AtSNE) to perform dimensionality reduction in two or three dimensions. This thesis also proposes an algorithm named RSFK (Random Sample Forest KNN) that uses GPU to compute a structure called Approximate KNN Graph, required in BH t-SNE algorithm. The preservation of global structures was measured with a new metric called Medium Neighborhood Preservation (MNP).