Dicotomias em Nuvens de Pontos

Como Shattering Se Parece

Coloque n pontos em nosso plano. Escolha uma classe de hipótese (classificadores lineares = linhas retas). Conte quantas maneiras distintas nossa classe pode rotular esses n pontos (+/− em cada lado de uma linha). Chame essa contagem de Π_H(n).

Se Π_H(n) = 2ⁿ, nossa classe shatter aquele conjunto de pontos — ela pode produzir cada rótulo possível. Se Π_H(n) < 2ⁿ, alguns rótulos não podem ocorrer.

Três Pontos em Posição Geral

Classificadores lineares em ℝ² shatter qualquer 3 pontos não-colineares. 2³ = 8 rótulos; todos os 8 alcançáveis por alguma linha. Pegue quaisquer 3 pontos; para cada rótulo ±/±, desenhe uma linha que separe positivos de negativos.

Quatro Pontos Recusam Shatter

Coloque 4 pontos nos cantos de um quadrado. Tente rotular o par diagonal como positivo & o par anti-diagonal como negativo (rótulo XOR). Nenhuma linha reta os separa. Então Π_H(4) ≤ 14 < 16 = 2⁴.

Dimensão VC como Tamanho Máximo de Shatter

VC(linear ℝ²) = 3. Podemos shatter 3 pontos; não podemos shatter 4. VC conta capacidade máxima de dicotomia de nossa classe de hipótese.

Intuição Geométrica

VC mais alta = nossa classe desenha limites de decisão mais elaborados. Linear (VC = d+1 em d dimensões) desenha hiperplanos. Polinômios desenham curvas. Redes neurais desenham manifolds altamente dobradas. Mais dobrabilidade = mais dicotomias = VC mais alta = requisito de amostra mais alto.

Contando Dicotomias

Considere classificadores lineares em ℝ² (linhas). Temos 5 pontos colocados em posição geral (nenhum 3 colineares, nenhum redundante).

Massa de Probabilidade em Manifold de Hipótese

Visualizando PAC-Bayes

Imagine nosso espaço de hipótese como um manifold de alta dimensão. Cada ponto neste manifold corresponde a uma configuração de peso de uma rede neural. Prior P atribui uma distribuição de probabilidade por todo nosso manifold (frequentemente Gaussiana centrada na inicialização). Posterior Q concentra massa de probabilidade onde dados de treinamento dirigiram nossos pesos.

Divergência KL como Distância Geométrica

KL(Q‖P) mede o quão longe Q se desviou de P. Leitura geométrica: quão distante nossa nuvem posterior se moveu de nuvem prior, ponderada por quanto improvável cada região posterior era sob nosso prior.

KL pequena = Q sobrepõe P muito. Posterior mal se moveu. Intervalo de generalização permanece pequeno.

KL grande = Q concentrada em regiões que P atribuiu pouca massa. Posterior se moveu muito. Intervalo de generalização cresce.

Por Que Essa Geometria Importa

Imagine SGD como uma trajetória de busca por nosso manifold de hipótese. Trajetória termina em uma bacia de perda de treinamento baixa. PAC-Bayes pergunta: quão larga é essa bacia?

Bacia larga = muitas configurações de peso vizinhas também alcançam perda de treinamento baixa. Posterior Q pode se espalhar por uma região larga & ainda ter risco baixo. KL(Q‖P) permanece limitada. Intervalo de generalização pequeno.

Bacia estreita = apenas um fino conjunto de pesos alcança perda baixa. Posterior deve se concentrar agudamente. KL cresce. Intervalo de generalização se alarga.

Isso conecta diretamente ao discurso de mínima-plana-vs-afiada (Hochreiter & Schmidhuber 1997, Keskar et al 2017). Mínimas planas generalizam melhor porque suportam posteriores mais largos com KL menor.

Lendo uma Largura de Bacia

Dois modelos treinados alcançam perda de treinamento idêntica mas vivem em bacias diferentes:

- Modelo A: bacia plana, posterior se espalha por região com KL(Q_A‖P) = 50 nats.

- Modelo B: bacia afiada, posterior se concentra com KL(Q_B‖P) = 500 nats.

Ambos treinados em n = 10.000 exemplos com risco empírico 0,05, δ = 0,05.

Uma Curva Que Desce Onde a Teoria Previa Subida

Curva U Clássica

Plote capacidade do modelo no eixo horizontal. Plote risco de teste no eixo vertical. Teoria clássica de viés-variância prevê:

- Capacidade baixa: viés alto, risco de teste alto (underfit)

- Capacidade média: viés baixo + variância baixa, risco de teste baixo (ponto doce)

- Capacidade alta: viés baixo, variância alta, risco de teste alto (overfit)

Resultado: curva em forma de U. Escolha capacidade em nosso fundo.

O Que Belkin et al (2019) Observaram

Passado do limiar de interpolação (capacidade onde modelo ajusta exatamente dados de treinamento com erro zero), risco de teste CAIA novamente. Curva lê: descida → pico em interpolação → segunda descida. Duas descidas, uma curva.

Leitura Geométrica da Segunda Descida

No limiar de interpolação, modelo tem apenas capacidade suficiente para ajustar dados de treinamento — apenas uma (ou poucas) soluções interpolantes existem & tendem a ser irregulares. Generalização sofre porque solução escolhida é forçada.

Passado do limiar de interpolação, MUITAS soluções interpolantes existem. SGD tem liberdade para escolher uma lisa (norma mínima, curvatura baixa). Imagem geométrica: manifold de solução se torna mais larga & plana. Viés implícito de SGD escolhe soluções benignas deste manifold plano. Risco de teste cai.

