Qual é a definição exata da dimensão VC?

Estou estudando aprendizado de máquina com as palestras de Andrew Ng Stanford e me deparei com a teoria das dimensões do VC. De acordo com as palestras e o que entendi, a definição da dimensão VC pode ser dada como,

Se você puder encontrar um conjunto de pontos, para que ele possa ser quebrado pelo classificador (ou seja, classifique corretamente todas as etiquetas possíveis ) e você não poderá encontrar nenhum conjunto de pontos que possam ser quebrados (ou seja, para qualquer conjunto de pontos, há pelo menos uma ordem de rotulagem para que o classificador não possa separar todos os pontos corretamente), então a dimensão VC é . $n$ $2^n$ $n+1$ $n+1$ $n$

O professor também deu um exemplo e explicou isso muito bem. Qual é:

Deixei,

$H=\{{set\ of\ linear\ classifiers\ in\ 2\ Dimensions \}}$

Em seguida, quaisquer 3 pontos podem ser classificados por corretamente, com o hiperplano de separação, conforme mostrado na figura a seguir. $H$

E é por isso que a dimensão VC de é 3. Porque para quaisquer 4 pontos no plano 2D, um classificador linear não pode quebrar todas as combinações dos pontos. Por exemplo, $H$

Para este conjunto de pontos, não há hiperplano separador que possa ser desenhado para classificar esse conjunto. Portanto, a dimensão VC é 3.

Eu tenho a idéia até aqui. Mas e se seguirmos o tipo de padrão?

Ou o padrão em que três pontos coincidem entre si. Aqui também não podemos desenhar hiperplano separador entre 3 pontos. Mas esse padrão ainda não é considerado na definição da dimensão VC. Por quê? O mesmo ponto também é discutido nas palestras que estou assistindo aqui às 16:24, mas o professor não menciona a razão exata por trás disso.

Qualquer exemplo intuitivo de explicação será apreciado. obrigado

machine-learning classification vc-theory Kaushal28
fonte

extraído de datascience.stackexchange.com/a/16146/23305

oW_

Respostas:

A definição da dimensão VC é: se existe um conjunto de n pontos que podem ser destruídos pelo classificador e não há um conjunto de n + 1 pontos que podem ser destruídos pelo classificador, então a dimensão VC do classificador é n.

A definição não diz: se qualquer conjunto de n pontos puder ser quebrado pelo classificador ...

Se a dimensão VC de um classificador for 3, ele não precisará quebrar todas as disposições possíveis de 3 pontos.

Se de todas as disposições de 3 pontos você puder encontrar pelo menos uma dessas disposições que possam ser destruídas pelo classificador e não encontrar 4 pontos que possam ser destruídas, a dimensão VC será 3.

Vladislav Gladkikh
fonte

Nesse caso, podemos obter pelo menos um padrão de qualquer número de pontos que pode ser classificado por linha reta. Por exemplo, pense em 4 pontos. Dois pontos vermelhos no lado esquerdo e dois pontos azuis no lado direito permitiriam classificar e a dimensão VC seria 4. Então, por que não considerar isso?

precisa saber é o seguinte

Classificado - sim. Shattered - no

Vladislav Gladkikh

Então, qual é o significado de quebrar um arranjo de pontos? Estou realmente confuso aqui. Graças

Kaushal28

Um arranjo de pontos pode ser quebrado se qualquer subconjunto desse arranjo puder ser isolado e colocado em uma classe. Digamos, você deseja testar se um determinado arranjo (nem todos os arranjos possíveis, mas apenas um arranjo específico) de n pontos pode ser quebrado por um certo tipo de classificador. Então você primeiro testa se um único ponto pode ser isolado. Então, se quaisquer 2 pontos puderem ser isolados, se houver 3 pontos, etc., até quaisquer n-1 pontos desse arranjo em particular. Veja aqui en.wikipedia.org/wiki/Shattered_set

Vladislav Gladkikh

A figura com 8 subparcelas é uma ilustração muito boa do que está quebrando. Aqui você tem 3 pontos, 2 classes, então 2 ^ 3 = 8 possíveis marcações desses 3 pontos. Todas as 8 etiquetas podem ser feitas e isoladas com uma linha, portanto, este conjunto pode ser quebrado por uma linha. A figura com 4 pontos: possui algumas etiquetas que podem ser isoladas com uma linha (digamos, duas à esquerda são vermelhas, duas à direita são azuis), mas também possui uma etiqueta que não pode ser isolada com uma linha (como na Figura: superior e azul inferior; esquerda e direita são deixadas). Como possui uma etiqueta que não pode ser isolada com uma linha, este conjunto não é quebrado.

Vladislav Gladkikh