4 Quão bem aprendemos?

Nos capítulos anteriores, definimos aprendizado como a construção de uma hipótese a partir de uma amostra finita. Também distinguimos o erro observado nos dados de treinamento do erro esperado em exemplos futuros. Agora enfrentaremos a pergunta quantitativa: quando o erro observado fornece informação confiável sobre o erro verdadeiro?

Considere uma hipótese \(h\) e uma amostra i.i.d.

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

Para uma perda limitada, calculamos o risco empírico

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

mas desejamos conhecer o risco esperado

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

Como \(P\) é desconhecida, \(R_P(h)\) não pode ser calculado diretamente. A teoria de generalização estuda a diferença

\[ \bigl|\widehat{R}_D(h)-R_P(h)\bigr|. \]

Uma diferença pequena indica que a amostra estima bem o desempenho da hipótese. Uma diferença grande significa que o resultado observado pode ser uma descrição enganosa da população.

A primeira dificuldade: a amostra é aleatória. Se repetirmos a coleta, obteremos outros exemplos e outro risco empírico. Precisamos de uma afirmação probabilística que limite a chance de um desvio grande. A desigualdade de Hoeffding cumprirá esse papel para médias de variáveis independentes e limitadas.

A segunda dificuldade: a hipótese também depende da amostra. Hoeffding controla diretamente uma hipótese fixada antes de observar os dados. Um algoritmo, porém, examina os dados e escolhe

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

Se procurarmos entre muitas hipóteses, alguma pode parecer boa apenas por acaso. Esse efeito é semelhante a lançar muitas moedas e selecionar a que apresentou a maior proporção de caras: a seleção torna o resultado extremo menos surpreendente.

A terceira dificuldade: muitas classes são infinitas. Existem infinitas retas, planos e combinações de pesos reais. Não podemos simplesmente contar todos os elementos de \(\mathcal{H}\). Precisamos medir quantos comportamentos distintos a classe consegue produzir sobre uma amostra finita.

A dimensão de Vapnik–Chervonenkis, ou dimensão VC, mede essa capacidade em classificação binária. Ela é o maior tamanho de um conjunto que pode ser estilhaçado pela classe: todas as suas rotulações binárias podem ser realizadas por alguma hipótese.

Para classificadores lineares no plano, a dimensão VC é \(3\):

existem três pontos que podem receber quaisquer rótulos e ainda ser separados por uma reta;
nenhum conjunto de quatro pontos pode realizar, por retas, todas as \(2^4\) rotulações possíveis.

Os quatro vértices de um quadrado com rótulos alternados formam o conhecido padrão XOR e mostram uma rotulação que uma reta não separa. Para concluir que a dimensão é \(3\), porém, precisamos ainda argumentar que todo conjunto de quatro pontos falha em alguma rotulação, não apenas exibir um conjunto particular.

O roteiro do capítulo. Desenvolveremos a análise em etapas:

entenderemos o defeito de selecionar hipóteses usando a mesma amostra em que medimos o erro;
aplicaremos a desigualdade de Hoeffding a uma hipótese fixa e depois a classes finitas;
substituiremos a cardinalidade de uma classe infinita pelo número de rotulações que ela induz em amostras finitas;
definiremos dimensão VC e obteremos cotas de generalização dependentes da capacidade.

Uma garantia típica terá a forma

\[ P_D\left( \sup_{h\in\mathcal{H}} \bigl|\widehat{R}_D(h)-R_P(h)\bigr| >\varepsilon \right) \leq\delta. \]

O supremo exige que a aproximação seja válida simultaneamente para todas as hipóteses. Isso permite escolher uma hipótese depois de observar a amostra sem perder a garantia.

4.0.1 Capacidade, dados e confiança

As cotas revelarão três dependências gerais:

maior precisão, isto é, menor \(\varepsilon\), requer mais exemplos;
maior confiança, isto é, menor \(\delta\), requer mais exemplos;
uma classe mais expressiva requer mais exemplos para controlar seleção e sobreajuste.

Essas relações não justificam regras universais como “dez exemplos por parâmetro”. A quantidade necessária depende da perda, da capacidade efetiva, da distribuição, do ruído e do tipo de garantia. Cotas teóricas de pior caso podem ser conservadoras, mas sua estrutura explica quais fatores tornam o aprendizado mais difícil.

4.0.2 O que as cotas podem e não podem fazer

Uma cota de generalização não escolhe automaticamente a melhor representação, não corrige rótulos incorretos e não garante estabilidade quando a distribuição muda. Ela responde a uma pergunta condicional: sob determinadas hipóteses, qual é a probabilidade de o desempenho empírico diferir muito do esperado?

Também devemos distinguir:

cota teórica: válida para uma família de situações, muitas vezes conservadora;
estimativa experimental: calculada em validação ou teste para um modelo e conjunto concretos.

As duas são complementares. A teoria explica por que o procedimento pode generalizar; a avaliação mede como uma implementação específica se comportou.

Uma mudança de perspectiva

O problema não é apenas encontrar uma hipótese com baixo erro de treinamento. É controlar quantas oportunidades o algoritmo teve de encontrar um ajuste acidental e demonstrar que o baixo erro contém informação sobre novos dados.

4.0.3 Exemplo motivador: muitas moedas

Suponha \(M\) moedas honestas, cada uma lançada \(N\) vezes. Para uma moeda fixada antes do experimento, a frequência de caras tende a ficar próxima de \(1/2\). Entretanto, se escolhermos depois a moeda com menor frequência de caras, o valor selecionado será mais extremo à medida que \(M\) cresce.

A moeda selecionada desempenha o papel da hipótese escolhida pelo algoritmo. Cada moeda individual possui boa concentração, mas controlar a seleção exige considerar todas as candidatas. Para um conjunto finito, faremos isso com a cota da união; para classes infinitas, usaremos capacidade combinatória.

4.0.4 Perguntas de preparação

Diferencie risco empírico e risco esperado.
Por que uma garantia para uma hipótese fixa não pode ser aplicada diretamente a \(A(D)\)?
Como aumentar a quantidade de hipóteses afeta a chance de encontrar um ajuste acidental?
O que significa estilhaçar um conjunto?
Por que o padrão XOR de quatro pontos, isoladamente, não completa a prova de que retas no plano têm dimensão VC igual a \(3\)?
Explique por que não existe uma regra universal de exemplos por parâmetro.

4.1 Defeito

Dada uma hipótese \(h\), podemos calcular seu risco empírico na amostra,

\[ \widehat{R}_D(h), \]

mas não seu risco esperado exato,

\[ R_P(h), \]

porque a distribuição \(P\) é desconhecida. Chamaremos de lacuna de generalização — ou, seguindo a terminologia histórica deste texto, defeito — a diferença

\[ \Delta_D(h) = R_P(h)-\widehat{R}_D(h). \]

A identidade

\[ R_P(h) = \widehat{R}_D(h)+\Delta_D(h) \]

mostra os dois ingredientes de um bom resultado: erro de treinamento pequeno e lacuna controlada.

4.1.1 Lacuna assinada e lacuna absoluta

\(\Delta_D(h)\) é uma quantidade assinada:

\(\Delta_D(h)>0\): o treino subestimou o erro verdadeiro;
\(\Delta_D(h)<0\): o treino superestimou o erro verdadeiro;
\(\Delta_D(h)\approx0\): a amostra estimou bem o risco.

Para uma garantia que não dependa da direção, usamos

\[ \left| R_P(h)-\widehat{R}_D(h) \right|. \]

Então,

\[ R_P(h) \leq \widehat{R}_D(h) + \left| R_P(h)-\widehat{R}_D(h) \right|. \]

Não tentamos “minimizar a lacuna” diretamente, pois ela envolve \(R_P(h)\), que não conhecemos. Procuramos demonstrar que ela é pequena com alta probabilidade.

