Lema de Johnson–Lindenstrauss

Visão geral

O lema de Johnson–Lindenstrauss (Johnson–Lindenstrauss (JL) lemma) é um resultado fundamental em análise funcional geométrica (geometric functional analysis), com impacto desproporcional no aprendizado de máquina (machine learning) moderno. Ele afirma que um conjunto finito de pontos em um espaço euclidiano (Euclidean space) de alta dimensão pode ser mapeado para um espaço euclidiano de dimensão muito menor usando uma projeção linear aleatória (random linear projection), ao mesmo tempo em que preserva aproximadamente todas as distâncias par-a-par (pairwise distances).

De forma concreta: dados (n) pontos em (\mathbb{R}^d) e um parâmetro de precisão (\varepsilon \in (0, 1)), existe (e uma construção aleatória encontrará com alta probabilidade) uma aplicação linear (linear map) (f:\mathbb{R}^d \to \mathbb{R}^k) com

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

tal que, para todo par de pontos (x_i, x_j),

Isso é notável porque (k) depende logaritmicamente do número de pontos (n), e não da dimensão original (d). Em muitos cenários de aprendizado de máquina, em que (d) pode chegar a dezenas de milhares (texto) ou milhões (atributos one-hot esparsos (sparse one-hot features)), o lema de Johnson–Lindenstrauss fornece uma forma fundamentada de reduzir a dimensionalidade mantendo a estrutura baseada em distâncias.

O lema de Johnson–Lindenstrauss também aborda diretamente alguns pontos de dor descritos pela Maldição da Dimensionalidade (Curse of Dimensionality): mesmo que espaços de alta dimensão se comportem de maneira contraintuitiva, projeções aleatórias podem preservar a geometria de um conjunto de dados finito de modo suficiente para que muitos algoritmos funcionem de forma eficaz em dimensões menores.

O lema (enunciado típico)

Uma versão comum, de alta probabilidade, é:

Lema de Johnson–Lindenstrauss (forma probabilística).
Sejam (0 < \varepsilon < 1) e (0 < \delta < 1). Seja (X = {x_1,\dots,x_n} \subset \mathbb{R}^d).
Escolha uma matriz aleatória (R \in \mathbb{R}^{k \times d}) com entradas i.i.d. (independent and identically distributed) (R_{ij} \sim \mathcal{N}(0, 1/k)) (ou outras distribuições subgaussianas (subgaussian distributions)) e defina (f(x)=Rx).
Se [ k ;\ge; C,\frac{\log(n/\delta)}{\varepsilon^2} ] para uma constante universal (C), então, com probabilidade de pelo menos (1-\delta), [ (1-\varepsilon)|x_i-x_j|_2^2 \le |f(x_i)-f(x_j)|_2^2 \le (1+\varepsilon)|x_i-x_j|_2^2 ] vale para todos os pares (i,j).

Algumas observações:

O lema frequentemente é enunciado para distâncias ao quadrado; tirar a raiz quadrada produz um limite comparável ((1\pm O(\varepsilon))) para as distâncias.
O mapeamento é linear e independente dos dados (data-independent): você não precisa “ajustar (fit)” a projeção ao conjunto de dados (ao contrário da análise de componentes principais).
A dependência em (\log n) surge porque precisamos preservar distâncias apenas entre um conjunto finito de pontos, e não em todo (\mathbb{R}^d).

Por que funciona: intuição

O lema de Johnson–Lindenstrauss é um fenômeno de “concentração de medida (concentration of measure)”. A intuição-chave é:

Uma projeção aleatória se comporta como tomar direções aleatórias no espaço.
Em alta dimensão, direções aleatórias ficam muito “bem espalhadas”.
Quando você projeta um vetor fixo (v) em (k) direções aleatórias e faz a escala apropriada, a norma ao quadrado resultante se concentra fortemente em torno de (|v|_2^2).

