Aprender É Viável? Generalização e o Limite de Hoeffding

• Enunciar com precisão a pergunta da viabilidade do aprendizado: dá para confiar que uma hipótese escolhida para ajustar uma amostra de treino finita vai ter bom desempenho em dados fora dessa amostra?
• Distinguir o erro dentro da amostra (medido nos dados de treino) do erro fora da amostra (o erro verdadeiro, não mensurável, na população inteira).
• Enunciar a desigualdade de Hoeffding e explicar, em termos simples, o que ela garante sobre a diferença entre o erro dentro e fora da amostra conforme o tamanho da amostra cresce.
• Explicar por que esse limite, sozinho, ainda não resolve por completo a pergunta da viabilidade, e qual ingrediente adicional (o número de hipóteses consideradas) o resto do bloco de complexidade de modelos desta disciplina existe para tratar.

Antes de escrever um único algoritmo de aprendizado, o curso "Learning From Data" do Caltech para numa pergunta fácil de pular e genuinamente fundamental: aprender a partir de uma amostra finita é sequer possível em princípio? Sempre dá para fazer um modelo ajustar perfeitamente os dados de treino (basta memorizá-los), mas isso não garante nada sobre dados novos. Todo o empreendimento do machine learning é uma aposta de que os padrões encontrados numa amostra se generalizam para dados nunca vistos; este conceito é o primeiro argumento real e quantitativo de por que essa aposta não é fé cega.

A ferramenta estatística central é a mesma lei que já apareceu, com outra roupagem, na disciplina de probabilidade deste currículo: a Lei dos Grandes Números diz que uma média amostral converge para a média verdadeira da população conforme a amostra cresce. A desigualdade de Hoeffding é uma versão mais afiada, para amostras finitas, exatamente dessa ideia, e é a espinha dorsal matemática por baixo de toda afirmação posterior desta disciplina de que "mais dados de treino reduzem o overfitting".

Erro dentro da amostra versus erro fora da amostra

Para uma hipótese fixa h (um modelo candidato), defina o erro dentro da amostra E_in(h) como a fração de exemplos de treino que h erra, e o erro fora da amostra E_out(h) como a probabilidade verdadeira de h errar um exemplo sorteado ao acaso da população inteira da qual os dados de treino foram amostrados. E_in é algo que dá para calcular de fato; E_out não: exigiria testar na população inteira, normalmente infinita ou indisponível. A pergunta da viabilidade é exatamente: quão perto E_in(h) está de E_out(h)?

A desigualdade de Hoeffding

Para uma única hipótese fixa h (escolhida antes de olhar os dados, e não ajustada a eles), a desigualdade de Hoeffding afirma:

text
P( |E_in(h) − E_out(h)| > ε ) ≤ 2·exp(−2ε²N)

em que N é o tamanho da amostra e ε é qualquer tolerância que se escolha. Em termos simples: a probabilidade de o erro de treino e o erro verdadeiro diferirem em mais de ε encolhe exponencialmente rápido conforme o tamanho da amostra N cresce. É precisamente a garantia de que o aprendizado precisa: com dados suficientes, o desempenho medido de uma hipótese na amostra se torna um substituto confiável do seu desempenho verdadeiro em todo lugar.

O porém: esse limite só vale para uma hipótese fixa

O limite de Hoeffding acima é provado para um único h fixado de antemão; ele ainda não diz nada sobre o que acontece quando um algoritmo de aprendizado busca entre muitas hipóteses candidatas e escolhe a que por acaso melhor ajusta os dados de treino. Buscar entre mais hipóteses aumenta a chance de pelo menos uma delas ajustar bem a amostra de treino por pura sorte, mesmo tendo um erro fora da amostra ruim; é o mesmo risco estatístico de testar muitas estratégias aleatórias de escolha de ações e reportar só a que por acaso bateu o mercado. É exatamente essa preocupação que a dimensão VC (um conceito posterior deste bloco) existe para quantificar com precisão: ela conta quantas hipóteses uma classe de modelos consegue efetivamente produzir e estende a garantia no estilo de Hoeffding para cobrir o caso de um algoritmo de aprendizado de fato escolhendo entre elas.

