Projeção Aleatória

Visão geral

Projeção aleatória (random projection) é uma técnica de redução de dimensionalidade linear que mapeia vetores de um espaço de alta dimensão (\mathbb{R}^d) para um espaço de menor dimensão (\mathbb{R}^k) usando uma matriz aleatória, ao mesmo tempo em que preserva aproximadamente as distâncias par-a-par (e, portanto, a estrutura de vizinhança) com alta probabilidade.

Ela é mais conhecida por sua conexão com o lema de Johnson–Lindenstrauss (Johnson–Lindenstrauss (JL) lemma), que (informalmente) diz:

Qualquer conjunto de (n) pontos em alta dimensão pode ser embutido em (\mathbb{R}^k) com pequena distorção nas distâncias, desde que (k) seja da ordem de (\log n) (e dependa inversamente do quadrado da distorção permitida).

A projeção aleatória é frequentemente usada para mitigar a maldição da dimensionalidade (curse of dimensionality) em pipelines que dependem de distâncias ou produtos escalares: agrupamento, vizinhos mais próximos aproximados, recuperação em larga escala e como uma etapa rápida de pré-processamento antes de treinar modelos lineares.

Métodos relacionados de redução de dimensionalidade incluem Análise de Componentes Principais (PCA) (dependente dos dados e orientada à reconstrução) e métodos não lineares focados em visualização como t-SNE (Incorporação Estocástica de Vizinhos distribuída em t (t-distributed Stochastic Neighbor Embedding)) e UMAP (Aproximação e Projeção de Variedade Uniforme (Uniform Manifold Approximation and Projection)).

Intuição: por que a aleatoriedade pode preservar a geometria

Em alto nível, a projeção aleatória funciona porque, em altas dimensões, muitas quantidades geométricas se concentram:

  • Se você escolhe uma direção aleatória, a projeção de um vetor nessa direção se comporta de forma previsível (por concentração de medida).
  • Se você projeta em muitas direções aleatórias e reescala apropriadamente, o comportamento médio se torna estável.
  • Distâncias entre pontos são determinadas por normas de vetores de diferença (|x-y|). A projeção aleatória preserva aproximadamente as normas de todos esses vetores de diferença simultaneamente (para um conjunto finito de pontos).

Uma projeção aleatória típica tem a forma:

[ f(x) = \frac{1}{\sqrt{k}} R x ]

onde:

  • (x \in \mathbb{R}^d)
  • (R \in \mathbb{R}^{k \times d}) é uma matriz aleatória (a construção varia)
  • o fator (1/\sqrt{k}) mantém a escala das normas aproximadamente consistente

Se você escolher (R) a partir de uma boa distribuição, então, para qualquer vetor fixo (v), (|f(v)|_2^2) se concentra em torno de (|v|_2^2). O lema de Johnson–Lindenstrauss estende isso de um vetor para todas as diferenças par-a-par entre (n) pontos usando um argumento de cota por união (union bound).

O lema de Johnson–Lindenstrauss (o que ele garante)

Uma formulação comum do lema de Johnson–Lindenstrauss:

Seja (0 < \varepsilon < 1) e (X={x_1,\dots,x_n}\subset \mathbb{R}^d). Existe um mapeamento (f:\mathbb{R}^d \to \mathbb{R}^k) tal que

[ (1-\varepsilon)|x_i-x_j|_2 \le |f(x_i)-f(x_j)|_2 \le (1+\varepsilon)|x_i-x_j|_2 ]

para todo (i,j), desde que

[ k = O\left(\frac{\log n}{\varepsilon^2}\right) ]

Além disso, um mapeamento linear aleatório (f(x)=\frac{1}{\sqrt{k}}Rx) alcança isso com alta probabilidade para distribuições adequadas de matrizes aleatórias.

O que “preservar aproximadamente as distâncias” significa na prática

  • (\varepsilon) é a tolerância de distorção.
    • (\varepsilon=0.1): distâncias preservadas dentro de aproximadamente ±10%
    • (\varepsilon=0.3): dentro de aproximadamente ±30%
  • (n) é o número de pontos cujas distâncias mútuas você se importa em preservar.
    • O limite depende de (\log n), não da dimensão original (d).
  • A garantia é probabilística e baseada em conjunto:
    • Fixe um conjunto de (n) pontos; uma projeção aleatória funciona para esse conjunto com alta probabilidade.
    • Isso não diz que uma única projeção aleatória preserva distâncias para todos os pontos possíveis em (\mathbb{R}^d) simultaneamente.

