Dimensão VC de um retângulo

9

O livro "Introdução ao aprendizado de máquina" de Ethem Alpaydın afirma que a dimensão VC de um retângulo alinhado ao eixo é 4. Mas como um retângulo pode quebrar um conjunto de quatro pontos colineares com pontos positivos e negativos alternativos?

Alguém pode explicar e provar a dimensão VC de um retângulo?

kaz
fonte

Respostas:

20

tl; dr: Você está com a definição de dimensão VC incorreta.

A dimensão VC dos retângulos é a cardinalidade do conjunto máximo de pontos que pode ser quebrado por um retângulo.

A dimensão VC dos retângulos é 4 porque existe um conjunto de 4 pontos que podem ser quebrados por um retângulo e qualquer conjunto de 5 pontos não pode ser quebrado por um retângulo. Portanto, embora seja verdade que um retângulo não pode quebrar um conjunto de quatro pontos colineares com positivo e negativo alternativo, a dimensão VC ainda é 4 porque existe uma configuração de 4 pontos que pode ser quebrada.

neutralino
fonte
11

A dimensão VC de um algoritmo é o número máximo de pontos que

  • existe algum layout dos pontos tal que

  • para todas as rotulações desses pontos, o algoritmo não comete erros

E, de fato, há um layout de quatro pontos (como um diamante), de modo que um retângulo pode dividir qualquer conjunto de pontos positivos dos outros. A existência de um layout de quatro pontos em que o retângulo falhará é irrelevante.

Aqui está um artigo com um diagrama .

Andy Jones
fonte
essa é uma ótima resposta e a redação ajuda muito, mas ainda estou curioso sobre a impossibilidade de 5 pontos não serem destruídos? Eu acho que também existe um layout no qual é possível separar positivos e negativos, por exemplo, em forma de estrela, em que três pontos são positivos e o restante negativo ou vice-versa. Estou esquecendo de algo?
Kirk Walla
0

Considere isso como um jogo entre você e um oponente. Você escolhe a localização dos pontos e o oponente os rotula como quiser. Se ele vencer encontrando uma rotulagem que não pode ser quebrada, a dimensão VC será menor que o número de pontos, mas se você vencer, a dimensão VC será igual ou superior ao número de pontos. Na sua pergunta, você não é forçado a selecionar esse arranjo; pode encontrar um arranjo melhor de pontos, o que permite ganhar.

Ahmad
fonte
11
Tudo isso é verdade, mas você realmente não respondeu à pergunta, que tem a ver com a dimensão VC de um retângulo alinhado ao eixo. Estender sua resposta para mostrar como ela se aplica a uma pergunta específica seria ótimo!
jbowman