3  O que é aprendizado?

No capítulo anterior, formalizamos um método de aprendizado como um algoritmo que recebe uma amostra e devolve uma hipótese. Essa descrição esclarece como o treinamento é organizado, mas ainda deixa aberta a pergunta central deste capítulo: quando podemos afirmar que houve aprendizado?

Acertar os exemplos conhecidos não é suficiente. Um programa poderia armazenar cada par da amostra e devolver a resposta memorizada quando encontrasse exatamente a mesma entrada. Seu erro de treinamento seria zero, mas ele não saberia como responder a uma entrada nova. Aprender exige alguma forma de generalização.

Neste capítulo, diremos que um método aprende quando utiliza uma amostra finita para produzir uma hipótese cujo desempenho permanece bom em exemplos ainda não observados, provenientes do processo de interesse. Essa ideia envolve três elementos:

  1. uma medida de qualidade ou erro;
  2. uma afirmação sobre dados fora da amostra;
  3. uma garantia probabilística, pois diferentes amostras podem levar a hipóteses diferentes.

Retomando a notação.

No aprendizado supervisionado, consideramos:

\[ D=\{(x_i,y_i)\}_{i=1}^{N}; \]

\[ \widehat{h}=A(D)\in\mathcal{H}. \]

Em um modelo determinístico, podemos supor \(y=f(x)\) para alguma função-alvo \(f\). Em problemas com ruído, trabalhamos com a distribuição condicional \(P(Y\mid X=x)\). As ideias de erro e generalização valem nos dois casos.

O risco empírico mede o desempenho nos exemplos observados:

\[ \widehat{R}_D(h) =\frac{1}{N}\sum_{i=1}^{N}\ell(h(x_i),y_i). \]

O risco esperado mede o desempenho médio no processo gerador:

\[ R(h) =\mathbb{E}_{(X,Y)\sim P} \bigl[\ell(h(X),Y)\bigr]. \]

O primeiro pode ser calculado a partir do treinamento; o segundo é o que realmente nos interessa, mas depende de uma distribuição desconhecida.

Aprendizado como generalização.

Uma hipótese generaliza quando seu erro em dados novos é próximo do erro observado na amostra. Intuitivamente, desejamos que

\[ R(\widehat{h}) \approx \widehat{R}_D(\widehat{h}). \]

Essa aproximação não ocorre automaticamente. O próprio algoritmo escolheu \(\widehat{h}\) depois de observar \(D\), portanto a hipótese pode ter explorado detalhes acidentais da amostra. Quanto mais flexível for a classe \(\mathcal{H}\), maior sua capacidade de ajustar padrões reais — e também ruído.

Dois tipos de falha ajudam a organizar essa discussão:

O objetivo não é obter o menor erro de treinamento a qualquer custo. Queremos equilibrar ajuste e capacidade de generalização.

ImportantO conjunto de teste não participa do aprendizado

Se usamos repetidamente o desempenho de teste para escolher atributos, hiperparâmetros ou modelos, o teste deixa de representar dados não vistos. Essas escolhas devem ser feitas com dados de treinamento e validação; o teste é reservado para a avaliação final.

O papel da probabilidade.

A amostra é aleatória. Duas equipes podem coletar \(N\) exemplos da mesma população e obter conjuntos diferentes. Consequentemente, o algoritmo pode produzir hipóteses diferentes.

Uma garantia de aprendizado costuma ter a forma:

\[ P_D\bigl(R(A(D))\leq\varepsilon\bigr) \geq1-\delta, \]

em que:

Lemos a expressão assim: com probabilidade de pelo menos \(1-\delta\), o algoritmo devolve uma hipótese cujo risco não ultrapassa \(\varepsilon\). Em formulações mais gerais, comparamos \(R(A(D))\) ao melhor risco alcançável dentro de \(\mathcal{H}\).

Essa é a origem da expressão provavelmente aproximadamente correto: “provavelmente” refere-se à confiança \(1-\delta\) e “aproximadamente” à tolerância \(\varepsilon\).

O que determina a dificuldade.

A quantidade de dados necessária depende de vários fatores:

Exigir erro menor ou confiança maior normalmente requer mais exemplos. Classes muito expressivas também precisam de maior quantidade de dados para que possamos distinguir padrões generalizáveis de ajustes acidentais.

Três perguntas do capítulo.

As próximas seções desenvolverão três perguntas complementares.

  1. Como medir a discrepância? Precisamos definir erro, perda e noção de proximidade entre uma hipótese e o comportamento desejado.
  2. Quando o erro observado é confiável? Estudaremos garantias probabilísticas que relacionam amostra e população.
  3. Como estimar o desempenho na prática? Discutiremos divisões entre treino, validação e teste.

Essas perguntas conectam teoria e engenharia. A teoria fornece condições e limites; o protocolo experimental produz evidência sobre um modelo concreto.

Exemplo motivador.

Suponha que um classificador de spam acerte \(990\) de \(1\,000\) mensagens de treinamento. A taxa de erro empírico é

\[ \widehat{R}_D(h)=\frac{10}{1\,000}=0{,}01. \]

Ainda não podemos concluir que seu erro futuro será \(1\%\). Talvez as mensagens tenham sido usadas para escolher palavras-chave específicas, talvez a amostra contenha mensagens muito semelhantes ou talvez o padrão de spam tenha mudado.

Se avaliarmos o classificador uma única vez em \(2\,000\) mensagens de teste independentes e encontrarmos \(60\) erros, a estimativa de teste será

\[ \widehat{R}_{\text{teste}}(h) =\frac{60}{2\,000} =0{,}03. \]

A diferença entre \(1\%\) no treino e \(3\%\) no teste sugere uma lacuna de generalização. Para interpretar a incerteza dessa estimativa, precisaremos de ferramentas probabilísticas.

Exercícios de preparação.

  1. Explique por que memorizar uma amostra não é suficiente para caracterizar aprendizado.
  2. Diferencie risco empírico e risco esperado.
  3. Dê um exemplo de subajuste e um de sobreajuste.
  4. Interprete \(\varepsilon\) e \(\delta\) em uma garantia probabilística.
  5. Por que avaliar repetidamente no conjunto de teste compromete sua função?
  6. No exemplo de spam, cite duas causas possíveis para a diferença entre os erros de treino e teste.