Se (v\in\mathbb{R}^d) é fixo e (R) é uma matriz de projeção aleatória com a escala apropriada, então (|Rv|_2^2) é uma soma de (k) contribuições aleatórias quase independentes. Por desigualdades de concentração (concentration inequalities) (por exemplo, limites de cauda (tail bounds) para variáveis aleatórias subgaussianas ou qui-quadrado (chi-square)), essa soma fica fortemente concentrada em torno de sua esperança.

Em seguida, estendemos de “um vetor é preservado” para “todas as diferenças par-a-par são preservadas”:

Existem (\binom{n}{2}) vetores de diferença (x_i-x_j).
Use um limite da união (union bound): se cada um for preservado com probabilidade suficientemente alta, então todos serão preservados simultaneamente com alta probabilidade.
Por isso (k) precisa escalar como (\log n): você paga pelo número de pares via (\log(\text{#pares}) \approx 2\log n).

Esse padrão de “aleatoriedade + concentração + limite da união” aparece repetidamente na teoria do aprendizado (learning theory), inclusive em tópicos como Aprendizado PAC (PAC Learning) e controle de capacidade (capacity control) (por exemplo, Dimensão VC (VC Dimension), Complexidade de Rademacher (Rademacher Complexity)).

Esboço de prova (sem teoria de medida pesada)

Um roteiro padrão de prova (para projeções gaussianas (Gaussian projections)) é:

1) Reduzir ao caso de preservar a norma de um único vetor

Para quaisquer dois pontos (x,y), defina (v = x-y). Então

[ |f(x)-f(y)|_2^2 = |R(x-y)|_2^2 = |Rv|_2^2. ]

Assim, basta mostrar que, para um (v) fixo,

[ |Rv|_2^2 \approx |v|_2^2. ]

2) Analisar \(\|Rv\|_2^2\)

Seja cada linha (r_\ell^\top) de (R) distribuída como (\mathcal{N}(0, I_d/k)). Então (r_\ell^\top v) é uma gaussiana unidimensional (1D Gaussian):

[ r_\ell^\top v \sim \mathcal{N}\left(0, \frac{|v|_2^2}{k}\right). ]

Portanto,

[ |Rv|2^2 = \sum{\ell=1}^k (r_\ell^\top v)^2 = \frac{|v|2^2}{k}\sum{\ell=1}^k Z_\ell^2, ]

onde (Z_\ell \sim \mathcal{N}(0,1)). A soma (\sum Z_\ell^2) tem distribuição (\chi^2_k), que se concentra em torno de (k). Limites de cauda para (\chi^2_k) implicam:

[ \Pr\left[\left||Rv|_2^2 - |v|_2^2\right| \ge \varepsilon|v|_2^2\right] \le 2\exp(-c,\varepsilon^2 k) ]

para alguma constante (c>0).

3) Aplicar limite da união sobre todos os pares

Existem no máximo (n^2) pares. Escolha (k) de modo que:

[ 2\exp(-c,\varepsilon^2 k) \le \frac{\delta}{n^2}. ]

Resolvendo, obtemos:

[ k \ge C\frac{\log(n/\delta)}{\varepsilon^2}. ]

Esse é o limite de dimensão do lema de Johnson–Lindenstrauss.

Que tipos de projeções aleatórias funcionam?

Matrizes gaussianas (Gaussian matrices) são as mais limpas do ponto de vista teórico, mas nem sempre são as mais rápidas na prática. Muitas alternativas ainda satisfazem garantias do tipo Johnson–Lindenstrauss, desde que tenham caudas subgaussianas (subgaussian tails) e a escala correta.

Escolhas comuns:

JL Gaussiano (denso)
- (R_{ij} \sim \mathcal{N}(0, 1/k))
- Teoria forte, fácil de implementar, mas a multiplicação por matriz densa pode ser cara.
JL de Rademacher / Achlioptas (Rademacher / Achlioptas JL)
- (R_{ij} \in {\pm 1/\sqrt{k}}) uniformemente (ou um esquema esparso ({-1,0,+1}))
- Mais rápido e econômico em memória; frequentemente funciona muito bem na prática.
JL Esparso / transformações no estilo CountSketch (CountSketch-style transforms)
- Cada dimensão original contribui para apenas algumas dimensões projetadas (matriz (R) muito esparsa).
- Útil para entradas esparsas de dimensão extremamente alta (por exemplo, saco de palavras (bag-of-words), one-hot).
Transformação Rápida de Johnson–Lindenstrauss (Fast Johnson–Lindenstrauss Transform, FJLT)
- Combina transformadas aleatorizadas de Hadamard/Fourier com subamostragem (subsampling).
- Reduz o tempo de multiplicação de (O(dk)) para aproximadamente (O(d\log d + k ,\text{polylog}(d))) em certos regimes.

Redução prática de dimensionalidade via Johnson–Lindenstrauss

Quando você deve usar Johnson–Lindenstrauss?

O lema de Johnson–Lindenstrauss é mais apropriado quando:

Seu algoritmo subsequente (downstream) depende de distâncias euclidianas (ou produtos internos/ângulos).
Você tem muitos pontos (n) e uma dimensão de atributos (d) muito alta.
Você quer uma projeção rápida, simples e independente dos dados.
Você não precisa de interpretabilidade dos novos atributos.

Tarefas subsequentes típicas:

busca de vizinho mais próximo (nearest neighbor search) / recuperação (retrieval)
agrupamento (clustering) (por exemplo, (k)-médias (k-means))
detecção de anomalias baseada em distância
acelerar modelos lineares e algumas aproximações de kernel
pré-processamento para pipelines de aprendizado em larga escala

Como escolher a dimensão-alvo \(k\)

Uma regra prática do lema de Johnson–Lindenstrauss é:

[ k \approx \Theta!\left(\frac{\log n}{\varepsilon^2}\right). ]

Interpretação:

Quer distorção mais apertada (menor (\varepsilon))? (k) cresce como (1/\varepsilon^2).
Mais pontos para preservar a geometria? (k) cresce lentamente como (\log n).

Exemplo: se (n = 10^6), então (\log n \approx 13.8) (logaritmo natural).
Se você quer (\varepsilon = 0.2), então (\log n / \varepsilon^2 \approx 13.8 / 0.04 \approx 345).
Assim, (k) na casa de algumas centenas frequentemente consegue preservar distâncias par-a-par de maneira razoável para um milhão de pontos — independentemente da dimensão original (d).

Na prática, costuma-se ajustar (k) com base em métricas de validação da tarefa subsequente, usando o lema de Johnson–Lindenstrauss como ponto de partida fundamentado.

Exemplo: projeção aleatória em Python (NumPy)

Abaixo está uma projeção JL gaussiana simples para uma matriz de dados (X\in\mathbb{R}^{n\times d}):

import numpy as np

def jl_project(X, k, seed=0):
    """
    X: (n, d) data matrix
    k: target dimension
    returns: (n, k) projected matrix
    """
    rng = np.random.default_rng(seed)
    n, d = X.shape
    R = rng.normal(loc=0.0, scale=1.0/np.sqrt(k), size=(d, k))  # note shape (d, k)
    return X @ R

# Example usage
n, d = 10000, 20000
X = np.random.randn(n, d)
Z = jl_project(X, k=500)
print(X.shape, Z.shape)

Notas:

A escala (1/\sqrt{k}) é essencial para que as normas sejam preservadas em esperança.
Para (X) esparso, use transformações compatíveis com esparsidade (JL esparso / truque de hashing (hashing trick)) para evitar multiplicação densa.

Exemplo: acelerando agrupamento com k-médias

Muitos algoritmos de agrupamento (como k-médias) calculam distâncias repetidamente. Se (d) é enorme, os cálculos de distância dominam o tempo de execução.

Pipeline (pipeline):

Comece com dados de alta dimensão (X \in \mathbb{R}^{n\times d}).
Aplique a projeção JL para obter (Z \in \mathbb{R}^{n\times k}) com (k \ll d).
Execute k-médias em (Z) em vez de (X).

