Complementary t-SNE-UMAP Optimization for High-Dimensional Data Visualization

Resumo Técnico: Otimização Complementar t-SNE–UMAP para Visualização de Dados de Alta Dimensionalidade

Declaração do Problema
A visualização de dados de alta dimensionalidade é desafiadora porque a redução de dados para duas ou três dimensões frequentemente resulta na perda de relações estruturais críticas. Embora o t-Distributed Stochastic Neighbor Embedding (t-SNE) seja altamente eficaz na preservação de estruturas de vizinhança local, ele pode ter dificuldades com a geometria global e exige uma interpretação cuidadosa das distâncias entre clusters. Por outro lado, o Uniform Manifold Approximation and Projection (UMAP) oferece eficiência computacional e boa continuidade, mas otimiza uma função objetivo diferente. As abordagens existentes frequentemente envolvem escolher um método em detrimento do outro ou combinar dois embeddings completados independentemente. Os autores argumentam que essas estratégias falham em aproveitar as forças complementares de ambos os algoritmos dentro de um único processo de otimização, especificamente perdendo a oportunidade de usar a estrutura de grafo do UMAP para corrigir representações de vizinhança fracas no t-SNE.

Metodologia
O método proposto introduz um framework híbrido onde a informação do UMAP é integrada diretamente no processo de otimização do t-SNE, em vez de fundir dois embeddings separados. A inovação central é um mecanismo de ponderação de arestas complementar projetado para aplicar a orientação do UMAP apenas onde o t-SNE é fraco.

1. Ponderação de Arestas Complementar:
   O método define um peso complementar $C_{ij}$ para uma aresta entre as amostras $i$ e $j$:
   $$C_{ij} = W^U_{ij} (1 - T^{tSNE}_{ij})$$
   Onde $W^U_{ij}$ é o peso do grafo difuso do UMAP e $T^{tSNE}_{ij}$ é a confiança normalizada da afinidade do t-SNE.

   • Se o UMAP conecta fortemente dois pontos, mas a confiança do t-SNE é baixa, $C_{ij}$ torna-se grande, adicionando uma força de atração forte.
   • Se ambos os métodos já concordam em uma relação forte, $C_{ij}$ torna-se pequeno, evitando influência redundante.

2. Objetivo de Otimização:
   A função objetivo final combina a divergência de Kullback–Leibler (KL) padrão do t-SNE com um termo de atração esparso baseado nas arestas complementares do UMAP:
   $$L_H(Y, t) = D_{KL}(P^{tSNE} || Q^Y) + \lambda(t) L_C(Y)$$
   Crucialmente, o termo complementar $L_C(Y)$ não inclui os termos repulsivos de não-aresta do UMAP, garantindo que a estrutura primária permaneça impulsionada pelo t-SNE.

3. Ativação Retardada:
   Para evitar interferência na formação inicial de clusters, o termo complementar é desativado durante a fase de "exagero precoce" (early exaggeration) do t-SNE. Seu peso $\lambda(t)$ é aumentado gradualmente usando um cronograma de smoothstep após a fase de exagero precoce (especificamente após 250 iterações nos experimentos) até atingir um valor máximo ($\lambda_{max} = 0.05$).

4. Inicialização:
   A otimização é inicializada usando um embedding de UMAP, fornecendo um ponto de partida favorável para o processo de t-SNE.

Principais Contribuições
O artigo descreve cinco contribuições primárias:

1. Framework: Um novo híbrido t-SNE–UMAP onde a informação do grafo UMAP é utilizada dentro do loop de otimização do t-SNE.
2. Estratégia de Ponderação: A introdução do peso de confiança complementar $C_{ij}$, que ajusta dinamicamente a influência do UMAP com base na força da afinidade existente do t-SNE.
3. Cronograma de Otimização: Uma estratégia de ativação retardada que introduz o termo complementar apenas após a fase de exagero precoce para preservar a integridade da otimização inicial do t-SNE.
4. Controle Rigoroso: O uso de um controle KL correspondente (t-SNE inicializado por UMAP sem o termo complementar) e várias variantes de ablação para isolar os efeitos específicos da inicialização, atração de grafo e regularização complementar.
5. Avaliação Abrangente: Testes extensos em nove conjuntos de dados de referência (incluindo MNIST, CIFAR-10/100 e dados tabulares) usando uma ampla gama de métricas (confiabilidade, continuidade, recall de vizinhança, preservação de densidade e preservação de distância global) juntamente com testes de significância estatística.

Resultos
O método foi avaliado contra t-SNE padrão, UMAP padrão, t-SNE inicializado por UMAP e outros métodos não lineares (densMAP, TriMap, PaCMAP, LocalMAP) em nove conjuntos de dados.

• Confiabilidade (Trustworthiness) e Recall de Vizinhança: O método proposto (A6) alcançou a maior média de confiabilidade (0.9602) e recall de vizinhança (0.4426) entre todos os métodos testados.
• Significância Estatística: Comparado ao controle de KL correspondente (A3), o método proposto melhorou a confiabilidade em todos os nove conjuntos de dados. Essa melhoria foi estatisticamente significativa após a correção de Holm ($p_{Holm} = 0.046875$) com um tamanho de efeito pareado grande ($d_z = 1.47$).
• Compromissos (Trade-offs): A melhoria na confiabilidade da vizinhança local veio com um compromisso. O método mostrou uma preservação de densidade significativamente menor em comparação ao controle correspondente ($p_{Holm} = 0.046875$).
• Estrutura Global: Não houve melhoria significativa na preservação de distância Euclidiana ou Jensen–Shannon global em comparação ao t-SNE padrão. De fato, o t-SNE padrão reteve pontuações de distância Euclidiana global ligeiramente superiores.
• Tempo de Execução: O pipeline proposto foi aproximadamente 1,77 vezes mais lento que o t-SNE padrão (58,59s vs. 33,01s), principalmente devido à inicialização do UMAP e ao framework de otimização customizado, e não ao termo complementar em si.

Significância e Alegações
Os autores alegam que a principal significância deste trabalho reside em demonstrar que a confiabilidade da vizinhança local pode ser aumentada pela integração seletiva de informações de grafo complementares, em vez de simplesmente pela média de embeddings.

O artigo afirma explicitamente que o método não é uma solução universal para melhorar todos os aspectos da redução de dimensionalidade. Em vez disso, ele oferece um benef_io específico: melhorar a confiabilidade das vizinhanças locais (reduzindo falsos vizinhos) enquanto mantém uma qualidade estrutural geral competitiva. Os autores enfatizam que este ganho vem com um compromisso claro na preservação da densidade e no aumento do tempo de execução. Consequentemente, o método é mais adequado para aplicações onde a precisão das relações de vizinhança local é a prioridade sobre a preservação da densidade ou o tempo de execução mínimo. Os resultados sugerem que métodos híbridos devem ser avaliados usando múltiplas métricas, pois otimizar para uma propriedade estrutural (confiabilidade local) pode inerentemente degradar outras (densidade).