3.1 2.1 Erro

Aprender exige comparar previsões com resultados observados. Essa comparação é feita por uma função de perda, que traduz a qualidade de uma previsão em um número. Quanto menor a perda, melhor a previsão segundo o critério escolhido.

Não existe uma única noção de erro apropriada para todos os problemas. Errar uma classe é diferente de errar uma quantidade contínua; em algumas aplicações, certos erros têm consequências muito mais graves do que outros. A função de perda faz parte da formulação e deve refletir o objetivo real do sistema.

3.1.1 Perda por exemplo, risco e métrica

A perda por exemplo compara uma previsão \(\widehat{y}\) com o alvo \(y\):

\[ \ell\colon\widehat{Y}\times Y\to[0,\infty). \]

O risco empírico agrega as perdas na amostra:

\[ \widehat{R}_D(h) =\frac{1}{N}\sum_{i=1}^{N} \ell(h(x_i),y_i). \]

Uma métrica de avaliação resume algum aspecto do comportamento do modelo, como acurácia, precisão, revocação ou erro absoluto médio. Algumas métricas podem ser usadas como objetivo de treinamento; outras são difíceis de otimizar diretamente e servem principalmente para avaliação.

O algoritmo pode minimizar um objetivo com risco empírico e regularização:

\[ J(\theta) =\widehat{R}_D(h_\theta)+\lambda\Omega(\theta). \]

Usaremos perda para um exemplo, risco para uma média de perdas e objetivo para a quantidade efetivamente otimizada.

3.1.2 Classificação: perda zero-um

Em classificação, a perda zero-um vale \(0\) para um acerto e \(1\) para um erro:

\[ \ell_{0/1}(\widehat{y},y) =\mathbb{1}[\widehat{y}\neq y]. \]

Seu risco empírico é a taxa de classificações incorretas:

\[ \widehat{R}_{0/1}(h) =\frac{1}{N}\sum_{i=1}^{N} \mathbb{1}[h(x_i)\neq y_i]. \]

Se um classificador erra \(18\) de \(300\) exemplos, então \(\widehat{R}_{0/1}(h)=18/300=0{,}06\) e sua acurácia é \(0{,}94\).

A perda zero-um expressa diretamente a quantidade de erros, mas é descontínua. Por isso, muitos algoritmos treinam com perdas substitutas diferenciáveis.

3.1.3 Matriz de confusão

Em classificação binária há quatro resultados:

Alvo \(y\) Previsão \(\widehat{y}\) Nome
positivo positivo verdadeiro positivo (VP)
negativo negativo verdadeiro negativo (VN)
negativo positivo falso positivo (FP)
positivo negativo falso negativo (FN)

A partir dessas contagens calculamos

\[ \operatorname{precisão} =\frac{VP}{VP+FP}, \qquad \operatorname{revocação} =\frac{VP}{VP+FN} \]

e

\[ \operatorname{especificidade} =\frac{VN}{VN+FP}. \]

Precisão responde: entre as previsões positivas, quantas estavam corretas? Revocação responde: entre os casos realmente positivos, quantos foram detectados?

Quando classes são muito desbalanceadas, a acurácia pode enganar. Se apenas \(1\%\) das transações são fraudulentas, prever “não fraude” para todas produz \(99\%\) de acurácia e nenhuma capacidade de detectar fraude.

3.1.4 Custos assimétricos

Falsos positivos e falsos negativos podem ter custos diferentes:

\[ \ell(\widehat{y},y) = \begin{cases} 0, & \widehat{y}=y,\\ c_{FP}, & \widehat{y}=1 \text{ e } y=0,\\ c_{FN}, & \widehat{y}=0 \text{ e } y=1. \end{cases} \]

O risco empírico correspondente é

\[ \widehat{R}_D(h) =\frac{c_{FP}FP+c_{FN}FN}{N}. \]

Em autenticação, aceitar uma pessoa não autorizada pode ser mais grave do que pedir que a pessoa autorizada tente novamente. Em triagem, deixar de sinalizar um caso urgente pode ser mais grave do que encaminhar um caso não urgente. Os custos devem representar consequências do contexto.

3.1.5 Regressão: resíduo

Em regressão, o resíduo do exemplo \(i\) é

\[ r_i=h(x_i)-y_i. \]

\(r_i>0\) indica superestimação e \(r_i<0\) indica subestimação. Uma perda transforma esse resíduo em penalidade não negativa.

Figure 3.1: A perda absoluta cresce linearmente com o resíduo; a quadrática cresce mais rapidamente; a logística diminui conforme aumenta a margem correta.

3.1.6 Erro quadrático médio

A perda quadrática é

\[ \ell_{\text{quad}}(\widehat{y},y) =(\widehat{y}-y)^2. \]

O erro quadrático médio (mean squared error, MSE) é

\[ \operatorname{MSE}(h) =\frac{1}{N}\sum_{i=1}^{N} \bigl(h(x_i)-y_i\bigr)^2. \]

Erros grandes recebem penalidade desproporcional. Um resíduo de magnitude \(3\) contribui \(9\), enquanto três resíduos de magnitude \(1\) contribuem \(3\) no total. Isso torna o MSE sensível a valores extremos.

A raiz do MSE,

\[ \operatorname{RMSE}(h) =\sqrt{\operatorname{MSE}(h)}, \]

possui a mesma unidade do alvo.

3.1.7 Erro absoluto médio

A perda absoluta é

\[ \ell_{\text{abs}}(\widehat{y},y) =|\widehat{y}-y|. \]

O erro absoluto médio (mean absolute error, MAE) é

\[ \operatorname{MAE}(h) =\frac{1}{N}\sum_{i=1}^{N} |h(x_i)-y_i|. \]

O MAE cresce linearmente e é menos sensível a observações extremas do que o MSE. Para resíduos \((1,1,4)\),

\[ \operatorname{MAE}=2, \qquad \operatorname{MSE}=6. \]