Como o lema de Johnson–Lindenstrauss preserva aproximadamente as distâncias par-a-par, a estrutura de clusters que depende da geometria euclidiana muitas vezes é preservada o suficiente para produzir um agrupamento semelhante, com custo muito menor.

Essa é uma forma concreta de o lema de Johnson–Lindenstrauss mitigar a Maldição da Dimensionalidade: ele não “resolve” o aprendizado em alta dimensão em geral, mas pode preservar a geometria relevante para seu conjunto de dados finito enquanto torna os cálculos viáveis.

Exemplo: busca de vizinho mais próximo e recuperação

Métodos de vizinho mais próximo degradam em alta dimensão por razões estatísticas e computacionais. O lema de Johnson–Lindenstrauss ajuda em:

Computação: cálculos de distância são mais baratos em menor dimensão.
Fidelidade geométrica: se as distâncias são preservadas até ((1\pm\varepsilon)), então vizinhos mais próximos aproximados continuam aproximadamente mais próximos.

Um padrão típico em sistemas de recuperação:

Incorporar itens/usuários em um espaço vetorial de alta dimensão (a partir de um modelo).
Aplicar uma projeção Johnson–Lindenstrauss para reduzir a dimensão.
Construir um índice de vizinhos mais próximos aproximados (approximate nearest neighbor, ANN) (por exemplo, HNSW, IVF) sobre os vetores reduzidos.

Mesmo que seu índice já seja aproximado, o lema de Johnson–Lindenstrauss pode reduzir memória e acelerar consultas, muitas vezes com pouca perda na qualidade do ranqueamento.

Conexões com produtos internos, ângulos e kernels

O lema de Johnson–Lindenstrauss implica preservação aproximada de produtos internos (inner products) para dados centrados (ou usando identidades de polarização (polarization identities)). Se distâncias são preservadas, então:

ângulos entre vetores são aproximadamente preservados,
similaridade cosseno (cosine similarity) frequentemente é aproximadamente preservada (após normalização).

Isso importa porque muitos pipelines de aprendizado de máquina usam similaridade cosseno ou produtos escalares (dot products).

O lema de Johnson–Lindenstrauss também se relaciona a mapas de características aleatorizados (randomized feature maps) usados em aproximação de kernel, embora isso normalmente seja discutido sob características aleatórias (random features) em vez de Johnson–Lindenstrauss diretamente. Conceitualmente, ambos dependem de aleatorização + concentração para preservar certas quantidades geométricas após o mapeamento para um novo espaço.

Por que Johnson–Lindenstrauss é fundamental para aprendizado de máquina e teoria do aprendizado

Redução de dimensionalidade sem aprendizado

Ao contrário da análise de componentes principais, o lema de Johnson–Lindenstrauss não depende da distribuição dos dados além do conjunto finito de pontos que você deseja preservar. Isso tem várias implicações:

É robusto e simples de implantar.
Funciona em cenários de fluxo contínuo (streaming) ou online (online): você pode projetar novos pontos à medida que eles chegam.
Evita sobreajustar a etapa de projeção (a projeção não é otimizada com base em rótulos).

Mitigando patologias de alta dimensão (para conjuntos de dados finitos)

A Maldição da Dimensionalidade destaca problemas como concentração de distâncias e esparsidade dos dados. O lema de Johnson–Lindenstrauss oferece um contraponto:

Para um conjunto finito de (n) pontos, você muitas vezes pode trabalhar em (k = O(\log n)) dimensões preservando distâncias.
O comportamento de muitos algoritmos depende principalmente da geometria par-a-par, não da dimensão ambiente (d).

Isso não é uma contradição: a maldição frequentemente diz respeito ao comportamento de pior caso conforme (d) cresce e os dados permanecem esparsos, ou à necessidade de um número exponencial de amostras para cobrir o espaço. O lema de Johnson–Lindenstrauss diz: dados os pontos que você já tem, você pode re-embuti-los em um espaço de menor dimensão com pequena distorção.

Apoio à estabilidade e generalização (indiretamente)

