Aprendizado de Variedades

O que é aprendizado de variedades?

Aprendizado de variedades (manifold learning) é uma família de métodos de redução de dimensionalidade não linear (nonlinear dimensionality reduction) baseada na hipótese da variedade (manifold hypothesis): embora os dados possam ser representados em um espaço de alta dimensionalidade (p. ex., pixels, incorporações de palavras (word embeddings), leituras de sensores), os graus de liberdade que realmente variam muitas vezes vivem em ou perto de uma variedade de dimensionalidade muito menor embutida nesse espaço.

O objetivo prático é computar uma representação de baixa dimensionalidade (uma incorporação (embedding)) que:

  • Preserva a estrutura de vizinhança local (local neighborhood structure) (pontos próximos permanecem próximos),
  • Às vezes também preserva a geometria global (global geometry) (p. ex., distâncias geodésicas aproximadas),
  • Produz representações úteis para visualização (visualization), agrupamento (clustering), pré-processamento (preprocessing) ou aprendizado a jusante (downstream learning).

O aprendizado de variedades complementa métodos lineares como Análise de Componentes Principais (Principal Component Analysis, PCA) e técnicas lineares aleatórias como Projeção Aleatória (Random Projection). Quando a estrutura subjacente é não linear (p. ex., um “rolinho suíço (Swiss roll)”), métodos lineares podem falhar em “desenrolar” os dados.

Por que variedades aparecem em dados de aprendizado de máquina (intuição)

Uma variedade (manifold) é um espaço que, localmente, se parece com um espaço euclidiano (Euclidean space). Um exemplo clássico é a superfície de uma esfera: globalmente curva, mas pequenos trechos parecem planos.

Em termos de aprendizado de máquina:

  • Imagens de rostos podem variar principalmente por alguns fatores: pose, iluminação, expressão. Mesmo que cada imagem seja um ponto em um enorme espaço de pixels, a dimensão intrínseca (intrinsic dimension) pode ser pequena.
  • Configurações de um braço robótico podem ser controladas por um pequeno número de ângulos das juntas; leituras de sensores podem ser uma função não linear desses ângulos.
  • Muitos conjuntos de dados “naturais” têm restrições que reduzem os graus de liberdade efetivos.

Essa ideia se conecta à maldição da dimensionalidade (curse of dimensionality): em altas dimensões, distâncias tornam-se menos informativas, vizinhanças tornam-se esparsas e a complexidade amostral (sample complexity) aumenta. O aprendizado de variedades tenta explorar a baixa dimensão intrínseca para tornar a geometria baseada em vizinhança mais significativa. Veja também Maldição da Dimensionalidade.

Ideia central: preservar vizinhanças, não coordenadas brutas

A maioria dos algoritmos de aprendizado de variedades segue um modelo semelhante:

  1. Definir vizinhanças locais (p. ex., k vizinhos mais próximos (k-nearest neighbors, k-NN) ou pontos dentro de um raio ε).
  2. Construir um grafo (graph) em que arestas conectam vizinhos.
  3. Definir uma noção de similaridade (similarity) ou distância (distance) ao longo desse grafo.
  4. Computar uma incorporação de baixa dimensionalidade que melhor preserva essas relações.

Isso normalmente resulta em um método espectral (spectral method): resolver um problema de autovalores (eigenvalue problem) derivado de uma matriz do grafo (adjacência (adjacency), Laplaciano (Laplacian) ou matriz de distâncias geodésicas).

A definição de vizinhança geralmente é feita via:

  • grafo k-NN (k-NN graph): conecte cada ponto aos seus k vizinhos mais próximos (comum, robusto).
  • grafo de bola-ε (ε-ball graph): conecte pontos dentro da distância ε (sensível à densidade).

A escolha da distância importa (euclidiana, cosseno, etc.), assim como o escalonamento de atributos (feature scaling).

Fundamentos matemáticos (alto nível)