O erro de magnitude \(4\) exerce influência muito maior no MSE.

3.1.8 Perda de Huber

A perda de Huber combina comportamento quadrático perto de zero e linear para resíduos grandes:

\[ \ell_\delta(r) = \begin{cases} \frac{1}{2}r^2, & |r|\leq\delta,\\[4pt] \delta\left(|r|-\frac{1}{2}\delta\right), & |r|>\delta. \end{cases} \]

O parâmetro \(\delta\) determina a transição. Essa perda mantém suavidade perto do mínimo e reduz a influência de valores muito discrepantes.

3.1.9 Classes codificadas por \(-1\) e \(+1\)

Se \(y,\widehat{y}\in\{-1,+1\}\), então

\[ (\widehat{y}-y)^2 = \begin{cases} 0, & \widehat{y}=y,\\ 4, & \widehat{y}\neq y. \end{cases} \]

Logo, a perda quadrática é quatro vezes a perda zero-um nesse caso específico. Ela não vale \(1\) quando há erro. Se o modelo produz uma pontuação real, a perda quadrática também considera a distância da pontuação ao rótulo.

3.1.10 Probabilidades e entropia cruzada binária

Considere \(y\in\{0,1\}\) e uma previsão \(p=h(x)\in(0,1)\). A entropia cruzada binária é

\[ \ell_{\text{BCE}}(p,y) =-\bigl[y\log p+(1-y)\log(1-p)\bigr]. \]

Se \(y=1\), a perda é \(-\log p\); se \(y=0\), é \(-\log(1-p)\). Uma previsão confiante e errada recebe perda grande:

\[ -\log(0{,}9)\approx0{,}105, \qquad -\log(0{,}01)\approx4{,}605. \]

Essa perda avalia a probabilidade atribuída ao resultado observado, não apenas a classe final.

3.1.11 Máxima verossimilhança

Para exemplos i.i.d. e um modelo \(P_\theta(Y=y\mid X=x)\), a verossimilhança é

\[ L(\theta) =\prod_{i=1}^{N} P_\theta(Y=y_i\mid X=x_i). \]

Máxima verossimilhança escolhe parâmetros que maximizam \(L(\theta)\). Como o logaritmo é estritamente crescente,

\[ \underset{\theta}{\operatorname{argmax}}\;L(\theta) = \underset{\theta}{\operatorname{argmax}}\;\log L(\theta). \]

Para escrever o treinamento como minimização, usamos a log-verossimilhança negativa média:

\[ \operatorname{NLL}(\theta) =-\frac{1}{N}\sum_{i=1}^{N} \log P_\theta(Y=y_i\mid X=x_i). \]

Para um modelo de Bernoulli, a NLL coincide com a entropia cruzada binária.

WarningTransformações e pontos ótimos

Uma transformação estritamente crescente preserva mínimos e máximos. Uma transformação estritamente decrescente troca máximos por mínimos. Assim, \(\log\) preserva o máximo da verossimilhança; \(-\log\) converte esse máximo em mínimo.

3.1.12 Entropia cruzada multiclasse

Para \(K\) classes, o modelo produz \(\mathbf{p}=(p_1,\ldots,p_K)\), com \(p_k\geq0\) e \(\sum_kp_k=1\). Se a classe correta é \(y\), a perda é

\[ \ell(\mathbf{p},y)=-\log p_y. \]

Com alvo one-hot \(\mathbf{y}\),

\[ \ell(\mathbf{p},\mathbf{y}) =-\sum_{k=1}^{K}y_k\log p_k. \]

Essa é a perda habitual para classificadores multiclasse treinados com softmax.

3.1.13 Perdas de margem

Em classificação binária com \(y\in\{-1,+1\}\) e pontuação \(s(x)\in\mathbb{R}\), definimos a margem

\[ m=y\,s(x). \]

Margem positiva indica classificação correta; margem negativa indica erro. A perda logística é

\[ \ell_{\text{log}}(m)=\log(1+e^{-m}). \]

Ela diminui suavemente conforme a margem correta aumenta. Podemos otimizar entropia cruzada e avaliar acurácia, precisão, revocação e calibração.

3.1.14 Escolhendo uma perda

Situação Opção comum Característica
Regressão com ruído aproximadamente simétrico MSE penaliza fortemente erros grandes
Regressão com valores extremos MAE ou Huber maior robustez
Classificação probabilística binária entropia cruzada binária avalia probabilidades
Classificação multiclasse entropia cruzada penaliza baixa probabilidade da classe correta
Custos diferentes entre erros perda ponderada incorpora assimetria

A escolha deve considerar o tipo de saída, as consequências dos erros, valores extremos, propriedades necessárias à otimização e a métrica de interesse. Nenhuma perda corrige dados inadequados ou substitui avaliação fora da amostra.

3.1.15 Exemplo computacional

def mse(previsoes, alvos):
    erros = [(p - y) ** 2 for p, y in zip(previsoes, alvos)]
    return sum(erros) / len(erros)


def mae(previsoes, alvos):
    erros = [abs(p - y) for p, y in zip(previsoes, alvos)]
    return sum(erros) / len(erros)


y = [10, 12, 14]
pred = [11, 13, 18]

print(mse(pred, y))  # 6.0
print(mae(pred, y))  # 2.0

Em produção, também devemos verificar comprimentos, valores ausentes, tipos numéricos e o comportamento quando a amostra está vazia.

3.1.16 Exercícios de fixação

  1. Um classificador obteve \(VP=80\), \(VN=900\), \(FP=20\) e \(FN=100\). Calcule acurácia, precisão e revocação.
  2. Para resíduos \((2,-1,-3)\), calcule MAE, MSE e RMSE.
  3. Explique por que a perda quadrática vale \(4\), e não \(1\), quando \(y=-1\) e \(\widehat{y}=+1\).
  4. Calcule a entropia cruzada binária para \(y=1\) com \(p=0{,}8\) e com \(p=0{,}2\).
  5. Mostre por que maximizar \(L(\theta)\) equivale a minimizar \(-\log L(\theta)\).
  6. Dê um exemplo no qual \(c_{FN}>c_{FP}\) e outro no qual \(c_{FP}>c_{FN}\).
  7. Quando você preferiria MAE à MSE?
  8. Explique a diferença entre perda de treinamento e métrica de avaliação.