4.1.2 Classificação binária

Para \(Y=\{-1,+1\}\) e perda zero-um,

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

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

O primeiro é a frequência de erros nos \(N\) exemplos; o segundo é a probabilidade de erro em um novo exemplo.

Se \(\widehat{R}_D(h)=0{,}02\) e uma cota garante

\[ \left|R_P(h)-\widehat{R}_D(h)\right| \leq0{,}03, \]

então

\[ R_P(h)\leq0{,}05. \]

A cota não afirma que o risco seja exatamente \(5\%\); fornece um limite superior.

4.1.3 Uma hipótese fixada antes dos dados

Suponha que \(h\) seja escolhida sem observar \(D\). Cada variável

\[ Z_i = \mathbb{1}[h(x_i)\neq y_i] \]

é Bernoulli, com média

\[ \mathbb{E}[Z_i]=R_P(h). \]

O risco empírico é a média

\[ \widehat{R}_D(h) = \frac{1}{N}\sum_{i=1}^{N}Z_i. \]

Uma desigualdade de concentração pode então limitar a probabilidade de essa média afastar-se de sua esperança. Para uma hipótese fixa, a amostra funciona como uma pesquisa de opinião: mais observações tornam desvios grandes menos prováveis.

4.1.4 O defeito da seleção

Um algoritmo não avalia apenas uma hipótese fixada antecipadamente. Ele usa os dados para escolher

\[ \widehat{h} \in \underset{h\in\mathcal{H}}{\operatorname{argmin}} \;\widehat{R}_D(h). \]

A hipótese escolhida é uma variável aleatória dependente de \(D\). Aplicar diretamente uma garantia para \(h\) fixa a \(\widehat{h}=A(D)\) ignora essa dependência.

Figure 4.1: Ao comparar muitas hipóteses, a selecionada pelo menor erro de treino pode ser justamente aquela que mais se beneficiou de uma flutuação da amostra.

Mesmo que cada risco empírico seja individualmente um estimador razoável, o menor entre muitos estimadores tende a ser otimista. Esse fenômeno é chamado de viés de seleção ou efeito de comparações múltiplas.

4.1.5 Analogia das moedas

Imagine \(M\) moedas honestas lançadas \(N\) vezes. Para cada moeda \(j\), seja \(\nu_j\) a frequência de caras. Cada \(\nu_j\) concentra-se em torno de \(1/2\).

Agora selecionamos

\[ j^* \in \underset{1\leq j\leq M}{\operatorname{argmin}} \;\nu_j. \]

\(\nu_{j^*}\) tende a ficar abaixo de \(1/2\), não porque a moeda escolhida seja desonesta, mas porque procuramos deliberadamente a flutuação mais baixa entre \(M\) tentativas.

Quanto maior \(M\), maior a oportunidade de observar um valor extremo. Em aprendizado, hipóteses desempenham o papel das moedas e o erro empírico desempenha o papel da frequência observada.

4.1.6 Controle uniforme

Para permitir seleção dependente dos dados, buscamos controlar todas as hipóteses simultaneamente:

\[ \sup_{h\in\mathcal{H}} \left| R_P(h)-\widehat{R}_D(h) \right|. \]

Se, para uma amostra, vale

\[ \sup_{h\in\mathcal{H}} \left| R_P(h)-\widehat{R}_D(h) \right| \leq\varepsilon, \]

então a desigualdade vale para qualquer hipótese da classe, inclusive aquela escolhida depois de observar \(D\).

Esse é o motivo para uma cota uniforme. A complexidade de \(\mathcal{H}\) aparece porque controlar mais comportamentos simultaneamente é mais difícil.

4.1.7 Decomposição para minimização do risco empírico

Seja

\[ \widehat{h} \in \underset{h\in\mathcal{H}}{\operatorname{argmin}} \widehat{R}_D(h) \]

e seja

\[ h^* \in \underset{h\in\mathcal{H}}{\operatorname{argmin}} R_P(h). \]

Suponha que o desvio uniforme seja no máximo \(\varepsilon\):

\[ \sup_{h\in\mathcal{H}} \left| R_P(h)-\widehat{R}_D(h) \right| \leq\varepsilon. \]

Então,

\[ \begin{aligned} R_P(\widehat{h}) &\leq \widehat{R}_D(\widehat{h})+\varepsilon\\ &\leq \widehat{R}_D(h^*)+\varepsilon\\ &\leq R_P(h^*)+2\varepsilon. \end{aligned} \]

A segunda desigualdade usa o fato de que \(\widehat{h}\) minimiza o risco empírico. Portanto,

\[ R_P(\widehat{h})-R_P(h^*) \leq2\varepsilon. \]

Essa derivação mostra como convergência uniforme transforma minimização empírica em uma garantia de excesso de risco.

4.1.8 Erro de aproximação e erro de estimação

O desempenho pode ser separado conceitualmente em:

erro de aproximação: a melhor hipótese de \(\mathcal{H}\) ainda pode ser inadequada;
erro de estimação: a amostra finita pode levar o algoritmo a escolher uma hipótese pior do que a melhor da classe;
erro de otimização: o procedimento numérico pode não encontrar o mínimo empírico.

Uma classe maior tende a reduzir o erro de aproximação, mas pode aumentar o erro de estimação. Mais dados reduzem a incerteza estatística, mas não corrigem uma classe que não representa o padrão.

4.1.9 Sobreajuste como lacuna

O sobreajuste ocorre quando o modelo aproveita detalhes específicos da amostra que não se repetem na população. Um sinal típico é

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

A lacuna pode crescer quando:

a classe possui alta capacidade;
comparamos muitas configurações;
a amostra é pequena;
os dados contêm ruído;
repetimos decisões usando o mesmo conjunto de validação.

Regularização, validação independente e controle de capacidade reduzem oportunidades de ajuste acidental, mas não substituem dados representativos.

4.1.10 Uma estimativa não observável

Durante treinamento conhecemos \(\widehat{R}_D(h)\), mas não \(\Delta_D(h)\), pois este depende de \(R_P(h)\). Uma cota teórica limita a lacuna sob hipóteses. Um conjunto de teste independente fornece outra estimativa empírica:

\[ \widehat{R}_{\text{teste}}(h) \approx R_P(h). \]

Teste e teoria abordam o mesmo risco por caminhos diferentes, ambos sujeitos a condições.

Escolher e avaliar no mesmo conjunto

Quanto mais decisões forem tomadas olhando uma métrica, menos esse conjunto poderá ser tratado como avaliação independente. O sobreajuste pode ocorrer na validação, não apenas no treinamento.

4.1.11 Exemplo numérico

Considere três hipóteses:

Hipótese	Erro de treino	Erro de validação
\(h_1\)	\(0{,}12\)	\(0{,}13\)
\(h_2\)	\(0{,}07\)	\(0{,}11\)
\(h_3\)	\(0{,}00\)	\(0{,}24\)

Se escolhermos apenas pelo treino, \(h_3\) vence. A validação sugere que ela se ajustou demais. \(h_2\) possui menor erro de validação, embora não tenha o menor erro de treino.

Não conhecemos o risco verdadeiro dessas hipóteses, mas dados independentes ajudam a detectar a discrepância.

4.1.12 Exercícios de fixação

Interprete o sinal de \(\Delta_D(h)\).
Se \(\widehat{R}_D(h)=0{,}08\) e a lacuna absoluta é no máximo \(0{,}04\), qual cota obtemos para \(R_P(h)\)?
Por que a hipótese escolhida por minimização empírica não é fixa em relação à amostra?
Explique a analogia entre muitas moedas e muitas hipóteses.
Reproduza a decomposição que leva a \(R_P(\widehat{h})\leq R_P(h^*)+2\varepsilon\).
Diferencie erro de aproximação, estimação e otimização.
Dê um exemplo de sobreajuste ao conjunto de validação.
Por que não podemos calcular diretamente a lacuna de generalização durante o treinamento?

