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

Aprendizado Não Supervisionado

Autor

Marcos M. Raimundo — Instituto de Computação, UNICAMP

Data de Publicação

5 de outubro de 2026

Aula Exercícios

Respostas das Questões Discursivas

Questão 1: A Geometria do Crowding Problem e a Razão Volume/Superfície

O volume de uma esfera em \(\mathbb{R}^D\) de raio \(r\) é \(V_D(r) = C_D r^D\). O volume contido na casca esférica periférica de espessura \(\epsilon \ll r\) é a diferença entre a esfera de raio \(r\) e a esfera de raio \(r - \epsilon\): \[\frac{V_{\text{casca}}}{V_D(r)} = \frac{V_D(r) - V_D(r - \epsilon)}{V_D(r)} = \frac{C_D r^D - C_D (r - \epsilon)^D}{C_D r^D} = 1 - \left(1 - \frac{\epsilon}{r}\right)^D\] Como \(0 < 1 - \frac{\epsilon}{r} < 1\), quando \(D \to \infty\), o termo \(\left(1 - \frac{\epsilon}{r}\right)^D \to 0\), de modo que: \[\lim_{D \to \infty} \frac{V_{\text{casca}}}{V_D(r)} = 1\] Consequência geométrica: Em alta dimensão, todo o volume de uma esfera concentra-se em sua superfície externa. Existe um volume angular imenso que permite que centenas de pontos fiquem a uma distância moderada \(r\) sem que suas vizinhanças interfiram entre si. No plano euclidiano \(\mathbb{R}^2\), a área do círculo cresce apenas com \(r^2\). Não há área suficiente para acomodar tantos vizinhos a distâncias moderadas; tentar manter as distâncias proporcionais às originais faz com que as forças atrativas mútuas comprimam todos os pontos em direção ao centro do mapa, gerando o colapso e o congelamento (crowding problem).

Questão 2: O Domínio das Escalas Longas no MDS

A função Stress do MDS métrico minimiza \(\sigma_M = \sum_{i<j} (d_{ij}^{(X)} - d_{ij}^{(Y)})^2\). Considere dois clusters \(C_1\) e \(C_2\) com diâmetro interno \(r_{\text{local}} \approx 1{,}0\) e separados por \(L = 50{,}0\). 1. Suponha que o mapa distorça as distâncias internas de \(C_1\) em 100% (\(d_{\text{local}} \to 2{,}0\)). A perda incorrida por esse par é \((1 - 2)^2 = 1{,}0\). 2. Agora suponha que o mapa altere a distância inter-cluster de \(50{,}0\) para \(48{,}0\) (um erro relativo de apenas 4%). A perda associada a esse par é \((50 - 48)^2 = 4{,}0\). Como a penalidade é quadrática na discrepância absoluta, o otimizador penaliza o erro no par distante quatro vezes mais severamente do que a destruição completa da escala local do cluster. Além disso, se \(C_1\) e \(C_2\) têm \(n\) pontos cada, há \(2 \times \binom{n}{2} \approx n^2\) pares locais e \(n^2\) pares inter-cluster. À medida que o número de clusters aumenta, o número de pares inter-cluster escala quadraticamente e domina a soma irrestrita, forçando o algoritmo a sacrificar as distâncias locais para preservar a geometria macroscópica.

Questão 3: A Assimetria da Divergência KL no SNE

A perda é \(C = \mathrm{KL}(P \parallel Q) = \sum_{i \ne j} p_{ij} \ln \frac{p_{ij}}{q_{ij}}\). - Cenário (a) — Falso Afastamento: Se \(p_{ij} \gg 0\) (vizinhos em \(\mathbb{R}^D\)) e o mapa 2D os afasta de tal forma que \(q_{ij} \to 0\), a razão \(\frac{p_{ij}}{q_{ij}} \to \infty\). O termo \(p_{ij} \ln(p_{ij}/q_{ij}) \to +\infty\). A perda explode, exercendo uma força atrativa imensa que obriga o algoritmo a recolocar \(\mathbf{y}_i\) e \(\mathbf{y}_j\) próximos no plano. - Cenário (b) — Falsa Aproximação: Se \(p_{ij} \approx 0\) (pontos distantes em \(\mathbb{R}^D\)) e o mapa 2D os posiciona próximos (\(q_{ij}\) moderado), temos \(\lim_{p \to 0^+} p \ln(p / q) = 0\). A penalidade incorrida é praticamente nula. Conclusão: O algoritmo prioriza estritamente manter verdadeiros vizinhos juntos (preservação de precisão local), mas é indiferente a aproximações espúrias de pontos distantes. Essa propriedade protege a integridade interna dos clusters, mas significa que a distância entre agrupamentos distintos no mapa 2D não é controlada pela divergência KL, não devendo ser interpretada como distância física real.

