Aula 8: Redução para Visualização — MDS e t-SNE

Aprendizado Não Supervisionado

Slides Lista de aulas

1 Revisão e Introdução

1.1 Revisão Cuidadosa: O Que a Aula 7 Deixou Pronto

Nas duas aulas anteriores, estudamos a redução de dimensionalidade sob a ótica da reconstrução ótima e da modelagem generativa:

1. Aula 6 (O Mundo Linear): Vimos que a PCA encontra o subespaço linear de dimensão \(M\) que minimiza o erro quadrático de reconstrução \(\frac{1}{N}\sum_n \|\mathbf{x}_n - \tilde{\mathbf{x}}_n\|^2\) ou, equivalentemente, maximiza a variância projetada. Provamos também que a Probabilistic PCA (PPCA) formula essa projeção como um modelo generativo gaussiano de posto reduzido \(\mathbf{x} = \mathbf{W}\mathbf{z} + \boldsymbol\mu + \boldsymbol\epsilon\), e que o autoencoder linear com restrição de posto recupera rigorosamente o mesmo subespaço principal.
2. Aula 7 (O Mundo Não Linear): Estendemos esse princípio para variedades curvadas (manifolds) por meio de autoencoders profundos e autoencoders variacionais (VAEs). No VAE, regularizamos o espaço latente contínuo \(\mathbf{z}\) via divergência \(\mathrm{KL}(q_\phi(\mathbf{z}\mid\mathbf{x}) \parallel p(\mathbf{z}))\) para impor continuidade e densidade a priori \(p(\mathbf{z}) = \mathcal{N}(\mathbf{0}, \mathbf{I})\), permitindo síntese e interpolação.

Em ambos os casos, a métrica de sucesso era clara: quão bem as coordenadas latentes \(\mathbf{z}\) conseguem reconstruir os atributos originais \(\mathbf{x}\). Contudo, existe uma tarefa prática fundamentalmente diferente em ciência de dados: a visualização exploratória em 2D ou 3D para o olho humano. Quando \(D\) é grande (\(D=30\) no câncer de mama, \(D=784\) em imagens de dígitos ou \(D=20.000\) em expressão gênica) e forçamos a dimensão latente a ser estritamente \(d=2\), o critério de reconstrução global colapsa.

1.2 Ideia Central: Preservar Vizinhança \(\neq\) Preservar Distância

A ideia central desta aula apoia-se em um princípio topológico: preservar a topologia de vizinhanças locais é incompatível com a preservação de distâncias métricas globais quando o espaço de destino tem dimensionalidade muito inferior ao espaço de origem.

Em alta dimensão (\(D \gg 2\)), o volume disponível em torno de qualquer ponto cresce exponencialmente com a distância (\(r^D\)). Isso permite que dezenas ou centenas de pontos coexistam como “vizinhos moderadamente distantes” sem interferirem uns nos outros. Ao forçarmos esses pontos a se acomodarem em um plano bidimensional (\(d=2\)), onde a área cresce apenas com \(r^2\), deparamo-nos com o crowding problem (o problema da superlotação). Métodos que tentam preservar distâncias métricas globais (como MDS e PCA) acabam comprimindo todos os agrupamentos no centro do gráfico, misturando classes distintas.

Para superar esse impasse, van der Maaten & Hinton (2008) propuseram o t-SNE (t-Distributed Stochastic Neighbor Embedding). A formulação opera em três frentes: 1. Converte distâncias geométricas rígidas em probabilidades de vizinhança baseadas em similaridade gaussiana. 2. Utiliza a divergência de Kullback-Leibler assimétrica, que pune violentamente falsos afastamentos de vizinhos próximos, mas tolera aproximações de pontos distantes. 3. Substitui a distribuição gaussiana no espaço 2D por uma distribuição \(t\)-Student com 1 grau de liberdade (Cauchy). A cauda pesada da Student-\(t\) alivia a pressão volumétrica: pontos moderadamente distantes na alta dimensão são acomodados muito mais longe no plano sem sofrer penalidade, abrindo espaço para que cada cluster organize com extrema nitidez sua microestrutura interna.

1.3 Roteiro da Aula

Para construir essa teoria de forma rigorosa, estruturaremos a aula em torno de cinco questões fundamentais:

1. Por que métodos de projeção global falham ao mapear dados complexos em 2D? Compreender a impossibilidade geométrica de preservar distâncias globais e vizinhanças locais simultaneamente no plano.
2. Como o MDS formaliza a preservação de distâncias e qual é o viés da função Stress? Analisar a perda quadrática do MDS e provar por que distâncias longas dominam a otimização em detrimento da estrutura fina local.
3. Por que modelar vizinhanças probabilisticamente via divergência KL? Derivar a formulação do SNE (Stochastic Neighbor Embedding), a calibração da Perplexidade via entropia e o papel crucial da assimetria da perda de Kullback-Leibler.
4. De que maneira a distribuição \(t\)-Student de 1 grau de liberdade resolve o crowding problem? Demonstrar como a lei de potência \(1/(1+d^2)\) alivia a pressão de atração entre aglomerados distintos e balanceia as forças de atração e repulsão no gradiente.
5. Quais são as armadilhas metodológicas cruciais na interpretação de projeções t-SNE? Identificar por que distâncias entre clusters, dispersões aparentes e tamanhos de nuvens no t-SNE não refletem diretamente as grandezas físicas do espaço original.

1.4 Problema Motivador: O Esmagamento de Classes em 2D

Para observar o fenômeno empiricamente, tomemos o conjunto de dados MNIST (\(N=1.500\) imagens de dígitos \(28\times 28\), portanto \(D=784\) dimensões) e projetemo-lo em duas dimensões usando três abordagens conceituais distintas: 1. PCA (Aula 6): Projeção linear que preserva a máxima variância global. 2. MDS Métrico: Otimização numérica que tenta preservar todas as distâncias euclidianas par a par minimizando a perda Stress. 3. t-SNE: Minimização da divergência KL com probabilidades baseadas em kernel Student-\(t\) no plano.

O resultado numérico e visual é revelador. Na PCA e no MDS, dígitos com traços distintos (como 4, 7 e 9, ou 3, 5 e 8) ficam confinados em uma nuvem central densa e indistinta. Apenas os dígitos 0 e 1, que possuem variâncias extremas (pixels periféricos quase sempre pretos versus centro preenchido), se afastam ligeiramente. Em contrapartida, o t-SNE desmembra os 10 dígitos em ilhas nítidas e isoladas, mesmo sem ter recebido nenhum rótulo durante o treinamento.

1.5 Pausa Ativa 1: O Dilema da Projeção 2D

DicaO Tetraedro no Plano

Se tivermos 4 pontos mutuamente equidistantes em \(\mathbb{R}^3\) (os vértices de um tetraedro regular tridimensional), é geometricamente possível posicioná-los em uma folha plana \(\mathbb{R}^2\) de modo que as 6 distâncias entre pares permaneçam exatamente iguais?

DicaV ou F: Restrições Geométricas em Baixa Dimensão

Julgue V ou F — a questão só conta se acertar os 4 itens:

• □ Em qualquer espaço euclidiano de dimensão \(d\), o número máximo de pontos mutuamente equidistantes é \(d+1\).
• □ A PCA em 2 componentes preserva perfeitamente as distâncias de vizinhança local entre pontos próximos, pois maximiza a variância projetada.
• □ Quando reduzimos a dimensionalidade de \(D\) para \(d \ll D\), a perda de informação geométrica é matematicamente inevitável a menos que os dados residam em uma variedade afim de dimensão \(\le d\).
• □ O objetivo principal de algoritmos de visualização como t-SNE é permitir a reconstrução dos atributos originais \(\mathbf{x} \in \mathbb{R}^D\) a partir das coordenadas 2D \(\mathbf{y}\).

