Dimensão VC e Capacidade

A dimensão de Vapnik-Chervonenkis mede a capacidade de uma classe de modelos pelo maior conjunto de pontos que ela pode rotular de todas as maneiras possíveis, quantificando a complexidade de um aprendiz.

Definition

A dimensão de Vapnik-Chervonenkis de uma classe de classificadores é o maior número de pontos que a classe pode rotular de todas as maneiras possíveis; é uma medida de capacidade que limita o quanto a classe pode sofrer overfitting e, portanto, quantos dados são necessários para aprender de forma confiável.

Scope

Este tópico aborda medidas da riqueza de uma classe de hipóteses: a noção de "shattering" (separação completa) de um conjunto de pontos, a dimensão de Vapnik-Chervonenkis como o tamanho do maior conjunto "shattered", a função de crescimento e como essas medidas de capacidade entram nos limites de generalização. Explica por que a capacidade, em vez do número de parâmetros isoladamente, governa a capacidade de generalizar.

Core questions

• O que significa para uma classe de modelos "shatter" (separar completamente) um conjunto de pontos?
• Como a dimensão de Vapnik-Chervonenkis é definida e calculada?
• Por que a capacidade, e não a contagem de parâmetros, governa a generalização?
• Como a capacidade entra nos limites da lacuna entre o treinamento e o erro verdadeiro?

Key theories

Shattering e capacidade

Uma classe "shatters" um conjunto de pontos se puder realizar todas as possíveis rotulações deles; o maior conjunto desse tipo define a dimensão de Vapnik-Chervonenkis, uma medida independente da distribuição de quão flexível a classe é.

A capacidade controla a convergência uniforme

A capacidade finita garante que o erro empírico converge para o erro verdadeiro uniformemente sobre a classe, de modo que um aprendiz com dimensão de Vapnik-Chervonenkis limitada não pode sofrer overfitting arbitrariamente à medida que os dados aumentam.

Capacidade versus contagem de parâmetros

A capacidade, e não o número bruto de parâmetros, determina a generalização, de modo que dois modelos com a mesma contagem de parâmetros podem diferir muito na quantidade de dados que exigem.

Clinical relevance

A dimensão de Vapnik-Chervonenkis fornece a medida central de capacidade da teoria clássica da aprendizagem e justifica a prática de controlar a complexidade do modelo; ela fundamenta a análise baseada em margem de máquinas de vetores de suporte e enquadra os esforços contínuos para entender por que alguns modelos de altíssima capacidade, no entanto, generalizam.

History

Vapnik e Chervonenkis introduziram a dimensão que leva seus nomes em trabalhos do final da década de 1960 e no artigo de 1971 sobre convergência uniforme, estabelecendo uma teoria de capacidade independente da distribuição. O conceito tornou-se fundamental para máquinas de vetores de suporte e para a análise mais ampla da generalização.

Key figures

• Vladimir Vapnik
• Alexey Chervonenkis

Seminal works

• vapnik1971
• vapnik1995
• hastie2009

Frequently asked questions

O que significa "shattering"?

Um conjunto de pontos é "shattered" por uma classe de modelos se, para cada possível atribuição de rótulos a esses pontos, algum modelo na classe produzir exatamente essa rotulação. O tamanho do maior conjunto "shatterable" é a dimensão de Vapnik-Chervonenkis.

Um modelo com mais parâmetros sempre tem maior capacidade?

Não necessariamente. A capacidade é medida pela dimensão de Vapnik-Chervonenkis ou quantidades relacionadas, que podem diferir da contagem de parâmetros. A medida correta de complexidade para generalização é a capacidade, não simplesmente quantos parâmetros um modelo possui.