Cómo calcular la dimensión Vapnik-Chervonenkis

Question

Es mi primer post aquí, así que me disculpo si he roto alguna regla.

Estoy leyendo Introducción al aprendizaje automático y se quedó atascado en la dimensión VC. Aquí hay una cita del libro:

"...vemos que un rectángulo alineado con el eje puede romper cuatro puntos en dos dimensiones. Entonces VC(H), cuando H es la clase de hipótesis de los rectángulos alineados con el eje en dos dimensiones, es cuatro. Para calcular la dimensión VC, basta con que encontremos cuatro puntos que puedan ser destrozados; no es necesario que podamos destrozar cuatro puntos cualesquiera..."

Y no lo entiendo. Si es suficiente para encontrar algunos combinaciones separables, ¿por qué no podemos elegir un "rectángulo con ejemplos positivos" de la imagen anterior, poner otro $n$ positivos en ella, y luego decir $VC(H)$ aumentó en $n$ ? Y si todos los casos deben ser separables, entonces ¿por qué no consideramos 4 puntos colocados en una línea - que en general no es posible romper por un rectángulo?

Lo mismo con el ejemplo del clasificador lineal en el artículo de la wikipedia VC - en su imagen cuatro puntos son imposibles de romper, pero podemos llegar a una disposición en la que es posible. Y a la inversa, podemos poner 3 puntos (como "+", "-", "+") en una línea y no será posible separar los positivos de los negativos mediante un clasificador lineal.

¿Puede alguien explicar dónde está mi error?

Answer 1

Creo que sólo tienes que pensar cuidadosamente en cómo tus ejemplos se relacionan con la definición. La dimensión VC de H es el máximo h tal que existe un conjunto de cardinalidad h destrozado por H. Para demostrar que VC(H)=4 debes demostrar:

• Hay un conjunto de cardinalidad 4 roto por H, y
• Cualquier conjunto de cardinalidad superior a 4 no es destrozado por H

En la imagen, están haciendo lo primero: dar un límite inferior a la dimensión VC dando un ejemplo de un conjunto que está destrozado. Para demostrar que VC(H)<5 también deberían demostrar que ningún conjunto de cinco puntos está destrozado.

En general, habrá muchos conjuntos de diversos tamaños que no se destrozan, pero eso no importa, esencialmente porque la dimensión VC es un máximo sobre los conjuntos que se destrozan. Su ejemplo de $n$ puntos en una línea no implica nada sobre la dimensión de la CV. Espero que esto ayude.

Answer 2

La explicación de @Srivatsan tiene sentido para mí. Yo tuve este mismo problema cuando empecé a aprender esto. Tienes que permitir cualquier dicotomía de puntos posible, y luego demostrar que puedes destrozarla. Por lo tanto, si encuentras una combinación de clases para un número de puntos que no puedes destrozar, esa máquina debe tener una dimensión VC menor que ese número de puntos. Por lo tanto, el hecho de que un clasificador lineal no pueda romper XOR significa que no puede manejar nada más grande que 3 puntos, lo que es una ilustración de la regla de Burges n(-dimensión)+1 para la dimensión VC del clasificador lineal.

Answer 3

@andreister, sólo añadiendo algo de color:

La confusión surge porque la definición de la dimensión CV implica TANTO un calificador existencial ("existe"), como un calificador universal ("para todos"):

Obsérvese que, si la dimensión de la CV es h, entonces existe al menos un conjunto de h puntos que pueden ser destrozado pero en general no será ser cierto que cada conjunto de h puntos pueda ser destrozado Burgess (1998)

Por lo tanto, un tal conjunto de puntos tiene que existir, pero su ruptura == para todos los etiquetados == una afirmación universal.

Answer 4

La dimensión VC de una clase de hipótesis, H es la cardinalidad del mayor conjunto que puede ser destrozado por un H El requisito es que se pueda encontrar al menos un conjunto de puntos para el que se pueda encontrar un H que se rompe (o siempre puede encontrar un miembro de H que puede clasificar todos los posibles etiquetados de un ) conjunto particular.

Ahora, considera el conjunto dado de 3 puntos (vértices de un triángulo). Puedes encontrar un h que clasifica correctamente todos los posibles etiquetados del conjunto. No importa que no puedas hacerlo para otro conjunto de 3 puntos (tres puntos sobre una línea). La condición suficiente es que encuentres al menos un conjunto así.

Mientras que, por supuesto, se podría pensar en un etiquetado de 4 puntos (digamos que los puntos tienen la misma etiqueta) que un clasificador bidimensional podría clasificar correctamente, pero ¿puede clasificar correctamente todos los posibles etiquetados del conjunto de puntos? Piense en ello. Te darás cuenta de que no existe tal par.