4.2 3.2 Desigualdade de Hoeffding

A desigualdade de Hoeffding controla o desvio entre a média de variáveis aleatórias limitadas e sua esperança. Ela é especialmente útil em aprendizado porque muitas perdas são limitadas e o risco empírico é uma média amostral.

4.2.1 Enunciado geral

Sejam \(Z_1,\ldots,Z_N\) variáveis aleatórias independentes, com

\[ a_i\leq Z_i\leq b_i. \]

Defina

\[ \overline{Z} =\frac{1}{N}\sum_{i=1}^{N}Z_i \]

\[ \mu =\mathbb{E}[\overline{Z}]. \]

Então, para \(\varepsilon>0\),

\[ P\left( |\overline{Z}-\mu|\geq\varepsilon \right) \leq 2\exp\left( -\frac{2N^2\varepsilon^2} {\sum_{i=1}^{N}(b_i-a_i)^2} \right). \]

Quando todas as variáveis pertencem a \([0,1]\), obtemos a forma conhecida:

\[ P\left( |\overline{Z}-\mu|\geq\varepsilon \right) \leq 2e^{-2N\varepsilon^2}. \]

A desigualdade é livre de distribuição: não exige que conheçamos a forma da distribuição de \(Z_i\). Exige independência e limites conhecidos.

Figure 4.2: À medida que \(N\) aumenta, a média amostral se concentra ao redor da esperança e a probabilidade nas caudas fora de \(\mu\pm\varepsilon\) diminui.

4.2.2 Interpretação

A cota decai exponencialmente em \(N\) e em \(\varepsilon^2\):

\[ 2e^{-2N\varepsilon^2}. \]

Isso significa:

mais exemplos tornam desvios fixos menos prováveis;
tolerar um desvio maior torna a garantia mais fácil;
reduzir o desvio desejado pela metade requer aproximadamente quatro vezes mais exemplos.

A cota pode ser maior que \(1\) para \(N\) pequeno ou \(\varepsilon\) muito pequeno. Como uma probabilidade nunca excede \(1\), podemos escrever

\[ P(\cdots) \leq \min\{1,2e^{-2N\varepsilon^2}\}. \]

Uma cota maior que \(1\) é válida, mas não informativa.

4.2.3 Aplicação a uma hipótese fixa

Fixe uma hipótese \(h\) antes de observar a amostra. Na classificação binária, defina

\[ Z_i =\mathbb{1}[h(x_i)\neq y_i]. \]

Cada \(Z_i\in\{0,1\}\) e, para exemplos i.i.d.,

\[ \mathbb{E}[Z_i] =R_P(h). \]

A média é exatamente o risco empírico:

\[ \overline{Z} =\widehat{R}_D(h). \]

Portanto,

\[ P_D\left( \left| \widehat{R}_D(h)-R_P(h) \right| \geq\varepsilon \right) \leq 2e^{-2N\varepsilon^2}. \]

Essa é uma garantia para uma hipótese fixa e independente de \(D\). O subscrito \(D\) lembra que a aleatoriedade está na amostra.

4.2.4 Forma de intervalo

Queremos uma afirmação com probabilidade de falha no máximo \(\delta\):

\[ 2e^{-2N\varepsilon^2} \leq\delta. \]

Isolando \(\varepsilon\),

\[ \varepsilon \geq \sqrt{ \frac{\log(2/\delta)}{2N} }. \]

Assim, com probabilidade de pelo menos \(1-\delta\),

\[ \left| \widehat{R}_D(h)-R_P(h) \right| \leq \sqrt{ \frac{\log(2/\delta)}{2N} }. \]

Equivalentemente,

\[ R_P(h) \leq \widehat{R}_D(h) + \sqrt{ \frac{\log(2/\delta)}{2N} }. \]

Essa é uma cota superior para o risco de uma hipótese previamente fixada.

4.2.5 Forma de complexidade amostral

Também podemos isolar \(N\). Para garantir desvio no máximo \(\varepsilon\) com confiança \(1-\delta\), basta

\[ N \geq \frac{\log(2/\delta)}{2\varepsilon^2}. \]

Por exemplo, com

\[ \varepsilon=0{,}05, \qquad \delta=0{,}05, \]

temos

\[ N \geq \frac{\log 40}{2(0{,}05)^2} \approx737{,}78. \]

Logo, \(738\) exemplos independentes são suficientes segundo essa cota para uma hipótese fixa. É uma garantia de pior caso; não afirma que toda aplicação necessitará exatamente dessa quantidade.

4.2.6 Exemplo numérico de intervalo

Suponha uma hipótese fixada avaliada em \(N=1\,000\) exemplos independentes, com erro observado

\[ \widehat{R}_D(h)=0{,}12. \]

Para \(\delta=0{,}05\),

\[ \varepsilon = \sqrt{ \frac{\log 40}{2\,000} } \approx0{,}0429. \]

Com confiança de pelo menos \(95\%\), Hoeffding garante

\[ R_P(h) \leq0{,}12+0{,}0429 =0{,}1629. \]

A cota bilateral também fornece limite inferior, truncado em zero:

\[ R_P(h) \in [0{,}0771,\;0{,}1629]. \]

Esse intervalo não é necessariamente o mais estreito para uma proporção binomial, mas é simples e não depende do valor desconhecido de \(R_P(h)\).

4.2.7 Forma unilateral

Se precisamos apenas limitar o risco por cima, uma versão unilateral fornece

\[ P_D\left( R_P(h)-\widehat{R}_D(h) \geq\varepsilon \right) \leq e^{-2N\varepsilon^2}. \]

Com probabilidade de pelo menos \(1-\delta\),

\[ R_P(h) \leq \widehat{R}_D(h) + \sqrt{ \frac{\log(1/\delta)}{2N} }. \]

A ausência do fator \(2\) melhora ligeiramente a cota porque controlamos somente uma direção do desvio.

4.2.8 Perdas limitadas

A aplicação não se restringe à perda zero-um. Se

\[ 0\leq\ell(h(x),y)\leq B, \]

podemos normalizar \(Z_i=\ell(h(x_i),y_i)/B\in[0,1]\). Resulta

\[ P_D\left( \left| \widehat{R}_D(h)-R_P(h) \right| \geq\varepsilon \right) \leq 2\exp\left( -\frac{2N\varepsilon^2}{B^2} \right). \]

Quanto maior o intervalo possível da perda, mais fraca é a concentração para o mesmo \(\varepsilon\).

Perdas não limitadas, como a quadrática sem restrição nas previsões e alvos, exigem hipóteses adicionais ou outras desigualdades. Não podemos aplicar Hoeffding diretamente sem um limite quase certo.

4.2.9 O problema da hipótese escolhida

Em aprendizado, usamos

\[ \widehat{h}=A(D), \]

portanto a hipótese depende da mesma amostra. A desigualdade para uma \(h\) fixa não pode ser simplesmente reescrita como

\[ P_D\left( \left| \widehat{R}_D(A(D))-R_P(A(D)) \right| \geq\varepsilon \right) \leq 2e^{-2N\varepsilon^2}. \]

Essa passagem seria injustificada: \(A(D)\) foi selecionada justamente por seu comportamento em \(D\).

Precisamos controlar todas as hipóteses que o algoritmo poderia escolher.

4.2.10 Classe finita e cota da união

\[ \mathcal{H} =\{h_1,\ldots,h_M\}, \]

então o evento de falha uniforme é

\[ \left\{ \exists h\in\mathcal{H}: \left| \widehat{R}_D(h)-R_P(h) \right| \geq\varepsilon \right\}. \]