3.2 Provavelmente Aproximadamente Correto

A teoria provavelmente aproximadamente correta, abreviada por PAC (probably approximately correct), transforma a ideia de generalização em uma garantia matemática. Ela reconhece duas limitações inevitáveis:

  • uma amostra finita não determina perfeitamente o comportamento em toda a população;
  • como a amostra é aleatória, algumas amostras podem ser pouco representativas.

Em vez de exigir certeza e perfeição, fixamos uma tolerância de erro \(\varepsilon\) e uma probabilidade de falha \(\delta\). Perguntamos quantos exemplos são necessários para que o algoritmo produza uma hipótese suficientemente boa com alta probabilidade.

Figure 3.2: Na garantia PAC, pelo menos uma fração \(1-\delta\) das amostras leva o algoritmo a uma hipótese cujo erro é no máximo \(\varepsilon\).

3.2.1 Duas fontes de probabilidade

Considere uma distribuição \(P\) sobre \(X\times Y\) e uma hipótese \(h\). Seu risco é

\[ R_P(h) =\mathbb{E}_{(X,Y)\sim P} \bigl[\ell(h(X),Y)\bigr]. \]

Na classificação com perda zero-um,

\[ R_P(h) =P_{(X,Y)\sim P}\bigl(h(X)\neq Y\bigr). \]

Essa probabilidade é sobre um novo exemplo sorteado de \(P\). Ela mede a região da população em que \(h\) erra.

O algoritmo recebe uma amostra aleatória

\[ D=((x_1,y_1),\ldots,(x_N,y_N)) \sim P^N \]

e devolve \(A(D)\). Como \(D\) varia, a hipótese também varia. A expressão

\[ P_{D\sim P^N} \bigl(R_P(A(D))\leq\varepsilon\bigr) \geq1-\delta \]

contém uma segunda probabilidade, agora sobre o sorteio da amostra inteira. Ela afirma que no máximo uma fração \(\delta\) das amostras conduz a uma hipótese cujo risco ultrapassa \(\varepsilon\).

ImportantNão confunda \(\varepsilon\) e \(\delta\)

\(\varepsilon\) limita o erro da hipótese na população. \(\delta\) limita a probabilidade de o procedimento de treinamento não alcançar essa garantia. Um atua dentro de cada hipótese; o outro atua sobre as possíveis amostras.

3.2.2 Lendo “provavelmente aproximadamente correto”

Na desigualdade

\[ P_D\bigl(R_P(A(D))\leq\varepsilon\bigr) \geq1-\delta, \]

cada palavra possui um papel:

  • provavelmente: o evento desejado ocorre com probabilidade de pelo menos \(1-\delta\);
  • aproximadamente: admitimos erro de até \(\varepsilon\);
  • correto: o erro é medido em relação à distribuição de interesse, não somente na amostra de treinamento.

Se \(\varepsilon=0{,}05\) e \(\delta=0{,}01\), a garantia diz: com confiança de pelo menos \(99\%\) sobre a amostra coletada, a hipótese produzida terá risco de no máximo \(5\%\).

Isso não significa que exatamente \(5\%\) das previsões estarão erradas ou que o algoritmo falhará exatamente uma vez em cem. Trata-se de uma cota probabilística válida sob as hipóteses do teorema.

3.2.3 Cenário realizável

A forma mais simples da teoria supõe que existe uma hipótese perfeita dentro da classe \(\mathcal{H}\). Esse é o caso realizável:

\[ \exists h^*\in\mathcal{H} \quad\text{tal que}\quad R_P(h^*)=0. \]

Um algoritmo \(A\) é um aprendiz PAC realizável para \(\mathcal{H}\) se existe uma função de complexidade amostral

\[ m_{\mathcal{H}}\colon(0,1)^2\to\mathbb{N} \]

tal que, para quaisquer \(\varepsilon,\delta\in(0,1)\), qualquer distribuição de entradas e qualquer alvo representável por \(\mathcal{H}\), toda amostra i.i.d. com

\[ N\geq m_{\mathcal{H}}(\varepsilon,\delta) \]

satisfaz

\[ P_D\bigl(R_P(A(D))\leq\varepsilon\bigr) \geq1-\delta. \]

No caso realizável, um algoritmo consistente procura uma hipótese com erro empírico zero. A teoria precisa mostrar quando consistência na amostra implica risco pequeno fora dela.

A hipótese de realizabilidade é forte. Dados podem conter ruído, classes podem se sobrepor e a família escolhida pode não representar o mecanismo real.

3.2.4 Cenário agnóstico

No aprendizado PAC agnóstico, não supomos que alguma hipótese em \(\mathcal{H}\) seja perfeita. Comparamos o resultado do algoritmo à melhor hipótese disponível na classe:

\[ R_P(A(D)) \leq \inf_{h\in\mathcal{H}}R_P(h)+\varepsilon. \]

Formalmente, exigimos

\[ P_D\left( R_P(A(D)) \leq \inf_{h\in\mathcal{H}}R_P(h)+\varepsilon \right) \geq1-\delta. \]

\(\varepsilon\) agora é um excesso de risco. O algoritmo pode não atingir erro absoluto pequeno se toda hipótese da classe for inadequada; ele deve aproximar o melhor desempenho possível dentro de \(\mathcal{H}\).

Essa formulação separa dois componentes:

\[ R_P(A(D)) = \underbrace{\inf_{h\in\mathcal{H}}R_P(h)}_{\text{limitação da classe}} + \underbrace{\text{excesso de risco}}_{\text{limitação da amostra e do algoritmo}}. \]

Ampliar \(\mathcal{H}\) pode reduzir a limitação de representação, mas torna a seleção estatística mais difícil. Esse é um aspecto do equilíbrio entre ajuste e complexidade.

3.2.5 Complexidade amostral

A complexidade amostral \(m_{\mathcal{H}}(\varepsilon,\delta)\) é o número mínimo de exemplos suficiente para a garantia desejada. Ela responde a uma pergunta estatística: quanta informação é necessária?

