The Curse of Dimensionality

A Maldição da Dimensionalidade

Acrescente uma coluna a uma tabela e você acrescentou informação — é essa a intuição e ela está errada com frequência suficiente para merecer uma página só dela.

Em dimensão alta, a geometria deixa de se comportar como a intuição de duas e três dimensões espera. O volume foge para a superfície de uma bola, a bola inscrita praticamente some dentro do cubo dela, direções aleatórias ficam quase perpendiculares e — a que de fato quebra o aprendizado de máquina — as distâncias par a par se concentram, de modo que "vizinho mais próximo" pouco a pouco deixa de significar algo.

Onde você encontra isso na prática

Antes da geometria, os lugares onde ela aparece — porque o fenômeno é abstrato e as consequências não são.

A razão pela qual o kNN ainda funciona razoavelmente no MNIST com 784 colunas é a mesma ideia pelo outro lado: a dimensão intrínseca dos dígitos manuscritos está estimada em torno de 12 a 15, não 784. Quem manda não é a contagem ambiente.

A0 · Ancoragem em 3D

Tudo o que vem abaixo só acontece em dimensão alta, onde não há como desenhar. Este painel faz o oposto: mostra em 3D — onde a intuição ainda funciona — o começo de cada efeito e coloca ao lado o número analítico para o \(d\) que você escolher. Gire a figura e acompanhe a distância entre os dois crescer.

Como ler o painel

O painel tem três cenas e o slider significa uma coisa diferente em cada uma:

• Em cubo e casca, a figura é sempre a de 3D — não tem como ser outra. O slider escolhe uma dimensão de referência \(d\) e só os cartões numéricos mudam: os da esquerda são o que a amostra em 3D mede, os da direita são a fórmula fechada avaliada no seu \(d\). A lição é a distância entre as duas colunas.
• Em 3 grupos afogados por ruído, o slider escolhe quantas colunas de ruído \(m\) são acrescentadas (0, 3, 10, 30, 100 ou 250) e a própria figura muda, porque o que se vê é a projeção de uma nuvem genuinamente de alta dimensão.
• Arraste para girar; desmarque girar para parar a rotação. Um cartão fica vermelho quando o efeito já tomou conta — uma esfera abaixo de 0,1% do cubo ou grupos cuja razão caiu abaixo de 1,5.

Cena 1 · O cubo, a esfera inscrita e os cantos

O que está desenhado. As arestas do cubo \([-1,1]^3\), a esfera de raio 1 dentro dele (três círculos máximos, em laranja) e 1 100 pontos sorteados uniformemente no cubo: azuis se caem dentro da esfera, vermelhos se caem fora dela — nos cantos.

O que observar. A amostra mede cerca de 53% dentro; a fórmula dá \(\pi/6 = 52{,}4\%\). Com 1 100 pontos o erro-padrão é de cerca de 1,5 ponto percentual, então os dois concordam. Mesmo em 3D, metade do cubo já é canto.

Por que a esfera se esvazia. A fração do cubo ocupada pela esfera inscrita é

mas um argumento de uma linha explica melhor do que a fórmula. Para um ponto uniforme no cubo, cada coordenada \(x_j\) é uniforme em \([-1,1]\) e \(\mathbb E[x_j^2] = 1/3\). Logo

O ponto só está dentro da esfera se \(\lVert x\rVert^2 \le 1\). Em \(d = 3\) a norma ao quadrado típica vale exatamente 1 — por isso cerca de metade dos pontos cai dentro. Daí em diante o ponto típico fica numa norma ao quadrado de \(d/3 > 1\) e estar dentro da esfera exige que todas as coordenadas sejam pequenas ao mesmo tempo, o que fica exponencialmente improvável. Os cantos estão a \(\sqrt d\) do centro, enquanto a esfera nunca passa do raio 1.

Experimente. Leve o slider a 10 e depois a 20 com o cubo girando. A figura não consegue acompanhar; os cartões conseguem.

Cena 2 · A casca: onde ficam os pontos

O que está desenhado. 900 pontos uniformes dentro da esfera, a esfera externa (círculos cinza) e uma esfera interna a 80% do raio (laranja tracejado). Os pontos nos 20% externos do raio — a casca — são laranja; os do interior são azuis.

Como os pontos são sorteados. Uma direção uniforme (um vetor gaussiano normalizado) vezes um raio \(U^{1/3}\), com \(U\) uniforme em \([0,1]\). A raiz cúbica é o que torna os pontos uniformes em volume: o volume dentro do raio \(r\) cresce como \(r^3\), então precisa haver menos pontos perto do centro do que perto da superfície. Sortear o raio uniformemente amontoaria os pontos no centro.

