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 geometria de esferas em alta dimensão e a origem matemática do crowding problem.
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?

Dica para discussão: Quantos pontos mutuamente equidistantes cabem em um plano euclidiano? O que isso implica quando tentamos projetar 30 ou 784 dimensões em um gráfico 2D?

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 Intuição — O Dilema do Volume e o “Crowding Problem”

2.1 O Dilema do Volume e o Crowding Problem: \(\mathbb{R}^D\) vs. \(\mathbb{R}^2\)

Para compreender por que os métodos lineares e métricos falham tão drasticamente em 2D, precisamos recorrer à geometria de espaços vetoriais de alta dimensão estudada na Aula 2 (A Maldição da Dimensionalidade).

Considere uma esfera de raio \(r\) em \(\mathbb{R}^D\). O volume dessa esfera é dado por: \[V_D(r) = \frac{\pi^{D/2}}{\Gamma(D/2 + 1)} r^D \propto r^D\]

Agora considere uma casca esférica de raio interno \(r - \epsilon\) e raio externo \(r\). A fração de volume contida nessa casca em relação ao volume total da esfera é: \[\frac{V_D(r) - V_D(r - \epsilon)}{V_D(r)} = 1 - \left(1 - \frac{\epsilon}{r}\right)^D\]

Quando \(D\) é grande (digamos, \(D=50\) ou \(D=784\)), essa razão aproxima-se rapidamente de \(1\) mesmo para \(\epsilon/r\) relativamente pequeno. Isso significa que, em alta dimensão: 1. Quase todo o volume reside na casca superficial. 2. Há uma quantidade monumental de “espaço angular”: é possível colocar dezenas ou centenas de vetores que são quase mutuamente ortogonais e estão a distâncias semelhantes entre si.

O que acontece quando tentamos mapear esses pontos para \(d=2\)? No plano, o volume de uma esfera de raio \(R\) é apenas a área de um círculo: \(V_2(R) = \pi R^2\). A área cresce apenas quadraticamente. Em torno de um ponto central \(\mathbf{y}_i\), a quantidade de “vagas” para vizinhos a uma distância moderada \(R\) é minúscula comparada ao espaço que existia em \(\mathbb{R}^D\).

Se tentarmos manter as distâncias proporcionais às originais, os centenas de pontos que estavam a distâncias moderadas em \(\mathbb{R}^D\) passam a disputar o mesmo anel circular estreito em \(\mathbb{R}^2\). Essa restrição força os pontos a se comprimirem uns contra os outros, colapsando em direção ao centro do mapa. Esse fenômeno é o que van der Maaten & Hinton (2008) denominaram crowding problem (o problema da superlotação).

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

3.1 A Formulação Clássica do MDS: Preservação Global de Distâncias

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

Suponha que dispomos de \(N\) objetos e conhecemos as distâncias euclidianas (ou dissimilaridades) entre todos os pares no espaço original: \[d_{ij}^{(X)} = \|\mathbf{x}_i - \mathbf{x}_j\|_2\]

O MDS busca encontrar coordenadas bidimensionais \(\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\), sejam o mais próximas possível de \(d_{ij}^{(X)}\).

Para quantificar a discrepância global, Kruskal definiu a função de perda denominada Stress (em sua versão quadrática direta): \[\sigma_M(\mathbf{Y}) = \sum_{i < j} \left( d_{ij}^{(X)} - d_{ij}^{(Y)} \right)^2\]

Ou na forma normalizada padronizada (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} }\]

3.2 Por Que o Stress Falha: A Tirania das Distâncias Longas

A razão pela qual o MDS falha em separar agrupamentos reside na própria natureza quadrática e uniforme da função Stress:

1. A tirania das distâncias longas: Suponha que dois pontos pertencentes ao mesmo cluster estejam separados por \(d_{\text{local}} = 1{,}0\) no espaço original e sejam mapeados para \(\|\mathbf{y}_i - \mathbf{y}_j\| = 2{,}0\) (um erro relativo de 100%, que funde ou destrói o agrupamento). A penalidade no Stress é: \[(1{,}0 - 2{,}0)^2 = 1{,}0\] Agora, suponha que dois pontos de clusters opostos estejam a uma distância \(d_{\text{global}} = 50{,}0\), e o mapa 2D os posicione a uma distância \(48{,}0\) (um erro insignificante de apenas 4%). A penalidade no Stress é: \[(50{,}0 - 48{,}0)^2 = 4{,}0\] Ou seja, o otimizador prefere errar grotescamente nas pequenas distâncias locais para economizar uma fração mínima de erro em uma única distância longa.