2 Bloco 1: Preservando Distâncias Métricas — MDS e a Perda Stress

2.1 MDS: Reconstruindo Mapas a Partir de Distâncias

A primeira tentativa histórica e intuitiva de projetar dados preservando a geometria foi o Multidimensional Scaling (MDS) (Torgerson, 1952; Kruskal, 1964).

Imagine a metáfora clássica da cartografia: suponha que você receba uma tabela contendo exclusivamente as distâncias rodoviárias em quilômetros entre todas as capitais brasileiras (São Paulo, Rio de Janeiro, Salvador, Brasília, Porto Alegre), sem qualquer coordenada de latitude ou longitude. É possível reconstruir a posição geográfica relativa de cada cidade em um mapa plano bidimensional?

Essa é exatamente a proposta do MDS. Dado um conjunto de \(N\) objetos cujas distâncias euclidianas (ou dissimilaridades arbitrárias) no espaço original são conhecidas: \[d_{ij}^{(X)} = \|\mathbf{x}_i - \mathbf{x}_j\|_2\] o MDS busca encontrar uma configuração de coordenadas de baixa dimensão \(\mathbf{y}_1, \dots, \mathbf{y}_N \in \mathbb{R}^2\) tais que as distâncias euclidianas no mapa, \(d_{ij}^{(Y)} = \|\mathbf{y}_i - \mathbf{y}_j\|_2\), reproduzam \(d_{ij}^{(X)}\) da forma mais fiel possível.

Na literatura matemática, essa formulação divide-se em duas abordagens: 1. MDS Clássico (Principal Coordinate Analysis — PCoA / Torgerson, 1952): Opera analiticamente sobre a matriz de distâncias quadradas \(\mathbf{D}^{(2)} = [ (d_{ij}^{(X)})^2 ]\). Aplica a operação de centralização dupla via matriz de projeção ortogonal \(\mathbf{H} = \mathbf{I} - \frac{1}{N}\mathbf{1}\mathbf{1}^\top\): \[\mathbf{B} = -\frac{1}{2} \mathbf{H} \mathbf{D}^{(2)} \mathbf{H}\] A matriz \(\mathbf{B}\) representa os produtos internos centrados entre os pontos (\(\mathbf{B} = \mathbf{X}\mathbf{X}^\top\)). As coordenadas ótimas \(\mathbf{Y}\) em 2D são obtidas analiticamente pela decomposição espectral dos dois maiores autovalores e autovetores: \(\mathbf{B} = \mathbf{V}\boldsymbol\Lambda\mathbf{V}^\top \implies \mathbf{Y} = \mathbf{V}_2 \boldsymbol\Lambda_2^{1/2}\). * Teorema de Young-Householder (1938): Se as distâncias \(d_{ij}^{(X)}\) forem estritamente euclidianas, a solução do MDS clássico coincide rigorosamente com a projeção PCA sobre as duas componentes principais! 2. MDS Métrico com Otimização de Stress (Kruskal, 1964): Abandona a exigência de produtos internos e formula o problema como uma otimização não linear direta sobre as distâncias observadas.

2.2 O Critério de Stress de Kruskal (1964)

No MDS métrico moderno, a discrepância entre as distâncias originais e as distâncias projetadas no mapa é quantificada pela função de custo Stress: \[\sigma_M(\mathbf{Y}) = \sum_{i < j} \left( d_{ij}^{(X)} - d_{ij}^{(Y)} \right)^2\]

Para tornar a métrica invariante à escala geral do mapa, define-se o Stress Normalizado (Normalized Stress): \[\text{Stress}(\mathbf{Y}) = \sqrt{ \frac{\sum_{i < j} \left( d_{ij}^{(X)} - d_{ij}^{(Y)} \right)^2}{\sum_{i < j} (d_{ij}^{(X)})^2} }\]

Essa função de perda possui propriedades numéricas importantes: 1. Não possui solução analítica fechada: A presença das normas euclidianas \(\|\mathbf{y}_i - \mathbf{y}_j\|_2 = \sqrt{\sum_k (y_{ik} - y_{jk})^2}\) torna o gradiente não linear e acoplado. 2. Otimização via SMACOF: Algoritmos clássicos (como sklearn.manifold.MDS) resolvem o Stress iterativamente pelo método SMACOF (Scaling by Majorizing a Complicated Function / De Leeuw, 1977), construindo majorantes quadráticos sucessivos que convergem monotonicamente para um mínimo local.

À primeira vista, o critério de Stress parece perfeito: se \(\text{Stress}(\mathbf{Y}) = 0\), todas as distâncias foram perfeitamente preservadas. Mas o que acontece quando é matematicamente impossível zerar o Stress (ao projetar de \(D=784\) para \(d=2\))? Como o algoritmo decide onde alocar o erro inevitável?

2.3 A Falha do Stress: A Tirania das Distâncias Longas

A razão fundamental pela qual o MDS métrico falha em separar agrupamentos no plano 2D reside na própria estrutura quadrática e desponderada da função Stress:

Considere um conjunto de dados com múltiplos aglomerados densos e compare o tratamento de dois pares de pontos:

1. Par Local (Vizinhos do mesmo cluster): Suponha que dois pontos próximos no espaço original tenham distância real \(d_{\text{local}} = 1{,}0\). No mapa 2D, o algoritmo os afasta para \(\|\mathbf{y}_i - \mathbf{y}_j\| = 2{,}0\).
   • O erro relativo é de \(100\%\), o que funde clusters vizinhos e destrói completamente a topologia local.
   • A penalidade imposta no Stress é: \[(1{,}0 - 2{,}0)^2 = \mathbf{1{,}0}\]
2. Par Global (Pontos de clusters opostos): Suponha agora que dois pontos pertencentes a clusters distintos estejam a uma distância macroscópica original \(d_{\text{global}} = 50{,}0\). No mapa 2D, o algoritmo os posiciona a uma distância de \(48{,}0\).
   • O erro relativo é de míseros \(4\%\), absolutamente imperceptível visualmente no gráfico macroscópico.
   • A penalidade imposta no Stress é: \[(50{,}0 - 48{,}0)^2 = \mathbf{4{,}0}\]

O Diagnóstico:
A penalidade do par distante (\(4{,}0\)) é quatro vezes maior que a penalidade do par local (\(1{,}0\))! O otimizador do MDS prefere tolerar um erro catastrófico de \(100\%\) na vizinhança local para economizar um desvio insignificante de \(4\%\) em um par de pontos distantes. As distâncias longas governam a perda com mãos de ferro.

2.4 O Efeito Combinatório

O problema da tirania das distâncias longas torna-se exponencialmente pior quando consideramos a contagem estatística de pares em um conjunto de dados real:

1. Pares Locais (Intra-cluster): Se os dados formam clusters de tamanho médio \(k\), o número de pares que realmente representam vizinhos imediatos é da ordem de: \[N_{\text{local}} \approx O(N \cdot k)\]
2. Pares Globais (Inter-cluster): O número total de pares em um dataset de \(N\) amostras é \(\frac{N(N-1)}{2} \approx \frac{N^2}{2}\). Logo, o número de pares entre aglomerados distintos é da ordem de: \[N_{\text{global}} \approx \mathbf{O(N^2)}\]

Exemplo com o MNIST (\(N = 1.500\) amostras): - O número total de pares é \(\frac{1.500 \times 1.499}{2} = \mathbf{1.124.250\text{ pares}}\)! - Se cada dígito tiver \(\approx 150\) amostras, os pares dentro do mesmo dígito somam apenas \(\approx 110.000\) pares (\(< 10\%\) do total). - Mais de \(90\%\) de todos os termos da função Stress medem distâncias longas entre dígitos completamente distintos!