Dimensão intrínseca vs. extrínseca

  • Dimensão extrínseca (extrinsic dimension): a dimensão do espaço observado (p. ex., 784 pixels).
  • Dimensão intrínseca: os graus de liberdade efetivos da variedade (p. ex., 2–10).

O aprendizado de variedades assume que os dados estão próximos de uma variedade suave ( \mathcal{M} \subset \mathbb{R}^D ) com dimensão intrínseca ( d \ll D ), e busca uma incorporação ( f: \mathbb{R}^D \to \mathbb{R}^d ).

Linearidade local

Mesmo que a variedade seja globalmente não linear, pequenas vizinhanças são aproximadamente lineares (um espaço tangente (tangent space)). Muitos algoritmos exploram isso:

  • Aproximar cada vizinhança com pesos de reconstrução (reconstruction weights) lineares (LLE),
  • Aproximar distâncias locais e “colar” vizinhanças de forma consistente (Mapas Próprios do Laplaciano),
  • Aproximar distâncias globais na variedade via caminhos mínimos (shortest paths) em um grafo de vizinhança (Isomap).

Laplacianos de grafo e incorporações espectrais

Uma construção comum é o Laplaciano do grafo (graph Laplacian):

  • Construir pesos ( W_{ij} ) entre vizinhos (i,j) (p. ex., núcleo de calor (heat kernel) ( \exp(-|x_i-x_j|^2/\sigma^2) )).
  • Matriz de grau (degree matrix) ( D ) com ( D_{ii} = \sum_j W_{ij} ).
  • Laplaciano não normalizado (unnormalized Laplacian) ( L = D - W ), ou variantes normalizadas (normalized variants).

Autovetores (eigenvectors) de (L) (ou problemas de autovalores generalizados envolvendo (D)) geram incorporações que preservam a estrutura local. Isso é estreitamente relacionado à teoria espectral de grafos (spectral graph theory) e ao Agrupamento Espectral (Spectral Clustering).

Algoritmos comuns de aprendizado de variedades

Isomap (Mapeamento Isométrico, Isometric Mapping)

Ideia: Preservar distâncias geodésicas (geodesic distances) (distâncias ao longo da variedade), não distâncias euclidianas em linha reta no espaço ambiente (ambient space).

Passos:

  1. Construir um grafo de vizinhança (k-NN ou ε).
  2. Aproximar distâncias geodésicas entre todos os pares usando caminhos mínimos no grafo (p. ex., Dijkstra/Floyd–Warshall).
  3. Executar MDS clássico (escalonamento multidimensional, multidimensional scaling) na matriz de distâncias geodésicas para encontrar uma incorporação de baixa dimensionalidade.

Pontos fortes:

  • Captura parte da estrutura global ao usar caminhos mínimos entre todos os pares.
  • Funciona bem quando a variedade é bem amostrada e “desenrolável” (p. ex., rolinho suíço).

Pontos fracos:

  • Sensível à conectividade do grafo (graph connectivity): k muito pequeno desconecta; k muito grande “curto-circuita” atravessando dobras.
  • Mais caro do que métodos puramente locais devido aos caminhos mínimos em grafos.

Quando usar:

  • Visualização/desenrolamento quando você espera uma variedade globalmente coerente e amostragem suficiente.

LLE (Incorporação Linear Local, Locally Linear Embedding)

Ideia: Cada ponto pode ser reconstruído a partir de uma combinação linear de seus vizinhos. Preservar esses pesos de reconstrução na incorporação.

Passos:

  1. Para cada ponto (x_i), encontrar seus k vizinhos mais próximos.
  2. Computar pesos (w_{ij}) que reconstruam (x_i \approx \sum_{j \in \mathcal{N}(i)} w_{ij} x_j) com restrições (p. ex., os pesos somam 1).
  3. Encontrar pontos incorporados (y_i) que minimizam o erro de reconstrução ( \sum_i |y_i - \sum_j w_{ij} y_j|^2 ).
  4. Resolver um problema de autovalores.