Em geral:

  • diminuir \(\varepsilon\) exige mais exemplos;
  • diminuir \(\delta\) exige mais exemplos;
  • aumentar a complexidade de \(\mathcal{H}\) exige mais exemplos.

Para uma classe finita no caso realizável, uma cota típica é

\[ N \geq \frac{1}{\varepsilon} \left( \log|\mathcal{H}| +\log\frac{1}{\delta} \right). \]

Constantes e pequenas variações dependem da derivação, mas a estrutura é importante. A dependência é logarítmica no número de hipóteses e em \(1/\delta\), e proporcional a \(1/\varepsilon\).

No caso agnóstico, uma cota de ordem típica é

\[ N = O\left( \frac{ \log|\mathcal{H}|+\log(1/\delta) }{ \varepsilon^2 } \right). \]

A dependência \(1/\varepsilon^2\) reflete a dificuldade adicional de comparar hipóteses quando nenhuma é necessariamente perfeita.

3.2.6 De onde vem a cota para uma classe finita?

Considere o caso realizável e uma hipótese ruim \(h\) com

\[ R_P(h)>\varepsilon. \]

A probabilidade de \(h\) acertar todos os \(N\) exemplos independentes é no máximo

\[ (1-\varepsilon)^N \leq e^{-\varepsilon N}. \]

Há no máximo \(|\mathcal{H}|\) hipóteses ruins. Pela cota da união, a probabilidade de alguma hipótese ruim permanecer consistente é no máximo

\[ |\mathcal{H}|e^{-\varepsilon N}. \]

Queremos que essa quantidade seja no máximo \(\delta\):

\[ |\mathcal{H}|e^{-\varepsilon N} \leq\delta. \]

Aplicando logaritmos e isolando \(N\),

\[ N \geq \frac{1}{\varepsilon} \left( \log|\mathcal{H}| +\log\frac{1}{\delta} \right). \]

A derivação mostra por que precisamos controlar simultaneamente a chance de cada hipótese ruim sobreviver e a quantidade de hipóteses candidatas.

3.2.7 Um exemplo numérico

Suponha uma classe finita com

\[ |\mathcal{H}|=1\,000, \qquad \varepsilon=0{,}05, \qquad \delta=0{,}01. \]

A cota realizável fornece

\[ N \geq \frac{1}{0{,}05} \left( \log 1\,000+\log 100 \right). \]

Usando logaritmo natural,

\[ N \geq 20(6{,}908+4{,}605) \approx230{,}26. \]

Logo, a cota pede pelo menos \(231\) exemplos. Esse valor é uma garantia de pior caso, não uma previsão exata de quantos exemplos serão necessários em toda aplicação.

3.2.8 Classes infinitas

Muitas classes importantes são infinitas. Há infinitas retas no plano e infinitas combinações de pesos de uma rede neural. Nesse caso, \(\log|\mathcal{H}|\) não pode ser usado diretamente.

Precisamos de uma medida mais refinada da capacidade da classe. A dimensão de Vapnik–Chervonenkis, estudada adiante, mede quantos padrões de classificação uma família consegue realizar sobre conjuntos finitos. Outras ferramentas incluem números de cobertura, complexidade de Rademacher e normas dos parâmetros.

Uma classe infinita pode ser PAC-aprendível se sua capacidade efetiva for controlada. Infinito em cardinalidade não significa automaticamente impossível de aprender.

3.2.9 Aprendibilidade e eficiência computacional

Complexidade amostral e complexidade computacional são diferentes.

  • Aprendibilidade estatística: existe um algoritmo que alcança a garantia usando um número finito e controlado de exemplos?
  • Eficiência computacional: esse algoritmo executa em tempo e memória viáveis?

Uma classe pode admitir boa complexidade amostral, mas exigir uma busca computacionalmente intratável. Um aprendiz PAC eficiente costuma exigir tempo polinomial nos parâmetros relevantes da representação, em \(1/\varepsilon\) e em \(\log(1/\delta)\) ou \(1/\delta\), conforme a convenção formal adotada. O ponto central é que obter informação suficiente não garante que conseguiremos processá-la eficientemente.

3.2.10 O que a garantia PAC não afirma

Uma garantia PAC depende de condições. Ela não afirma que:

  • os dados i.i.d. representam qualquer cenário futuro;
  • a distribuição permanecerá estável após a implantação;
  • os rótulos são corretos;
  • a perda escolhida representa todos os impactos relevantes;
  • o modelo é causal, justo ou seguro;
  • a cota é apertada para uma aplicação concreta.

Se treinamento e uso têm distribuições diferentes, a garantia derivada para \(P\) pode não descrever a operação real. A teoria fornece uma afirmação condicional: se as hipóteses forem satisfeitas, então a cota vale.

3.2.11 Exemplo finito e o viés indutivo

Considere

\[ X=\{1,2,\ldots,8\}, \qquad Y=\{-1,+1\}, \]

e uma amostra que revela os rótulos de cinco entradas. Restam três rótulos desconhecidos, portanto existem

\[ 2^3=8 \]

extensões compatíveis com os cinco valores observados.

Somente a amostra não permite escolher logicamente uma extensão. O algoritmo precisa de um viés indutivo: preferir funções simples, padrões suaves, fronteiras lineares ou outra estrutura. PAC não elimina essa necessidade; ele analisa quando a combinação de classe, algoritmo e quantidade de dados generaliza.

3.2.12 PAC e validação experimental

Uma cota teórica e um conjunto de teste respondem a perguntas diferentes.

  • A cota PAC fornece garantia sob hipóteses matemáticas e frequentemente vale no pior caso.
  • O teste estima o desempenho de uma hipótese concreta em uma amostra independente.

Na prática, usamos ambos quando disponíveis: teoria para compreender dependências e limites; avaliação experimental para medir o sistema treinado.

3.2.13 Resumo

Um método PAC controla dois níveis de incerteza:

\[ \boxed{ P_D\bigl( R_P(A(D)) \leq\varepsilon \bigr) \geq1-\delta } \]

