Aprendizagem PAC

O que é Aprendizado PAC?

Aprendizado PAC (PAC learning)—abreviação de Provavelmente Aproximadamente Correto (Probably Approximately Correct)—é uma estrutura fundamental na teoria estatística do aprendizado (statistical learning theory) que formaliza o que significa para um algoritmo de aprendizado generalizar a partir de dados. Ela responde perguntas como:

Quantos exemplos de treinamento são suficientes para aprender um bom preditor?
Como a capacidade do modelo (model capacity) afeta o risco de sobreajuste (overfitting)?
Que garantias podemos dar de que um modelo treinado terá bom desempenho em dados não vistos?

O aprendizado PAC é especialmente útil como uma lente de alto nível: ele fornece garantias de aprendibilidade (learnability guarantees) e limites de complexidade de amostra (sample complexity bounds) (limites superiores para o número de exemplos necessários) sob suposições claras.

Este artigo complementa tópicos relacionados como Generalização e Viés/Variância, Sobreajuste e Regularização e Dimensão VC (VC Dimension).

A configuração central: conceitos, hipóteses e distribuições

O aprendizado PAC é tipicamente descrito em termos de:

Espaço de entrada (input space): ( \mathcal{X} ) (por exemplo, imagens, vetores, atributos de texto)
Espaço de rótulos (label space): ( \mathcal{Y} = {0,1} ) para classificação binária (binary classification) (existem extensões)
Distribuição de dados desconhecida (unknown data distribution): ( \mathcal{D} ) sobre ( \mathcal{X} )
Conceito-alvo (target concept): ( c: \mathcal{X} \to \mathcal{Y} ) (a regra “verdadeira” de rotulagem)
Classe de hipóteses (hypothesis class): ( \mathcal{H} \subseteq {h: \mathcal{X}\to \mathcal{Y}} ) (o conjunto de preditores que você considera)
Amostra de treinamento (training sample): ( S = {(x_i, y_i)}_{i=1}^m ), onde ( x_i \sim \mathcal{D} ) são independentes e identicamente distribuídos (i.i.d.) e ( y_i = c(x_i) ) (no cenário realizável (realizable setting) básico)

A quantidade-chave é o erro de generalização (generalization error) (também chamado de risco verdadeiro (true risk)) de uma hipótese (h):

[ \mathrm{err}{\mathcal{D}}(h) = \Pr{x \sim \mathcal{D}}[h(x) \neq c(x)]. ]

O aprendizado PAC tenta garantir que um algoritmo retorne uma hipótese com pequeno (\mathrm{err}_{\mathcal{D}}(h)) usando apenas uma amostra finita (S).

“Provavelmente” e “Aproximadamente” em uma definição

Um algoritmo de aprendizado (A) aprende no modelo PAC (PAC-learns) uma classe de conceitos (\mathcal{C}) usando a classe de hipóteses (\mathcal{H}) se:

Para qualquer alvo (c \in \mathcal{C}), qualquer distribuição (\mathcal{D}) sobre (\mathcal{X}) e quaisquer parâmetros de acurácia/confiança (accuracy/confidence parameters) ( \varepsilon \in (0,1), \delta \in (0,1)), existe um tamanho de amostra (m = m(\varepsilon,\delta)) tal que:

Dado (m) exemplos rotulados i.i.d. de (\mathcal{D}),
O algoritmo produz (h \in \mathcal{H}) satisfazendo

[ \Pr_{S \sim \mathcal{D}^m}\left[\mathrm{err}_{\mathcal{D}}(h) \le \varepsilon\right] \ge 1-\delta. ]

Interpretação:

Aproximadamente correto: erro no máximo (\varepsilon)
Provavelmente: o evento acontece com probabilidade pelo menos (1-\delta) sobre o sorteio aleatório da amostra

Uma característica crucial do aprendizado PAC clássico é que ele é tipicamente livre de distribuição (distribution-free): a garantia deve valer para todas as distribuições (\mathcal{D}), não apenas para distribuições “boas”.

Os cenários realizável vs. agnóstico

Aprendizado PAC realizável (realizable PAC learning) (sem ruído)

O modelo PAC básico assume que existe uma hipótese perfeita em (\mathcal{H}):

[ \exists h^\star \in \mathcal{H}: \mathrm{err}_{\mathcal{D}}(h^\star)=0. ]

