Dimensão VC

Dimensão VC: por que ela importa

A dimensão Vapnik–Chervonenkis (VC) (Vapnik–Chervonenkis (VC) dimension) é um conceito central na teoria estatística do aprendizado (statistical learning theory) que formaliza a capacidade (capacity) de uma classe de modelos — quão flexível ela é — e conecta essa capacidade à complexidade de amostra (sample complexity) — quanto dado você precisa para aprender de forma confiável.

Em alto nível:

Uma classe de hipóteses (hypothesis class) com maior dimensão VC consegue ajustar uma variedade maior de padrões de rótulos (incluindo padrões “semelhantes a ruído”).
Mais flexibilidade significa que, em geral, você precisa de mais dados para evitar sobreajuste (overfitting) e garantir boa generalização (generalization).
Uma dimensão VC finita é (grosso modo) a condição certa para a aprendibilidade PAC (PAC learnability) de classificação binária sob cenários relativamente gerais (veja Aprendizado PAC (PAC Learning)).

A dimensão VC é mais diretamente aplicável à classificação binária (binary classification) (rótulos em ({0,1}) ou ({-1,+1})), mas a intuição se estende à regressão via noções relacionadas como pseudo-dimensão (pseudo-dimension).

Intuição: capacidade como “habilidade de realizar rotulagens arbitrárias”

Imagine que você escolhe (m) pontos em um espaço de entrada (por exemplo, pontos em uma reta, ou em (\mathbb{R}^d)). Uma classe de hipóteses ( \mathcal{H} ) (digamos, todos os classificadores de limiar (threshold classifiers), ou todos os separadores lineares (linear separators)) pode rotular esses pontos de algumas maneiras.

Se ( \mathcal{H} ) consegue realizar toda rotulagem possível desses (m) pontos (existem (2^m) rotulagens), então dizemos que esses pontos são estilhaçados (shattered) por ( \mathcal{H} ).
A dimensão VC é o tamanho do maior conjunto de pontos que pode ser estilhaçado.

Assim, a dimensão VC mede o maior número de pontos para os quais a classe de modelos tem flexibilidade suficiente para “ajustar qualquer coisa”, inclusive rótulos adversariais ou aleatórios.

Isso fornece um modelo mental útil:

Se sua classe de hipóteses consegue estilhaçar 1.000 pontos, então, com poucas amostras, ela pode conseguir ajustar o conjunto de treino de muitas formas espúrias, tornando a generalização mais difícil.
Se ela só consegue estilhaçar, digamos, 10 pontos, ela tem flexibilidade limitada, o que pode proteger contra sobreajuste, mas pode causar subajuste.

Isso se relaciona de perto com as ideias em Generalização e Viés/Variância e Sobreajuste e Regularização.

Definição formal

Seja:

(\mathcal{X}) o espaço de entrada,
(\mathcal{H}) um conjunto de classificadores binários (h : \mathcal{X} \to {0,1}),
(S = {x_1, \dots, x_m} \subseteq \mathcal{X}) um conjunto de (m) pontos.

Estilhaçamento

Dizemos que (\mathcal{H}) estilhaça (S) se, para toda rotulagem ((y_1,\dots,y_m) \in {0,1}^m), existe algum (h \in \mathcal{H}) tal que: [ h(x_i) = y_i \quad \text{para todo } i=1,\dots,m. ]

Dimensão VC

A dimensão VC de (\mathcal{H}), denotada por (\mathrm{VC}(\mathcal{H})), é:

o maior (m) tal que existe algum conjunto (S) de tamanho (m) que é estilhaçado por (\mathcal{H}),
ou (\infty) se conjuntos de tamanho arbitrário puderem ser estilhaçados.

Exemplos simples (para construir intuição)

Limiares na reta real: dimensão VC = 1

Considere classificadores da forma: [ h_t(x) = \mathbf{1}[x \ge t] ] em (\mathbb{R}).

Qualquer ponto único (x_1) pode ser rotulado como 0 ou 1 escolhendo (t) adequadamente → 1 ponto pode ser estilhaçado.
Mas, para dois pontos (x_1 < x_2), você não consegue realizar a rotulagem (h(x_1)=1, h(x_2)=0) com um único limiar → 2 pontos não podem ser estilhaçados.

Logo, (\mathrm{VC} = 1).

Intervalos na reta real: dimensão VC = 2