no caso realizável, ou

\[ \boxed{ P_D\left( R_P(A(D)) \leq \inf_{h\in\mathcal{H}}R_P(h)+\varepsilon \right) \geq1-\delta } \]

no caso agnóstico.

\(\varepsilon\) controla a qualidade aproximada, \(\delta\) controla a confiança e \(m_{\mathcal{H}}(\varepsilon,\delta)\) informa quantos exemplos são suficientes.

3.2.14 Exercícios de fixação

  1. Explique, com palavras, as duas probabilidades envolvidas em uma garantia PAC.
  2. Interprete uma garantia com \(\varepsilon=0{,}02\) e \(\delta=0{,}05\).
  3. Diferencie o caso realizável do caso agnóstico.
  4. Para \(|\mathcal{H}|=100\), \(\varepsilon=0{,}1\) e \(\delta=0{,}05\), calcule a cota realizável apresentada.
  5. Mostre a passagem de \(|\mathcal{H}|e^{-\varepsilon N}\leq\delta\) para a cota sobre \(N\).
  6. Por que uma classe infinita não é automaticamente impossível de aprender?
  7. Dê um exemplo em que a hipótese i.i.d. falha.
  8. Diferencie complexidade amostral de eficiência computacional.
  9. Explique por que uma garantia PAC não substitui um conjunto de teste.

3.3 2.3 Treinar e Testar

Uma hipótese é escolhida porque se ajusta aos dados disponíveis. Avaliá-la nos mesmos exemplos usados para escolhê-la produz uma estimativa otimista: o modelo já teve oportunidade de adaptar-se a particularidades dessa amostra. Para estimar generalização, precisamos de dados que não tenham participado das escolhas.

A prática usual divide as observações em conjuntos com papéis distintos:

  • treinamento: ajusta os parâmetros do modelo;
  • validação: escolhe hiperparâmetros, atributos, arquitetura e limiares;
  • teste: estima uma única vez o desempenho da configuração final.
Figure 3.3: Os dados de treino ajustam parâmetros, a validação orienta escolhas e o teste permanece isolado até a avaliação final.

3.3.1 Parâmetros e hiperparâmetros

Parâmetros são aprendidos diretamente pelo algoritmo de treinamento. Em uma função linear, são os pesos \(\mathbf{w}\) e o viés \(b\).

Hiperparâmetros controlam o método, mas não são ajustados pela mesma minimização. Exemplos incluem taxa de aprendizado, intensidade de regularização, número de camadas, profundidade de uma árvore e quantidade de vizinhos.

Treinar em \(D_{\text{treino}}\) produz

\[ \widehat{\theta}_\lambda \in \underset{\theta}{\operatorname{argmin}} \;\widehat{R}_{\text{treino}}(h_{\theta,\lambda}), \]

em que \(\lambda\) representa uma configuração de hiperparâmetros. A validação escolhe

\[ \widehat{\lambda} \in \underset{\lambda\in\Lambda}{\operatorname{argmin}} \;\widehat{R}_{\text{val}}(h_{\widehat{\theta}_\lambda,\lambda}). \]

Somente após fixar \(\widehat{\lambda}\) avaliamos a configuração final no teste.

3.3.2 Holdout

No protocolo holdout, fazemos uma única divisão dos dados. Uma proporção ilustrativa é

\[ 70\%\text{ treino},\qquad 15\%\text{ validação},\qquad 15\%\text{ teste}. \]

Não existe uma proporção universal. Com milhões de exemplos, uma pequena fração pode formar um teste preciso. Com poucos dados, reservar uma parte grande reduz demais o treinamento e torna a validação instável.

A divisão deve ser feita antes da exploração orientada pelos rótulos. Uma semente pseudoaleatória registrada permite reproduzir a partição, mas testar muitas sementes e escolher a mais favorável também constitui uma forma de sobreajuste.

ImportantTeste não é validação

Se uma decisão muda depois que observamos o resultado no teste, então o teste participou do desenvolvimento. Ele deve ser considerado validação, e um novo conjunto independente será necessário para avaliação final.

3.3.3 Independência e representatividade

A validade do holdout depende de treino, validação e teste representarem o cenário de uso sem compartilhar informação indevida. Em uma divisão aleatória i.i.d., esperamos que os subconjuntos tenham distribuições semelhantes.

Entretanto, a divisão aleatória simples não é adequada em todos os casos:

  • em séries temporais, o futuro não pode aparecer no treino de uma previsão do passado;
  • em dados de pacientes, registros da mesma pessoa não devem ficar em subconjuntos diferentes;
  • em imagens extraídas de um vídeo, quadros vizinhos são quase duplicados;
  • em recomendação, podemos querer testar usuários ou itens ainda não observados;
  • em implantação geográfica, pode ser necessário reservar regiões inteiras.

A unidade de independência deve corresponder ao uso. Se a previsão será feita para novas pessoas, a divisão precisa ocorrer por pessoa, não por registro.

3.3.4 Divisão estratificada

Em classificação desbalanceada, uma divisão puramente aleatória pode produzir poucos exemplos da classe rara. A estratificação preserva aproximadamente as proporções das classes em cada subconjunto.

Se há \(1\,000\) exemplos, dos quais \(100\) são positivos, uma divisão estratificada de \(80\%/20\%\) coloca aproximadamente \(80\) positivos no treino e \(20\) no teste.

Estratificar não cria informação nova e não resolve uma classe extremamente rara. Também não deve violar grupos ou tempo. Quando há várias restrições, usamos uma estratégia que respeite primeiro a estrutura causal do conjunto de dados.

3.3.5 Vazamento de dados

Vazamento ocorre quando informação indisponível no momento real da previsão influencia o treinamento ou a avaliação. O resultado parece melhor do que o sistema será em produção.

Exemplos:

  • normalizar usando média e desvio calculados em todos os dados;
  • escolher atributos observando correlação no conjunto de teste;
  • imputar valores ausentes antes da divisão;
  • incluir uma variável registrada depois do evento previsto;
  • manter cópias do mesmo exemplo em treino e teste.