Este é o caso realizável, frequentemente usado para explicar ideias centrais e derivar limites mais simples.

Aprendizado PAC agnóstico (agnostic PAC learning) (permite ruído / especificação incorreta)

Dados reais são ruidosos; rótulos podem ser inconsistentes, e o conceito “verdadeiro” pode não pertencer a (\mathcal{H}). A versão agnóstica compara com a melhor hipótese possível em (\mathcal{H}):

[ \mathrm{err}{\mathcal{D}}(h) \le \inf{h' \in \mathcal{H}} \mathrm{err}_{\mathcal{D}}(h') + \varepsilon ]

com probabilidade de pelo menos (1-\delta).

Isso é mais realista, mas os limites de amostra são tipicamente mais fracos (frequentemente escalando como (1/\varepsilon^2) em vez de (1/\varepsilon)).

Um primeiro limite de complexidade de amostra: classes de hipóteses finitas

Um dos resultados PAC mais instrutivos diz respeito a classes de hipóteses finitas (onde (|\mathcal{H}| < \infty)). Ele formaliza uma versão da navalha de Occam (Occam’s razor): se você busca em menos hipóteses, precisa de menos dados para evitar sobreajuste.

Ideia-chave: convergência uniforme (uniform convergence)

Se o erro empírico na amostra for próximo do erro verdadeiro para todas as hipóteses simultaneamente, então selecionar uma hipótese que se ajuste à amostra irá generalizar.

Defina o erro empírico (empirical error) como:

[ \widehat{\mathrm{err}}S(h)=\frac{1}{m}\sum{i=1}^m \mathbf{1}[h(x_i)\neq y_i]. ]

Usando desigualdades de concentração (concentration inequalities) (por exemplo, a desigualdade de Hoeffding (Hoeffding’s inequality)) mais um limite da união (union bound), pode-se mostrar que, para (\mathcal{H}) finito, com probabilidade de pelo menos (1-\delta):

[ \forall h \in \mathcal{H}:\quad |\mathrm{err}_{\mathcal{D}}(h) - \widehat{\mathrm{err}}_S(h)| \text{ é pequeno.} ]

Limite no caso realizável ( \(\mathcal{H}\) finito)

Se existe uma hipótese em (\mathcal{H}) com erro verdadeiro zero e retornamos qualquer hipótese consistente com os dados (erro de treinamento zero), então basta tomar:

[ m ;\ge; \frac{1}{\varepsilon}\left(\ln|\mathcal{H}| + \ln\frac{1}{\delta}\right). ]

Este limite é um pilar: ele explicita a troca entre:

Acurácia ((\varepsilon)): acurácia mais estrita requer mais amostras
Confiança ((\delta)): maior confiança requer mais amostras
Capacidade ((|\mathcal{H}|)): conjuntos de hipóteses maiores requerem mais amostras

Limite no caso agnóstico ( \(\mathcal{H}\) finito)

No cenário agnóstico (não necessariamente existe uma hipótese perfeita), um limite típico torna-se:

[ m ;=; O\left(\frac{1}{\varepsilon^2}\left(\ln|\mathcal{H}| + \ln\frac{1}{\delta}\right)\right). ]

A dependência (1/\varepsilon^2) reflete o problema mais difícil: você está estimando qual hipótese é a melhor, e não apenas encontrando uma que se ajuste perfeitamente.

Exemplo prático: “De quantos exemplos eu preciso?”

Suponha que você esteja escolhendo entre (|\mathcal{H}| = 10^6) regras possíveis (digamos, um milhão de heurísticas candidatas). Você quer:

erro no máximo (\varepsilon = 0.05) (5%)
confiança (1-\delta = 0.95) ((\delta = 0.05))

Limite realizável para classe finita:

[ m \ge \frac{1}{0.05}\left(\ln(10^6) + \ln(20)\right) \approx 20 \cdot (13.82 + 2.996) \approx 336. ]

Então algumas centenas de exemplos poderiam bastar em princípio para garantias de generalização—assumindo realizabilidade, amostragem i.i.d. e que você realmente se restrinja àquelas 1.000.000 de hipóteses.

Isso ajuda a construir intuição sobre por que limitar o espaço de hipóteses (via escolha de modelo, atributos ou regularização) pode reduzir sobreajuste, conectando diretamente com Sobreajuste e Regularização.