Por Que Teoria Clássica Perde Isso

Dimensão VC conta capacidade de conjunto de solução mas ignora qual solução fica escolhida. Limite clássico assume minimizador de risco empírico pior-caso. Realidade: SGD escolhe confiávelmente a solução interpolante mais plana & mais lisa. Uma vez que contamos soluções ESCOLHIDAS-POR-SOLVER em vez de todas as soluções, segunda descida faz sentido.

Conclusão Geométrica

Capacidade importa menos que geometria de bacia. Bacias largas & planas (pós-interpolação) generalizam melhor que estreitas & afiadas (em interpolação). Teoria moderna tenta limitar generalização por largura de bacia, não por contagem de parâmetro.

Localizando as Duas Descidas

Em uma curva de double descent, três regiões importam: (1) regime sub-parametrizado, (2) pico de interpolação, (3) regime sobre-parametrizado.

Superfície de Lei de Potência no Espaço Parâmetro-Token

Uma Superfície 3D

Plote parâmetros N em um eixo horizontal. Plote tokens D em um segundo eixo horizontal. Plote perda L na vertical. Perda empírica esculpe uma superfície de lei de potência por este plano (N, D):

L(N, D) ≈ (Nc/N)^αN + (Dc/D)^αD + L∞

Superfície se inclina para baixo conforme N ou D cresce. Inclinações seguem leis de potência log-lineares (linhas retas em gráfico log-log). Assíntota L∞ permanece positiva — perda irredutível nosso modelo não pode diminuir.

Crista de Computação Ótima

Fixe orçamento de computação total C ∝ N × D (parâmetros × tokens, aproximadamente). Corte nossa superfície ao longo desta restrição. Corte de traço corta uma curva 2D por superfície 3D. Fundo desta curva = ponto de computação-ótima.

Chinchilla (Hoffmann et al 2022) computou este fundo analiticamente: D_opt ≈ 20 × N. Curva ao longo orçamento de computação = uma crista. Caminhando ao longo crista: computação igual, perda decrescente. Caminhando fora da crista (mais parâmetros que 20× tokens, ou menos): computação desperdiçada.

Leitura Geométrica de GPT-3 vs Chinchilla

GPT-3: 175B params, 300B tokens. Chinchilla-ótima quereria 175B × 20 = 3500B tokens. GPT-3 senta longe da crista de computação-ótima em nossa direção carregada-de-parâmetro. Chinchilla ela mesma: 70B params treinada em 1400B tokens. 1400 / 70 = 20 — exatamente na crista. Chinchilla venceu GPT-3 com menos de metade sua contagem de parâmetro ao sentar em ótimo geométrico.

Parede de Dados como Plano Vertical

Web pública ~10¹³ tokens utilizáveis. Isso plota como parede vertical em D = 10¹³ no plano parâmetro-token. Além desta parede, treinamento de computação-ótima requer N ≤ D / 20 = 5 × 10¹¹ params. Paredes além N = 5 × 10¹¹ seja executam sub-treinadas (fora-crista) ou requerem dado sintético / multimodal / RL para empurrar parede para fora.

Caminhando a Crista de Computação-Ótima

Nós sentamos em coordenadas GPT-3: N = 175B params, D = 300B tokens. Proxy de computação C = N × D = 5,25 × 10²² param-tokens.

Posterior Beta se Apertando em uma Agulha

Uma Densidade de Probabilidade em [0, 1]

Beta(α, β) é uma densidade de probabilidade sobre o intervalo unitário [0, 1]. Variável: ε = taxa de erro verdadeira. Forma: α controla massa no lado ε-alto; β controla massa no lado ε-baixo.

Beta(1, 1): uniforme — nenhuma informação, densidade plana por [0, 1].

Beta(α, β) com α + β grande: pico concentrado em α / (α + β).

Largura de pico Beta encolhe como 1/√(α+β). Adicionando 100 observações a nosso prior aperta o pico pelo fator √100 = 10. Adicionando 10000 observações aperta por √10000 = 100.

Leitura Geométrica de uma Rodada de Auditoria

Começar: Beta(1, 1) = retângulo plano em [0, 1]. Incerteza máxima sobre ε.

Após 200 consultas com 8 falsificações: Beta(9, 193). Média = 9/202 ≈ 0,045. Densidade agora um pico aguçado centrado perto de 0,045 com largura característica σ ≈ 0,014.

Após 2000 consultas com 80 falsificações: Beta(81, 1921). Média ainda ≈ 0,045, mas largura σ ≈ 0,0046. Pico três vezes mais aguçado.

Após 200.000 consultas com 8000 falsificações: Beta(8001, 192.001). Média ≈ 0,040, largura σ ≈ 0,0004. Pico vira uma agulha.

Convergência Geométrica a uma Massa Pontual

Conforme n → ∞, posterior Beta colapsa para um delta de Dirac em ε verdadeira. Geometria: retângulo → pico largo → pico estreito → agulha → ponto. Cada consulta aperta nossa distribuição por 1/√n.

Por Que Isso Bate Limites PAC Teóricos

Limites PAC teóricos dão estimativa ε ESTÁTICA baseada em tamanho de classe de hipótese. Posterior Beta dá estimativa ε DINÂMICA que aperta com cada observação, calibrada contra sua distribuição do mundo real. Limite teórico = uma garantia sob suposições pior-caso. Auditoria empírica = uma medição de realidade atual.

Quantas Consultas para Dividir o Intervalo Credível pela Metade?

Nós atualmente sentamos em Beta(9, 193) após 200 consultas: média ε ≈ 0,045, σ ≈ 0,014. Queremos dividir a largura de intervalo credível pela metade para σ ≈ 0,007.