Todo pré-processamento que aprende alguma quantidade deve ser ajustado somente no treino. Para uma padronização,

\[ z_j =\frac{x_j-\mu_j}{\sigma_j}, \]

\(\mu_j\) e \(\sigma_j\) são calculados em \(D_{\text{treino}}\) e depois aplicados, sem reajuste, à validação e ao teste.

Uma pipeline reúne pré-processamento e modelo para que cada etapa seja ajustada dentro do protocolo correto.

3.3.6 Validação cruzada \(k\)-fold

Quando os dados são limitados, uma única validação pode depender muito da divisão. Na validação cruzada \(k\)-fold, separamos os dados de desenvolvimento em \(k\) blocos aproximadamente iguais:

\[ D_{\text{desenv}} =F_1\cup F_2\cup\cdots\cup F_k. \]

Para cada \(j\), treinamos em todos os blocos exceto \(F_j\) e avaliamos em \(F_j\). A estimativa é

\[ \widehat{R}_{CV} =\frac{1}{k}\sum_{j=1}^{k} \widehat{R}_{F_j}(h^{(-j)}), \]

em que \(h^{(-j)}\) foi treinada sem o bloco \(F_j\).

Cada exemplo participa da validação uma vez e do treinamento \(k-1\) vezes. Valores comuns são \(k=5\) ou \(k=10\), mas a escolha depende do custo computacional e da quantidade de dados.

É importante que o teste final permaneça fora da validação cruzada. Usamos os folds para escolher a configuração; depois treinamos a configuração escolhida nos dados de desenvolvimento e avaliamos no teste isolado.

3.3.7 Validação cruzada estratificada e por grupos

A validação cruzada também precisa respeitar a estrutura dos dados.

  • Estratificada: preserva proporções de classes em cada fold.
  • Por grupos: mantém todos os exemplos de um grupo no mesmo fold.
  • Temporal: usa blocos que respeitam a ordem, treinando no passado e validando no futuro.

Em previsão temporal, uma forma progressiva é

\[ \{1,\ldots,t_1\}\to\{t_1+1,\ldots,t_2\}, \]

seguida por

\[ \{1,\ldots,t_2\}\to\{t_2+1,\ldots,t_3\}. \]

Isso imita o modo como o sistema acumulará histórico e fará previsões futuras.

3.3.8 Amostragem aleatória repetida

O holdout repetido, também chamado de random subsampling, cria várias divisões aleatórias treino-validação. Para cada repetição \(r\), treinamos uma nova hipótese \(h_r\) e calculamos uma métrica \(M_r\).

Relatamos, por exemplo,

\[ \overline{M} =\frac{1}{R}\sum_{r=1}^{R}M_r \]

e a variabilidade entre repetições. Diferentemente do \(k\)-fold, um exemplo pode aparecer na validação várias vezes e outro nenhuma vez.

Esse protocolo mede a sensibilidade do procedimento à divisão dos dados. Os valores não são totalmente independentes porque as partições se sobrepõem; a dispersão deve ser interpretada como diagnóstico, não automaticamente como intervalo de confiança clássico.

3.3.9 Validação cruzada aninhada

Se usamos validação cruzada tanto para escolher hiperparâmetros quanto para estimar desempenho, podemos obter otimismo. A validação cruzada aninhada usa dois níveis:

  1. folds internos escolhem hiperparâmetros;
  2. um fold externo, que não participou da escolha, avalia o procedimento.

O ciclo externo estima o desempenho do processo completo de seleção. Esse método é útil quando o conjunto é pequeno e muitas configurações são comparadas, embora seja computacionalmente mais caro.

3.3.10 Matriz de confusão no teste

Para \(K\) classes, definimos a matriz \(C\in\mathbb{N}^{K\times K}\) por