Por que a casca ganha. O volume escala como \(r^d\), então a esfera interna de raio \(1-\varepsilon\) guarda uma fração \((1-\varepsilon)^d\) do volume e a casca guarda o resto:

A amostra mede cerca de 47% contra 48,8% — de novo dentro do erro de amostragem.

Cena 3 · Três grupos afogados por ruído

O que está desenhado. 270 pontos em três grupos (90 cada). Os grupos vivem nas três primeiras colunas, com centros a 2,8–2,9 de distância entre si e dispersão de 0,55 em torno de cada um. Depois são acrescentadas \(m\) colunas de puro ruído \(\mathcal N(0,1)\). O painel calcula as três primeiras componentes principais da tabela inteira (com \(3+m\) colunas) e desenha os pontos nelas.

O número do cartão é a razão entre e dentro na vista: a distância média entre os centroides dos grupos dividida pela distância média de cada ponto ao seu próprio centroide. Grosso modo: acima de 2 os grupos estão claramente separados; abaixo de 1 eles se sobrepõem.

O que de fato acontece, medido nesta mesma cena:

A terceira coluna da tabela é o ponto central: os grupos nunca se mexeram. Medida nas três colunas que os definem, a separação fica em torno de 3,3 para qualquer \(m\). O que colapsa é a vista, em três etapas:

1. Em \(m = 3\) o terceiro eixo se perde de imediato. As três colunas de sinal não têm a mesma variância: duas têm cerca de 1,6, mas a terceira tem só 0,48 — menos que a variância 1 de cada coluna de ruído. A PCA ordena direções por variância, então a terceira componente principal vira na hora uma direção de ruído (sua parcela nas colunas verdadeiras cai para 2%) e a razão cai de 3,5 para 2,4.
2. Até \(m \approx 30\) os dois primeiros eixos resistem. A variância de 1,6 ainda supera a do ruído, então CP1 e CP2 continuam sendo majoritariamente sinal e os três grupos seguem visíveis no plano que elas geram. Essa resistência é exatamente o motivo de rodar PCA antes do t-SNE funcionar: a PCA guarda as direções de sinal de alta variância e descarta a maior parte do ruído.
3. Perto de \(m \approx 100\) a resistência quebra. Com amostra finita, o ruído não parece ter variância 1 em toda direção: algumas direções aleatórias do ruído por acaso têm variância amostral maior. Quanto mais colunas de ruído houver, maior fica a maior delas. Com \(n\) pontos e \(m\) colunas de ruído, a maior variância espúria cresce até cerca de \((1+\sqrt{m/n})^2\) — 1,4 em \(m = 10\), 2,6 em \(m = 100\), 3,9 em \(m = 250\). Uma direção de sinal cuja variância excede a do ruído por \(\theta\) só é recuperada enquanto \(\theta > \sqrt{m/n}\). Aqui \(\theta \approx 0{,}6\) e \(n = 270\), então o limiar é \(m \approx 0{,}6^2 \times 270 \approx 97\) — exatamente onde a tabela mostra CP1 e CP2 virando ruído. Em \(m = 250\) elas são 97% ruído; os três grupos continuam perfeitamente separados nos dados e sumiram da figura.

A1 · O volume foge para a casca

Para pontos espalhados uniformemente pela bola unitária, quase todo o volume fica numa pele fina junto à superfície. A fração dentro dos \(\varepsilon\) externos do raio é \(1 - (1-\varepsilon)^d\) e o raio mediano é \((1/2)^{1/d}\) — em \(d = 100\) isso vale \(0{,}993\).

A consequência pouco intuitiva é que o centro fica vazio. Em \(d = 50\) essencialmente nenhum ponto está abaixo de 90% do raio, então a noção de "ponto típico próximo do centroide" — que sustenta boa parte da intuição de baixa dimensão — simplesmente deixa de valer. Um centroide em dimensão alta não está perto de nada.

A2 · A bola some dentro do cubo

A bola inscrita no cubo \([-1,1]^d\) ocupa \(\pi^{d/2} / \big(\Gamma(d/2+1)\,2^d\big)\) dele: 78,5% do quadrado, 52,4% do cubo, 0,25% em \(d=10\) e \(2{,}5\times10^{-8}\) em \(d=20\). O cubo tem \(2^d\) cantos e é para lá que o volume vai.