Classificadores que valem 1 em um intervalo ([a,b]) e 0 fora: [ h_{a,b}(x) = \mathbf{1}[a \le x \le b] ]

Dois pontos podem ser estilhaçados: você pode incluir nenhum, apenas um, ou ambos escolhendo ([a,b]).
Três pontos não podem ser estilhaçados (intuitivamente, porque um intervalo cria uma única região positiva “contígua”).

Logo, (\mathrm{VC} = 2).

Separadores lineares em \(\mathbb{R}^d\): dimensão VC = \(d+1\)

Para hiperplanos (hyperplanes) (h(x)=\mathrm{sign}(w^\top x + b)):

Em (\mathbb{R}^2), você consegue estilhaçar 3 pontos em posição geral (um triângulo), mas não 4.
Em (\mathbb{R}^d), a dimensão VC é (d+1).

Este é um ponto prático essencial: adicionar atributos aumenta a capacidade. Um modelo linear em 1.000 dimensões tem dimensão VC 1.001, apesar de ser “apenas linear”.

Mais exemplos de dimensão VC que você verá na prática

Abaixo estão classes de hipóteses comuns e resultados típicos de dimensão VC (constantes exatas podem depender de definições precisas).

Retângulos alinhados aos eixos em \(\mathbb{R}^d\): dimensão VC = \(2d\)

Classificadores que predizem 1 dentro de uma caixa: [ {x \in \mathbb{R}^d : a_i \le x_i \le b_i \ \forall i} ] têm (\mathrm{VC} = 2d). Cada dimensão contribui com dois “graus de liberdade” (fronteira inferior e superior).

Uniões de \(k\) intervalos em \(\mathbb{R}\): dimensão VC = \(2k\)

Uma união de (k) intervalos disjuntos pode representar padrões “liga/desliga” mais complexos ao longo da reta. A dimensão VC cresce linearmente com (k).

Redes neurais (neural networks): tipicamente dimensão VC muito grande

Para muitas famílias de redes neurais, a dimensão VC cresce na ordem do número de parâmetros (frequentemente com fatores log adicionais). Em termos gerais:

Mais parâmetros → dimensão VC muito maior.
Redes modernas superparametrizadas (overparameterized) podem ter dimensão VC muito acima do tamanho do conjunto de dados.

Ainda assim, redes profundas podem generalizar bem na prática; a dimensão VC é parte da história, mas não é a história inteira (mais sobre isso abaixo).

Do estilhaçamento à generalização: função de crescimento e Sauer–Shelah

Uma ponte importante entre “pode estilhaçar” e “vai generalizar” é a função de crescimento (growth function).

Seja ( \Pi_{\mathcal{H}}(m) ) o número máximo de rotulagens distintas que (\mathcal{H}) consegue produzir em qualquer conjunto de (m) pontos: [ \Pi_{\mathcal{H}}(m) = \max_{S:|S|=m} |{(h(x_1),\dots,h(x_m)) : h\in\mathcal{H}}|. ]

Se (\mathcal{H}) estilhaça (m) pontos, então (\Pi_{\mathcal{H}}(m)=2^m).
Se (\mathrm{VC}(\mathcal{H}) = d) é finita, então, para (m>d), (\Pi_{\mathcal{H}}(m)) cresce polinomialmente em vez de exponencialmente.

O lema de Sauer–Shelah (Sauer–Shelah lemma) formaliza isso: [ \Pi_{\mathcal{H}}(m) \le \sum_{i=0}^{d} {m \choose i} \le \left(\frac{em}{d}\right)^d \quad \text{para } m \ge d. ]

Isso é crucial: uma dimensão VC finita impede “rotulagens demais”, permitindo convergência uniforme (uniform convergence) (o erro de treino se aproxima do erro verdadeiro de forma uniforme sobre (\mathcal{H})).

Dimensão VC e complexidade de amostra (o resultado principal)

Seja:

(D) a distribuição dos dados,
(S) um conjunto de (m) amostras de treino i.i.d. (independentes e identicamente distribuídas) extraídas de (D),
(\mathrm{err}_D(h)) o erro verdadeiro (populacional),
(\mathrm{err}_S(h)) o erro empírico (empirical error) (erro de treino).