Pontos fortes:

  • Forte em preservar a geometria local.
  • Muitas vezes é bom em desenrolar sem computar explicitamente distâncias geodésicas entre todos os pares.

Pontos fracos:

  • Sensível a ruído e à escolha de k.
  • Pode ter dificuldades com densidade de amostragem variável.
  • Preserva principalmente estrutura local; o arranjo global pode ser distorcido.

Variantes:

  • Modified LLE, Hessian LLE, LTSA (Local Tangent Space Alignment), etc., que tentam lidar com problemas de estabilidade e curvatura.

Mapas Próprios do Laplaciano (Laplacian Eigenmaps)

Ideia: Preservar localidade incentivando vizinhos a permanecerem próximos na incorporação, usando o Laplaciano do grafo.

Visão de otimização: Minimizar [ \sum_{i,j} W_{ij} |y_i - y_j|^2 ] sujeito a restrições que evitem colapso (p. ex., (Y^T D Y = I)).

Pontos fortes:

  • Conexão teórica clara com geometria de variedades: o Laplaciano do grafo aproxima o operador de Laplace–Beltrami (Laplace–Beltrami operator) na variedade sob suposições de amostragem.
  • Frequentemente robusto e conceitualmente simples.

Pontos fracos:

  • Como o LLE, é majoritariamente local; a geometria global pode ser arbitrária até distorções.
  • A qualidade da incorporação depende da construção de afinidade (W) e de sua escala.

Fortemente relacionado:

  • Incorporações espectrais (spectral embeddings) usadas em agrupamento e em aprendizado semissupervisionado (semi-supervised learning).

Como o aprendizado de variedades se relaciona com t-SNE e UMAP

Aprendizado de variedades é um guarda-chuva amplo; t-SNE e UMAP são frequentemente discutidos ao lado de métodos clássicos como Isomap/LLE/Mapas Próprios do Laplaciano porque também constroem grafos de vizinhança e focam na estrutura local.

t-SNE

t-SNE (Incorporação Estocástica de Vizinhança com Distribuição t, t-distributed Stochastic Neighbor Embedding) constrói distribuições de probabilidade (probability distributions) sobre vizinhos no espaço de alta dimensionalidade e encontra uma incorporação de baixa dimensionalidade cujas probabilidades de vizinhança correspondam, usando uma distribuição de cauda pesada (heavy-tailed distribution) em baixas dimensões para reduzir o “apinhamento” (crowding).

  • Excelente para visualização 2D/3D de agrupamentos.
  • Não foi projetado para preservar fielmente geometria global ou distâncias.
  • Sensível a hiperparâmetros (hyperparameters) (perplexity, learning rate) e à aleatoriedade (randomness).
  • Tipicamente não é usado como uma incorporação de propósito geral para modelos a jusante (embora possa ser).

UMAP

UMAP (Aproximação e Projeção Uniforme de Variedades, Uniform Manifold Approximation and Projection) é explicitamente motivado por ideias de variedades e topologia. Ele constrói um complexo simplicial difuso (fuzzy simplicial complex) a partir do grafo k-NN e otimiza uma incorporação de baixa dimensionalidade para preservar essas relações difusas de vizinhança.

  • Frequentemente preserva mais estrutura global do que t-SNE (embora ainda seja primariamente local).
  • Escala bem e oferece suporte para transformar novos pontos em implementações comuns.
  • Amplamente usado para visualização e como etapa de pré-processamento.

Regra prática

  • Isomap: experimente quando você quiser um desenrolamento mais global e acreditar que a variedade está bem amostrada.
  • LLE / Mapas Próprios do Laplaciano: experimente quando relações de vizinhança local forem o mais importante.
  • t-SNE / UMAP: use principalmente para visualização; UMAP é mais comumente usado para incorporações reutilizáveis.

