Shattering e Dimensão VC

Quando os Espaços de Hipóteses se Tornam Infinitos

O limite m ≥ (1/ε)(ln|H| + ln(1/δ)) falha quando |H| = ∞. A maioria das classes de hipóteses úteis (classificadores lineares em ℝᵈ, árvores de decisão, redes neurais) contém infinitos candidatos. Vapnik & Chervonenkis resolveram isso por volta de 1971 com uma medida de complexidade mais rica: a dimensão VC.

Shattering

Uma classe de hipóteses H shatters um conjunto de n pontos se H consegue produzir todas as rotulações possíveis desses n pontos (todas as 2ⁿ dicotomias). Classificadores lineares em ℝ² shatter qualquer conjunto de 3 pontos em posição geral: para cada uma das 8 possíveis rotulações +/− desses 3 pontos, existe uma reta que os separa corretamente.

Mas classificadores lineares em ℝ² não podem shatter 4 pontos dispostos em configuração XOR. Nenhuma reta separa o par diagonal do par antidiagonal.

Dimensão VC

VC(H) = o maior n tal que H shatter algum conjunto de n pontos. Para classificadores lineares em 2D: VC = 3. Para retângulos alinhados aos eixos em 2D: VC = 4. Para redes neurais com W pesos: VC ≤ O(W² log W) (Bartlett & Anthony 1999).

Complexidade de Amostra com Dimensão VC

Substitua ln|H| no nosso limite PAC pela dimensão VC d:

m = O((d/ε) log(1/ε) + (1/ε) log(1/δ))

A dimensão VC atua como nossa "complexidade efetiva" de uma classe infinita. Uma classe de hipóteses com baixa dimensão VC generaliza a partir de poucas amostras; uma classe com alta dimensão VC exige mais dados.

Dimensão VC como Contagem Efetiva de Hipóteses

Uma rede neural tem W = 10⁹ pesos. Pelo limite de Bartlett-Anthony, VC ≤ O(W² log W). Aproxime VC ≈ W² log₂ W.

Descartando a Realizabilidade, Posteriores sobre Hipóteses

Duas Generalizações Importantes

O PAC clássico assume que nosso conceito-alvo c vive dentro da nossa classe de hipóteses H. Dados reais trazem ruído, rótulos incorretos e conceitos que nossa classe não consegue representar. Duas extensões lidam com isso.

PAC Agnóstico

Abandonamos a suposição de que c ∈ H. Agora competimos contra nossa hipótese melhor-da-classe h* = argmin_{h ∈ H} risk(h). A forma do limite muda: em vez de nos aproximarmos da perfeição, nos aproximamos do melhor possível dentro de H.

Limite agnóstico: P[risk(h) ≤ risk(h*) + ε] ≥ 1 − δ com complexidade de amostra m = O(1/ε² × (VC(H) + log(1/δ))). Observe ε² em vez de ε no denominador: o aprendizado agnóstico exige mais amostras para a mesma precisão.

PAC-Bayes (McAllester 1999)

Passamos de escolher uma única hipótese para escolher uma distribuição sobre hipóteses. Começamos com um prior P. Observamos os dados. Derivamos o posterior Q. Os limites PAC-Bayes aplicam-se ao risco esperado sob Q:

𝔼_{h~Q}[risk(h)] ≤ 𝔼_{h~Q}[empirical_risk(h)] + √[(KL(Q‖P) + ln(2√n/δ)) / 2n]

KL(Q‖P) mede o quanto nossa posteriori se afastou da nossa priori. Duas interpretações:

1. Visão de compressão. Uma posteriori próxima da sua priori (KL pequeno) generaliza bem — pequeno custo de informação = pequena lacuna de generalização.

2. Visão bayesiana. Priori forte + atualização fraca dos dados = limite apertado; priori fraca + atualização pesada dos dados = limite mais frouxo.

Por que PAC-Bayes importa. Limites PAC-Bayes empíricos (Catoni 2007, Dziugaite & Roy 2017) fornecem garantias de generalização numericamente significativas para redes neurais reais, onde os limites PAC clássicos se tornam vácuos. Eles permanecem nossa ferramenta teórica mais apertada para generalização em modelos superparametrizados.

Leitura de um Limite PAC-Bayes