O lema de Johnson–Lindenstrauss não é, por si só, um teorema de generalização, mas apoia o aprendizado prático ao:

reduzir o número de atributos, o que pode reduzir a variância e melhorar o condicionamento,
acelerar o treinamento (mais iterações ou conjuntos de dados maiores tornam-se viáveis),
permitir que regularidades baseadas em distância permaneçam significativas.

Esses temas se conectam a ideias mais amplas como Sobreajuste e Regularização (Overfitting & Regularization) e Estabilidade Algorítmica (Algorithmic Stability): tornar algoritmos menos sensíveis a ruído e a peculiaridades de alta dimensão pode melhorar a confiabilidade.

Equívocos comuns e limitações

“O lema de Johnson–Lindenstrauss sempre preserva todas as distâncias em todo o espaço.”
Não — o lema de Johnson–Lindenstrauss garante preservação para um conjunto finito de (n) pontos (ou um número finito de vetores). Preservar distâncias em todo (\mathbb{R}^d) exigiria (k \ge d).
“O lema de Johnson–Lindenstrauss é o mesmo que análise de componentes principais.”
A análise de componentes principais é uma projeção determinística e dependente dos dados que minimiza o erro de reconstrução (em um sentido (\ell_2)). O lema de Johnson–Lindenstrauss é aleatorizado e independente dos dados, com garantias sobre distâncias par-a-par para um conjunto finito.
“Funciona para qualquer métrica.”
O lema de Johnson–Lindenstrauss é fundamentalmente sobre geometria euclidiana ((\ell_2)). Existem outros resultados de incorporação (embedding) para outras métricas, mas eles diferem nas garantias e nas dimensões-alvo.
“Se (k = O(\log n)), sempre podemos ir para dimensões extremamente baixas.”
Constantes importam. Além disso, se você precisa de distorção muito pequena ((\varepsilon) minúsculo), (k) ainda pode ser grande devido ao fator (1/\varepsilon^2).
“A projeção aleatória preservará a separabilidade entre classes.”
Às vezes sim, às vezes não. Se a separabilidade depende de margens euclidianas, o lema de Johnson–Lindenstrauss pode preservar margens aproximadamente, mas o desempenho de classificação ainda depende da distribuição dos dados e do modelo.

Dicas práticas

Normalize quando apropriado: se você se importa com similaridade cosseno, normalize vetores antes/depois da projeção (e valide).
Use transformações esparsas para dados esparsos: para saco de palavras ou atributos one-hot, JL esparso ou projeções baseadas em hashing são muito mais rápidas do que matrizes gaussianas densas.
Trate (k) como um hiperparâmetro (hyperparameter): comece com (k \sim \frac{\log n}{\varepsilon^2}), depois ajuste com base nas métricas da tarefa (revocação de recuperação, objetivo de agrupamento, acurácia do classificador).
Valide a distorção empiricamente: amostre pares aleatórios ((i,j)) e compare (|x_i-x_j|) com (|f(x_i)-f(x_j)|) para estimar a distorção prática.

Resumo

O lema de Johnson–Lindenstrauss explica por que projeções lineares aleatórias podem reduzir a dimensionalidade de forma dramática enquanto preservam a geometria de um conjunto de dados finito:

(n) pontos em (\mathbb{R}^d) podem ser incorporados em (k = O(\log n/\varepsilon^2)) dimensões.
Distâncias euclidianas par-a-par são preservadas dentro de um fator ((1\pm\varepsilon)) (com alta probabilidade).
O mecanismo é aleatoriedade + concentração de medida, estendido a todos os pares via um limite da união.
O lema de Johnson–Lindenstrauss sustenta técnicas práticas de redução de dimensionalidade, acelera algoritmos baseados em distância e oferece uma rota fundamentada de mitigação para aspectos da Maldição da Dimensionalidade.

Em sistemas modernos de aprendizado de máquina, projeções aleatórias no estilo Johnson–Lindenstrauss continuam sendo uma poderosa “ferramenta padrão”: simples, escalável, embasada teoricamente e, muitas vezes, surpreendentemente eficaz.