Dimensión Vapnik-Chervonenkis: ¿por qué los rectángulos no pueden romper cuatro puntos de una línea?

8

Así que estoy leyendo "Introducción al aprendizaje automático" 2ª edición, por Bishop, et. todas. En la página 27 discuten la Dimensión Vapnik-Chervonenkis que es,

"El número máximo de puntos que puede ser destruido por H [la clase de hipótesis] se llama Dimensión Vapnik-Chervonenkis (VC) de H, se denota VC (H) y mide la capacidad de H."

Mientras que "rompe" indica una hipótesis hHpara un conjunto de N puntos de datos de manera que separe los ejemplos positivos de los negativos. En tal ejemplo se dice que "H rompe N puntos".

Hasta ahora creo que entiendo esto. Sin embargo, los autores me pierden con lo siguiente:

"Por ejemplo, cuatro rectángulos no pueden romper cuatro puntos en una línea".

Debe haber algún concepto aquí que no entiendo completamente, porque no puedo entender por qué este es el caso. ¿Puede alguien explicarme esto?

HermanoJack
fuente
2
Llama a los cuatro puntos pags,q,r,sen orden a lo largo de la línea. No hay rectángulo que contengapags y r pero excluye q y s.
JeffE
Sí, pero hay rectángulos que pueden contener pags y q, Excluyendo r y s; o contenerq y r y excluir pags y s. ¿Estás diciendo que cada combinación debe ser posible para que los puntos se rompan, y si es así, POR QUÉ ESTO NO ES UNA RESPUESTA: P?
BrotherJack

Respuestas:

10

La definición de "un conjunto PAGSpuede ser destrozado por rectángulos "es eso por cada subconjunto dePAGS, hay un rectángulo que contiene precisamente ese subconjunto y excluye el resto de PAGS. De manera equivalente, cada etiquetado de los puntos como positivo y negativo es consistente con al menos una hipótesis enH.

Ahora considere cuatro puntos pags,q,r,sa lo largo de una línea en el avión. Como no hay un rectángulo que contengapags y r pero excluye q y s, estos cuatro puntos no pueden romperse con rectángulos.

JeffE
fuente
Aquí vamos. Mucho mejor tener esto como respuesta, ¿no?
BrotherJack