Pela cota da união,

\[ \begin{aligned} &P_D\left( \exists h\in\mathcal{H}: \left| \widehat{R}_D(h)-R_P(h) \right| \geq\varepsilon \right)\\ &\quad\leq \sum_{h\in\mathcal{H}} P_D\left( \left| \widehat{R}_D(h)-R_P(h) \right| \geq\varepsilon \right)\\ &\quad\leq 2M e^{-2N\varepsilon^2}. \end{aligned} \]

No evento complementar, todas as hipóteses satisfazem a cota. Portanto, qualquer \(A(D)\in\mathcal{H}\) também satisfaz.

Observe que, dentro da união, cada \(h\) é fixa. O evento não deve ser escrito com \(h(D)\) para cada parcela.

4.2.11 Cota uniforme em forma de intervalo

Impondo

\[ 2M e^{-2N\varepsilon^2} \leq\delta, \]

obtemos

\[ \varepsilon \geq \sqrt{ \frac{\log(2M/\delta)}{2N} }. \]

Com probabilidade de pelo menos \(1-\delta\),

\[ \sup_{h\in\mathcal{H}} \left| \widehat{R}_D(h)-R_P(h) \right| \leq \sqrt{ \frac{\log(2M/\delta)}{2N} }. \]

Para a hipótese selecionada,

\[ R_P(A(D)) \leq \widehat{R}_D(A(D)) + \sqrt{ \frac{\log(2M/\delta)}{2N} }. \]

O preço de examinar \(M\) hipóteses aparece como \(\log M\) depois que isolamos \(\varepsilon\).

4.2.12 Complexidade amostral para classe finita

Isolando \(N\),

\[ N \geq \frac{ \log(2M/\delta) }{ 2\varepsilon^2 } \]

é suficiente para desvio uniforme no máximo \(\varepsilon\).

Se \(M=1\), recuperamos a cota para uma hipótese fixa. Se multiplicarmos o número de hipóteses por mil, adicionamos \(\log 1\,000\) ao numerador, não um fator mil ao tamanho necessário.

4.2.13 Exemplo com seleção

Considere \(M=100\) hipóteses, \(N=2\,000\) e \(\delta=0{,}05\). A largura uniforme é

\[ \varepsilon = \sqrt{ \frac{\log(2\cdot100/0{,}05)}{2\cdot2\,000} } = \sqrt{ \frac{\log 4\,000}{4\,000} } \approx0{,}0455. \]

Se a hipótese selecionada tem erro empírico \(0{,}08\), então

\[ R_P(A(D)) \leq0{,}1255 \]

com confiança de pelo menos \(95\%\), sob as condições da desigualdade.

4.2.14 O equilíbrio entre ajuste e capacidade

Uma classe maior pode conter uma hipótese com erro empírico menor, mas aumenta a penalidade de complexidade:

\[ \widehat{R}_D(h) + \sqrt{ \frac{\log(2M/\delta)}{2N} }. \]

Isso sugere uma ideia de minimização estrutural do risco: comparar não apenas o ajuste, mas ajuste mais uma penalidade de capacidade.

Não há uma oposição absoluta entre “erro empírico” e “erro verdadeiro”. O objetivo é escolher uma classe expressiva o suficiente para representar padrões, mas controlada o suficiente para generalizar com os dados disponíveis.

4.2.15 Limitações

Hoeffding não resolve todos os problemas:

exige independência;
exige variáveis limitadas;
a cota pode ser conservadora;
a união direta não ajuda quando \(\mathcal{H}\) é infinita;
não trata mudança de distribuição;
não corrige seleção feita fora da classe contabilizada.

Para classes infinitas, substituiremos \(M\) por uma medida do número de comportamentos relevantes sobre amostras finitas. Esse caminho leva à função de crescimento e à dimensão VC.

4.2.16 Exemplo computacional

from math import log, sqrt


def raio_hoeffding(n, delta, numero_hipoteses=1):
    return sqrt(log(2 * numero_hipoteses / delta) / (2 * n))


print(raio_hoeffding(1000, 0.05))
print(raio_hoeffding(2000, 0.05, numero_hipoteses=100))

O cálculo supõe perda em \([0,1]\). Para perda em \([0,B]\), multiplique o raio por \(B\).

4.2.17 Exercícios de fixação

Enuncie as condições da desigualdade de Hoeffding.
Calcule a cota bilateral para \(N=500\) e \(\varepsilon=0{,}1\).
Isole \(\varepsilon\) em \(2e^{-2N\varepsilon^2}\leq\delta\).
Quantos exemplos são suficientes para \(\varepsilon=0{,}02\) e \(\delta=0{,}01\) em uma hipótese fixa?
Por que Hoeffding não se aplica diretamente a \(A(D)\)?
Derive a cota \(2M e^{-2N\varepsilon^2}\) usando a união.
Para \(M=50\), \(N=1\,000\) e \(\delta=0{,}05\), calcule o raio uniforme.
Explique por que a dependência em \(M\) se torna logarítmica ao isolar \(\varepsilon\).
Dê um exemplo de perda não limitada à qual Hoeffding não pode ser aplicada diretamente.
Compare as formas bilateral e unilateral.

4.3 A dimensão de Vapnik–Chervonenkis

Para uma classe finita, a cota de Hoeffding uniforme contém \(\log|\mathcal{H}|\). Classes importantes, porém, possuem infinitas hipóteses: há infinitas retas no plano e infinitas escolhas de pesos reais.

A cardinalidade infinita superestima o número de comportamentos relevantes em uma amostra finita. Duas retas diferentes podem classificar os mesmos \(N\) pontos exatamente da mesma maneira. Para generalização, interessa contar as rotulações distintas que a classe consegue produzir sobre conjuntos finitos.

4.3.1 Restrições e dicotomias

Seja uma classe de classificadores binários

\[ \mathcal{H}\subseteq\{-1,+1\}^{X} \]

e um conjunto de pontos distintos

\[ S=\{x_1,\ldots,x_N\}\subseteq X. \]

A restrição de \(h\) a \(S\) é o vetor

\[ h|_S = \bigl(h(x_1),\ldots,h(x_N)\bigr) \in\{-1,+1\}^{N}. \]

O conjunto de dicotomias realizadas por \(\mathcal{H}\) em \(S\) é

\[ \mathcal{H}|_S = \left\{ \bigl(h(x_1),\ldots,h(x_N)\bigr) \mid h\in\mathcal{H} \right\}. \]

Embora \(\mathcal{H}\) possa ser infinita,

\[ |\mathcal{H}|_S| \leq2^N, \]

pois existem apenas \(2^N\) rotulações binárias dos \(N\) pontos.

Duas hipóteses que diferem fora de \(S\), mas coincidem em todos os pontos de \(S\), contam como uma única dicotomia sobre esse conjunto.

4.3.2 Função de crescimento

A função de crescimento é o maior número de dicotomias que a classe consegue realizar em qualquer conjunto de \(N\) pontos:

\[ m_{\mathcal{H}}(N) = \max_{\substack{S\subseteq X\\|S|=N}} |\mathcal{H}|_S|. \]

Também é comum usar a notação \(\Pi_{\mathcal{H}}(N)\). Sempre vale

\[ 1\leq m_{\mathcal{H}}(N)\leq2^N. \]

O máximo é tomado sobre a posição dos pontos. Um conjunto particular pode admitir poucas rotulações mesmo quando outro conjunto do mesmo tamanho admite todas.

4.3.3 Estilhaçamento

Dizemos que \(\mathcal{H}\) estilhaça \(S\) quando realiza todas as rotulações possíveis:

\[ |\mathcal{H}|_S|=2^{|S|}. \]

Equivalentemente,

