How smoothing the affinity matrix affects neighborhood preservation in t-SNE

Resumo Técnico: Como o Suavizamento da Matriz de Afinidade Afeta a Preservação de Vizinhança no t-SNE

Declaração do Problema
O t-SNE (t-Distributed Stochastic Neighbor Embedding) é uma técnica de redução de dimensionalidade amplamente utilizada, conhecida por preservar estruturas de vizinhança local. No entanto, apesar de sua popularidade, os embeddings do t-SNE frequentemente exibem pontuações baixas de preservação absoluta de vizinhança, e os erros são frequentemente distribuídos de forma desigual. Embora muito da pesquisa tenha se concentrado em melhorar a preservação da estrutura global do t-SNE ou na otimização do procedimento de otimização (ex: inicialização, taxas de aprendizado), houve uma investigação explícita limitada sobre se a preservação da estrutura local do t-SNE pode ser melhorada modificando a própria matriz de afinidade de alta dimensão.

Os autores observam que, no t-SNE padrão, as distribuições de probabilidade condicional (linhas de afinidade) são frequentemente muito "agudas" (sharp), o que significa que alguns vizinhos próximos dominam a massa de probabilidade. Além disso, a agudeza dessas distribuições varia entre os pontos de dados. O artigo investiga como a "agudeza" dessas distribuições de afinidade influencia a preservação de vizinhança em diferentes escalas e se modificar essa agudeza pode gerar melhores embeddings do que o t-SNE padrão ou métodos multiescala alternativos.

Metodologia
O estudo introduz uma perturbação controlada à construção de afinidade padrão do t-SNE: uma transformação de potência por linha aplicada às probabilidades condicionais $p_{j|i}$.

1. A Transformação: Para um dado ponto $i$, as probabilidades condicionais são transformadas usando um parâmetro $\gamma \geq 0$:
   $$\tilde{p}_{j|i} = \frac{p_{j|i}^\gamma}{\sum_{m \neq i} p_{m|i}^\gamma}$$

   • $\gamma = 1$: Recupera o t-SNE padrão.
   • $\gamma < 1$ (Suavizamento/Smoothing): Reduz as grandes probabilidades em relação às menores, redistribuindo a massa para vizinhos de menor probabilidade.
   • $\gamma > 1$ (Aguçamento/Sharpening): Concentra ainda mais a massa nos maiores valores de probabilidade.
   • $\gamma = 0$: Resulta em uma distribuição uniforme sobre os vizinhos (descartando a ordem de classificação).

2. Caracterização Teórica:

   • Os autores provam que esta transformação de potência é matematicamente equivalente ao redimensionamento da largura de banda Gaussiana ($\sigma_i$) do kernel original. Especificamente, a nova largura de banda efetiva torna-se $\tilde{\sigma}_i = \sigma_i / \sqrt{\gamma}$.
   • Crucialmente, ao contrário de alterar o parâmetro de perplexidade global $\rho$ (que força cada ponto a ter o mesmo número efetivo de vizinhos), a aplicação de um $\gamma$ fixo resulta em perplexidades efetivas dependentes do ponto. A perplexidade efetiva varia com base na forma da distribuição original para cada ponto específico.

3. Configuração Experimental:

   • O método foi implementado dentro do openTSNE e avaliado nos conjuntos de dados MNIST, UCI Adult e Mouse Cortex.
   • A métrica principal para avaliação foi a Sobreposição de Vizinhança em $k$ (NO@k), medindo a fração de vizinhos mais próximos de alta dimensão preservados no embedding.
   • Comparações foram feitas contra o t-SNE padrão, variando a perplexidade global, e contra construções de afinidade alternativas (Multiescala, Sigma Fixo, Uniforme e tt-SNE).

Principais Resultados
Os experimentos revelam um trade-off claro dependente de escala governado por $\gamma$:

• Aguçamento ($\gamma > 1$): Melhora a preservação dos vizinhos mais próximos (pequenos $k$). No entanto, o desempenho degrada-se rapidamente conforme $k$ aumenta.
• Suavizamento ($\gamma < 1$): Melhora a preservação de vizinhanças locais mais amplas (médio alcance de $k$) e a estrutura global.
  • Especificamente, o suavizamento com $\gamma \approx 0,7$ superou o t-SNE padrão e os métodos multiescala na faixa "médio-local" ($k \approx 25–90$).
  • O suavizamento também melhorou a preservação da estrutura global (medida pela correlação de postos de Spearman das distâncias), particularmente em perplexidades mais altas.
• Comparação com o Ajuste de Perplexidade Global: Simplesmente aumentar a perplexidade global $\rho$ no t-SNE padrão não replica os benefícios do suavizamento. O suavizamento cria uma distribuição heterogênea de tamanhos de vizinhança efetivos entre os pontos, enquanto o aumento de $\rho$ desloca uniformemente a escala para todos os pontos. Consequentemente, o t-SNE suavizado alcançou pontuações de NO@k mais altas em valores específicos de $k$ médio do que o t-SNE padrão com perplexidades equivalentes ou superiores.
• Comparação com Outros Métodos: Na faixa médio-local, a variante suavizada ($\gamma=0,7$) superou o Multiscale Mixture e os métodos Multiscale, que incorporam múltiples escalas de largura de banda. As variantes aguçadas ($\gamma=1,5$) dominaram em $k$ muito pequenos, enquanto as distribuições uniformes ($\gamma=0$) dominaram em $k$ muito grandes.

Significância e Alegações
O artigo alega que a agudeza da afinidade é um eixo de comportamento do t-SNE significativo e anteriormente pouco explorado. As principais contribuições são:

1. Desacoplamento do Tamanho e da Distribuição de Vizinhança: O estudo demonstra que o número de vizinhos (controlado pela perplexidade) e a distribuição da massa de probabilidade entre eles (controlada por $\gamma$) são fatores distintos.
2. Ajuste Leve (Lightweight Tuning): O parâmetro $\gamma$ oferece aos praticantes um mecanismo simples e leve para deslocar o foco do embedding:
   • Use afinidades mais aguçadas ($\gamma > 1$) se o objetivo for alta fidelidade para os vizinhos mais próximos.
   • Use afinidades mais suaves ($\gamma < 1$) para melhorar a preservação de estruturas locais mais amplas e a topologia global.
3. Limitações: Os autores notam modestamente que, embora as melhorias sejam consistentes, elas são modestas em termos absolutos. O estudo foca em uma única medida de qualidade (NO@k), e a tradução prática dessas melhorias métricas para insights de domínio específicos permanece uma questão aberta. Adicionalmente, os hiperparâmetros ideais ($\rho, \gamma$) para valores específicos de $k$ não foram exaustivamente otimizados neste trabalho.

Em conclusão, o artigo argumenta que o t-SNE padrão pode concentrar a massa de probabilidade excessivamente nos primeiros vizinhos, limitando sua capacidade de preservar estruturas locais mais amplas. Ao suavizar a matriz de afinidade, é possível redistribuir essa massa para vizinhos de ranking médio, aumentando assim a confiabilidade das subestruturas de clusters e do layout global sem alterar o procedimento de otimização ou a escalabilidade computacional.