2. A abundância de pares distantes: Em qualquer conjunto de dados com clusters, a imensa maioria dos pares \((i, j)\) é formada por pontos de clusters diferentes (distâncias longas). Há muito mais pares inter-cluster do que pares intra-cluster. Como a perda soma sobre todos os pares sem ponderação, as distâncias longas dominam a soma numérica por magnitude individual e por quantidade de termos.

O resultado inescapável é que o MDS atua como um método de alinhamento macroscópico: ele preserva a forma geral da nuvem e a orientação dos eixos de maior variância, mas sacrifica completamente as microestruturas locais que revelam subpopulações.

3.3 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\).

Dica para discussão: Calcule as duas contribuições quadráticas e reflita sobre o impacto visual de cada uma no mapa 2D.

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.

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

4.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\).

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

Em um conjunto de dados real, a densidade local varia consideravelmente: há regiões densamente povoadas e regiões esparsas. Usar um \(\sigma\) global constante faria com que pontos em áreas densas tivessem centenas de vizinhos e pontos em áreas esparsas não tivessem nenhum.

Para resolver isso, o SNE calibra um \(\sigma_i\) específico para cada ponto \(\mathbf{x}_i\) por meio do conceito de Perplexidade da distribuição condicional \(P_i\): \[\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}\]

A perplexidade possui uma interpretação operacional elegante: ela representa o número efetivo de vizinhos que o usuário deseja que cada ponto possua. O algoritmo realiza uma busca binária unidimensional em \(\sigma_i\) até que a entropia de \(P_i\) satisfaça a perplexidade escolhida: - Em regiões densas, \(\sigma_i\) torna-se automaticamente pequeno. - Em regiões esparsas, \(\sigma_i\) expande-se automaticamente para englobar vizinhos mais distantes.

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

No mapa bidimensional \(\mathbf{Y}\), podemos definir analogamente a probabilidade condicional \(q_{j|i}\). No entanto, van der Maaten & Hinton (2008) simplificaram a formulação e melhoraram a convergência do gradiente definindo probabilidades conjuntas simétricas: \[p_{ij} = \frac{p_{j|i} + p_{i|j}}{2N}, \quad p_{ii} = 0\]

Isso garante que \(\sum_{i, j} p_{ij} = 1\) e que mesmo um ponto atípico \(\mathbf{x}_i\) com todos os \(p_{j|i}\) difusos tenha uma probabilidade conjunta mínima garantida se outro ponto o reconhecer como vizinho.

No mapa 2D, as probabilidades conjuntas no SNE simétrico original eram dadas por: \[q_{ij} = \frac{\exp(-\|\mathbf{y}_i - \mathbf{y}_j\|^2)}{\sum_{k} \sum_{l \ne k} \exp(-\|\mathbf{y}_k - \mathbf{y}_l\|^2)}, \quad q_{ii} = 0\]

O objetivo do aprendizado é ajustar as posições \(\mathbf{y}_1, \dots, \mathbf{y}_N\) para que a distribuição conjunta \(Q\) no mapa seja o mais fiel possível à distribuição \(P\) da alta dimensão. A medida canônica da teoria da informação para discrepância entre distribuições é a Divergência de Kullback-Leibler (KL): \[C = \mathrm{KL}(P \parallel Q) = \sum_{i \ne j} p_{ij} \ln \frac{p_{ij}}{q_{ij}} = \sum_{i \ne j} p_{ij} \ln p_{ij} - \sum_{i \ne j} p_{ij} \ln q_{ij}\]

4.4 A Assimetria da 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.

4.5 Pausa Ativa 3: Vizinhanças Probabilísticas e a Assimetria da 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.

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

5.1 Por Que o SNE Original Ainda Sofria de Crowding em 2D

Apesar do avanço conceitual da divergência KL, o SNE simétrico original (com kernel gaussiano no mapa 2D) ainda sofria do crowding problem: na prática, ao projetar conjuntos com muitos agrupamentos, o mapa 2D resultava em uma grande massa indiferenciada no centro.

A razão matemática é sutil: - No espaço de alta dimensão, \(p_{ij}\) decai com \(\exp(-\|\mathbf{x}_i - \mathbf{x}_j\|^2 / 2\sigma^2)\). Como o volume da esfera escala com \(r^D\), há uma enorme quantidade de pares a distâncias intermediárias. Cada par individual tem uma probabilidade \(p_{ij}\) pequena, mas a soma de milhares desses termos pequenos representa uma massa de probabilidade total substancial. - No mapa 2D, se \(q_{ij}\) também decai com uma gaussiana \(\exp(-\|\mathbf{y}_i - \mathbf{y}_j\|^2)\), a única forma de gerar um \(q_{ij}\) pequeno é afastando os pontos no plano. - Mas o plano 2D não tem área suficiente para acomodar tantos pares moderadamente afastados ao mesmo tempo. Para evitar que os \(q_{ij}\) fiquem excessivamente pequenos (o que explodiria a perda KL), o otimizador é forçado a manter todos os pontos moderadamente próximos entre si, comprimindo os diferentes agrupamentos no centro do mapa.