\[ C_{ij} =\#\{(x,y)\in D_{\text{teste}} \mid y=i,\;h(x)=j\}. \]

Nesta convenção, linhas são classes verdadeiras e colunas são classes previstas. A diagonal contém acertos; elementos fora da diagonal mostram quais classes foram confundidas.

Um exemplo é

alvo \(\backslash\) previsão classe 1 classe 2 classe 3
classe 1 7 2 1
classe 2 1 8 1
classe 3 1 0 9

A acurácia é

\[ \frac{7+8+9}{30}=0{,}8. \]

A matriz é mais informativa do que a acurácia isolada porque revela a direção dos erros.

3.3.11 Incerteza da estimativa de teste

O desempenho observado no teste ainda é uma estimativa aleatória. Para classificação, se \(M\) exemplos de teste são aproximadamente independentes e a taxa observada de erro é \(\widehat{p}\), um erro-padrão aproximado é

\[ \operatorname{EP}(\widehat{p}) \approx \sqrt{\frac{\widehat{p}(1-\widehat{p})}{M}}. \]

Com \(\widehat{p}=0{,}10\) e \(M=1\,000\),

\[ \operatorname{EP} \approx \sqrt{\frac{0{,}1\cdot0{,}9}{1\,000}} \approx0{,}0095. \]

Um teste pequeno produz uma estimativa instável. Para proporções próximas de \(0\) ou \(1\), amostras pequenas ou dependência entre exemplos, devemos usar métodos de intervalo adequados em vez de depender apenas dessa aproximação.

3.3.12 Escolha de limiar

Modelos probabilísticos frequentemente produzem uma pontuação \(p(x)\). Escolher um limiar com base no teste vaza informação. O procedimento correto é:

  1. treinar o modelo no treino;
  2. escolher o limiar na validação, considerando a métrica ou o custo;
  3. congelar modelo e limiar;
  4. avaliar ambos no teste.

O mesmo vale para seleção de atributos, regularização, quantidade de épocas e qualquer decisão guiada por desempenho.

3.3.13 Um protocolo recomendado

Para um projeto supervisionado típico:

  1. defina a unidade de divisão e reserve o teste;
  2. construa uma pipeline de pré-processamento e modelo;
  3. use treino e validação, ou validação cruzada, para escolhas;
  4. registre a configuração final;
  5. se apropriado, reajuste essa configuração em treino mais validação;
  6. avalie uma única vez no teste;
  7. relate métricas, incerteza, tamanho dos conjuntos e estratégia de divisão;
  8. monitore mudança de distribuição após a implantação.

Reajustar em treino mais validação é permitido depois que todas as escolhas estão congeladas. O teste continua isolado. Se o resultado de teste motivar nova alteração, inicia-se outra rodada de desenvolvimento e será preciso obter uma avaliação final independente.

3.3.14 Reprodutibilidade

Uma avaliação reproduzível registra:

  • versão e origem dos dados;
  • critérios de inclusão e exclusão;
  • identificadores ou índices de cada partição;
  • semente aleatória;
  • etapas de pré-processamento;
  • hiperparâmetros e critério de seleção;
  • métricas e respectivas definições;
  • versão do código e das dependências.

Registrar somente a semente não basta se os dados ou a biblioteca mudarem.

3.3.15 Relação com a teoria

A teoria PAC pergunta quando o risco empírico se aproxima do risco esperado sob certas hipóteses. O protocolo treino-validação-teste fornece uma avaliação operacional para um conjunto de dados concreto.

Este livro usa análises teóricas para compreender algoritmos, mas exemplos computacionais devem manter avaliação separada sempre que afirmarem desempenho preditivo. Não devemos confiar apenas no erro de treinamento.

WarningRegra de ouro

Qualquer dado usado para escolher o modelo pertence ao processo de desenvolvimento. Somente dados que permaneceram intocados podem sustentar uma avaliação final honesta.

3.3.16 Exercícios de fixação

  1. Diferencie parâmetros, hiperparâmetros e métricas.
  2. Explique por que normalizar antes da divisão causa vazamento.
  3. Proponha uma divisão adequada para várias consultas do mesmo usuário.
  4. Em que situação uma divisão temporal é necessária?
  5. Descreva o procedimento de validação cruzada \(5\)-fold.
  6. Diferencie holdout repetido e validação cruzada.
  7. Por que a validação cruzada aninhada reduz o viés de seleção?
  8. Calcule a acurácia da matriz de confusão apresentada e a revocação da classe 2.
  9. Para \(\widehat{p}=0{,}2\) e \(M=400\), calcule o erro-padrão aproximado.
  10. Explique o que fazer se o resultado de teste motivar uma nova escolha de modelo.

3.4 Exercícios de múltipla escolha

Assinale a única alternativa correta em cada questão. O gabarito comentado está recolhido ao final da seção.

  1. A perda zero–um de um classificador vale \(1\) quando:

    1. a previsão está correta.
    2. a previsão difere do rótulo verdadeiro.
    3. a probabilidade prevista é exatamente \(1\).
    4. o conjunto de teste está vazio.

  2. Em uma aplicação médica na qual deixar de detectar uma doença é muito grave, qual medida merece atenção especial?

    1. Revocação da classe positiva.
    2. Número de atributos.
    3. Erro de arredondamento.
    4. Cardinalidade do espaço de saída.

  3. Em comparação com o erro quadrático médio, o erro absoluto médio é, em geral:

    1. mais sensível a valores atípicos.
    2. menos sensível a valores atípicos.
    3. sempre igual a zero.
    4. aplicável somente à classificação.

  4. Na entropia cruzada binária, atribuir probabilidade próxima de zero ao evento que realmente ocorreu produz:

    1. perda próxima de zero.
    2. perda negativa.
    3. perda muito elevada.
    4. nenhuma alteração na perda.

  5. Na linguagem PAC, o parâmetro \(\epsilon\) controla:

    1. a tolerância de erro ou precisão desejada.
    2. a quantidade de classes do problema.
    3. a semente do gerador aleatório.
    4. o custo de uma multiplicação matricial.

  6. Ainda no contexto PAC, \(1-\delta\) representa:

    1. a taxa de aprendizado.
    2. o nível de confiança da garantia.
    3. o erro empírico exato.
    4. o número de hipóteses.

  7. Se aumentamos a complexidade da classe de hipóteses e mantemos os demais fatores, a quantidade de dados necessária para uma mesma garantia tende a:

    1. diminuir até zero.
    2. permanecer sempre idêntica.
    3. aumentar.
    4. tornar-se independente de \(\epsilon\).

  8. Qual prática caracteriza vazamento de dados?

    1. Ajustar o normalizador somente com o treino.
    2. Escolher hiperparâmetros usando validação.
    3. Calcular média e desvio com todo o conjunto antes da divisão.
    4. Avaliar uma única vez no teste ao final.

  9. Quando várias observações pertencem ao mesmo paciente, a divisão mais segura é:

    1. sortear cada observação independentemente.
    2. manter todas as observações de cada paciente no mesmo subconjunto.
    3. duplicar pacientes raros no teste.
    4. usar treino e teste com os mesmos pacientes obrigatoriamente.

  10. Depois que o conjunto de teste influenciou uma escolha de modelo, ele deve ser tratado como:

    1. parte do processo de desenvolvimento, e uma nova avaliação final exige dados intocados.
    2. um teste final ainda perfeitamente independente.
    3. um conjunto sem qualquer utilidade.
    4. uma amostra de treinamento sem rótulos.
  1. b. A perda zero–um registra erro com \(1\) e acerto com \(0\).
  2. a. A revocação mede a fração dos positivos reais que foram detectados e, portanto, evidencia falsos negativos.
  3. b. O quadrado amplifica resíduos grandes; o valor absoluto cresce apenas linearmente.
  4. c. O logaritmo penaliza fortemente previsões confiantes e incorretas.
  5. a. \(\epsilon\) expressa quão próximo do desempenho desejado o resultado deve estar.
  6. b. \(\delta\) limita a probabilidade de falha; assim, \(1-\delta\) é a confiança.
  7. c. Uma classe mais rica exige mais evidência para controlar a seleção entre suas hipóteses.
  8. c. As estatísticas incorporariam informação dos conjuntos que deveriam permanecer independentes.
  9. b. A separação por grupos impede que informações específicas do paciente apareçam simultaneamente no treino e na avaliação.
  10. a. Toda informação usada para decidir passa a integrar o desenvolvimento; a estimativa final requer novos dados independentes.