Questão 4: O Mecanismo da Cauda Pesada de Student-\(t\)

Seja \(d = \|\mathbf{y}_i - \mathbf{y}_j\|\). Sob o kernel gaussiano, \(q_{\text{gauss}} \propto \exp(-d^2)\). Sob o kernel Student-\(t\) com 1 grau de liberdade, \(q_{\text{student}} \propto (1 + d^2)^{-1}\). Para uma probabilidade pequena de vizinhança na cauda, digamos \(q \approx 0{,}01\): - Na Gaussiana: \(\exp(-d^2) \approx 0{,}01 \implies -d^2 = \ln(0{,}01) \approx -4{,}6 \implies d \approx \sqrt{4{,}6} \approx 2{,}14\). - Na Student-\(t\): \(\frac{1}{1 + d^2} \approx 0{,}01 \implies 1 + d^2 \approx 100 \implies d^2 \approx 99 \implies d \approx 9{,}95\). A distância euclidiana necessária para produzir a mesma probabilidade residual é quase cinco vezes maior sob a Student-\(t\). Isso significa que pontos e agrupamentos moderadamente distantes em \(\mathbb{R}^D\) podem ficar muito mais afastados fisicamente no mapa 2D sem inflacionar a perda de Kullback-Leibler. Essa cauda pesada atua dissipando a pressão de confinamento, abrindo uma vasta região central livre onde cada aglomerado pode desdobrar sua microestrutura sem sofrer repulsão esmagadora.

Questão 5: Auditoria Metodológica: Diagnóstico de Falácias no t-SNE

  1. Afirmação (i) — Errada: A variância de \(\sigma_i\) é adaptada localmente pelo t-SNE via perplexidade. Regiões muito densas no espaço original têm seu raio de vizinhança encolhido e são “infladas” no mapa 2D para acomodar os pontos; regiões esparsas são comprimidas. O diâmetro visual do cluster no mapa 2D não reflete a variância ou o volume intrínseco no espaço de alta dimensão.
  2. Afirmação (ii) — Errada: Quando dois agrupamentos se separam no mapa, \(p_{ij} \approx 0\) para todos os pontos entre eles. A força atrativa da perda cessa e a distância entre eles é determinada pela dinâmica de repulsão eletrostática no plano e pela inicialização aleatória. Distâncias inter-cluster em gráficos t-SNE não têm significado quantitativo ou filogenético.
  3. Afirmação (iii) — Errada: O t-SNE clássico é um método não paramétrico baseado em otimização direta de coordenadas \(\mathbf{Y}\). Não existe uma função analítica aprendida \(f: \mathbb{R}^D \to \mathbb{R}^2\) para projetar pontos novos fora da amostra original. Mapear um novo paciente requer reotimização global com \(N+1\) pontos ou uso de redes neurais paramétricas dedicadas (Parametric t-SNE).

Gabarito dos Testes Conceituais (Verdadeiro ou Falso)

Teste 1: Geometria de Altas Dimensões e Crowding Problem

  • (a) V: Trata-se do simplex regular de dimensão \(D\) (2 pontos em 1D, 3 no triângulo em 2D, 4 no tetraedro em 3D, \(D+1\) em dimensão \(D\)).
  • (b) V: A área do plano euclidiano (\(r^2\)) é insuficiente para acomodar a quantidade de vizinhos que cabem na casca esférica de volume proporcional a \(r^D\).
  • (c) F: A PCA busca os eixos de máxima variância global; pontos distantes ortogonalmente a esses eixos são projetados sobrepostos, destruindo vizinhanças locais.
  • (d) V: O objetivo de métodos como o t-SNE é a preservação de vizinhança topológica, sem suporte a decodificação ou reconstrução métrica de atributos.