O Resultado Inevitável:
O gradiente do MDS é completamente sequestrado pelos pares distantes. O algoritmo atua como uma ferramenta macroscópica de rotação e escala global, preservando a forma externa da nuvem mas compactando todas as classes em uma massa disforme sobreposta no centro.

2.5 Tentativas Correção: Sammon e MDS Não-Métrico

Estatísticos e psicometristas perceberam essa limitação cedo e desenvolveram duas correções clássicas para o MDS nos softwares estatísticos:

2.5.1 1. Mapeamento de Sammon (Sammon Mapping / Sammon, 1969)

Para contrabalançar o peso desproporcional dos termos grandes, John W. Sammon propôs ponderar cada resíduo quadrático pelo inverso da distância original: \[E_{\text{Sammon}}(\mathbf{Y}) = \frac{1}{\sum_{i < j} d_{ij}^{(X)}} \sum_{i < j} \frac{\left( d_{ij}^{(X)} - d_{ij}^{(Y)} \right)^2}{\mathbf{d_{ij}^{(X)}}}\]

Observe o impacto do peso \(1/d_{ij}^{(X)}\): - Para um par de vizinhos próximos com \(d_{ij}^{(X)} = 1{,}0\), o peso é \(1 / 1{,}0 = \mathbf{1{,}0}\). - Para um par de pontos distantes com \(d_{ij}^{(X)} = 50{,}0\), o peso despenca para \(1 / 50{,}0 = \mathbf{0{,}02}\) (reduzido em 50 vezes!). O Sammon Mapping (disponível no pacote MASS::sammon do R) foi um marco pioneiro na tentativa de proteger a estrutura local.

2.5.2 2. MDS Não-Métrico (Non-Metric / Ordinal MDS — Kruskal, 1964)

Em muitas ciências sociais e cognitivas, os valores absolutos das distâncias são irrelevantes; apenas a ordem importa (saber quem é mais próximo de quem). O MDS Não-Métrico relaxa as distâncias exatas e exige apenas a preservação da ordem monótona dos postos: \[\text{Se } d_{ij}^{(X)} < d_{kl}^{(X)} \implies d_{ij}^{(Y)} \le d_{kl}^{(Y)}\] Isso é implementado substituindo \(d_{ij}^{(X)}\) por disparidades ajustadas \(\hat{d}_{ij}\) via regressão isotônica, visualizada no clássico Diagrama de Shepard.

2.6 Por Que Abordagens Métricas Falham em 2D

Apesar do progresso trazido pelo Mapeamento de Sammon e pelo MDS Não-Métrico, ambos ainda falham ao tentar visualizar variedades complexas em 2D. Os motivos revelam os limites intrínsecos de qualquer abordagem métrica:

1. Incapacidade de adaptar-se à densidade local: O peso de Sammon (\(1/d_{ij}\)) é puramente geométrico e universal. Mas em distribuições reais, a densidade varia ponto a ponto: uma distância \(d=2{,}0\) pode representar um ponto isolado em um cluster denso, mas um vizinho íntimo em uma região esparsa. Não existe no MDS um mecanismo capaz de calibrar o “tamanho da lupa” individualmente para cada amostra.
2. O aprisionamento no gargalo volumétrico (\(r^D \leftrightarrow r^2\)): Mesmo com pesos invertidos ou regressão ordinal, Sammon e MDS continuam tentando acomodar distâncias métricas no plano \(\mathbb{R}^2\). Como vimos na seção de intuição, em alta dimensão centenas de vizinhos vivem na casca hiperdimensional (\(r^D\)); ao projetar para a área limitada \(r^2\), o plano não possui área física suficiente, gerando um conflito mecânico que esmaga os pontos no centro.

A Ruptura Metodológica Necessária:
Para resolver de fato o problema da visualização em duas dimensões, Hinton & Roweis (2002) perceberam que era preciso uma mudança radical de paradigma: \[\textbf{Abandonar distâncias métricas rígidas} \quad \longrightarrow \quad \textbf{Modelar probabilidades de vizinhança estocástica}\] Essa é a fundação do SNE e do t-SNE.

2.7 Pausa Ativa 2: MDS e o Critério de Stress

DicaErro Absoluto vs. Erro Relativo no MDS

Se um algoritmo de redução de dimensionalidade minimiza \(\sum_{i<j} (d_{ij}^{(X)} - d_{ij}^{(Y)})^2\), qual dos seguintes desvios gera maior aumento na função de custo? - (A) Uma distância entre vizinhos imediatos que era \(0{,}5\) e virou \(2{,}5\). - (B) Uma distância entre pontos de clusters distintos que era \(40{,}0\) e virou \(37{,}0\).

DicaV ou F: Propriedades do MDS

Julgue V ou F — a questão só conta se acertar os 4 itens:

• □ O MDS clássico com centralização dupla aplicado sobre matriz de distâncias euclidianas fornece resultados idênticos aos scores da PCA linear.
• □ Na função Stress quadrática, errar uma distância de \(100\) para \(90\) gera exatamente a mesma penalidade numérica que errar uma distância de \(11\) para \(1\).
• □ O MDS requer obrigatoriamente as coordenadas originais \(\mathbf{X}\); ele não pode ser computado se recebermos apenas uma tabela de dissimilaridades arbitrárias entre indivíduos.
• □ A função de custo do MDS prioriza a preservação de pequenas distâncias de vizinhança local em detrimento de distâncias de longa escala.

3 Bloco 2: Vizinhanças Probabilísticas — SNE e Divergência KL

3.1 O Salto Conceitual do SNE: De Distâncias Métricas a Probabilidades

Para romper com a tirania das distâncias longas, Hinton & Roweis (2002) propuseram uma mudança radical de formulação com o SNE (Stochastic Neighbor Embedding): abandonar a tentativa de reproduzir os valores numéricos das distâncias euclidianas e passar a modelar probabilidades de vizinhança.

A pergunta central deixa de ser “Qual é a distância entre \(\mathbf{x}_i\) e \(\mathbf{x}_j\)?” e passa a ser: \[\text{"Se } \mathbf{x}_i \text{ escolhesse um vizinho estocasticamente, qual seria a probabilidade de escolher } \mathbf{x}_j \text{?"}\]

Em alta dimensão, modelamos essa probabilidade centrando uma densidade gaussiana em \(\mathbf{x}_i\). A probabilidade condicional de \(\mathbf{x}_i\) escolher \(\mathbf{x}_j\) como seu vizinho é definida por uma função softmax sobre as distâncias euclidianas negativas: \[p_{j|i} = \frac{\exp\left(-\frac{\|\mathbf{x}_i - \mathbf{x}_j\|^2}{2\sigma_i^2}\right)}{\sum_{k \ne i} \exp\left(-\frac{\|\mathbf{x}_i - \mathbf{x}_k\|^2}{2\sigma_i^2}\right)}, \quad p_{i|i} = 0\]

Onde \(\sigma_i^2\) é a variância da gaussiana em torno do ponto \(\mathbf{x}_i\).

3.2 Calibração Local: O Hiperparâmetro Perplexidade

A formulação probabilística \(p_{j|i} \propto \exp(-\|\mathbf{x}_i - \mathbf{x}_j\|^2 / 2\sigma_i^2)\) introduz um problema prático imediato: como determinar a variância \(\sigma_i^2\) do kernel gaussiano?

