Estou estudando aprendizado de máquina com as palestras de Andrew Ng Stanford e acabei de descobrir a teoria das dimensões de capital de risco. 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 $ n $ pontos, de modo que possa ser quebrado pelo classificador (ou seja classifique todos os $ 2 ^ n $ rotulagem possíveis corretamente) e você não pode encontrar qualquer conjunto de $ n + 1 $ pontos que podem ser quebrados (ou seja, para qualquer conjunto de $ n + 1 $ pontos, há pelo menos uma ordem de rotulagem para que o classificador não consegue separar todos os pontos corretamente), então a dimensão VC é $ n $.
O professor também deu um exemplo e explicou isso muito bem. Que é:
Vamos,
$ H = \ {{set \ of \ linear \ classifiers \ in \ 2 \ Dimensions \}} $
Então, quaisquer 3 pontos podem ser classificado por $ H $ corretamente com a separação do hiperplano como mostrado na figura a seguir.
E é por isso que a dimensão VC de $ H $ é 3. Porque para quaisquer 4 pontos no plano 2D, um classificador linear pode não quebrar todas as combinações dos pontos. Por exemplo,
Para este conjunto de pontos, não há nenhum hiperplano de separação pode ser desenhado para classificar este conjunto. Portanto, a dimensão VC é 3.
Eu entendi a ideia até aqui. Mas e se seguirmos o tipo de padrão?
Ou o padrão onde três pontos coincidem, aqui também não podemos desenhar separando hiperplano entre 3 pontos. Mas ainda assim este padrão não é considerado na definição da dimensão VC. Por quê? mesmo ponto também é discutido nas palestras que estou assistindo Aqui às 16:24 , mas o professor não menciona o motivo exato por trás disso.
Qualquer exemplo intuitivo de explicação será apreciado. Obrigado
Comentários
- retirados de datascience.stackexchange.com/a/16146/23305
Resposta
A definição da dimensão VC é: if existe um conjunto de n pontos que pode ser quebrado pelo classificador e não há conjunto de n + 1 pontos que podem ser quebrados pelo classificador, então a dimensão VC do classificador é n.
A definição não diz: se qualquer conjunto de n pontos pode ser quebrado pelo classificador. ..
Se a dimensão VC de um classificador for 3, ele não precisa quebrar todas as arranjos de 3 pontos.
Se de todos os arranjos de 3 pontos, você pode encontrar pelo menos um tal arranjo que pode ser quebrado pelo classificador e não consegue encontrar 4 pontos que podem ser quebrados, então a dimensão VC é 3.
Comentários
- Então neste caso, podemos obter pelo menos um padrão de qualquer número de pontos que podem ser classificados por linha reta. Por exemplo, pense em 4 pontos. Dois pontos vermelhos no lado esquerdo e dois pontos azuis no lado direito tornariam possível classificar, e a dimensão VC seria 4. Então, por que isso não é considerado?
- Classificado – sim. Destruído – não
- Então, qual é o significado de quebrando um arranjo de pontos? Eu ' estou realmente confuso aqui. Obrigado
- Um arranjo de pontos pode ser quebrado se qualquer subconjunto deste arranjo puder ser isolado e colocado em uma classe. Digamos que você queira testar se um determinado arranjo (nem todos os arranjos possíveis, mas apenas um arranjo particular) de n pontos pode ser quebrado por um certo tipo de classificadores. Em seguida, você primeiro testa se algum ponto único pode ser isolado. Então, se quaisquer 2 pontos podem ser isolados, então se quaisquer 3 pontos, etc, até quaisquer n-1 pontos daquele arranjo particular. Veja aqui en.wikipedia.org/wiki/Shattered_set
- Figura com 8 subtramas é uma ilustração muito boa do que está se quebrando. Aqui você tem 3 pontos, 2 classes, então 2 ^ 3 = 8 classificações possíveis desses 3 pontos. Todas as 8 marcações podem ser feitas e isoladas com uma linha, portanto, este conjunto pode ser quebrado por uma linha. A figura com 4 pontos: possui algumas marcações que podem ser isoladas com uma linha (digamos, duas esquerdas são vermelhas, duas direitas são azuis), mas também possui uma marcação que não pode ser isolada com uma linha (como na Figura: superior e azul inferior; esquerda e direita são esquerda). Por possuir uma etiqueta que não pode ser isolada com uma linha, este conjunto não se quebra.
Resposta
Os pontos devem cumprir os pontos na condição geral antes de serem considerados para a dimensão VC. 