\[ \forall\mathbf{y}\in\{-1,+1\}^{|S|}, \quad \exists h\in\mathcal{H} \quad\text{tal que}\quad h|_S=\mathbf{y}. \]

A ordem dos quantificadores é essencial: fixamos um único conjunto \(S\) e exigimos que, para cada rotulação, possa existir uma hipótese diferente.

Se a classe estilhaça algum conjunto de \(N\) pontos, então

\[ m_{\mathcal{H}}(N)=2^N. \]

Se nenhum conjunto de \(N\) pontos é estilhaçado, então

\[ m_{\mathcal{H}}(N)<2^N. \]

4.3.4 Dimensão VC

A dimensão de Vapnik–Chervonenkis é o maior tamanho de um conjunto estilhaçado:

\[ d_{\mathrm{VC}}(\mathcal{H}) = \sup \left\{ N\in\mathbb{N} \mid m_{\mathcal{H}}(N)=2^N \right\}. \]

Se conjuntos arbitrariamente grandes podem ser estilhaçados, definimos

\[ d_{\mathrm{VC}}(\mathcal{H})=\infty. \]

Se \(k\) é o menor inteiro para o qual

\[ m_{\mathcal{H}}(k)<2^k, \]

ele é chamado de ponto de interrupção. Quando existe,

\[ d_{\mathrm{VC}}(\mathcal{H})=k-1. \]

Para provar \(d_{\mathrm{VC}}(\mathcal{H})=d\), precisamos de duas partes:

cota inferior: exibir um conjunto de \(d\) pontos que é estilhaçado;
cota superior: provar que nenhum conjunto de \(d+1\) pontos pode ser estilhaçado.

Encontrar uma rotulação impossível em um conjunto particular fornece informação sobre aquele conjunto, mas não prova sozinho a cota superior para todos os conjuntos.

4.3.5 Exemplo 1: limiares na reta

Considere

\[ \mathcal{H}_{\mathrm{limiar}} = \left\{ h_a(x)= \begin{cases} -1, & x<a,\\ +1, & x\geq a \end{cases} \;\middle|\; a\in\mathbb{R} \right\}. \]

Para \(N\) pontos ordenados,

\[ x_1<x_2<\cdots<x_N, \]

o limiar pode ser colocado antes de todos, entre dois pontos consecutivos ou depois de todos. Existem \(N+1\) dicotomias:

\[ m_{\mathcal{H}_{\mathrm{limiar}}}(N)=N+1. \]

Um ponto é estilhaçado, pois podemos classificá-lo como \(-1\) ou \(+1\). Dois pontos não são estilhaçados: a rotulação \((+1,-1)\) contradiz a monotonicidade do limiar. Logo,

\[ d_{\mathrm{VC}}(\mathcal{H}_{\mathrm{limiar}})=1. \]

Se permitíssemos ambas as orientações do limiar, a classe seria diferente e a contagem precisaria ser refeita.

4.3.6 Exemplo 2: intervalos na reta

Agora considere classificadores positivos dentro de um intervalo:

\[ h_{a,b}(x) = \begin{cases} +1, & a\leq x\leq b,\\ -1, & \text{caso contrário}. \end{cases} \]

Sobre \(N\) pontos ordenados, os positivos formam um bloco consecutivo. Há

\[ \frac{N(N+1)}{2} \]

blocos não vazios e uma rotulação sem ponto positivo. Portanto,

\[ m_{\mathcal{H}_{\mathrm{int}}}(N) = \frac{N(N+1)}{2}+1. \]

Dois pontos podem receber qualquer uma das quatro rotulações. Três pontos não podem realizar \((+1,-1,+1)\), pois um intervalo que contém os extremos também contém o ponto central. Assim,

\[ d_{\mathrm{VC}}(\mathcal{H}_{\mathrm{int}})=2. \]

4.3.7 Exemplo 3: retas no plano

Considere semiplanos afins em \(\mathbb{R}^2\):

\[ \mathcal{H}_{\mathrm{reta}} = \left\{ \operatorname{sign} (\mathbf{w}^{\mathsf T}\mathbf{x}+b) \mid \mathbf{w}\in\mathbb{R}^2,\; b\in\mathbb{R} \right\}. \]

Três pontos não colineares podem ser estilhaçados. Para qualquer rotulação, uma reta separa os positivos dos negativos.

Figure 4.3: Retas realizam todas as oito rotulações de três pontos não colineares; a rotulação XOR em quatro vértices é um exemplo não separável.

Para a cota superior, considere qualquer conjunto de quatro pontos.

Se um ponto está no interior do triângulo formado pelos outros três, rotule o ponto interno como positivo e os demais como negativos. Nenhum semiplano o separa.
Se os quatro pontos estão em posição convexa, rotule vértices alternados como positivos. Surge o padrão XOR, que não é linearmente separável.
Degenerações colineares não aumentam a capacidade.

Logo, nenhum conjunto de quatro pontos é estilhaçado e

\[ d_{\mathrm{VC}}(\mathcal{H}_{\mathrm{reta}})=3. \]

Para quatro pontos em posição geral, retas realizam \(14\) das \(16\) rotulações: faltam as duas rotulações XOR com diagonais opostas.

4.3.8 Exemplo 4: semiplanos em \(\mathbb{R}^d\)

Para classificadores afins

\[ h_{\mathbf{w},b}(\mathbf{x}) = \operatorname{sign} (\mathbf{w}^{\mathsf T}\mathbf{x}+b) \]

em \(\mathbb{R}^d\),

\[ d_{\mathrm{VC}}=d+1. \]

A cota inferior pode ser demonstrada usando \(d+1\) pontos afim-independentes. A cota superior decorre da dependência afim de qualquer conjunto com \(d+2\) pontos e de um argumento de separação.

Ao incorporar uma coordenada constante,

\[ \widetilde{\mathbf{x}}=(1,\mathbf{x}), \]

o viés \(b\) passa a fazer parte de um vetor de \(d+1\) pesos. Isso ajuda a compreender o valor \(d+1\), mas contar parâmetros é apenas uma intuição, não uma prova geral de dimensão VC.

4.3.9 Exemplo 5: conjuntos convexos no plano

Considere a classe de todos os subconjuntos convexos de \(\mathbb{R}^2\), com rótulo positivo dentro do conjunto.

Para qualquer \(N\), escolha \(N\) pontos sobre uma circunferência. Dada uma rotulação, tome o fecho convexo dos pontos positivos. Nenhum ponto negativo da circunferência pertence a esse fecho, porque cada ponto é um vértice extremo da configuração. Os casos de todos positivos ou nenhum positivo também são realizáveis.

Portanto, a classe estilhaça conjuntos de qualquer tamanho:

\[ d_{\mathrm{VC}}(\mathcal{H}_{\mathrm{conv}})=\infty. \]

Esse exemplo mostra que uma descrição geométrica simples em palavras pode ter capacidade ilimitada.

4.3.10 Comparação dos exemplos

Classe	Função de crescimento	Dimensão VC
limiar orientado em \(\mathbb{R}\)	\(N+1\)	\(1\)
intervalo em \(\mathbb{R}\)	\(\frac{N(N+1)}{2}+1\)	\(2\)
semiplano afim em \(\mathbb{R}^2\)	\(2^N\) até \(N=3\); \(m(4)=14\)	\(3\)
semiplano afim em \(\mathbb{R}^d\)	crescimento polinomial após \(d+1\)	\(d+1\)
conjuntos convexos em \(\mathbb{R}^2\)	\(2^N\) para todo \(N\)	\(\infty\)

A função de crescimento contém mais informação que um único número. A dimensão VC identifica o ponto a partir do qual o crescimento deixa de ser máximo; o próximo resultado mostrará que, depois desse ponto, o crescimento é limitado por um polinômio em \(N\).

4.3.11 Dimensão VC não é apenas número de parâmetros