Compensação entre distorção e dimensão-alvo

A compensação central é:

  • Menor (\varepsilon) (menos distorção) requer maior (k)
  • Maior (n) (mais pontos) requer maior (k), mas apenas de forma logarítmica

Uma intuição aproximada: para reduzir a distorção pela metade (por exemplo, (\varepsilon) de 0,2 para 0,1), você precisa de cerca de 4× a dimensão-alvo, devido à dependência (\varepsilon^{-2}).

Planejamento por regra de bolso

Se você tem:

  • (n = 10^6) pontos
  • quer (\varepsilon = 0.2)

Então (k) normalmente ficará na faixa de centenas a poucos milhares. Isso pode ser um ganho enorme se sua dimensão original (d) for de dezenas ou centenas de milhares (comum em texto e em atributos esparsos do tipo bag-of-words).

Nuance importante: o limite do JL costuma ser conservador

Em cargas de trabalho reais de aprendizado de máquina (machine learning), o (k) necessário para um desempenho “bom o suficiente” costuma ser menor do que o que limites de pior caso sugerem — porque:

  • seus dados não são adversariais,
  • você não precisa que todas as distâncias par-a-par sejam preservadas igualmente,
  • tarefas a jusante toleram alguma distorção.

Construções comuns de projeção aleatória

Diferentes matrizes aleatórias (R) oferecem diferentes compensações entre garantias teóricas, custo computacional e memória.

Projeção aleatória Gaussiana

Construção:

  • Amostre (R_{ij} \sim \mathcal{N}(0,1))
  • Use (f(x)=\frac{1}{\sqrt{k}}Rx)

Prós

  • Teoria “limpa”; provas clássicas do JL
  • Simples de implementar

Contras

  • Matriz densa: multiplicação custa (O(kd)) por ponto
  • Custo de memória (O(kd)) se armazenada explicitamente

A projeção Gaussiana é boa quando (d) é moderado e você quer simplicidade.

Projeção de Rademacher (±1)

Construção:

  • Amostre (R_{ij} \in {-1,+1}) com igual probabilidade
  • Escale por (1/\sqrt{k})

Isso frequentemente se comporta de forma semelhante à projeção Gaussiana, mas pode ser mais rápido e mais amigável em termos de memória devido à aritmética mais simples.

Projeção aleatória esparsa / Achlioptas

Um esquema esparso popular (estilo Achlioptas) usa entradas em ({-1,0,+1}):

[ R_{ij} = \begin{cases} +1 & \text{com prob } 1/(2s)\ 0 & \text{com prob } 1 - 1/s\ -1 & \text{com prob } 1/(2s) \end{cases} ]

com escalonamento apropriado.

Prós

  • Muito mais rápida para dados esparsos de alta dimensão (por exemplo, texto)
  • Menos memória
  • Frequentemente funciona muito bem na prática

Contras

  • É preciso escolher o nível de esparsidade (s)
  • Implementação um pouco mais complexa

Projeções aleatórias esparsas são especialmente úteis quando seus vetores de entrada são esparsos (comum em one-hot, bag-of-words e outras representações de atributos baseadas em contagens).

Transformações rápidas de Johnson–Lindenstrauss (FJLT)

Para (d) muito grande, você pode reduzir ainda mais a computação usando matrizes aleatórias estruturadas, por exemplo:

  • inversões aleatórias de sinal
  • transformadas de Hadamard/Fourier
  • subamostragem de coordenadas

Isso pode reduzir o custo por ponto de (O(kd)) para aproximadamente (O(d\log d + k)) (dependendo da implementação). Elas são comuns em álgebra linear numérica em larga escala e em alguns sistemas de recuperação, embora sejam menos frequentemente expostas como “one-liners” em bibliotecas de aprendizado de máquina do dia a dia.

Quais propriedades são preservadas (além da distância Euclidiana)?