1. Por que achar \(\sigma\) diretamente é uma tarefa inglória:

   • Em dados reais de alta dimensão, a densidade varia drasticamente ao longo do espaço. Em regiões centrais de clusters densos, os vizinhos estão a distâncias microscópicas (ex.: \(d=0{,}1\)); já em regiões periféricas ou esparsas, o vizinho mais próximo pode estar a distâncias muito maiores (ex.: \(d=5{,}0\)).
   • Um \(\sigma\) universal único falha miseravelmente: se for pequeno demais, os pontos esparsos ficam isolados (\(p_{j|i} \approx 0\) para todos os \(j\)); se for grande demais, os clusters densos ficam saturados (todos os pontos viram vizinhos com probabilidade quase uniforme, apagando as nuances locais).
   • Porém, estipular manualmente um \(\sigma_i\) numérico diferente para cada um dos \(N\) pontos é impossível: o usuário teria que adivinhar \(N\) parâmetros contínuos sem nenhuma intuição geométrica da escala em 784 dimensões!

2. A inversão do problema: fixar a “quantidade de vizinhos” desejada: A sacada fundamental de Hinton & Roweis foi inverter a lógica: em vez de pedir ao usuário um desvio padrão numérico abstrato \(\sigma_i\), o algoritmo pede um número inteiro intuitivo de vizinhos que cada ponto deve manter. Essa grandeza é formalizada pela Perplexidade: \[\text{Perp}(P_i) = 2^{H(P_i)}\] onde \(H(P_i)\) é a entropia de Shannon (em bits) da distribuição de vizinhança de \(\mathbf{x}_i\): \[H(P_i) = -\sum_{j \ne i} p_{j|i} \log_2 p_{j|i}\]

3. Por que a Perplexidade é o número efetivo de vizinhos: Imagine que a probabilidade condicional \(P_i\) fosse perfeitamente uniforme sobre exatamente \(K\) vizinhos próximos (e zero para todos os outros). A entropia seria \(H(P_i) = -\sum_{k=1}^K \frac{1}{K} \log_2 \frac{1}{K} = \log_2 K\). Nesse caso, a perplexidade seria: \[\text{Perp}(P_i) = 2^{\log_2 K} = K\] Ou seja, a perplexidade é literalmente o número efetivo de vizinhos!

4. Calibração automática por busca binária: Como a entropia \(H(P_i)\) é uma função contínua e estritamente monótona crescente em relação a \(\sigma_i\) (quando \(\sigma_i \to 0\), \(H \to 0\); quando \(\sigma_i \to \infty\), \(H \to \log_2(N-1)\)), para qualquer valor de perplexidade escolhido pelo usuário (tipicamente entre \(5\) e \(50\)), existe um único valor de \(\sigma_i\) que satisfaz a equação. O algoritmo encontra esse \(\sigma_i\) para cada ponto de forma rápida e exata via busca binária unidimensional (bisseção).

3.3 Simetrização e a Função de Custo: Divergência KL

Após calibrar as probabilidades locais na alta dimensão, precisamos definir com precisão qual é o objetivo matemático do aprendizado:

Temos em mãos duas matrizes de probabilidade sobre os mesmos \(N\) objetos: 1. \(P = [p_{ij}]\) (A Verdade de Alta Dimensão): Mede a afinidade de vizinhança real entre cada par de amostras no espaço \(\mathbb{R}^D\). 2. \(Q(\mathbf{Y}) = [q_{ij}]\) (O Mapa 2D Candidato): Mede as probabilidades de vizinhança induzidas pelas coordenadas bidimensionais \(\mathbf{Y} = [\mathbf{y}_1, \dots, \mathbf{y}_N]^\top \in \mathbb{R}^{N \times 2}\).

O Objetivo Fundamental: Encontrar as coordenadas \(\mathbf{y}_1, \dots, \mathbf{y}_N\) no plano que façam a distribuição de vizinhanças \(Q(\mathbf{Y})\) espelhar a distribuição original \(P\) da forma mais fiel possível.

3.3.1 Por Que a Divergência de Kullback-Leibler (KL)?

Como \(P\) e \(Q\) são distribuições de probabilidade conjuntas (com \(\sum_{i,j} p_{ij} = 1\) e \(\sum_{i,j} q_{ij} = 1\)), a ferramenta matemática canônica da teoria da informação para quantificar a discrepância (ou perda de informação ao aproximar \(P\) por \(Q\)) é a Divergência KL: \[C(\mathbf{Y}) = \mathrm{KL}(P \parallel Q) = \sum_{i \ne j} p_{ij} \ln \frac{p_{ij}}{q_{ij}(\mathbf{Y})}\]

Diferentemente do erro quadrático \(\sum (p_{ij} - q_{ij})^2\), a divergência KL possui fundamentação probabilística rigorosa e, como veremos a seguir, introduz uma assimetria geométrica essencial para proteger agrupamentos locais.

3.3.2 Por Que Simetrizar as Probabilidades (\(p_{ij}\) Conjunto)?

No SNE original de 2002, as probabilidades eram condicionais \(p_{j|i}\) e a perda somava \(\sum_i \mathrm{KL}(P_i \parallel Q_i)\). van der Maaten & Hinton (2008) propuseram a probabilidade conjunta simétrica: \[p_{ij} = \frac{p_{j|i} + p_{i|j}}{2N}, \quad p_{ii} = 0\]

Essa simetrização cumpre três papéis vitais: 1. Tratamento robusto de outliers: Se \(\mathbf{x}_i\) for um ponto anômalo afastado de todos, todos os seus \(p_{j|i}\) originais seriam minúsculos. No SNE condicional, o softmax forçava esses termos a somarem 1, atribuindo peso excessivo ao ruído de um ponto isolado. Com a probabilidade conjunta, \(p_{ij}\) só é expressivo se \(\mathbf{x}_i\) escolher \(\mathbf{x}_j\) OU se \(\mathbf{x}_j\) escolher \(\mathbf{x}_i\). Se ninguém o escolhe, o ponto atípico tem \(p_{ij} \approx 0\) e não desestabiliza o mapa. 2. Simplificação e aceleração do gradiente: A simetrização elimina derivadas cruzadas assimétricas, gerando uma expressão elegante e eficiente para o gradiente descendente.

3.4 KL: Falso Afastamento vs. Falsa Aproximação

A escolha de minimizar \(\mathrm{KL}(P \parallel Q)\) é o elemento matemático que muda completamente o comportamento em relação ao MDS. Vamos analisar a penalidade termo a termo:

1. Falsos Afastamentos (Vizinhos separados no mapa):
   • Na alta dimensão, \(\mathbf{x}_i\) e \(\mathbf{x}_j\) são vizinhos próximos \(\implies p_{ij}\) é grande (ex.: \(p_{ij} = 0{,}10\)).
   • Se o mapa 2D colocá-los distantes, a distância \(\|\mathbf{y}_i - \mathbf{y}_j\|\) é grande \(\implies q_{ij}\) é infinitesimal (ex.: \(q_{ij} = 10^{-4}\)).
   • A contribuição na perda é: \[p_{ij} \ln \frac{p_{ij}}{q_{ij}} = 0{,}10 \times \ln\left(\frac{0{,}10}{10^{-4}}\right) = 0{,}10 \times \ln(1.000) \approx 0{,}10 \times 6{,}91 = \mathbf{+0{,}691}\]
   • O custo é explosivo: o algoritmo sofre uma penalidade severa se quebrar um par de vizinhos.
2. Falsas Aproximações (Pontos distantes colocados perto no mapa):
   • Na alta dimensão, \(\mathbf{x}_i\) e \(\mathbf{x}_j\) pertencem a clusters opostos \(\implies p_{ij} \approx 0\) (ex.: \(p_{ij} = 10^{-6}\)).
   • Se o mapa 2D os colocar próximos, \(\|\mathbf{y}_i - \mathbf{y}_j\|\) é pequeno \(\implies q_{ij}\) é moderado (ex.: \(q_{ij} = 0{,}05\)).
   • A contribuição na perda é: \[p_{ij} \ln \frac{p_{ij}}{q_{ij}} = 10^{-6} \times \ln\left(\frac{10^{-6}}{0{,}05}\right) \approx 10^{-6} \times (-10{,}8) = \mathbf{-0{,}00001}\]
   • O custo é desprezível: como \(p_{ij}\) multiplica o logaritmo, quando \(p_{ij} \to 0\), o termo tende a zero (\(0 \ln 0 = 0\)).