Um limite padrão de generalização via dimensão VC (VC generalization bound) diz que, com probabilidade de pelo menos (1-\delta), para todo (h\in\mathcal{H}), [ |\mathrm{err}_D(h) - \mathrm{err}_S(h)| ;;\lesssim;; \sqrt{\frac{d \log(m/d) + \log(1/\delta)}{m}} ] onde (d = \mathrm{VC}(\mathcal{H})) e (\lesssim) oculta constantes.

Escalonamento da complexidade de amostra

Se você quer erro excedente de no máximo (\varepsilon) com probabilidade de pelo menos (1-\delta), uma forma típica de complexidade de amostra é: [ m = O!\left(\frac{d \log(1/\varepsilon) + \log(1/\delta)}{\varepsilon}\right). ]

O que lembrar:

Linear em (d) (até logs): maior dimensão VC → mais dados necessários.
Inverso em (\varepsilon): exigências de acurácia mais estritas pedem mais dados.
Log em (1/\delta): maior confiança precisa de mais dados, mas de forma suave.

Uma verificação numérica rápida de plausibilidade

Suponha que você use um classificador linear em (\mathbb{R}^{20}). Então (d = 21). Se você quer (\varepsilon=0.05) e (\delta=0.05), o limite sugere precisar, na ordem de: [ m \approx \frac{21\log(20) + \log(20)}{0.05} ] Ignorando constantes, isso cai na casa dos milhares. O desempenho no mundo real pode ser muito melhor do que limites de pior caso, mas o comportamento de escalonamento é informativo.

Significado prático: escolher capacidade para combinar com os dados

Capacidade vs. sobreajuste (qualitativo)

Se sua classe de modelos tem dimensão VC baixa demais para a tarefa, ela pode não conseguir representar a fronteira de decisão (decision boundary) → alto viés / subajuste.
Se ela tem dimensão VC alta demais em relação aos seus dados, ela pode ajustar idiossincrasias da amostra → alta variância / sobreajuste.

Essa é a versão, em teoria do aprendizado, do que praticantes veem em curvas de treino/validação (veja Generalização e Viés/Variância).

Por que a regularização ajuda (mesmo se a dimensão VC continuar alta)

Muitos regularizadores não alteram literalmente a classe de hipóteses (você ainda consegue representar muitas funções), mas restringem o conjunto efetivo de soluções que o algoritmo de aprendizagem prefere.

Exemplos:

regularização L2 (L2 regularization) / decaimento de pesos (weight decay) tende a produzir soluções de menor norma.
parada antecipada (early stopping) pode agir como controle implícito de norma.
maximização de margem (margin maximization) (por exemplo, Máquinas de Vetores de Suporte (Support Vector Machines)) produz limites que dependem da margem, e não apenas da dimensionalidade bruta.

Existem resultados no estilo VC para classificadores lineares com margem limitada, nos quais a capacidade efetiva depende de quantidades geométricas como (R/\gamma) (raio sobre margem), e não apenas de (d).

Exemplo resolvido: estilhaçamento com separadores lineares (intuição geométrica)

Em (\mathbb{R}^2):

Escolha 3 pontos não colineares (um triângulo).
Uma reta consegue realizar todas as (2^3=8) rotulagens possíveis desses pontos → estilhaçados.
Com 4 pontos em posição geral, existe uma rotulagem (o padrão clássico tipo XOR, alternando os vértices de um quadrilátero convexo) que não pode ser separada por uma reta → não estilhaçados.

Esse “padrão XOR” é exatamente por que um único separador linear não consegue representar XOR, motivando mapeamentos de características (feature maps) e Métodos de Kernel (Kernel Methods) ou Redes Neurais (Neural Networks) multicamadas.

Como a dimensão VC aparece em fluxos de trabalho reais de ML

1) Engenharia de atributos e aprendizado de representações

Se você usa modelos lineares, a dimensão VC cresce com a dimensionalidade dos atributos:

bag-of-words (bag-of-words) com 100.000 atributos → dimensão VC enorme para separadores lineares.
Isso explica parcialmente por que você frequentemente precisa de regularização forte, validação cuidadosa ou muitos dados.

O aprendizado de representações (representation learning) (por exemplo, redes profundas) altera o espaço de atributos de maneira dependente dos dados, complicando a análise clássica via dimensão VC, mas a lógica de capacidade vs. dados permanece.

2) Seleção de modelos e “mais simples é mais seguro”

A dimensão VC sustenta a ideia por trás da minimização de risco estrutural (structural risk minimization): escolher entre classes de hipóteses aninhadas, de capacidade crescente (por exemplo, polinômios de grau 1, 2, 3, …), para equilibrar ajuste ao treino e complexidade.