Como a projeção aleatória preserva aproximadamente normas de vetores e diferenças de vetores, ela também preserva aproximadamente:

  • Produtos internos (produtos escalares), sob condições adequadas
  • Ângulos entre vetores (relacionados à similaridade do cosseno)
  • Muitos algoritmos baseados em geometria Euclidiana, como:
    • agrupamento k-means (baseado em distância)
    • busca por vizinho mais próximo
    • classificadores lineares baseados em margem (até certo grau)

No entanto, ela não é otimizada para:

Aplicações práticas em IA/ML

1) Acelerando métodos baseados em distância

Muitos métodos de aprendizado de máquina desaceleram em alta dimensão porque:

  • calcular distâncias custa (O(d)),
  • estruturas de indexação se degradam (a “maldição da dimensionalidade”),
  • largura de banda de memória vira o gargalo.

A projeção aleatória reduz (d \to k), tornando cada cálculo de distância (O(k)), muitas vezes com perda mínima de qualidade.

Usos comuns:

2) Pré-processamento para modelos lineares em atributos esparsos gigantes

Em classificação de texto ou recomendação, (d) pode ser extremamente grande (por exemplo, milhões de n-grams). A projeção aleatória pode:

  • comprimir o espaço de atributos para um (k) gerenciável,
  • manter o treinamento mais rápido e reduzir memória,
  • frequentemente preservar geometria suficiente para que separadores lineares permaneçam eficazes.

Isso é conceitualmente relacionado ao “truque de hashing” / hashing de atributos (feature hashing) usado em PLN (NLP) em larga escala, embora o hashing de atributos normalmente seja uma abordagem diferente de mapeamento esparso.

3) Redução de dimensionalidade para streaming e com menor exposição de dados

Como a projeção aleatória é:

  • independente dos dados (você não precisa calcular covariância como na PCA),
  • fácil de aplicar incrementalmente,

ela funciona bem em cenários de streaming, nos quais os dados chegam continuamente e você quer uma dimensão de embedding fixa.

Além disso, como ela mistura as coordenadas originais, pode obscurecer atributos brutos individuais (embora não seja uma garantia formal de privacidade por si só).

4) Álgebra linear numérica e otimização

Projeções aleatórias são usadas em álgebra linear numérica aleatorizada para:

  • métodos aproximados de baixo posto,
  • sketching e pré-condicionamento para regressão,
  • acelerar métodos iterativos.

Em aprendizado de máquina, isso aparece em alguns solucionadores em larga escala para mínimos quadrados e objetivos relacionados (por exemplo, problemas do tipo regressão ridge).

Projeção aleatória vs PCA (e quando usar cada uma)

A projeção aleatória e a Análise de Componentes Principais (PCA) são ambas lineares, mas otimizam objetivos diferentes.

Projeção aleatória

  • Independente dos dados: não precisa de ajuste (além de escolher (k))
  • Preserva distâncias par-a-par com alta probabilidade
  • Extremamente escalável; funciona bem em dados esparsos (com construções esparsas)
  • Não foi projetada para reconstrução nem interpretabilidade

PCA

  • Dependente dos dados: aprende direções de variância máxima
  • Frequentemente é melhor quando você se importa com reconstrução e compressão
  • Pode ser mais precisa para tarefas a jusante quando direções de variância líderes importam
  • Mais cara de ajustar; pode ser difícil em escala massiva (embora exista PCA aleatorizada)

Uma heurística prática:

  • Use projeção aleatória quando você precisa de velocidade, capacidade de streaming e preservação de distância para (d) grande.
  • Use PCA quando você quer uma representação compacta que capture a estrutura de variância (e pode arcar com o ajuste).

Exemplo prático: preservação de distância em Python (scikit-learn)

O exemplo a seguir demonstra como a projeção aleatória preserva aproximadamente distâncias par-a-par.

import numpy as np
from sklearn.random_projection import GaussianRandomProjection
from sklearn.metrics import pairwise_distances

rng = np.random.default_rng(0)

n, d = 2000, 10000
X = rng.normal(size=(n, d))

# Project down to k dimensions
k = 500
rp = GaussianRandomProjection(n_components=k, random_state=0)
Xr = rp.fit_transform(X)