5.2 A Solução t-SNE: A Distribuição Student-\(t\)

A solução brilhante introduzida por Laurens van der Maaten e Geoffrey Hinton em 2008 foi quebrar a simetria de famílias de distribuição: - Manter o kernel gaussiano na alta dimensão (\(P\)). - Adotar a distribuição \(t\)-Student com 1 grau de liberdade (equivalente à distribuição de Cauchy) no mapa de baixa dimensão (\(Q\)).

A probabilidade conjunta \(q_{ij}\) no mapa 2D passa a ser definida como: \[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\]

Por que a Student-\(t\) com \(\nu=1\) resolve o problema? Observe o decaimento assintótico: - Kernel Gaussiano: decaimento exponencial超-rápido: \(e^{-d^2}\). - Kernel Student-\(t\) (\(\nu=1\)): decaimento em lei de potência com cauda pesada: \[\frac{1}{1 + d^2} \approx \frac{1}{d^2} \quad (\text{para } d \gg 1)\]

Essa cauda pesada opera uma mágica geométrica: ela permite que pontos moderadamente distantes no espaço original sejam posicionados muito mais longe uns dos outros no mapa 2D sem sofrer penalidade. Como a cauda da Student-\(t\) é muito mais alta que a da Gaussiana para distâncias médias e longas, uma probabilidade \(q_{ij}\) pequena pode ser satisfeita com uma distância euclidiana \(\|\mathbf{y}_i - \mathbf{y}_j\|\) substancialmente maior.

Isso dissipa completamente a pressão de confinamento: os aglomerados que não são vizinhos são “empurrados” para a periferia do mapa, abrindo uma vasta área interna livre para que cada agrupamento individual se organize sem interferência externa.

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

Além da elegância conceitual, a combinação de \(P\) (gaussiano) com \(Q\) (Student-\(t\)) produz uma derivada extraordinariamente simples e computacionalmente tratável para otimização via gradiente descendente.

Diferenciando \(C = \sum_{j \ne k} p_{jk} \ln(p_{jk}/q_{jk})\) em relação às coordenadas do ponto \(\mathbf{y}_i\), obtém-se: \[\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 de sistema de partículas: 1. Termo de Atração (\(p_{ij} > q_{ij}\)): Quando dois pontos são vizinhos na alta dimensão (\(p_{ij}\) significativo) mas estão afastados no mapa (\(q_{ij} < p_{ij}\)), o termo \((p_{ij} - q_{ij})\) é positivo. 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 juntos. 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, o termo \((p_{ij} - q_{ij})\) torna-se negativo (aproximadamente \(-q_{ij}\)). Como \(q_{ij} \propto (1 + \|\mathbf{y}_i - \mathbf{y}_j\|^2)^{-1}\), a força multiplica \((1 + \|\mathbf{y}_i - \mathbf{y}_j\|^2)^{-2} (\mathbf{y}_i - \mathbf{y}_j)\), gerando uma força de repulsão que empurra todos os pontos para longe uns dos outros, como partículas de mesma carga elétrica.

A configuração final de equilíbrio do t-SNE é o estado de energia mínima onde a atração entre verdadeiros vizinhos equilibra perfeitamente a repulsão global exercida por todos os outros pontos do conjunto.

5.4 Pausa Ativa 4: O “Crowding Problem” e a Cauda Pesada de 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.

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

6.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.

6.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).

6.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}\).

Ele escreve em seu relatório: “O Cluster A apresenta variância genética cinco vezes maior que o Cluster B, e a grande separação espacial comprova que essas duas populações celulares são filogeneticamente muito distantes”. O que está metodologicamente incorreto nessa afirmação?

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.

7 Fechamento

7.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? Devido ao crowding problem: em \(\mathbb{R}^D\) o volume da esfera escala com \(r^D\), permitindo que inúmeros vizinhos coexistam a distâncias moderadas. Em \(\mathbb{R}^2\), a área cresce apenas com \(r^2\), gerando um gargalo geométrico insolúvel se exigirmos proporcionalidade métrica.
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.

7.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.

7.3 Ponte para a Parte 3: Aula 9

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