Minimização do Risco Empírico (Empirical Risk Minimization, ERM) como um aprendiz PAC (caso finito)

Para (\mathcal{H}) finito, um algoritmo simples é a minimização do risco empírico: escolher uma hipótese com erro de treinamento mínimo.

def ERM(H, S):
    # H: list of hypotheses h(x) -> {0,1}
    # S: list of labeled examples (x, y)
    best_h = None
    best_err = float("inf")
    for h in H:
        err = sum(1 for x, y in S if h(x) != y) / len(S)
        if err < best_err:
            best_err = err
            best_h = h
    return best_h

A teoria do aprendizado PAC então pergunta: sob quais condições a minimização do risco empírico generaliza, e quão grande deve ser (m)?

Na prática, a minimização do risco empírico sobre (\mathcal{H}) enorme é computacionalmente inviável, o que motiva a distinção entre:

Aprendibilidade informação-teórica (information-theoretic learnability) (existem amostras suficientes)
Aprendibilidade computacional (computational learnability) (podemos aprender de forma eficiente)

O aprendizado PAC aborda principalmente a primeira, embora restrições computacionais importem muito no aprendizado de máquina moderno.

Além de classes finitas: dimensão VC e controle de capacidade

As classes de hipóteses mais interessantes são infinitas (por exemplo, todos os separadores lineares em (\mathbb{R}^{100})). Para estender garantias PAC além de (\mathcal{H}) finito, a teoria do aprendizado usa medidas de complexidade—mais notoriamente, a dimensão VC.

A dimensão VC (d = \mathrm{VC}(\mathcal{H})) é, aproximadamente, o maior número de pontos que (\mathcal{H}) consegue rotular de todas as formas possíveis (isto é, “estilhaçar”, shatter). Ela captura capacidade de uma forma que sustenta limites livres de distribuição. Veja Dimensão VC para intuição e exemplos.

Complexidade de amostra PAC em termos da dimensão VC

Para classificação binária, resultados típicos são:

PAC realizável (limite por VC):

[ m = O\left(\frac{1}{\varepsilon}\left(d \log\frac{1}{\varepsilon} + \log\frac{1}{\delta}\right)\right) ]

PAC agnóstico (limite por VC):

[ m = O\left(\frac{1}{\varepsilon^2}\left(d + \log\frac{1}{\delta}\right)\right) ]

Esses limites explicam de maneira fundamentada por que “modelos maiores precisam de mais dados” e se conectam diretamente à história viés-variância em Generalização e Viés/Variância.

Exemplo prático: classificadores lineares

Para separadores lineares em (\mathbb{R}^d) (hiperplanos), a dimensão VC é (d+1). Então, em 100 dimensões, (d_{\mathrm{VC}} \approx 101).

Mesmo com constantes aproximadas, a narrativa PAC prediz:

Modelos lineares de maior dimensionalidade geralmente exigem mais dados para generalizar
Regularização ou restrições de margem (margin constraints) podem efetivamente reduzir a complexidade (embora a VC clássica, por si só, possa não capturar todos os fenômenos modernos)

Como o aprendizado PAC se conecta à regularização na prática

Os limites PAC sugerem uma receita geral:

Escolher uma classe de hipóteses (\mathcal{H}) (família de modelos).
Coletar dados suficientes (m) para generalizar dada aquela capacidade.
Usar um algoritmo (frequentemente minimização do risco empírico ou uma aproximação) que encontre uma boa hipótese em (\mathcal{H}).

Em pipelines reais de aprendizado de máquina, raramente enumeramos (\mathcal{H}) ou calculamos a dimensão VC, mas os mesmos princípios aparecem como:

Limitar a complexidade do modelo (profundidade, parâmetros, seleção de atributos)
Penalizar complexidade (regularização L2/L1, parada antecipada (early stopping))
Selecionar modelos via conjuntos de validação (validation sets) (um proxy prático para limites de generalização)
Aumento de dados (data augmentation) e injeção de ruído (noise injection) (frequentemente aumentam o tamanho efetivo da amostra / estabilizam o aprendizado)

Isso é coberto com mais detalhes em Sobreajuste e Regularização.

Variantes comuns de PAC e ideias relacionadas

O aprendizado PAC é uma família de ideias, não um único teorema. Variações comuns incluem:

Aprendizado próprio vs. impróprio (proper vs. improper learning)
- Próprio: produz (h \in \mathcal{H})
- Impróprio: a saída pode estar fora de (\mathcal{H}) (às vezes permite algoritmos eficientes ou melhor complexidade de amostra)
Aprendizado fraco vs. forte (weak vs. strong learning)
- O aprendizado fraco garante apenas uma acurácia ligeiramente melhor do que aleatória; impulsionamento (boosting) pode converter aprendizes fracos em fortes (veja Boosting se estiver disponível na sua wiki)
Garantias específicas à distribuição (não uniformes) (distribution-specific (non-uniform) guarantees)
- O PAC clássico é livre de distribuição; em alguns domínios (por exemplo, imagens naturais) a estrutura distribucional importa, e limites mais apertados, dependentes da distribuição, podem ser mais informativos.
Limites PAC-Bayes (PAC-Bayes bounds)
- Fornecem limites para preditores aleatorizados (randomized predictors) e incorporam “distância” em relação a um prior (prior); frequentemente usados para raciocinar sobre redes neurais (neural networks) de modo mais preciso do que limites de pior caso baseados em VC.

O que o aprendizado PAC explica e o que não explica (especialmente para aprendizado profundo)

O aprendizado PAC é extremamente influente, mas tem limitações como explicação para o aprendizado profundo moderno:

O que ele explica bem

Por que controlar capacidade ajuda a evitar sobreajuste
Por que a generalização depende tanto do tamanho dos dados quanto da riqueza da classe de hipóteses
Por que podemos esperar generalização a partir de amostras i.i.d. em primeiro lugar, e quais suposições são necessárias
Por que garantias frequentemente escalam como ( \log(1/\delta) ): maior confiança custa mais amostras, mas não dramaticamente mais

Onde ele pode ser grosseiro demais

Folga de pior caso (worst-case looseness): limites VC/PAC podem ser ordens de grandeza maiores do que as necessidades de amostra observadas.
Sobreparametrização (overparameterization): redes modernas podem ter muito mais parâmetros do que dados e ainda assim generalizar; medidas clássicas de capacidade podem não capturar a regularização implícita (implicit regularization) vinda da otimização (optimization) (por exemplo, Descida do Gradiente (Gradient Descent)).
Dados não i.i.d. e mudança de distribuição (distribution shift): PAC assume que dados de treino e teste vêm da mesma distribuição. Sob mudança de distribuição, garantias podem falhar, a menos que isso seja modelado explicitamente.
Saídas complexas e predição estruturada (structured prediction): existem extensões, mas a narrativa PAC mais limpa é a classificação binária.

Mesmo quando os limites são frouxos, o PAC continua valioso porque esclarece o que precisa ser verdade para qualquer argumento de generalização: suposições, controle de capacidade e concentração a partir de amostras finitas.

Um modelo mental: aprendizado PAC como “orçamento de generalização”

Uma forma útil de internalizar o aprendizado PAC é como um orçamento:

Você “gasta” dados para comprar:
- acurácia ((\varepsilon))
- confiança ((\delta))
- e o direito de buscar em um grande conjunto de modelos ((\mathcal{H}))

Se você aumenta a flexibilidade do modelo sem aumentar os dados, você arrisca sobreajuste—exatamente o fenômeno descrito operacionalmente em Sobreajuste e Regularização, e teoricamente via dimensão VC em Dimensão VC.

Resumo

Aprendizado PAC formaliza aprendibilidade: com amostras i.i.d. suficientes, um algoritmo pode produzir uma hipótese com erro no máximo (\varepsilon) com probabilidade de pelo menos (1-\delta).
Para classes de hipóteses finitas, a complexidade de amostra escala como:
- realizável: (O\left(\frac{\ln|\mathcal{H}| + \ln(1/\delta)}{\varepsilon}\right))
- agnóstico: (O\left(\frac{\ln|\mathcal{H}| + \ln(1/\delta)}{\varepsilon^2}\right))
Para classes infinitas, a dimensão VC generaliza essas ideias e produz limites análogos.
O aprendizado PAC é um guia fundamental para por que a generalização é possível, embora o aprendizado profundo moderno frequentemente exija explicações mais nuançadas, dependentes de dados e de algoritmos.

Se você quer o próximo passo conceitual após PAC, a continuação mais direta é Dimensão VC, que explica como “capacidade” substitui (\ln|\mathcal{H}|) quando (\mathcal{H}) é infinito.