Exemplo prático: desenrolando um rolinho suíço em Python

O rolinho suíço é um conjunto de dados clássico: pontos ficam em uma folha 2D embutida em 3D, enrolada de modo que distâncias euclidianas podem ser enganosas.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_swiss_roll
from sklearn.manifold import Isomap, LocallyLinearEmbedding, SpectralEmbedding

# Generate data
X, color = make_swiss_roll(n_samples=2000, noise=0.05, random_state=0)

methods = {
    "Isomap": Isomap(n_neighbors=12, n_components=2),
    "LLE": LocallyLinearEmbedding(n_neighbors=12, n_components=2, method="standard"),
    "Laplacian Eigenmaps": SpectralEmbedding(n_neighbors=12, n_components=2, affinity="nearest_neighbors"),
}

fig, axes = plt.subplots(1, 3, figsize=(12, 4))
for ax, (name, model) in zip(axes, methods.items()):
    Y = model.fit_transform(X)
    sc = ax.scatter(Y[:, 0], Y[:, 1], c=color, s=5, cmap="Spectral")
    ax.set_title(name)
    ax.set_xticks([]); ax.set_yticks([])

plt.tight_layout()
plt.show()

O que observar:

  • Uma boa incorporação “desenrola” o rolinho suíço em uma folha 2D aproximadamente retangular.
  • Se n_neighbors for pequeno demais, o grafo pode desconectar → incorporação fragmentada.
  • Se for grande demais, o Isomap pode criar atalhos → desenrolamento ruim.

Fluxo de trabalho típico e boas práticas

1) Faça o pré-processamento com cuidado

  • Escalone os atributos (p. ex., padronização (standardization)). Muitos métodos baseados em distância quebram se um atributo dominar.
  • Considere remover ruído (denoising) ou usar primeiro uma redução linear leve (p. ex., PCA para 30–100 dimensões) para reduzir ruído e acelerar o k-NN.

2) Escolha um tamanho de vizinhança (k ou ε)

O tamanho da vizinhança controla o compromisso viés–variância (bias–variance tradeoff):

  • Pequeno demais: grafos de vizinhança desconectados ou instáveis; sensível a ruído.
  • Grande demais: vizinhanças violam a “linearidade local” e podem criar atalhos atravessando dobras da variedade.

Na prática:

  • Comece com k no intervalo 5–50, dependendo do tamanho do conjunto de dados e do ruído.
  • Verifique a conectividade do grafo (um único componente costuma ser desejável para métodos globais como Isomap).
  • Teste múltiplos valores de k e compare a estabilidade.

3) Escolha o método certo para o objetivo

  • Visualização (2D/3D): UMAP/t-SNE muitas vezes são os melhores; Isomap/LLE podem ser instrutivos em variedades “de brinquedo” ou quando um desenrolamento global é significativo.
  • Extração de atributos (feature extraction) para aprendizado de máquina a jusante: tenha cautela; incorporações de variedades podem distorcer distâncias e podem ser instáveis fora da amostra.

4) Lide com pontos fora da amostra (o problema de “dados novos”)

Muitos algoritmos clássicos de variedades são não paramétricos (non-parametric): eles computam incorporações apenas para os pontos de treino.

As opções incluem:

  • Recomputar a incorporação com pontos adicionados (caro; pode mudar coordenadas existentes).
  • Usar extensões fora da amostra (out-of-sample extensions) (p. ex., método de Nyström (Nyström method) para incorporações espectrais, Isomap com marcos (landmark Isomap)).
  • Preferir métodos com um .transform() natural (o UMAP comumente oferece isso; Isomap/LLE do scikit-learn suportam transformações em alguns cenários, mas ainda podem ser limitados).

5) Avalie incorporações de forma apropriada

