Por que a dimensão VC é importante?

A Wikipedia diz que:

A dimensão VC é a cardinalidade do maior conjunto de pontos que um algoritmo pode quebrar.

Por exemplo, um classificador linear tem uma cardinalidade n + 1. Minha pergunta é por que nos importamos? A maioria dos conjuntos de dados nos quais você classifica linearmente tendem a ser muito grandes e contêm muitos pontos.

Qual é a dimensão VC

Conforme mencionado por @CPerkins, a dimensão VC é uma medida da complexidade de um modelo. Também pode ser definido com relação à capacidade de quebrar pontos de dados como, como você mencionou, a wikipedia.

O problema básico

• Queremos um modelo (por exemplo, um classificador) que generalize bem em dados não vistos .
• Estamos limitados a uma quantidade específica de dados de amostra.

A imagem a seguir (tirada daqui ) mostra alguns modelos ( até ) de complexidade diferente (dimensão do VC), mostrados aqui no eixo x e chamados .S k$\mathcal{S_1}$$\mathcal{S_k}$$h$

As imagens mostram que uma dimensão de VC mais alta permite um risco empírico menor (o erro que um modelo comete nos dados da amostra), mas também introduz um intervalo de confiança mais alto. Esse intervalo pode ser visto como a confiança na capacidade de generalização do modelo.

Dimensão baixa de VC (alto viés)

Se usarmos um modelo de baixa complexidade, introduziremos algum tipo de suposição (viés) em relação ao conjunto de dados, por exemplo, ao usar um classificador linear, assumimos que os dados podem ser descritos com um modelo linear. Se não for esse o caso, nosso problema não pode ser resolvido por um modelo linear, por exemplo, porque o problema é de natureza não linear. Terminaremos com um modelo com desempenho ruim que não será capaz de aprender a estrutura dos dados. Devemos, portanto, tentar evitar a introdução de um forte viés.

Dimensão VC alta (maior intervalo de confiança)

Do outro lado do eixo x, vemos modelos de complexidade mais alta, que podem ter uma capacidade tão grande que memorizam os dados em vez de aprender sua estrutura geral subjacente, ou seja, o modelo é super ajustado. Depois de perceber esse problema, parece que devemos evitar modelos complexos.

Isso pode parecer controverso, pois não introduziremos um viés, ou seja, teremos uma dimensão baixa de VC, mas também não devemos ter uma dimensão alta de VC. Esse problema tem raízes profundas na teoria estatística da aprendizagem e é conhecido como compensação de desvio-variância . O que devemos fazer nessa situação é ser o mais complexo possível e simplista possível, portanto, ao comparar dois modelos que terminam com o mesmo erro empírico, devemos usar o menos complexo.

Espero poder mostrar a você que há mais por trás da ideia da dimensão VC.

A dimensão VC é o número de bits de informação (amostras) necessários para encontrar um objeto (função) específico entre um conjunto de objetos (funções)$N$ .

$VC$ dimensão vem de um conceito semelhante na teoria da informação. A teoria da informação partiu da observação de Shannon sobre o seguinte:

Se você tiver objetos e entre esses objetos, estará procurando um específico. Quantos bits de informação você precisa para encontrar este objeto ? Você pode dividir seu conjunto de objetos em duas metades e perguntar "Em que metade do objeto que estou procurando está localizado?" . Você recebe "sim" se estiver no primeiro semestre ou "não", se estiver no segundo semestre. Em outras palavras, você recebe 1 bit de informação . Depois disso, você faz a mesma pergunta e divide o seu conjunto várias vezes, até finalmente encontrar o objeto desejado. De quantos bits de informação você precisa ( respostas sim / não )? Está claramente$N$$N$l O g de 2 ( N )$log_2(N)$ bits de informação - semelhante ao problema de pesquisa binária na matriz classificada.

Vapnik e Chernovenkis fizeram uma pergunta semelhante no problema de reconhecimento de padrões. Suponha que você tenha um conjunto de funções com a entrada , cada função gera sim ou não (problema de classificação binária supervisionada) e entre essas funções, você está procurando uma função específica, que fornece resultados corretos sim / não para um determinado conjunto de dados . Você pode fazer a pergunta: "Quais funções retornam não e quais retornam sim para um determinado$N$$x$$N$$D=\{(x_1,y_1), (x_2, y_2), ..., (x_l, y_l)\}$$x_i$do seu conjunto de dados. Como você sabe qual é a resposta real dos dados de treinamento que você possui, você pode jogar fora todas as funções que fornecem respostas erradas para alguns . De quantos bits de informação você precisa? Ou em outras palavras: Quantos exemplos de treinamento você precisa para remover todas essas funções erradas? . Aqui está uma pequena diferença da observação de Shannon na teoria da informação. Você não está dividindo seu conjunto de funções pela metade (talvez apenas uma função de dê uma resposta incorreta para alguns ) e, talvez, seu conjunto de funções seja muito grande e suficiente para encontrar uma função que seja -close para a função desejada e você deseja ter certeza de que essa função é$x_i$$N$$x_i$$\epsilon$$\epsilon$ -feche com probabilidade ( - estrutura PAC ), o número de bits de informação (número de amostras) necessário será .$1-\delta$$(\epsilon, \delta)$$\frac{log_2N/\delta}{\epsilon}$

Suponha agora que entre o conjunto de funções não haja nenhuma função que não cometa erros. Como anteriormente, basta encontrar uma função que seja -close com probabilidade . O número de amostras que você precisa é .$N$$\epsilon$$1-\delta$$\frac{log_2N/\delta}{\epsilon^2}$

Observe que os resultados nos dois casos são proporcionais ao - semelhante ao problema de pesquisa binária.$log_2N$

Agora, suponha que você tenha um conjunto infinito de funções e, entre essas funções, você deseja encontrar a função -close para a melhor função com probabilidade . Suponha (para simplificar a ilustração) que as funções sejam afins contínuas (SVM) e você tenha encontrado uma função que esteja perto da melhor função. Se você mover sua função um pouco mais, isso não mudará os resultados da classificação, você terá uma função diferente que classifica com os mesmos resultados que a primeira. Você pode pegar todas as funções que fornecem os mesmos resultados de classificação (erro de classificação) e contá-las como uma única função, porque elas classificam seus dados com a mesma perda exata (uma linha na figura).$\epsilon$$1-\delta$$\epsilon$

^{___________________As duas linhas (função) classificarão os pontos com o mesmo sucesso ___________________}

Quantas amostras você precisa para encontrar uma função específica de um conjunto de conjuntos de funções (lembre-se de que nós dividimos nossas funções nos conjuntos de funções em que cada função fornece os mesmos resultados de classificação para um determinado conjunto de pontos)? É o que a dimensão informa - é substituído por porque você tem um número infinito de funções contínuas que são divididas em um conjunto de funções com o mesmo erro de classificação para pontos específicos. O número de amostras necessárias é se você tiver uma função que reconheça perfeitamente e$VC$$log_2N$$VC$$\frac{VC -log(\delta)}{\epsilon}$$\frac{VC - log(\delta)}{\epsilon^2}$ se você não tiver uma função perfeita no seu conjunto de funções original.

Ou seja, a dimensão fornece um limite superior (que não pode ser aprimorado) para um número de amostras necessárias para obter o erro com probabilidade .$VC$$\epsilon$$1-\delta$

A dimensão VC é uma medida da complexidade do modelo. Por exemplo, dada a dimensão VC Dvc, uma boa regra geral é que você deve ter n = 10xDvc pontos de dados, dada a complexidade do seu modelo.

Você também pode usá-lo para criar um limite superior no erro de teste.