Essa assimetria faz com que o SNE priorize a preservação de vizinhanças locais: se dois pontos eram vizinhos na alta dimensão, eles têm que ficar colados no mapa 2D. Se dois pontos estavam distantes, o algoritmo tem total liberdade para posicioná-los onde for mais conveniente, desde que não atrapalhe os verdadeiros vizinhos.

3.5 Pausa Ativa 3: Vizinhanças Probabilísticas e KL

DicaO Comportamento da Divergência KL

Por que a formulação \(\mathrm{KL}(P \parallel Q)\) tolera que dois clusters não relacionados se aproximem no mapa 2D, mas proíbe terminantemente que um cluster homogêneo seja partido ao meio? O que mudaria se minimizássemos a divergência inversa \(\mathrm{KL}(Q \parallel P)\)?

Dica para discussão: Analise o fator que multiplica o logaritmo em cada caso quando \(p_{ij}=0\) ou \(q_{ij}=0\).

DicaV ou F: SNE e Perplexidade

Julgue V ou F — a questão só conta se acertar os 4 itens:

• □ A variância \(\sigma_i^2\) do kernel gaussiano de cada ponto \(\mathbf{x}_i\) no SNE é única e universal para todas as amostras do conjunto de dados.
• □ Em regiões de alta densidade de dados, o valor de \(\sigma_i\) encontrado pelo algoritmo para uma dada perplexidade fixa será menor do que em regiões esparsas.
• □ A divergência \(\mathrm{KL}(P \parallel Q)\) penaliza com o mesmo rigor o erro de afastar vizinhos e o erro de aproximar pontos distantes.
• □ A Perplexidade pode ser interpretada operacionalmente como o número efetivo de vizinhos próximos que cada ponto tenta manter em sua vizinhança probabilística.

4 Bloco 3: A Solução da Cauda Pesada — t-SNE

4.1 Como a Gaussiana Chega ao SNE: O Modelo de Difusão e Vizinhança

Por que Hinton & Roweis (2002) adotaram distribuições gaussianas para quantificar afinidades de vizinhança? A escolha da gaussiana tanto no espaço de alta dimensão quanto no mapa 2D decorre de princípios probabilísticos e físicos bem fundamentados:

4.1.1 1. No Espaço Original (\(\mathbb{R}^D\)): Princípio da Máxima Entropia e Perturbação Isotrópica

Ao modelar a incerteza em torno de uma amostra \(\mathbf{x}_i \in \mathbb{R}^D\), suponha que fixemos apenas a média (o próprio ponto \(\mathbf{x}_i\)) e a dispersão quadrática esperada (variância isotrópica \(\sigma_i^2\)).

De acordo com o Princípio da Máxima Entropia de Jaynes, entre todas as distribuições de probabilidade contínuas com primeiro e segundo momentos especificados, a distribuição normal multivariada \(\mathcal{N}(\mathbf{x}_i, \sigma_i^2 \mathbf{I})\) é a que possui a máxima entropia diferencial de Shannon. Isso significa que a gaussiana é a escolha estatisticamente mais conservadora e honesta: ela maximiza a incerteza e não introduz nenhum viés ou pressuposição geométrica espúria além da variância estipulada.

Sob uma lente física, imagine um processo de difusão browniana: se o ponto \(\mathbf{x}_i\) emitir uma perturbação isotrópica com dispersão térmica \(\sigma_i^2\), a probabilidade infinitesimal de essa perturbação alcançar uma amostra vizinha \(\mathbf{x}_j\) é proporcional à densidade de transição: \[p(\mathbf{x}_j \mid \mathbf{x}_i) \propto \exp\left(-\frac{\|\mathbf{x}_i - \mathbf{x}_j\|^2}{2\sigma_i^2}\right)\]

Ao normalizar essa densidade sobre o conjunto discreto de todas as outras amostras candidatas (\(k \ne i\)), obtemos a função de escolha softmax: \[p_{j|i} = \frac{\exp\left(-\frac{\|\mathbf{x}_i - \mathbf{x}_j\|^2}{2\sigma_i^2}\right)}{\sum_{k \ne i} \exp\left(-\frac{\|\mathbf{x}_i - \mathbf{x}_k\|^2}{2\sigma_i^2}\right)}, \quad p_{i|i} = 0\] E a probabilidade conjunta simétrica: \[p_{ij} = \frac{p_{j|i} + p_{i|j}}{2N}\]

4.1.2 2. No Mapa Projetado (\(\mathbb{R}^2\)): A Hipótese Gaussiana e Invariância de Escala (\(2\sigma^2 = 1\))

No SNE original, a hipótese natural de partida foi adotar o mesmo modelo gaussiano para as afinidades no mapa bidimensional: \[q_{ij} \propto \exp\left(-\frac{\|\mathbf{y}_i - \mathbf{y}_j\|^2}{2\sigma_{\text{mapa}}^2}\right)\]

Por que podemos fixar \(2\sigma_{\text{mapa}}^2 = 1\) (isto é, \(\sigma_{\text{mapa}} = 1/\sqrt{2}\)) sem perda de generalidade?

No plano 2D, as posições \(\mathbf{y}_1, \dots, \mathbf{y}_N\) são variáveis livres que o algoritmo otimiza diretamente por descida de gradiente. Se multiplicássemos \(\sigma_{\text{mapa}}\) por uma constante arbitrária \(c > 0\), o algoritmo de otimização simplesmente reescalaria todas as coordenadas projetadas pelo mesmo fator: \[\mathbf{y}_k \leftarrow c \mathbf{y}_k \implies \|\mathbf{y}_i - \mathbf{y}_j\|^2 \leftarrow c^2 \|\mathbf{y}_i - \mathbf{y}_j\|^2\] O quociente \(\frac{\|\mathbf{y}_i - \mathbf{y}_j\|^2}{2(c\sigma)^2} = \frac{\|\mathbf{y}_i - \mathbf{y}_j\|^2}{2\sigma^2}\) permaneceria rigorosamente invariante! Como a escala global do mapa 2D é livre, fixar \(2\sigma^2 = 1\) elimina um grau de liberdade redundante, resultando na afinidade não normalizada simplificada \(\exp(-\|\mathbf{y}_i - \mathbf{y}_j\|^2)\) e na probabilidade conjunta: \[q_{ij} = \frac{\exp\left(-\|\mathbf{y}_i - \mathbf{y}_j\|^2\right)}{\sum_{k \ne l} \exp\left(-\|\mathbf{y}_k - \mathbf{y}_l\|^2\right)}, \quad q_{ii} = 0\]

4.2 O Gargalo do SNE Gaussiano: A Cauda Leve e o Colapso Central

Apesar da elegância teórica de usar gaussianas em ambos os espaços, o SNE simétrico original falhava sistematicamente em dados complexos: na prática, o mapa 2D colapsava em uma única massa indiferenciada no centro (crowding problem).

A causa matemática reside no decaimento superexponencial da cauda gaussiana:

4.2.1 1. A Velocidade de Decaimento da Afinidade Gaussiana

Observe como a afinidade não normalizada \(\exp(-d^2)\) desaba com a distância euclidiana \(d = \|\mathbf{y}_i - \mathbf{y}_j\|\) no plano:

Distância no Mapa (\(d\))	Afinidade \(\exp(-d^2)\)	Razão em Relação à Origem
\(d = 0\)	\(\exp(0) = 1{,}000\)	\(100\%\)
\(d = 1\)	\(\exp(-1) \approx 0{,}368\)	\(36{,}8\%\)
\(d = 2\)	\(\exp(-4) \approx 0{,}0183\)	\(1{,}83\%\)
\(d = 3\)	\(\exp(-9) \approx 1{,}23 \times 10^{-4}\)	\(0{,}012\%\)
\(d = 4\)	\(\exp(-16) \approx 1{,}13 \times 10^{-7}\)	\(0{,}00001\%\)
\(d = 5\)	\(\exp(-25) \approx 1{,}39 \times 10^{-11}\)	\(0{,}000000001\%\)

A afinidade cai quase cem mil vezes ao passar de \(d=1\) para \(d=4\)! Trata-se de uma cauda excessivamente leve (light-tailed).

4.2.2 2. A Armadilha da Penalidade KL: \(p_{ij} \ln(p_{ij} / q_{ij})\)

Na alta dimensão, entre amostras de clusters adjacentes ou em regiões intermediárias, a probabilidade conjunta \(p_{ij}\) não é exatamente zero — ela é pequena, digamos \(p_{ij} \approx 0{,}01\) ou \(0{,}001\).

Se no mapa 2D o algoritmo afastasse esses agrupamentos para uma distância moderada, como \(d = 4\): - A probabilidade \(q_{ij}\) afundaria para a ordem de \(10^{-7}\). - O termo correspondente na perda explodiria: \[p_{ij} \ln \frac{p_{ij}}{q_{ij}} = 0{,}01 \times \ln\left(\frac{0{,}01}{10^{-7}}\right) = 0{,}01 \times \ln(10^5) \approx 0{,}01 \times 11{,}51 = \mathbf{+0{,}115}\] Multiplicado por milhares de pares intermediários, essa perda gera uma força atrativa colossal sobre todos os pontos.

4.2.3 3. O Colapso Gravitacional no Centro do Mapa

Para que a perda KL não exploda, o otimizador é forçado a confinar quase todos os pontos a distâncias mútuas minúsculas (\(d \le 2\)).

Porém, a área de um disco de raio \(2\) em \(\mathbb{R}^2\) é de apenas: \[A = \pi (2)^2 \approx 12{,}57\] Não há espaço geométrico bidimensional suficiente nesse pequeno disco para acomodar dezenas de agrupamentos distintos sem que eles colidam e se sobreponham. O resultado prático do SNE original era um colapso gravitacional generalizado: todos os clusters eram esmagados em um “emaranhado amorfo” no centro do plano.

4.3 t-SNE: Da Distribuição Student-\(t\) ao Kernel de Cauchy

A solução revolucionária introduzida por Laurens van der Maaten e Geoffrey Hinton em 2008 consistiu em quebrar a simetria de distribuições entre os dois espaços: - No espaço de alta dimensão (\(P\)), mantém-se o kernel gaussiano. - No mapa de baixa dimensão (\(Q\)), adota-se a distribuição \(t\)-Student com 1 grau de liberdade, que coincide com a distribuição de Cauchy.

Vamos construir essa formulação passo a passo a partir da definição probabilística fundamental:

4.3.1 1. A Função Densidade da Distribuição Student-\(t\)

A densidade de probabilidade de uma distribuição Student-\(t\) padrão com \(\nu\) graus de liberdade é dada por: \[f(t; \nu) = \frac{\Gamma\left(\frac{\nu+1}{2}\right)}{\sqrt{\pi \nu} \, \Gamma\left(\frac{\nu}{2}\right)} \left(1 + \frac{t^2}{\nu}\right)^{-\frac{\nu+1}{2}}\]

4.3.2 2. Especialização para \(\nu = 1\) (Distribuição de Cauchy)

Quando fixamos \(\nu = 1\) grau de liberdade, temos \(\Gamma(1) = 1\) e \(\Gamma(1/2) = \sqrt{\pi}\), de modo que a constante multiplicativa simplifica-se para: \[\frac{\Gamma(1)}{\sqrt{\pi} \, \Gamma(1/2)} = \frac{1}{\sqrt{\pi} \cdot \sqrt{\pi}} = \frac{1}{\pi}\] Resultando na densidade univariada da distribuição de Cauchy padrão: \[f(t; 1) = \frac{1}{\pi \left(1 + t^2\right)} \propto \frac{1}{1 + t^2} = \left(1 + t^2\right)^{-1}\]

4.3.3 3. De Densidade Contínua para Similaridade no Mapa 2D

No mapa bidimensional \(\mathbb{R}^2\), a distância entre dois pontos projetados \(\mathbf{y}_i\) e \(\mathbf{y}_j\) é a norma euclidiana \(d_{ij} = \|\mathbf{y}_i - \mathbf{y}_j\|\). Substituindo essa distância no lugar de \(t\), a afinidade ou similaridade não normalizada entre \(\mathbf{y}_i\) e \(\mathbf{y}_j\) torna-se: \[k(\mathbf{y}_i, \mathbf{y}_j) = \frac{1}{1 + \|\mathbf{y}_i - \mathbf{y}_j\|^2} = \left( 1 + \|\mathbf{y}_i - \mathbf{y}_j\|^2 \right)^{-1}\]

4.3.4 4. Construção da Probabilidade Conjunta Normalizada \(q_{ij}\)

Para transformar essa afinidade em uma distribuição de probabilidade conjunta sobre todos os pares de pontos com \(q_{ii} = 0\) e \(\sum_{i, j} q_{ij} = 1\), normalizamos pela soma de todas as afinidades do conjunto: \[q_{ij} = \frac{\left(1 + \|\mathbf{y}_i - \mathbf{y}_j\|^2\right)^{-1}}{\sum_{k} \sum_{l \ne k} \left(1 + \|\mathbf{y}_k - \mathbf{y}_l\|^2\right)^{-1}}, \quad q_{ii} = 0\]

4.4 O Mecanismo da Cauda Pesada: Aliviando o Crowding

Por que a Student-\(t\) com \(\nu=1\) resolve de forma tão espetacular o crowding problem? A resposta está no contraste entre o decaimento exponencial e o decaimento por lei de potência:

• Kernel Gaussiano (usado no SNE original): decai como \(\exp(-d^2)\). Trata-se de uma cauda ultra-leve: quando \(d\) cresce moderadamente (ex.: \(d=3\)), \(\exp(-9) \approx 0{,}00012\), a probabilidade praticamente desaparece.
• Kernel Student-\(t\) (usado no t-SNE): decai como lei de potência \((1 + d^2)^{-1} \approx d^{-2}\) para distâncias grandes. A cauda é pesada: para \(d=3\), \((1+9)^{-1} = 0{,}10\), uma probabilidade quase mil vezes maior que a da Gaussiana!

A consequência geométrica:
Para produzir a mesma probabilidade pequena \(q_{ij} = p_{ij}\) exigida por pares moderadamente distantes, a distância euclidiana \(\|\mathbf{y}_i - \mathbf{y}_j\|\) no plano sob a Student-\(t\) pode ser muito maior. A cauda pesada permite que aglomerados distintos sejam empurrados para a periferia do mapa sem que a função de custo penalize esse afastamento. Isso abre um amplo espaço livre no interior do plano para que a microestrutura interna de cada cluster se desdobre com máxima fidelidade.

4.5 A Função Objetivo Global do t-SNE

Com as probabilidades \(P\) e \(Q\) rigorosamente estabelecidas, podemos agora formular de maneira completa o problema de otimização do t-SNE:

Buscamos a matriz de coordenadas bidimensionais \(\mathbf{Y} = [\mathbf{y}_1, \dots, \mathbf{y}_N]^\top \in \mathbb{R}^{N \times 2}\) que minimiza a divergência de Kullback-Leibler entre a distribuição conjunta de alta dimensão \(P\) e a distribuição Student-\(t\) de baixa dimensão \(Q(\mathbf{Y})\): \[\min_{\mathbf{Y} \in \mathbb{R}^{N \times 2}} C(\mathbf{Y}) = \mathrm{KL}(P \parallel Q) = \sum_{i \ne j} p_{ij} \ln \left( \frac{p_{ij}}{q_{ij}(\mathbf{Y})} \right)\]

Onde: - \(p_{ij} = \frac{p_{j|i} + p_{i|j}}{2N}\) são valores escalares constantes e fixos, pré-calculados a partir das distâncias originais \(\|\mathbf{x}_i - \mathbf{x}_j\|\) e da perplexidade escolhida. - \(q_{ij}(\mathbf{Y}) = \frac{(1 + \|\mathbf{y}_i - \mathbf{y}_j\|^2)^{-1}}{\sum_{k \ne l} (1 + \|\mathbf{y}_k - \mathbf{y}_l\|^2)^{-1}}\) são as probabilidades dependentes das coordenadas do mapa.

4.5.1 Decomposição Analítica da Função de Custo

Expandindo o logaritmo da razão: \[C(\mathbf{Y}) = \sum_{i \ne j} p_{ij} \ln p_{ij} - \sum_{i \ne j} p_{ij} \ln q_{ij}(\mathbf{Y})\]

Note que o primeiro termo \(\sum_{i \ne j} p_{ij} \ln p_{ij} = -H(P)\) é a entropia negativa da distribuição original \(P\). Esse termo é estritamente constante em relação a \(\mathbf{Y}\). Portanto: \[C(\mathbf{Y}) = \text{Constante} - \sum_{i \ne j} p_{ij} \ln q_{ij}(\mathbf{Y})\]

Isso demonstra que minimizar a divergência KL no t-SNE equivale a maximizar a entropia cruzada \(\sum_{i \ne j} p_{ij} \ln q_{ij}(\mathbf{Y})\). Para encontrar o mínimo dessa função não convexa, emprega-se o método do gradiente descendente com momento.

4.6 O Gradiente da Perda: Atração por Mola e Repulsão Global

Diferenciando a função objetivo \(C(\mathbf{Y})\) em relação às coordenadas vetoriais do ponto \(\mathbf{y}_i \in \mathbb{R}^2\), a combinação da distribuição conjunta simétrica com o kernel de Cauchy produz uma derivada extraordinariamente elegante: \[\frac{\partial C}{\partial \mathbf{y}_i} = 4 \sum_{j \ne i} \left( p_{ij} - q_{ij} \right) \left( 1 + \|\mathbf{y}_i - \mathbf{y}_j\|^2 \right)^{-1} \left( \mathbf{y}_i - \mathbf{y}_j \right)\]

Essa expressão admite uma interpretação física clássica e intuitiva de sistema mecânico de partículas: 1. Termo de Atração (\(p_{ij} > q_{ij}\)): Quando dois pontos são vizinhos na alta dimensão (\(p_{ij}\) apreciável) mas estão afastados no mapa (\(q_{ij} < p_{ij}\)), a diferença \((p_{ij} - q_{ij})\) é positiva. A força atua no sentido de puxar \(\mathbf{y}_i\) em direção a \(\mathbf{y}_j\), comportando-se exatamente como uma mola elástica esticada que une pontos que devem ficar próximos. 2. Termo de Repulsão (\(q_{ij} > p_{ij}\)): Quando dois pontos não são vizinhos na alta dimensão (\(p_{ij} \approx 0\)) mas acabam se aproximando no mapa 2D, a diferença \((p_{ij} - q_{ij})\) torna-se negativa (aproximadamente \(-q_{ij}\)). Como \(q_{ij} \propto (1 + \|\mathbf{y}_i - \mathbf{y}_j\|^2)^{-1}\), a força resultante empurra \(\mathbf{y}_i\) para longe de \(\mathbf{y}_j\), como duas partículas com cargas elétricas do mesmo sinal.

A configuração final do mapa 2D corresponde ao estado de energia mínima em que a atração exercida pelas molas dos verdadeiros vizinhos equilibra com precisão a repulsão global de todos os outros pontos.

4.7 Pausa Ativa 4: O “Crowding Problem” e Student-\(t\)

DicaPor Que a Student-\(t\) Alivia o Confinamento?

Se a probabilidade \(p_{ij}\) calculada no espaço de alta dimensão vale \(0{,}01\), explique por que a distância euclidiana \(\|\mathbf{y}_i - \mathbf{y}_j\|\) necessária para igualar \(q_{ij} = 0{,}01\) é muito maior sob a curva da Student-\(t\) do que sob uma curva gaussiana no mapa 2D. O que acontece com os clusters no mapa como consequência disso?

Dica para discussão: Compare a inclinação e a altura da cauda das duas funções para distâncias moderadas no gráfico anterior.

DicaV ou F: t-SNE e o Kernel de Cauchy

Julgue V ou F — a questão só conta se acertar os 4 itens:

• □ A distribuição \(t\)-Student com 1 grau de liberdade coincide matematicamente com a distribuição de Cauchy padrão.
• □ Para distâncias \(d = \|\mathbf{y}_i - \mathbf{y}_j\| \gg 1\), a probabilidade não normalizada sob o kernel do t-SNE decai com \(1/d^2\), enquanto sob a Gaussiana ela decai com \(\exp(-d^2)\).
• □ O t-SNE utiliza a distribuição \(t\)-Student tanto no espaço original de alta dimensão (\(p_{ij}\)) quanto no mapa 2D (\(q_{ij}\)).
• □ O gradiente do t-SNE pode ser fisicamente interpretado como forças de atração ao longo de vizinhanças e forças de repulsão entre todos os pares de pontos.

5 Bloco 4: Cuidados Práticos e as 4 Armadilhas de Interpretação

5.1 A Calibração Prática e o Impacto da Perplexidade

O hiperparâmetro mais importante do t-SNE é a Perplexidade. Vimos que ela dita a largura de banda efetiva das vizinhanças locais. Mas como a escolha desse número afeta a topologia visual do mapa?

Vejamos o comportamento extremo no conjunto do Breast Cancer Wisconsin (\(D=30\)): 1. Perplexidade excessivamente baixa (\(\text{Perp} = 2\) ou \(5\)): O algoritmo foca em microvizinhanças quase pontuais. A geometria global é completamente desintegrada: os dados dividem-se em dezenas de pequenos agrupamentos espúrios e filamentos lineares artificiais, pois cada ponto só tenta satisfazer 1 ou 2 vizinhos imediatos. 2. Perplexidade típica (\(\text{Perp} = 30\) a \(50\)): O algoritmo equilibra a coesão local com a continuidade da variedade. As lesões malignas e benignas separam-se com nitidez em dois grandes blocos, preservando a estrutura de vizinhança. 3. Perplexidade excessivamente alta (\(\text{Perp} = 200\) ou próxima de \(N\)): A distribuição condicional \(P_i\) aproxima-se de uma distribuição quase uniforme sobre todo o conjunto de dados. A perda de informação local faz o t-SNE comportar-se como um método global ruidoso, colapsando os clusters em uma nuvem esférica homogênea.

5.2 As 4 Falácias Clássicas de Interpretação do t-SNE

O t-SNE é uma das ferramentas de visualização mais populares da ciência de dados, mas é também uma das mais frequentemente mal interpretadas (Wattenberg et al., 2016). Para utilizá-lo de forma estatisticamente rigorosa, é fundamental conhecer as quatro falácias clássicas:

1. Falácia 1: Distâncias entre clusters não têm significado físico.
   • Quando dois clusters se separam no mapa 2D, as probabilidades conjuntas cruzadas entre eles tornam-se nulas (\(p_{ij} \approx 0\)).
   • A partir desse momento, a única força atuando entre os clusters é a repulsão global uniforme de \(q_{ij}\).
   • Se o Cluster A está a \(5\text{ cm}\) ou \(20\text{ cm}\) do Cluster B no gráfico, isso é resultado da dinâmica estocástica do gradiente descendente e do espaço disponível no mapa, não da distância euclidiana real entre eles no espaço original. Nunca meça distâncias entre aglomerados no t-SNE para tirar conclusões métricas.
2. Falácia 2: O tamanho e a dispersão visual do cluster não refletem sua densidade original.
   • O algoritmo calibra \(\sigma_i\) localmente para satisfazer a mesma perplexidade em todos os pontos.
   • Um cluster extremamente denso em alta dimensão tem seus \(\sigma_i\) reduzidos, sendo “inflado” no mapa 2D para que seus pontos possam se espalhar.
   • Um cluster esparso tem seus \(\sigma_i\) ampliados, sendo compactado no mapa.
   • Portanto, a área visual ocupada por uma nuvem de pontos no t-SNE não mede a variância ou a densidade física do cluster original.
3. Falácia 3: Agrupamentos visuais podem surgir de ruído puro.
   • Se aplicarmos o t-SNE com perplexidade intermediária ou baixa sobre ruído puramente uniforme ou gaussiano esférico sem nenhum cluster real, flutuações estatísticas finitas da amostra serão amplificadas.
   • O algoritmo agrupará pontos aleatórios e desenhará ilhas com aspecto nítido de clusters. Toda descoberta visual no t-SNE deve ser validada por testes estatísticos ou inspeção direta nos dados originais.
4. Falácia 4: O t-SNE não é um modelo paramétrico indutivo.
   • O t-SNE otimiza diretamente a matriz de coordenadas \(\mathbf{Y}_{N \times 2}\). Ele não aprende uma função \(f: \mathbb{R}^D \to \mathbb{R}^2\).
   • Se chegar um novo ponto de teste \(\mathbf{x}_{\text{novo}}\), não é possível simplesmente “passá-lo pelo t-SNE” para saber onde ele cai. Seria necessário recalcular toda a otimização com \(N+1\) pontos ou treinar uma rede neural paramétrica auxiliar (Parametric t-SNE).

5.3 Pausa Ativa 5: As 4 Armadilhas de Interpretação do t-SNE

DicaDiagnóstico de Interpretação

Um bioinformata executa o t-SNE sobre dados de expressão gênica e observa que o “Cluster A” tem um diâmetro visual de \(5\text{ cm}\) e o “Cluster B” tem um diâmetro de apenas \(1\text{ cm}\). Além disso, a distância entre os centros dos dois clusters no gráfico é de \(15\text{ cm}\).

DicaV ou F: Armadilhas do t-SNE

Julgue V ou F — a questão só conta se acertar os 4 itens:

• □ Executar o t-SNE com perplexidade excessivamente baixa tende a quebrar clusters reais contínuos em múltiplos subaglomerados artificiais desconectados.
• □ Dado um novo ponto de teste \(\mathbf{x}_{\text{novo}} \in \mathbb{R}^D\), podemos determinar sua posição \(\mathbf{y}_{\text{novo}} \in \mathbb{R}^2\) aplicando diretamente uma matriz de pesos ou fórmula analítica aprendida pelo t-SNE padrão.
• □ Ao aplicar o t-SNE sobre dados gerados por uma distribuição uniforme homogênea sem nenhuma estrutura de agrupamento, é garantido que o mapa 2D jamais formará ilhas ou falsos aglomerados.
• □ Múltiplas execuções do t-SNE com diferentes sementes aleatórias podem produzir mapas rotacionados ou com posições relativas de clusters diferentes, preservando ainda assim as vizinhanças locais.

6 Fechamento

6.1 Retomando as 5 Perguntas da Aula

Ao final desta jornada pela redução de dimensionalidade para visualização, podemos responder de forma conclusiva às cinco questões do nosso roteiro:

1. Por que métodos de projeção global falham ao mapear dados complexos em 2D? Porque no plano \(\mathbb{R}^2\) não é geometricamente possível manter distâncias métricas globais sem esmagar as vizinhanças locais (como provado no caso do tetraedro regular). A tentativa de acomodar todas as distâncias inter-pares em 2D força o colapso dos agrupamentos sobrepostos no centro.
2. Como o MDS formaliza a preservação de distâncias e qual é o viés da função Stress? O MDS busca minimizar \(\sum_{i<j} (d_{ij}^{(X)} - d_{ij}^{(Y)})^2\). A natureza quadrática da perda faz com que as distâncias longas (inter-cluster), que são a imensa maioria dos pares, dominem completamente o custo, sacrificando as microestruturas locais.
3. Por que modelar vizinhanças probabilisticamente via divergência KL? O SNE converte distâncias euclidianas em probabilidades de vizinhança \(p_{j|i}\) via kernel gaussiano com calibração adaptativa de \(\sigma_i\) (Perplexidade). A assimetria da divergência \(\mathrm{KL}(P \parallel Q)\) pune severamente falsos afastamentos de vizinhos reais, mas tolera aproximações de pontos distantes.
4. De que maneira a distribuição \(t\)-Student de 1 grau de liberdade resolve o crowding problem? A cauda pesada da Student-\(t\) (\(1/(1+d^2)\)) faz com que probabilidades baixas possam ser satisfeitas com distâncias euclidianas muito maiores no mapa 2D. Isso empurra clusters não relacionados para longe, aliviando a pressão e liberando espaço no centro para que cada cluster organize internamente sua topologia.
5. Quais são as armadilhas metodológicas cruciais na interpretação de projeções t-SNE? Distâncias entre clusters não refletem distâncias euclidianas reais; tamanhos de clusters não refletem densidade ou variância original; agrupamentos podem surgir de ruído puro; e o método não é indutivo/paramétrico para novos pontos.

6.2 O Que Fica em Aberto e Limitações do t-SNE

O t-SNE consolidou-se como o padrão de ouro para visualização exploratória não supervisionada de dados complexos, mas deixa lacunas importantes: - Custo computacional: O cálculo exato das probabilidades de repulsão \(q_{ij}\) exige somar sobre todos os \(O(N^2)\) pares a cada iteração do gradiente. Para conjuntos massivos (\(N > 100.000\)), são necessárias aproximações baseadas em árvores espaciais (Barnes-Hut t-SNE, com complexidade \(O(N \log N)\)) ou interpolação por FFT (FIt-SNE). - Preservação da estrutura global: Embora o t-SNE seja incomparável para revelar vizinhanças locais, ele perde completamente as relações de continuidade de longa escala. Métodos topológicos mais recentes, como o UMAP (Uniform Manifold Approximation and Projection, McInnes et al., 2018), utilizam geometria riemanniana e conjuntos fuzzy para tentar balancear a preservação de estruturas locais e globais com maior eficiência computacional.

6.3 Ponte para a Parte 3: Aula 9

Dica

Com esta aula, encerramos a Parte 2 do curso, dedicada à redução de dimensionalidade e representação latente (do mundo linear de PCA e PPCA, passando pela não linearidade dos Autoencoders e VAEs, até a projeção topológica para visualização com t-SNE).

Na próxima aula, iniciaremos a Parte 3: Descoberta de Informação e Estruturas em Grande Escala. Investigaremos como descobrir dependências complexas e regras de associação em dados categóricos massivos e esparsos utilizando Modelos Gráficos Probabilísticos (PGMs) e Redes Bayesianas, permitindo distinguir correlações espúrias de dependências estruturais verdadeiras.

Exercícios Soluções