Para visualização 2D, verificações qualitativas importam, mas você também pode usar:

  • Confiabilidade (trustworthiness) (quão bem as vizinhanças locais são preservadas de alta → baixa dimensão).
  • Continuidade (continuity) (preservação de vizinhanças de baixa → alta).
  • Desempenho em tarefas a jusante (classificação/agrupamento) como um proxy, mas atenção: uma incorporação visualmente bonita nem sempre é a melhor para modelagem preditiva.

Aplicações

Visualização e análise exploratória

  • Entender estrutura de grupos, gradientes, trajetórias (p. ex., RNA-seq de célula única (single-cell RNA-seq)).
  • Encontrar subpopulações, anomalias ou efeitos de lote (batch effects).

UMAP e t-SNE dominam aqui, mas Mapas Próprios do Laplaciano e Isomap podem oferecer visões complementares quando um desenrolamento global é significativo.

Pré-processamento para agrupamento e aprendizado semissupervisionado

Incorporações espectrais (Mapas Próprios do Laplaciano) estão intimamente ligadas ao aprendizado baseado em grafos (graph-based learning); elas podem melhorar a separação quando clusters seguem a estrutura de variedade. Isso se conecta naturalmente ao Agrupamento Espectral.

Compressão e aprendizado de representações

Embora o aprendizado de variedades clássico normalmente não seja usado para compressão em produção (devido a problemas fora da amostra), ele influencia o aprendizado de representações moderno:

Robótica, controle e sistemas dinâmicos

Observações de sensores podem estar em variedades induzidas por estados latentes (ângulos, posições). Métodos de variedades podem revelar espaços de estado de baixa dimensionalidade ou ajudar a construir modelos compactos.

Limitações e modos de falha comuns

A suposição de variedade pode estar errada

Se os dados não forem bem aproximados por uma variedade suave de baixa dimensionalidade (p. ex., muitos fatores discretos, muito ruído, amostragem esparsa), o aprendizado de variedades pode produzir incorporações enganosas.

Sensibilidade à densidade de amostragem

Muitos métodos assumem amostragem razoavelmente uniforme. Densidade variável pode:

  • Distorcer incorporações (regiões densas dominam),
  • Quebrar a seleção de vizinhança (k-NN abrange escalas físicas diferentes em áreas esparsas vs. densas).

O UMAP costuma ser mais robusto aqui do que métodos clássicos, mas problemas de densidade podem afetar qualquer abordagem baseada em grafo de vizinhança.

Ruído e “curto-circuitos”

Ruído pode conectar pontos que não deveriam ser vizinhos. No Isomap, algumas arestas erradas podem mudar drasticamente os caminhos mínimos geodésicos (criando atalhos através da variedade).

Escalonamento computacional

  • A construção do grafo k-NN pode ser cara para (n) grande e (D) alto (vizinhos mais próximos aproximados (approximate nearest neighbors) podem ajudar).
  • Caminhos mínimos e decomposição em autovalores (eigen-decomposition) do Isomap podem ser custosos em escala.

Interpretabilidade dos eixos

Diferentemente do PCA, eixos de incorporações de variedades tipicamente não têm um significado direto. Rotações/reflexões são arbitrárias; apenas a geometria relativa é significativa.

Aprendizado de variedades vs. métodos relacionados de redução de dimensionalidade

Resumo

O aprendizado de variedades fornece um conjunto de ferramentas fundamentado para redução de dimensionalidade não linear sob a suposição de que dados de alta dimensionalidade ficam próximos de uma variedade de baixa dimensionalidade. Algoritmos clássicos como Isomap, LLE e Mapas Próprios do Laplaciano constroem grafos de vizinhança e computam incorporações que preservam a estrutura geométrica local (e às vezes global).

Na prática moderna, ideias de variedades influenciam fortemente métodos de visualização amplamente usados como t-SNE e UMAP, e elas se conectam conceitualmente ao aprendizado de representações em modelos profundos. Os principais desafios práticos são escolher vizinhanças, lidar com ruído e variação de densidade, e generalização fora da amostra.