Empurre o controle para além de \(d = 18\) e a estimativa de Monte Carlo reporta exatamente zero: vinte mil pontos uniformes no cubo e nenhum deles cai na bola inscrita.

Por que importa: se você normaliza dentro de um hipercubo — que é o que o MinMaxScaler faz — a região "central" que a intuição imagina como típica é estatisticamente inatingível. Todo ponto é um caso extremo em alguma coordenada. É a mesma geometria que torna inviável uma busca em grade sobre mais que um punhado de hiperparâmetros: uma grade amostra cantos e cantos é tudo o que existe.

A3 · As distâncias se concentram

A distância típica entre dois pontos cresce como \(\sqrt d\) enquanto a dispersão em torno dela não cresce, então o contraste relativo \((d_{\max}-d_{\min})/d_{\min}\) decai como \(O(1/\sqrt d)\).¹

É este o que de fato afeta aprendizado de máquina — kNN, k-means, kernels RBF e o próprio t-SNE e UMAP — e é o único dos quatro cuja validade depende da distribuição dos dados.

Compare os cinco geradores: três colapsam e dois não. Em \(d = 256\) o contraste relativo é 0,37 no uniforme, 0,43 no gaussiano e 0,44 nos grupos com ruído — o par mais distante está a menos de uma vez e meia o mais próximo. Com sinal em todas as colunas ele ainda vale 2,6; no disco 2D girado vale 392, exatamente onde estava em \(d = 2\).

A4 · Tudo fica ortogonal

O cosseno entre duas direções aleatórias tem média zero e desvio padrão \(1/\sqrt d\). Em \(d = 1000\), 99% dos pares têm \(\lvert\cos\theta\rvert < 0{,}082\).

Este tem um lado bom raramente mencionado. A quase ortogonalidade é exatamente o que faz o lema de Johnson–Lindenstrauss funcionar: uma projeção aleatória em \(O(\log n / \varepsilon^2)\) dimensões preserva toda distância par a par com erro relativo \(\varepsilon\), independentemente da dimensão original. É também o que permite a um embedding de largura modesta acomodar um número enorme de conceitos quase mutuamente ortogonais — a razão pela qual um embedding de 768 dimensões carrega muito mais que 768 coisas distinguíveis.

A5 · A consequência prática

O sinal está sempre nas duas primeiras colunas; colunas extras de três sabores são acrescentadas por cima e um 5-NN é de fato treinado e testado em cada caso. O painel roda os 27 ajustes no seu navegador quando você chega até ele.

Nesta amostra, 250 colunas de ruído levam a acurácia de 90% para 71%, 250 colunas fracamente informativas a levam a 100% e 250 cópias ruidosas do sinal a deixam em 90%. Aperte nova amostra algumas vezes: as pontas mudam um ou dois pontos, mas a ordem nunca muda.

O mesmo experimento em scikit-learn, com semente própria e uma montagem um pouco diferente:

"""The curse of dimensionality is not about dimensions. It is about what is in them.

The signal always lives in the first two columns, and a 5-nearest-neighbour
classifier reads it at about 0.906. Then extra columns are added, of three
kinds, and only the kind changes:

  noise        independent gaussian columns, carrying nothing
  informative  columns that each shift with the label
  redundant    noisy copies of the two columns that already carried the signal

Read the three columns against each other. "High dimension hurts kNN" is true
only of the first, and it is the sentence people remember without the
qualification — which is why kNN works acceptably on MNIST at 784 dimensions,
where the intrinsic dimension of the digits is estimated at around 12 to 15.

Printed as a markdown table, in identifiers only, so one artifact serves both
the English and the Portuguese page.
"""

import numpy as np
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

N, REPEATS, EXTRA = 500, 5, (0, 2, 8, 32, 128)