Na prática, aproximamos isso com validação, penalidades no estilo AIC/BIC ou caminhos explícitos de regularização.

3) Entender quando “acurácia perfeita no treino” é suspeita

Se sua classe de hipóteses tem dimensão VC muito maior do que o tamanho do conjunto de dados, muitas vezes é possível obter erro de treino quase zero mesmo em rótulos aleatórios.

Essa observação fundamenta muitos experimentos de memorização em aprendizado profundo (deep learning) (por exemplo, treinar com rótulos embaralhados). A dimensão VC ajuda a explicar a possibilidade de memorização; ela não prevê completamente se o treinamento padrão de fato escolherá uma solução que memoriza.

Limitações: por que a dimensão VC não é a história completa da generalização moderna

A dimensão VC fornece garantias de pior caso sobre todas as distribuições e todas as rotulagens. A prática moderna de ML — especialmente em aprendizado profundo — frequentemente opera longe do pior caso.

Lacunas principais:

Dependência do algoritmo: a dimensão VC é uma propriedade da classe de hipóteses, não do algoritmo específico de treinamento. Mas a dinâmica de treinamento (por exemplo, descida do gradiente estocástica (SGD)) pode impor regularização implícita (implicit regularization).
Dependência da distribuição: dados reais têm estrutura; rotulagens de pior caso raramente aparecem.
Normas, margens e estabilidade importam: muitos limites modernos mais precisos dependem de normas, margens, compressão (compression) ou estabilidade, e não apenas da dimensão VC.

Conceitos relacionados que frequentemente fornecem limites mais apertados e informativos na prática incluem:

Complexidade de Rademacher (Rademacher Complexity)
Estabilidade Algorítmica (Algorithmic Stability)
análises baseadas em margem (comuns em Máquinas de Vetores de Suporte)

Ainda assim, a dimensão VC permanece fundamental porque estabelece de forma limpa que controlar a capacidade viabiliza o aprendizado e fornece um caminho principiado para a complexidade de amostra.

Um pequeno checklist prático de “mentalidade VC”

Ao projetar ou depurar um classificador, a dimensão VC sugere perguntas como:

Minha classe de modelos é muito mais flexível do que o necessário?
Se sim, espere maior variância; use regularização, mais dados ou uma classe mais simples.
Eu aumentei dramaticamente a dimensionalidade dos atributos?
Modelos lineares escalam capacidade com dimensionalidade; regularização torna-se mais importante.
Tenho dados suficientes para a capacidade que estou usando?
Não via cálculos exatos de dimensão VC (os limites são frouxos), mas via o escalonamento qualitativo: mais capacidade geralmente precisa de mais dados.
Estou usando mecanismos que reduzem a capacidade efetiva?
Decaimento de pesos, parada antecipada, maximização de margem, aumento de dados (data augmentation) — tudo isso pode melhorar a generalização além do que a dimensão VC bruta sugere.

Relação com tópicos irmãos em teoria do aprendizado

A dimensão VC fornece uma das pontes mais limpas entre “complexidade do modelo” e “limites de erro de generalização”, complementando a visão conceitual em Generalização e Viés/Variância.
Ela formaliza por que classes de hipóteses superparametrizadas podem sobreajustar sem restrições, alinhando-se a Sobreajuste e Regularização.
Ela é um resultado fundamental em teoria da aprendibilidade e sustenta resultados clássicos de complexidade de amostra em Aprendizado PAC.

Resumo

Dimensão VC é o número máximo de pontos que uma classe de hipóteses consegue estilhaçar (ajustar sob toda rotulagem possível).
Ela formaliza capacidade: maior dimensão VC significa uma classe mais rica de classificadores.
Uma dimensão VC finita implica garantias fortes de generalização e complexidade de amostra; limites típicos escalam como
[ m = O!\left(\frac{d\log(1/\varepsilon)+\log(1/\delta)}{\varepsilon}\right). ]
Na prática, a dimensão VC é mais útil como intuição e lei de escalonamento, enquanto análises modernas mais apertadas frequentemente se baseiam em margens, normas, estabilidade ou medidas de complexidade dependentes dos dados.

Se você entende a dimensão VC, você entende uma razão central pela qual “modelos mais flexíveis precisam de mais dados” — e ganha uma lente principiada para pensar sobre generalização para além de heurísticas.