Suponha que treinamos uma rede com n = 50.000 exemplos rotulados. Após o treinamento, nossa posterior Q sobre os pesos tem KL(Q‖P) = 200 nats em relação a um prior Gaussiano P. O risco empírico sob Q é 0,10. Defina δ = 0,05.

Sobreparametrização e Descida Dupla

O Desastre Previsto pelo PAC Clássico

O PAC clássico prevê: mais parâmetros que amostras = overfitting catastrófico. Aprende perfeitamente nos dados de treino, generaliza aleatoriamente nos dados de teste. O limite VC prevê memorização sem aprendizagem.

Redes neurais modernas rotineiramente têm de 10× a 1000× mais parâmetros que amostras de treino e ainda assim generalizam. Isso não deveria acontecer segundo a teoria clássica. Acontece mesmo assim.

A Curva em U que Nos Ensinaram

Viés-variância clássico: à medida que a capacidade do modelo cresce, o erro de treinamento cai monotonicamente; o erro de teste primeiro cai (menos underfit), atinge um mínimo e depois sobe (overfit). Curva em U prevista pela teoria VC.

O Que Realmente Acontece — Dupla Descida

Belkin et al (2019) mostraram que o erro de teste segue nossa curva em U clássica até o limiar de interpolação (capacidade = #amostras), depois CAI NOVAMENTE após esse limiar. Modelos massivamente superparametrizados generalizam melhor do que modelos apenas suficientemente grandes.

Por Que o PAC Clássico Não Captura Isso

1. A suposição livre de distribuição é excessivamente pessimista. Dados reais possuem estrutura (baixa dimensão intrínseca, geometria de variedades). Os limites PAC valem para distribuições de pior caso; distribuições reais exploram estrutura que o SGD também explora.

2. Regularização implícita. O SGD em redes superparametrizadas encontra soluções interpoladoras de norma mínima ou complexidade mínima, não soluções arbitrárias. A teoria clássica assume o minimizador de risco empírico no pior caso; os algoritmos reais escolhem soluções benignas.

3. Definição incorreta da classe de hipóteses. A classe de hipóteses efetiva explorada pelo SGD é muito menor que o espaço nominal de pesos. Os posteriors PAC-Bayes capturam isso; a dimensão VC não.

Trabalhos teóricos modernos (Bartlett, Long, Lugosi, Tsigler 2020 sobre benign overfitting; Nakkiran et al 2020 sobre double descent) estão construindo uma teoria de generalização pós-PAC que considera nosso regime superparametrizado.

Diagnosticando uma Falha do PAC Clássico

Uma equipe de pesquisa treina uma rede com 1 bilhão de parâmetros em 100.000 exemplos rotulados. O PAC clássico prevê limites vácuos. Empiricamente, a acurácia de teste atinge 95%.

Kaplan, Chinchilla e o Dimensionamento da Inteligência Geral Automatizada [BLOCK_TYPE SECTION/STEP]

De Limites a Leis de Escala Empíricas

O PAC clássico prevê o tamanho do conjunto de dados teoricamente e produz resultados vácuos. As leis de escala empíricas preveem o tamanho do conjunto de dados a partir da observação e realmente funcionam. Elas substituíram o PAC como nossa ferramenta prática de dimensionamento para modelos grandes. [BLOCK_TYPE SECTION/STEP]

[BLOCK_TYPE SECTION/STEP]

Kaplan et al (2020)

A perda segue uma lei de potência nos parâmetros N, tokens do conjunto de dados D e computação C:

L(N) ≈ (Nc/N)^αN L(D) ≈ (Dc/D)^αD L(C) ≈ (Cc/C)^αC

Dobrar os parâmetros reduz a perda por um fator multiplicativo fixo. Dobrar os dados reduz a perda por outro fator fixo. Esses expoentes (αN, αD, αC) medem e preveem o comportamento de fronteira em muitas ordens de magnitude.

Hoffmann et al 2022 (Chinchilla)

Chinchilla mostrou que os expoentes de Kaplan superestimavam os parâmetros em relação aos dados. O treinamento compute-optimal requer aproximadamente 20 tokens por parâmetro:

D_opt ≈ 20 × N

O GPT-3 (175B parâmetros) foi treinado em ~300B tokens — sub-treinado em grande escala segundo a matemática do Chinchilla. Um modelo compute-optimal de 175B parâmetros requer ~3,5 trilhões de tokens.

A Barreira dos Dados

Escalar nossa contagem de parâmetros exige escalar proporcionalmente nossa contagem de tokens. O rastreamento público da web produz ~10¹³ tokens úteis. Uma inteligência geral automatizada hipotética de 10¹⁵ parâmetros exigiria ~2×10¹⁶ tokens — três ordens de magnitude além dos dados disponíveis na web.

Esta é a nossa parede de dados. As leis de escalonamento preveem que enfrentaremos uma escassez de corpus muito antes de uma escassez de computação. Dados sintéticos, corpora multimodais (vídeo, áudio, fluxos de sensores) e RL a partir do ambiente visam superar essa barreira.

O PAC clássico nos dizia (incorretamente) que precisaríamos de 10²¹ amostras. As leis de escalonamento nos dizem (calibradas à realidade) que precisamos de 2×10¹⁶. Ambos os números excedem o texto disponível. O trabalho de fronteira atual lida com o fechamento dessa lacuna.

Estimando um Corpus para Inteligência Geral Automatizada

Suponha que um laboratório de fronteira proponha um modelo de 10¹⁴ parâmetros e afirme que ele alcançará inteligência geral automatizada. Queremos dimensionar seu corpus de treinamento pela regra de Chinchilla.

De Limites Teóricos a Medições em Produção

Pare de Calcular Limites; Comece a Medí-los

Limites PAC clássicos são vácuos. Limites PAC-Bayes são apertados sob suposições difíceis de verificar. Uma alternativa prática: medir ε empiricamente na sua distribuição real e atualizá-lo conforme o sistema opera.

Ideia 1 — Tornar a Cobertura um PAC Empírico

Um alvo make coverage executa N perguntas reservadas no seu sistema de consulta e mede duas taxas:

- cache_hit_rate — fração em que seu sistema encontrou uma resposta conhecida

- i_dont_know_rate — fração em que seu sistema adiou honestamente

Cada medição = um ensaio de Bernoulli. A partir das contagens observadas, calcule um intervalo de confiança de Wilson sobre a taxa real. Exemplo: N = 1000 consultas, i_dont_know_rate observado = 0.20 → IC 95% ≈ [0.177, 0.226]. O limite superior 0.226 funciona exatamente como um ε PAC com δ = 0.05, derivado de dados reais sobre a distribuição real, em vez de uma análise teórica de pior caso.

O vocabulário clássico do PAC se aplica (ε, δ, confiança). Diferente maquinaria (concentração binomial vs. teoria VC). Resultado mais apertado porque distribuições reais possuem estrutura explorável.

Ideia 2 — Auditoria PAC-Bayes via Eventos de Falsificação

Trate cada falsificação (resposta do sistema demonstravelmente errada) como evidência que atualiza a posteriori sobre a taxa real de erro ε:

1. Prior: ε ~ Beta(α₀, β₀). Escolha um prior fraco, ex.: Beta(1, 1) = uniforme.

2. Cada consulta produz um resultado de Bernoulli: falsificado (1) ou mantido (0).

3. Posterior após k falsificações em n consultas: Beta(α₀ + k, β₀ + n − k).

4. Média posterior: (α₀ + k) / (α₀ + β₀ + n) → taxa empírica de falsificação quando n → ∞.

5. Intervalo de credibilidade de 95% sobre ε estreita-se como 1/√n.

O Que Isso Nos Oferece

- Estimativa real de ε₀ a partir da implantação real, não teoria de pior caso

- Alarme anytime-valid: quando o intervalo de credibilidade posterior cruza o limiar do contrato, notificar alguém

- Confiança monotônica: mais consultas observadas → IC mais estreito → garantia mais forte

Técnicas relacionadas: previsão conforme com recalibração online (Vovk), testes sequenciais de razão de probabilidades (Wald), PAC-Bayes online (Haddouche & Guedj 2022). Mesma família, diferentes fundamentos matemáticos.

Calculando uma Posterior Beta em Falsificações

Nossa equipe executa uma auditoria de cobertura em um sistema de consultas em produção. Prior sobre a taxa real de erro ε: Beta(1, 1) (uniforme). Após 200 consultas de validação, observamos 8 falsificações.