Dimensão Vapnik-Chervonenkis: por que quatro pontos de uma linha não podem ser quebrados por retângulos?

8

Então, eu estou lendo "Introdução ao Machine Learning" 2ª edição, por Bishop, et. todos. Na página 27 eles discutem a dimensão Vapnik-Chervonenkis, que é,

"O número máximo de pontos que podem ser destruídos por H [a classe de hipóteses] é chamado de dimensão Vapnik-Chervonenkis (VC) de H, é designado VC (H) e mede a capacidade de H."

Enquanto "quebra" indica uma hipótese para um conjunto de N pontos de dados, de modo que separa os exemplos positivos dos negativos. Nesse exemplo, diz-se que "H quebra N pontos".hH

Até agora, acho que entendo isso. No entanto, os autores me perdem com o seguinte:

"Por exemplo, quatro pontos em uma linha não podem ser quebrados por retângulos."

Deve haver algum conceito aqui. Não estou entendendo completamente, porque não consigo entender por que esse é o caso. Alguém pode me explicar isso?

BrotherJack
fonte
2
Chame os quatro pontos em ordem ao longo da linha. Não há retângulo que contenha e mas exclua e . p,q,r,sprqs
18412 JeffE
Sim, mas há retângulos que podem conter e , excluindo e ; ou contém e e exclua e . Você está dizendo que cada combinação deve ser possível para que os pontos sejam quebrados e, em caso afirmativo, POR QUE ISSO NÃO É UMA RESPOSTA: P? pqrsqrps
BrotherJack

Respostas:

10

A definição de "um conjunto pode ser quebrado por retângulos" é que para cada subconjunto de , há um retângulo que contém precisamente esse subconjunto e exclui o resto da . Equivalentemente, cada marcação dos pontos como positivo e negativo é consistente com pelo menos uma hipótese em .PPPH

Agora considere quatro pontos ao longo de uma linha no plano. Como não há retângulo que contenha e mas exclua e , esses quatro pontos não podem ser quebrados por retângulos.p,q,r,sprqs

JeffE
fonte
Aqui vamos nós. Muito melhor ter isso como resposta, não?
BrotherJack