Teste 2: MDS e a Função Stress

  • (a) V: Pelo teorema de Young-Householder-Torgerson, o MDS clássico via centralização dupla da matriz euclidiana e autovalores é equivalente à PCA linear.
  • (b) V: Em ambos os casos, \(|50-40| = 10\) e \(|11-1| = 10\). Ao quadrado, ambos geram penalidade \((10)^2 = 100\), ignorando a escala relativa.
  • (c) F: O MDS não métrico (Kruskal, 1964) opera justamente com regressão isotônica sobre ordens monotônicas de postos/rankings de dissimilaridades.
  • (d) V: Como há \(O(N^2)\) pares e a maioria são pares inter-cluster com distâncias absolutas grandes, eles dominam a soma do Stress.

Teste 3: SNE, Perplexidade e Divergência KL

  • (a) V: A Perplexidade \(2^{H(P_i)}\) coincide com \(K\) para uma distribuição uniforme sobre \(K\) vizinhos, ditando o número efetivo de vizinhos.
  • (b) F: Em áreas de alta densidade, \(\sigma_i^2\) é calibrado para ser menor, pois uma região geométrica pequena já acumula a entropia exigida.
  • (c) V: Quando \(p_{ij} \to 0\), \(p_{ij} \ln(p_{ij}/q_{ij}) \to 0\), de modo que aproximações espúrias de pontos distantes não são severamente penalizadas.
  • (d) V: A simetrização \(p_{ij} = (p_{j|i} + p_{i|j})/(2N)\) garante que um ponto isolado receba peso significativo se for escolhido como vizinho por outros.

Teste 4: O Kernel Student-\(t\) e a Dinâmica do Gradiente

  • (a) F: A distribuição \(t\)-Student (\(\nu=1\)) possui decaimento em lei de potência \(1/(1+d^2)\), que é muito mais lento que o decaimento exponencial subgaussiano.
  • (b) V: O t-SNE mantém a Gaussiana no espaço original de alta dimensão (\(P\)) e aplica a Student-\(t\) exclusivamente no mapa de baixa dimensão (\(Q\)).
  • (c) V: O gradiente decompõe-se no termo \((p_{ij} - q_{ij})\). Quando \(q_{ij} > p_{ij}\), a força resultante é de repulsão eletrostática no plano.
  • (d) V: A cauda pesada permite que clusters não relacionados fiquem distantes no mapa com \(q_{ij}\) baixo sustentado, sem explodir a perda KL.

Teste 5: Armadilhas de Interpretação e Propriedades Práticas

  • (a) F: Quando \(p_{ij} \approx 0\), não há força de atração entre os clusters; a distância observada decorre da repulsão no plano e da inicialização.
  • (b) V: Perplexidade muito baixa (ex.: 2) restringe a vizinhança a pares imediatos, desintegrando o cluster em ilhas artificiais desconexas.
  • (c) F: O t-SNE padrão é um método não paramétrico baseado em otimização de coordenadas; não gera uma função indutiva \(f(\mathbf{x})\).
  • (d) V: Flutuações estatísticas em amostras finitas de ruído puro podem ser organizadas pelo t-SNE em falsos agrupamentos aparentes.

Teste 6: Estabilidade, Inicialização e Custo Computacional

  • (a) F: A função de custo da divergência KL sobre coordenadas \(\mathbf{Y}\) é altamente não convexa e repleta de mínimos locais.
  • (b) V: O cálculo exato exige avaliar todos os pares na soma do denominador de \(q_{ij}\), custando \(O(N^2)\) por iteração.
  • (c) V: A inicialização por PCA organiza previamente a orientação global macroscópica, reduzindo a variabilidade estocástica do gradiente descendente.
  • (d) V: A perda é invariante a translações e rotações globais, produzindo mapas geometricamente idênticos a menos de transformações rígidas.