Em alguns modelos lineares, dimensão VC e quantidade de parâmetros têm a mesma ordem. Isso não é uma lei universal. Restrições algébricas, parâmetros redundantes, precisão numérica e estrutura computacional alteram a capacidade.

Além disso, dimensão VC mede rotulações possíveis, não dificuldade de otimização, velocidade de treinamento ou qualidade da representação.

4.3.12 Como calcular uma dimensão VC

Um roteiro prático é:

escolha candidatos a conjuntos pequenos em posição favorável;
prove que todas as rotulações de um conjunto de tamanho \(d\) são realizáveis;
considere uma configuração arbitrária de \(d+1\) pontos;
construa, para cada possível configuração geométrica, ao menos uma rotulação impossível;
conclua as cotas inferior e superior.

Diagramas ajudam a descobrir a resposta, mas cada quantificador precisa aparecer na prova.

4.3.13 Exercícios de fixação

Liste as dicotomias de três pontos ordenados produzidas por limiares orientados.
Verifique a fórmula da função de crescimento de intervalos para \(N=3\).
Mostre explicitamente como três pontos não colineares realizam todas as oito rotulações por retas.
Explique por que o padrão XOR não é linearmente separável.
Complete o argumento da cota superior para quatro pontos quando um deles está dentro do triângulo dos outros.
Por que pontos sobre uma circunferência podem ser estilhaçados por conjuntos convexos?
Diferencie função de crescimento, ponto de interrupção e dimensão VC.
Dê um exemplo de afirmação em que contar parâmetros seria apenas heurístico.

4.3.14 Cota do número efetivo de hipóteses sobre uma amostra

A função de crescimento sempre satisfaz

\[ m_{\mathcal{H}}(N)\leq2^N. \]

Essa cota é exata quando a classe estilhaça algum conjunto de \(N\) pontos, mas é inútil para demonstrar controle de capacidade: substituir \(M\) por \(2^N\) em uma cota de união introduz um termo linear em \(N\) no expoente e pode impedir a convergência desejada.

A dimensão VC finita produz uma mudança decisiva. Depois do primeiro ponto de interrupção, a função de crescimento não pode continuar exponencial; ela passa a ser limitada por um polinômio.

Figure 4.4: Com dimensão VC finita, a função de crescimento deixa de acompanhar \(2^N\) após o ponto de interrupção e fica limitada por uma soma polinomial.

4.3.15 Lema de Sauer–Shelah

\[ d=d_{\mathrm{VC}}(\mathcal{H})<\infty, \]

então, para todo \(N\),

\[ m_{\mathcal{H}}(N) \leq \sum_{i=0}^{d} \binom{N}{i}. \]

Adotamos \(\binom{N}{i}=0\) quando \(i>N\). Para \(N\leq d\), a soma é

\[ \sum_{i=0}^{N}\binom{N}{i}=2^N, \]

compatível com a possibilidade de estilhaçamento. Para \(N>d\), a soma contém apenas os termos até \(d\) e cresce como um polinômio de grau \(d\).

Se \(k=d+1\) é o menor ponto de interrupção, a mesma cota pode ser escrita

\[ m_{\mathcal{H}}(N) \leq \sum_{i=0}^{k-1} \binom{N}{i}. \]

4.3.16 Exemplos da cota

Para \(d=1\),

\[ m_{\mathcal{H}}(N) \leq \binom{N}{0}+\binom{N}{1} =1+N. \]

A classe de limiares orientados atinge exatamente esse valor.

Para \(d=2\),

\[ m_{\mathcal{H}}(N) \leq 1+N+\frac{N(N-1)}{2}. \]

A classe de intervalos possui

\[ m_{\mathrm{int}}(N) = 1+\frac{N(N+1)}{2}, \]

que é maior do que a expressão de Sauer com \(d=2\)? Vamos comparar cuidadosamente:

\[ 1+N+\frac{N(N-1)}{2} = 1+\frac{N(N+1)}{2}. \]

As expressões são iguais. Portanto, intervalos também atingem a cota de Sauer.

Para semiplanos no plano, \(d=3\):

\[ m_{\mathcal{H}}(N) \leq 1+N+\binom{N}{2}+\binom{N}{3}. \]

Em \(N=4\),

\[ m_{\mathcal{H}}(4) \leq 1+4+6+4=15. \]

A função de crescimento real de semiplanos afins em posição geral é \(14\), portanto a cota é válida, mas não exata nesse ponto.

4.3.17 Ideia combinatória da prova

Defina \(M(N,d)\) como o maior número de dicotomias possível em \(N\) pontos para uma classe de dimensão VC no máximo \(d\). A prova usa a recorrência

\[ M(N,d) \leq M(N-1,d)+M(N-1,d-1). \]

Para compreender a recorrência, separe o último ponto \(x_N\). Ao restringir as dicotomias aos primeiros \(N-1\) pontos, há dois tipos:

padrões que admitem apenas uma extensão para \(x_N\);
padrões que admitem as duas extensões, \(-1\) e \(+1\).

O primeiro grupo contribui no máximo \(M(N-1,d)\). No segundo grupo, se fosse possível estilhaçar \(d\) pontos entre os primeiros \(N-1\), acrescentar \(x_N\) produziria um conjunto de \(d+1\) pontos estilhaçado. Portanto, a classe dos padrões com duas extensões possui dimensão no máximo \(d-1\) e contribui no máximo \(M(N-1,d-1)\).

Os valores de fronteira são

\[ M(N,0)=1 \]

\[ M(0,d)=1. \]

Aplicando a recorrência repetidamente e usando a identidade de Pascal,

\[ \binom{N}{i} = \binom{N-1}{i} + \binom{N-1}{i-1}, \]

obtemos

\[ M(N,d) \leq \sum_{i=0}^{d}\binom{N}{i}. \]

Essa é a estrutura central da prova de Sauer–Shelah.

4.3.18 Cota simplificada

Para \(1\leq d\leq N\), vale a cota padrão

\[ \sum_{i=0}^{d}\binom{N}{i} \leq \left(\frac{eN}{d}\right)^d. \]

Logo,

\[ m_{\mathcal{H}}(N) \leq \left(\frac{eN}{d}\right)^d. \]

Tomando logaritmos,

\[ \log m_{\mathcal{H}}(N) \leq d\log\left(\frac{eN}{d}\right). \]

Essa forma será útil na cota de generalização, pois a penalidade depende do logaritmo do número efetivo de dicotomias.

Para \(d\) fixo,

\[ m_{\mathcal{H}}(N)=O(N^d), \]

enquanto

\[ 2^N \]

cresce exponencialmente. A diferença entre crescimento polinomial e exponencial é o motivo pelo qual dimensão VC finita permite aprendizado uniforme.

4.3.19 Uma cota ainda mais simples

Também podemos usar, para \(N\geq1\) e \(d\geq1\), uma estimativa grosseira como

\[ m_{\mathcal{H}}(N) \leq (d+1)N^d. \]

Ela perde constantes e dependência refinada em \(d\), mas evidencia o grau polinomial. A expressão \(\left(eN/d\right)^d\) costuma ser preferível em derivações quantitativas.

4.3.20 Ponto de interrupção e efeito dominó

O lema contém uma mensagem combinatória forte: basta que a classe falhe em estilhaçar todos os conjuntos de algum tamanho finito para que o crescimento futuro inteiro fique controlado.

Não é possível ter

\[ m_{\mathcal{H}}(k)<2^k \]

e depois retornar ao crescimento máximo

\[ m_{\mathcal{H}}(N)=2^N \]

para algum \(N>k\). Se um conjunto maior fosse estilhaçado, qualquer subconjunto de tamanho \(k\) também seria estilhaçado, contradizendo o ponto de interrupção.

4.3.21 Cálculo numérico