def build(extra, kind, seed):
    rng = np.random.default_rng(seed)
    signal = rng.normal(size=(N, 2))
    y = ((signal[:, 0] + signal[:, 1] + 0.3 * rng.normal(size=N)) > 0).astype(int)
    if extra == 0:
        return signal, y
    if kind == "noise":
        added = rng.normal(size=(N, extra))
    elif kind == "informative":
        added = rng.normal(size=(N, extra)) + 0.9 * (2 * y - 1)[:, None]
    else:                                        # noisy copies of what we already had
        added = np.tile(signal, (1, extra // 2 + 1))[:, :extra] + 0.5 * rng.normal(size=(N, extra))
    return np.hstack([signal, added]), y


def accuracy(extra, kind):
    scores = []
    for seed in range(REPEATS):
        X, y = build(extra, kind, seed)
        X_train, X_test, y_train, y_test = train_test_split(
            X, y, test_size=0.5, random_state=seed, stratify=y
        )
        scores.append(KNeighborsClassifier(5).fit(X_train, y_train).score(X_test, y_test))
    return float(np.mean(scores))


print("| `extra_dimensions` | `noise` | `informative` | `redundant` |")
print("|---:|---:|---:|---:|")
for extra in EXTRA:
    cells = " | ".join(f"**{accuracy(extra, k):.3f}**"
                       for k in ("noise", "informative", "redundant"))
    print(f"| {extra} | {cells} |")

• Colunas de ruído: 0,906 → 0,595. Cada uma acrescenta distância que é igual para todo par e as duas colunas que importam vão se afogando.
• Colunas informativas: 0,906 → 1,000. Mais dimensões tornaram o problema mais fácil.
• Colunas redundantes — cópias ruidosas do sinal, então a dimensão intrínseca continua 2: 0,906 → 0,885. Se mantém.

As três formas fechadas, conferidas

"""Three claims about high-dimensional geometry, each in closed form and each checked.

None of these depends on the data: they are facts about the shape of space, and
they hold for every dataset that lives in d dimensions. Each row reports the
analytic value and a Monte Carlo estimate beside it, so the formula can be
believed rather than taken on trust.

  shell        fraction of a unit ball's volume within the outer 10% of the radius,
               1 - 0.9^d, and the median radius (1/2)^(1/d)
  ball_in_cube volume of the inscribed ball over the volume of the cube,
               pi^(d/2) / (Gamma(d/2 + 1) * 2^d) — the cube has 2^d corners and
               that is where everything ends up
  cos_sd       standard deviation of the cosine between two random directions,
               1/sqrt(d): in high dimensions, everything is almost orthogonal

Printed as a markdown table, in identifiers only, so one artifact serves both
the English and the Portuguese page.
"""

import numpy as np
from scipy.special import gammaln

DIMS, SAMPLES = (2, 3, 5, 10, 20, 50, 100), 40_000

rng = np.random.default_rng(4)


def uniform_in_ball(d, n):
    """Direction from a gaussian, radius from U^(1/d) — uniform by volume."""
    direction = rng.normal(size=(n, d))
    direction /= np.linalg.norm(direction, axis=1, keepdims=True)
    return direction * rng.random((n, 1)) ** (1 / d)


print("| `d` | `shell_10pct` | `(mc)` | `median_radius` | `ball_in_cube` | `(mc)` | `cos_sd` | `(mc)` |")
print("|---:|---:|---:|---:|---:|---:|---:|---:|")
for d in DIMS:
    radii = np.linalg.norm(uniform_in_ball(d, SAMPLES), axis=1)
    shell, shell_mc = 1 - 0.9 ** d, float((radii > 0.9).mean())

    # log-volumes, or the ratio underflows well before d = 100
    log_ratio = d / 2 * np.log(np.pi) - gammaln(d / 2 + 1) - d * np.log(2)
    cube = rng.random((SAMPLES, d)) * 2 - 1                    # the cube [-1, 1]^d
    inside = float((np.linalg.norm(cube, axis=1) <= 1).mean())  # the inscribed ball

    a, b = rng.normal(size=(SAMPLES, d)), rng.normal(size=(SAMPLES, d))
    cos = np.einsum("ij,ij->i", a, b) / (np.linalg.norm(a, axis=1) * np.linalg.norm(b, axis=1))

    fmt = lambda v: f"{v:.2e}" if 0 < v < 1e-4 else f"{v:.4f}"
    print(f"| {d} | {shell:.4f} | {shell_mc:.4f} | {0.5 ** (1 / d):.4f} "
          f"| {fmt(np.exp(log_ratio))} | {fmt(inside)} "
          f"| {1 / np.sqrt(d):.4f} | {cos.std():.4f} |")

Cada coluna analítica bate com a vizinha de Monte Carlo. Em \(d = 20\) a razão bola/cubo é \(2{,}46\times10^{-8}\) e quarenta mil amostras não encontram nada — a estimativa não está errada, apenas está abaixo da resolução do experimento.

Resumo

A6 · Vídeo complementar

Uma exposição narrada do mesmo argumento. Vale assistir antes do laboratório: os painéis acima ficam mais fáceis de ler depois de ouvir a história contada uma vez.