Exercícios — Aula 8: Redução para Visualização: MDS e t-SNE
Aprendizado Não Supervisionado
Questões Discursivas
A Geometria do Crowding Problem e a Razão Volume/Superfície: Considere o volume de uma esfera de raio \(r\) em \(\mathbb{R}^D\), dado por \(V_D(r) = C_D r^D\). Mostre analiticamente que a fração do volume total que reside na casca esférica periférica externa de espessura \(\epsilon \ll r\) tende a \(1\) quando a dimensão \(D \to \infty\). A partir desse resultado, explique por que tentar preservar simultaneamente todas as distâncias de um conjunto de pontos de \(\mathbb{R}^D\) em um plano \(\mathbb{R}^2\) gera inevitavelmente um congestionamento que comprime os pontos no centro do mapa.
O Domínio das Escalas Longas no MDS: A perda Stress do Multidimensional Scaling (MDS) métrico é dada por \(\sigma_M(\mathbf{Y}) = \sum_{i < j} (d_{ij}^{(X)} - d_{ij}^{(Y)})^2\). Suponha um conjunto de dados composto por dois agrupamentos densos e pequenos separados por uma distância grande \(L \gg 1\). Discuta analiticamente por que o otimizador do MDS priorizará manter a distância inter-cluster próxima de \(L\) mesmo que isso implique colapsar ou distorcer severamente as distâncias internas de vizinhança local dentro de cada cluster.
A Assimetria da Divergência KL no SNE: A função de custo do SNE é a divergência de Kullback-Leibler \(\mathrm{KL}(P \parallel Q) = \sum_{i \ne j} p_{ij} \ln \frac{p_{ij}}{q_{ij}}\). Analise matematicamente o comportamento do custo nos dois cenários extremos de erro:
- Falso Afastamento: \(p_{ij}\) é grande (pontos são vizinhos próximos em \(\mathbb{R}^D\)), mas \(q_{ij} \to 0\) (afastados no mapa 2D).
- Falsa Aproximação: \(p_{ij} \to 0\) (pontos pertencem a clusters distintos em \(\mathbb{R}^D\)), mas \(q_{ij}\) é moderado (colocados próximos no mapa 2D). Explique como essa assimetria protege a coesão dos clusters locais e por que ela impede que o t-SNE seja usado diretamente como medidor de distâncias globais entre agrupamentos.
O Mecanismo da Cauda Pesada de Student-\(t\): No t-SNE, a similaridade no mapa 2D é calculada via kernel de Cauchy (Student-\(t\) com 1 grau de liberdade): \[q_{ij} \propto \left(1 + \|\mathbf{y}_i - \mathbf{y}_j\|^2\right)^{-1}\] em contraste com o kernel gaussiano \(q_{ij} \propto \exp(-\|\mathbf{y}_i - \mathbf{y}_j\|^2)\) do SNE original. Demonstre por que, para valores pequenos e moderados de probabilidade de vizinhança \(p_{ij}\), a distância \(\|\mathbf{y}_i - \mathbf{y}_j\|\) necessária para que \(q_{ij} \approx p_{ij}\) é muito maior sob a Student-\(t\) do que sob a Gaussiana. Como essa propriedade física “abre espaço” para a microestrutura dos clusters no mapa 2D?
Auditoria Metodológica: Diagnóstico de Falácias no t-SNE: Um cientista de dados apresenta um relatório baseado em um gráfico t-SNE gerado com perplexidade \(\text{Perp}=30\). Ele afirma:
- “O Cluster 1 possui o triplo do diâmetro visual do Cluster 2, o que prova que sua variância intrínseca é 9 vezes maior.”
- “O Cluster 1 está a 20 cm do Cluster 2 e a 5 cm do Cluster 3, provando que as classes 1 e 3 são muito mais próximas geneticamente.”
- “Com este mapa ajustado, poderemos classificar novos pacientes recebidos em tempo real aplicando a função aprendida pelo t-SNE.” Aponte o erro conceitual rigoroso em cada uma das três afirmações.
Testes Conceituais (Verdadeiro ou Falso)
Julgue os itens a seguir como Verdadeiro (V) ou Falso (F).
Teste 1: Geometria de Altas Dimensões e Crowding Problem
- □ (a) Em qualquer espaço euclidiano de dimensão \(D\), é possível posicionar até \(D+1\) pontos de modo que todas as distâncias entre pares sejam rigorosamente idênticas.
- □ (b) O crowding problem surge porque o volume da esfera euclidiana em 2D cresce com \(r^2\), enquanto em \(\mathbb{R}^D\) cresce com \(r^D\), faltando área física no plano para acomodar vizinhos moderadamente distantes.
- □ (c) A projeção PCA em 2 componentes garante a preservação exata das vizinhanças locais mais próximas de cada ponto, minimizando distorções topológicas.
- □ (d) Métodos de visualização em 2D baseados em preservação de vizinhança abrem mão da capacidade de reconstrução métrica exata dos atributos originais.
Teste 2: MDS e a Função Stress
- □ (a) O MDS clássico exato baseado em produtos internos duplamente centralizados produz uma configuração bidimensional idêntica à projeção obtida pelos dois primeiros componentes da PCA.
- □ (b) Na função de perda Stress quadrática, errar a distância entre dois pontos distantes de \(50\) para \(40\) gera a mesma penalidade que errar a distância de vizinhos de \(11\) para \(1\).
- □ (c) O MDS não métrico exige que as dissimilaridades originais sejam distâncias euclidianas estritas, sendo incapaz de processar rankings ou ordens monotônicas de preferência.
- □ (d) Como a função Stress calcula a soma irrestrita sobre todos os \(O(N^2)\) pares, os pares inter-cluster (distâncias longas) exercem peso desproporcional na configuração final.
Teste 3: SNE, Perplexidade e Divergência KL
- □ (a) A Perplexidade pode ser interpretada operacionalmente como o número efetivo de vizinhos que o algoritmo tenta alocar para cada ponto na alta dimensão.
- □ (b) Em regiões de alta densidade no espaço original, o algoritmo SNE calibra automaticamente uma variância \(\sigma_i^2\) maior para conseguir abranger mais espaço.
- □ (c) Na divergência \(\mathrm{KL}(P \parallel Q)\), o termo associado a pontos distantes na alta dimensão (\(p_{ij} \approx 0\)) contribui com valor próximo de zero para a perda, independentemente de onde eles caiam no mapa 2D.
- □ (d) A simetrização das probabilidades conjuntas \(p_{ij} = \frac{p_{j|i} + p_{i|j}}{2N}\) assegura que pontos isolados (outliers) mantenham influência mínima no gradiente se forem considerados vizinhos por outros pontos.
Teste 4: O Kernel Student-\(t\) e a Dinâmica do Gradiente
- □ (a) A densidade de probabilidade da distribuição \(t\)-Student com \(1\) grau de liberdade possui decaimento exponencial análogo ao da distribuição normal.
- □ (b) O t-SNE adota o kernel de Student-\(t\) no espaço de projeção de baixa dimensão (\(Q\)), mas mantém o kernel gaussiano no espaço original de alta dimensão (\(P\)).
- □ (c) No gradiente do t-SNE, a força entre dois pontos é puramente repulsiva quando a probabilidade no mapa excede a probabilidade no espaço original (\(q_{ij} > p_{ij}\)).
- □ (d) A cauda pesada de Student-\(t\) resolve o crowding problem permitindo que agrupamentos não relacionados fiquem mais afastados no mapa 2D sem inflacionar a perda KL.
Teste 5: Armadilhas de Interpretação e Propriedades Práticas
- □ (a) A distância física observada entre dois clusters separados em uma figura t-SNE é diretamente proporcional à distância euclidiana entre seus centróides no espaço de alta dimensão.
- □ (b) Configurar uma perplexidade extremamente baixa (ex.: \(\text{Perp} = 2\)) pode fragmentar um cluster homogêneo e contínuo em dezenas de pequenos agrupamentos artificiais.
- □ (c) O t-SNE aprende uma função contínua paramétrica \(f(\mathbf{x})\) que permite mapear diretamente novos pontos de teste para o plano 2D sem reexecutar a otimização.
- □ (d) A aplicação de t-SNE sobre ruído branco puramente aleatório e sem correlação pode gerar padrões visuais com aspecto nítido de aglomerados devido a flutuações amostrais.
Teste 6: Estabilidade, Inicialização e Custo Computacional
- □ (a) A função de custo da divergência KL no t-SNE é estritamente convexa em relação às coordenadas \(\mathbf{Y}\), garantindo convergência para um mínimo global único a partir de qualquer inicialização.
- □ (b) Executar o t-SNE clássico exato para um conjunto de dados de \(N = 10^6\) pontos é computacionalmente inviável sem aproximações, pois o cálculo das forças repulsivas requer \(O(N^2)\) operações por iteração.
- □ (c) Inicializar o t-SNE com os dois primeiros componentes da PCA frequentemente melhora a reprodutibilidade e a preservação de estruturas de maior escala em relação à inicialização aleatória isotrópica.
- □ (d) Duas execuções do t-SNE com diferentes sementes de números aleatórios podem gerar figuras que são reflexões ou rotações uma da outra, preservando exatamente a mesma informação topológica local.