Por que isso justifica, e não enfraquece, o resto da disciplina

O objetivo de percorrer esse argumento primeiro não é lançar dúvida sobre o machine learning, e sim estabelecer, em bases matemáticas reais, exatamente que licença um algoritmo de aprendizado tem para confiar no seu desempenho de treino, e exatamente onde essa licença acaba (quando o espaço de hipóteses buscado é grande demais em relação ao tamanho da amostra). Todo conceito posterior do bloco de complexidade de modelos desta disciplina (viés-variância, dimensão VC, regularização, validação cruzada) é uma resposta prática diferente à mesma preocupação de viabilidade levantada aqui.

Exemplo 1: um cálculo concreto de Hoeffding

Suponha que uma hipótese fixa h seja testada em N = 1000 amostras independentes e que se escolha uma tolerância de ε = 0.05 (5 pontos percentuais). Substituindo no limite:

text
P( |E_in − E_out| > 0.05 ) ≤ 2·exp(−2 · 0.05² · 1000)
                            = 2·exp(−5)
                            ≈ 2 · 0.0067
                            ≈ 0.0135

Então, com 1000 amostras, há no máximo 1.35% de chance de o erro de treino medido diferir do erro verdadeiro em mais de 5 pontos percentuais: uma afirmação de confiança real e quantitativa, e não um aceno vago.

Exemplo 2: como o limite fica mais apertado com mais dados

Mantendo ε = 0.05 fixo e aumentando N de 100 para 1000 e para 10.000:

text
N = 100:    limite = 2·exp(−2·0.0025·100)   = 2·exp(−0.5)  ≈ 1.213  (vazio: passa de 1)
N = 1000:   limite = 2·exp(−2·0.0025·1000)  = 2·exp(−5)    ≈ 0.0135
N = 10000:  limite = 2·exp(−2·0.0025·10000) = 2·exp(−50)   ≈ 3.9e-21

Em N = 100, o limite é uma probabilidade matematicamente válida, mas inútil, maior que 1 (limites de Hoeffding só são informativos quando o termo exponencial é pequeno); em N = 10.000, a garantia é essencialmente certeza. Esse é o conteúdo real e numérico por trás da afirmação informal de que "mais dados significam que o modelo generaliza melhor".

• "O limite de Hoeffding prova que meu modelo treinado generaliza bem." Ele prova isso só para uma hipótese fixada antes de ver os dados de treino. Um modelo de fato escolhido ajustando os dados (que é o que todo algoritmo de aprendizado faz) exige a versão estendida desse argumento, com a dimensão VC; este conceito é a primeira metade honesta da história, e não a história inteira.
• "Um erro de treino pequeno garante um erro verdadeiro pequeno." Só probabilisticamente, e só com dados suficientes em relação ao tamanho do espaço de hipóteses buscado. Um modelo que memoriza o conjunto de treino pode ter E_in = 0 e um E_out arbitrariamente ruim.
• "Isso é só a Lei dos Grandes Números, nada de novo." A ligação é real e intencional: a desigualdade de Hoeffding é uma versão mais afiada e não assintótica da mesma ideia de convergência, dando um limite explícito em qualquer N finito, em vez de só uma garantia no limite quando N → ∞.

A viabilidade de aprender a partir de uma amostra finita se apoia na desigualdade de Hoeffding: para uma única hipótese fixa, a probabilidade de o seu erro dentro da amostra divergir do seu erro verdadeiro fora da amostra em mais que qualquer tolerância escolhida encolhe exponencialmente conforme o tamanho da amostra cresce. É uma justificativa real e quantitativa para confiar no desempenho de treino como substituto do desempenho verdadeiro, mas ela só se aplica de forma limpa antes de um algoritmo de aprendizado buscar entre muitas hipóteses e escolher a de melhor ajuste, uma lacuna que a dimensão VC fecha mais adiante neste bloco. Todos os conceitos restantes sobre overfitting, regularização e validação cruzada são respostas práticas à mesma preocupação de viabilidade levantada aqui.