Considere \(d=3\) e \(N=20\). Sauer–Shelah fornece

\[ m_{\mathcal{H}}(20) \leq \binom{20}{0} +\binom{20}{1} +\binom{20}{2} +\binom{20}{3}. \]

Calculando,

\[ m_{\mathcal{H}}(20) \leq 1+20+190+1\,140 =1\,351. \]

Sem usar capacidade, a cota trivial seria

\[ 2^{20}=1\,048\,576. \]

A redução do número efetivo de comportamentos é enorme.

A cota simplificada dá

\[ \left(\frac{20e}{3}\right)^3 \approx5\,950, \]

menos precisa que \(1\,351\), mas ainda muito menor do que \(2^{20}\).

4.3.22 Relação com compressão de padrões

A soma

\[ \sum_{i=0}^{d}\binom{N}{i} \]

conta subconjuntos de até \(d\) elementos. Isso sugere que uma classe de dimensão VC \(d\) não consegue tomar decisões independentes em todas as \(N\) posições; seus padrões são determinados por uma estrutura combinatória de ordem \(d\).

Essa interpretação não significa que toda classe VC admita automaticamente um esquema simples de compressão com exatamente \(d\) exemplos. A relação formal entre dimensão VC e compressão de amostras é mais delicada. A soma binomial é, antes de tudo, uma cota combinatória.

4.3.23 O que o lema não diz

Sauer–Shelah limita o número de dicotomias, mas não:

encontra a hipótese ótima;
garante que o algoritmo seja eficiente;
mede erro de aproximação;
trata regressão contínua diretamente;
fornece sozinho uma probabilidade de generalização.

Para obter uma cota de erro, combinaremos a função de crescimento com uma desigualdade de concentração e um argumento de uniformização.

4.3.24 Exemplo computacional

from math import comb


def cota_sauer(n, d):
    return sum(comb(n, i) for i in range(min(d, n) + 1))


print(cota_sauer(20, 3))  # 1351
print(2 ** 20)             # 1048576

4.3.25 Exercícios de fixação

Calcule a cota de Sauer para \(N=6\) e \(d=2\).
Verifique que a fórmula para \(d=1\) coincide com a função de crescimento dos limiares.
Mostre algebricamente que \(1+N+\binom{N}{2}=1+N(N+1)/2\).
Explique a recorrência \(M(N,d)\leq M(N-1,d)+M(N-1,d-1)\).
Use a identidade de Pascal para verificar que a soma binomial satisfaz a mesma recorrência.
Compare numericamente \(2^N\) e a cota de Sauer para \(N=10\), \(d=3\).
Por que uma classe não pode voltar a estilhaçar conjuntos maiores depois de um ponto de interrupção?
Diferencie a cota exata pela soma binomial da aproximação \((eN/d)^d\).
Explique por que o lema de Sauer–Shelah ainda não é, sozinho, uma cota de generalização.

4.3.26 Cota de erro

Até aqui, a dimensão VC e a função de crescimento mediram quantas formas diferentes uma classe de hipóteses pode produzir sobre uma amostra. Falta transformar essa medida combinatória em uma afirmação estatística: quão próximo o erro observado nos dados está do erro que a hipótese terá em exemplos futuros?

Seja

\[ \Delta_D(h)=E_{\mathrm{out}}(h)-E_{\mathrm{in}}(h), \]

em que \(E_{\mathrm{in}}\) é o erro na amostra de treinamento \(D\) e \(E_{\mathrm{out}}\) é o erro esperado na distribuição que gera os dados. O módulo \(|\Delta_D(h)|\) é chamado lacuna de generalização.

A dimensão VC limita a função de crescimento, que permite controlar simultaneamente a lacuna de todas as hipóteses.

4.3.26.1 Uma cota uniforme

Uma forma clássica da desigualdade de Vapnik–Chervonenkis afirma que, para qualquer \(\epsilon>0\),

\[ \Pr\!\left[ \sup_{h\in\mathcal H} |E_{\mathrm{out}}(h)-E_{\mathrm{in}}(h)|>\epsilon \right] \leq 4\,m_{\mathcal H}(2N) \exp\!\left(-\frac{N\epsilon^2}{8}\right). \tag{4.1}\]

As constantes podem variar entre versões do teorema, mas a estrutura é sempre a mesma: uma parcela mede a complexidade de \(\mathcal H\) e a exponencial mede o efeito benéfico do número \(N\) de exemplos.

O supremo é essencial. A desigualdade não controla apenas uma hipótese fixada antes de observar os dados; ela controla simultaneamente todas as hipóteses da classe. Portanto, continua válida para a hipótese \(g=A(D)\) escolhida pelo algoritmo depois de examinar a amostra. Esse é justamente o passo que uma aplicação direta da desigualdade de Hoeffding não consegue justificar.

Fixando uma probabilidade de falha \(\delta\in(0,1)\) e isolando \(\epsilon\) em Equation 4.1, obtemos, com probabilidade pelo menos \(1-\delta\),

\[ \sup_{h\in\mathcal H} |E_{\mathrm{out}}(h)-E_{\mathrm{in}}(h)| \leq \sqrt{\frac{8}{N} \ln\!\left(\frac{4m_{\mathcal H}(2N)}{\delta}\right)}. \tag{4.2}\]

Em particular, a hipótese devolvida pelo algoritmo satisfaz

\[ E_{\mathrm{out}}(g) \leq E_{\mathrm{in}}(g) +\sqrt{\frac{8}{N} \ln\!\left(\frac{4m_{\mathcal H}(2N)}{\delta}\right)}. \]

Assim, a cota separa dois objetivos: o algoritmo procura reduzir \(E_{\mathrm{in}}(g)\), enquanto a teoria limita a distância entre esse valor e \(E_{\mathrm{out}}(g)\).

4.3.26.2 Inserindo a dimensão VC

Se \(d=d_{\mathrm{VC}}(\mathcal H)<\infty\), o lema de Sauer–Shelah fornece

\[ m_{\mathcal H}(2N) \leq \sum_{i=0}^{d}\binom{2N}{i} \leq \left(\frac{2eN}{d}\right)^d, \qquad 2N\geq d. \]

Substituindo essa estimativa em Equation 4.2, chegamos à cota

\[ |E_{\mathrm{out}}(g)-E_{\mathrm{in}}(g)| \leq \sqrt{\frac{8}{N} \left[ d\ln\!\left(\frac{2eN}{d}\right) +\ln\!\left(\frac{4}{\delta}\right) \right]}. \tag{4.3}\]

Essa expressão explicita três relações importantes:

aumentar \(N\) tende a estreitar a cota;
aumentar \(d\) torna a classe mais flexível e alarga a cota;
reduzir \(\delta\) aumenta a confiança, mas também torna a garantia mais conservadora.

Para \(d\) fixo, o lado direito tem ordem aproximada

\[ O\!\left(\sqrt{\frac{d\ln N+\ln(1/\delta)}{N}}\right), \]

que converge para zero quando \(N\to\infty\). A convergência ocorre porque a função de crescimento é polinomial. Se ela permanecesse igual a \(2^{2N}\), seu logaritmo seria proporcional a \(N\) e a cota não desapareceria.

4.3.26.3 Quantos exemplos são necessários?

Para exigir uma lacuna de no máximo \(\epsilon\), basta procurar \(N\) tal que

\[ N\geq \frac{8}{\epsilon^2} \left[ d\ln\!\left(\frac{2eN}{d}\right) +\ln\!\left(\frac{4}{\delta}\right) \right]. \tag{4.4}\]

A desigualdade é implícita, pois \(N\) também aparece dentro do logaritmo. Em um programa, podemos encontrar o menor inteiro que a satisfaz por busca incremental ou binária. Uma iteração de ponto fixo também fornece uma estimativa rápida:

import math

def amostras_vc(d, epsilon, delta, n_inicial=1):
    n = max(n_inicial, math.ceil(d / 2))
    while True:
        rhs = (8 / epsilon**2) * (
            d * math.log(2 * math.e * n / d)
            + math.log(4 / delta)
        )
        novo_n = math.ceil(rhs)
        if novo_n <= n:
            return n
        n = novo_n

print(amostras_vc(d=3, epsilon=0.1, delta=0.1))

O resultado deve ser interpretado como uma condição suficiente, não como o número exato de exemplos de que todo problema precisará. Cotas VC são independentes da distribuição e do algoritmo; por cobrirem até os casos mais desfavoráveis, frequentemente são conservadoras.

Dimensão VC não é simplesmente número de parâmetros

Em alguns modelos lineares, a dimensão VC é próxima do número de parâmetros livres. Isso não constitui uma regra universal. Restrições, arquitetura, margem, regularização e até a forma de parametrização podem alterar a capacidade efetiva. O objeto matemático relevante é a classe de funções realizáveis, não apenas o tamanho do vetor de parâmetros.

4.3.26.4 Da generalização ao aprendizado PAC

Suponha que o algoritmo encontre \(g\) com erro de treinamento pequeno. Se a classe tem dimensão VC finita e \(N\) satisfaz Equation 4.4, então, com alta probabilidade, o erro fora da amostra também será pequeno. No caso realizável, em que existe uma hipótese perfeita na classe e o algoritmo encontra \(E_{\mathrm{in}}(g)=0\), Equation 4.3 fornece diretamente uma garantia para \(E_{\mathrm{out}}(g)\).

No caso não realizável, é útil decompor o desempenho em duas partes:

\[ E_{\mathrm{out}}(g) = \underbrace{E_{\mathrm{in}}(g)}_{\text{qualidade do ajuste}} + \underbrace{\bigl(E_{\mathrm{out}}(g)-E_{\mathrm{in}}(g)\bigr)} _{\text{lacuna de generalização}}. \]

A teoria VC controla a segunda parte; otimização e escolha do modelo tratam da primeira. Uma cota estreita não compensa um modelo que ajusta mal os dados, assim como erro de treinamento zero não garante sozinho boa generalização.

4.3.26.5 Exemplo de leitura da cota

Considere duas classes treinadas com a mesma amostra. A classe \(\mathcal H_1\) tem \(d=5\) e a classe \(\mathcal H_2\) tem \(d=500\). Se ambas alcançam o mesmo erro de treinamento, a cota favorece \(\mathcal H_1\), pois ela oferece menos maneiras de se adaptar acidentalmente ao ruído. Entretanto, se \(\mathcal H_1\) apresenta erro de treinamento muito alto, \(\mathcal H_2\) pode produzir a melhor soma entre ajuste e complexidade. Essa tensão é uma formulação matemática do compromisso entre subajuste e sobreajuste.

4.3.26.6 Recapitulação

A desigualdade VC controla uniformemente todas as hipóteses de \(\mathcal H\).
O lema de Sauer–Shelah converte dimensão VC finita em crescimento polinomial.
A lacuna garantida decresce aproximadamente como \(\sqrt{(d\ln N+\ln(1/\delta))/N}\).
A complexidade amostral cresce com a capacidade \(d\), com a precisão desejada \(1/\epsilon\) e com a confiança desejada \(1-\delta\).
A cota é uma garantia de pior caso; ela orienta o raciocínio, mas não substitui validação empírica.

4.3.26.7 Exercícios

Explique por que o supremo sobre \(h\in\mathcal H\) permite aplicar a cota à hipótese escolhida depois de observar os dados.
Mantendo \(d\) e \(\delta\) fixos, o que acontece aproximadamente com a cota quando \(N\) é quadruplicado?
Implemente a função amostras_vc e compare os resultados para \(d\in\{5,50,500\}\).
Mostre que, para \(d\) fixo, \((d\ln N)/N\to0\).
Dê um exemplo em que escolher a classe de menor dimensão VC provoque subajuste.

4.4 Exercícios de múltipla escolha

Cada questão possui uma única resposta correta. Tente relacionar a alternativa escolhida às definições e cotas estudadas no capítulo.

A lacuna de generalização absoluta de uma hipótese \(h\) é:
1. \(|E_{\mathrm{out}}(h)-E_{\mathrm{in}}(h)|\).
2. \(E_{\mathrm{out}}(h)+E_{\mathrm{in}}(h)\).
3. \(E_{\mathrm{in}}(h)^2\).
4. o número de parâmetros de \(h\).
Por que uma cota para uma hipótese fixada antes dos dados não basta para a hipótese selecionada por treinamento?
1. Porque o treinamento escolhe a hipótese com base na mesma amostra.
2. Porque hipóteses treinadas não possuem erro.
3. Porque a amostra deixa de conter variáveis aleatórias.
4. Porque Hoeffding se aplica somente à regressão.
A desigualdade de Hoeffding, na forma estudada, requer variáveis:
1. independentes e limitadas.
2. sempre gaussianas e negativas.
3. determinísticas e ilimitadas.
4. necessariamente vetoriais.
Ao quadruplicar \(N\), mantendo os outros termos fixos, uma cota proporcional a \(1/\sqrt{N}\) é aproximadamente:
1. duplicada.
2. reduzida à metade.
3. quadruplicada.
4. inalterada.
Para uma classe finita com \(M\) hipóteses, a cota da união introduz tipicamente qual dependência na complexidade?
1. \(\ln M\).
2. \(1/M^2\).
3. \(2^M\) dentro do erro.
4. Nenhuma dependência em \(M\).
Um conjunto é estilhaçado por \(\mathcal H\) quando:
1. apenas uma rotulação pode ser produzida.
2. todas as rotulações binárias de seus pontos podem ser realizadas por hipóteses de \(\mathcal H\).
3. todos os pontos recebem obrigatoriamente o mesmo rótulo.
4. sua cardinalidade é infinita.
A dimensão VC da classe de limiares em uma reta é:
4. infinita.
A dimensão VC da classe de intervalos em uma reta é:
4. infinita.
O lema de Sauer–Shelah mostra que, quando \(d_{VC}\) é finita, a função de crescimento para amostras grandes é limitada por um crescimento:
1. polinomial em \(N\).
2. necessariamente constante.
3. maior que todas as exponenciais.
4. independente de \(N\).
Qual afirmação interpreta corretamente uma cota VC?
1. Ela prevê exatamente o erro de teste de qualquer experimento.
2. Ela é uma garantia de pior caso e não substitui validação empírica.
3. Ela prova que modelos mais simples são sempre melhores.
4. Ela elimina o erro de aproximação.

Gabarito comentado

a. O valor absoluto mede o tamanho da diferença sem depender de seu sinal.
a. A seleção adapta \(h\) às flutuações da amostra, exigindo controle simultâneo sobre toda a classe.
a. Independência e limitação são condições centrais da forma apresentada.
b. \(1/\sqrt{4N}=1/(2\sqrt{N})\).
a. A aplicação da união às \(M\) hipóteses aparece como \(\ln M\) ao isolar a tolerância.
b. Estilhaçar significa realizar as \(2^N\) dicotomias possíveis naquele conjunto.
b. Um ponto pode receber ambos os rótulos, mas dois pontos não admitem todas as dicotomias com um único limiar orientado.
b. Intervalos estilhaçam dois pontos; três pontos alternados não podem ser rotulados positivo–negativo–positivo por um só intervalo.
a. Para \(N>d_{VC}\), o número efetivo de dicotomias deixa de crescer como \(2^N\) e recebe uma cota polinomial.
b. A cota explica dependências e oferece garantia probabilística, mas pode ser conservadora em uma aplicação concreta.