# Compare a sample of pairwise distances
idx = rng.choice(n, size=300, replace=False)
D_original = pairwise_distances(X[idx], metric="euclidean")
D_projected = pairwise_distances(Xr[idx], metric="euclidean")

# Relative error statistics
rel_err = np.abs(D_projected - D_original) / (D_original + 1e-12)
print("median relative error:", np.median(rel_err))
print("95th percentile relative error:", np.percentile(rel_err, 95))

O que esperar:

  • O erro relativo mediano pode ser pequeno (frequentemente de alguns por cento a dezenas de por cento, dependendo de (k)).
  • Erros de pior caso são maiores; aumentar (k) reduz a distorção.

Escolhendo \(k\) usando um helper baseado em JL

O scikit-learn fornece um helper baseado em limites de JL:

from sklearn.random_projection import johnson_lindenstrauss_min_dim

n_samples = 1_000_000
eps = 0.2
k_min = johnson_lindenstrauss_min_dim(n_samples=n_samples, eps=eps)
print(k_min)

Trate isso como um ponto de partida seguro, não como um requisito estrito.

Detalhes de implementação e armadilhas comuns

Centralização e escalonamento

  • A projeção aleatória não exige centralização da forma que a PCA exige.
  • Entretanto, escalonamento de atributos pode importar para tarefas baseadas em distância. Se alguns atributos dominarem por escala, as distâncias projetadas também refletirão essa dominância.
  • Para atributos heterogêneos, considere padronização ou normalização antes de projetar (veja Escalonamento de Atributos).

Entradas esparsas: use projeções esparsas

Se (X) é esparsa (matrizes CSR/CSC), prefira métodos de projeção aleatória esparsa para preservar eficiência:

  • Projeção Gaussiana densa pode destruir a esparsidade imediatamente.
  • Construções esparsas reduzem computação e memória drasticamente.

No scikit-learn, SparseRandomProjection costuma ser o padrão correto para matrizes esparsas do tipo texto.

Aleatoriedade e reprodutibilidade

  • Defina um random_state (semente) para experimentos reprodutíveis.
  • Diferentes amostragens aleatórias produzem embeddings ligeiramente diferentes; o desempenho deve ser semelhante se (k) for grande o suficiente, mas a variância pode importar quando (k) é pequeno.

E se você precisar de transformada inversa?

A projeção aleatória não foi projetada para inversão precisa. Em geral, você não consegue reconstruir bem os atributos originais a partir do espaço projetado (ao contrário da PCA, que oferece uma inversa aproximada significativa via componentes).

Quando a projeção aleatória funciona bem (e quando não)

Funciona bem quando

  • (d) é enorme e computação/memória são o gargalo
  • Seu pipeline depende de distâncias, produtos escalares ou estrutura de vizinhança
  • Os dados são esparsos e você pode explorar projeções esparsas
  • Você precisa de uma redução rápida, amigável para streaming e agnóstica aos dados

Pode ser uma escolha ruim quando

Resumo

A projeção aleatória é uma ferramenta simples, porém poderosa, para redução de dimensionalidade:

  • Ela mapeia vetores (d)-dimensionais para vetores (k)-dimensionais com um mapeamento linear aleatório.
  • Pelo lema de Johnson–Lindenstrauss, ela preserva aproximadamente distâncias Euclidianas par-a-par para um conjunto de (n) pontos quando (k = O(\log n / \varepsilon^2)).
  • Construções comuns incluem projeções Gaussiana, Rademacher e esparsa/Achlioptas, sendo os métodos esparsos particularmente valiosos para conjuntos de dados grandes e esparsos.
  • Na prática, ela é amplamente usada para reduzir custos de computação e memória em fluxos de trabalho de aprendizado de máquina com muitas operações de distância, ajudando a mitigar a maldição da dimensionalidade enquanto mantém grande parte da geometria necessária para tarefas a jusante.

Se você quer um embedding rápido, escalável e “bom o suficiente” para conjuntos de dados grandes — especialmente quando seu algoritmo a jusante se importa com distâncias — a projeção aleatória costuma ser uma das primeiras opções mais eficazes para testar.