¿Cuál es la definición exacta de dimensión VC?

8

Estoy estudiando el aprendizaje automático de las conferencias de Andrew Ng Stanford y acabo de encontrar la teoría de las dimensiones de CV. De acuerdo con las conferencias y lo que entendí, la definición de dimensión VC se puede dar como,

Si puedes encontrar un conjunto de n puntos, para que pueda ser destruido por el clasificador (es decir, clasificar todos los posibles 2n etiquetado correctamente) y no puede encontrar ningún conjunto de n+1 puntos que pueden romperse (es decir, para cualquier conjunto de n+1 puntos hay al menos un orden de etiquetado para que el clasificador no pueda separar todos los puntos correctamente), entonces la dimensión VC es n.

También el profesor tomó un ejemplo y lo explicó muy bien. Cual es:

Dejar,

H={set of linear classifiers in 2 Dimensions}

Entonces cualquier 3 puntos se pueden clasificar por H correctamente separando el hiperplano como se muestra en la siguiente figura.

ingrese la descripción de la imagen aquí

Y es por eso que la dimensión VC de Hes 3. Porque para cualquier 4 puntos en el plano 2D, un clasificador lineal no puede romper todas las combinaciones de los puntos. Por ejemplo,

ingrese la descripción de la imagen aquí

Para este conjunto de puntos, no se puede dibujar un hiperplano de separación para clasificar este conjunto. Entonces la dimensión VC es 3.

Tengo la idea hasta aquí. Pero, ¿y si seguimos el tipo de patrón?

ingrese la descripción de la imagen aquí

O el patrón donde coinciden tres puntos entre sí. Aquí tampoco podemos dibujar un hiperplano de separación entre 3 puntos. Pero aún así, este patrón no se considera en la definición de la dimensión VC. ¿Por qué? El mismo punto también se discute en las conferencias que estoy viendo aquí a las 16:24 pero el profesor no menciona la razón exacta detrás de esto.

Cualquier ejemplo intuitivo de explicación será apreciado. Gracias

Kaushal28
fuente

Respuestas:

9

La definición de dimensión VC es: si existe un conjunto de n puntos que el clasificador puede romper y no hay un conjunto de n + 1 puntos que el clasificador pueda romper, entonces la dimensión VC del clasificador es n.

La definición no dice: si el clasificador puede romper cualquier conjunto de n puntos ...

Si la dimensión VC de un clasificador es 3, no tiene que destruir todos los arreglos posibles de 3 puntos.

Si de todos los arreglos de 3 puntos puede encontrar al menos uno de esos arreglos que el clasificador puede romper, y no puede encontrar 4 puntos que puedan romperse, entonces la dimensión VC es 3.

Vladislav Gladkikh
fuente
1
Entonces, en este caso, podemos obtener al menos un patrón de cualquier número de puntos que se pueden clasificar por línea recta. Por ejemplo, piense en 4 puntos. Dos puntos rojos en el lado izquierdo y dos puntos azules en el lado derecho permitirían clasificar, y la dimensión VC sería 4. Entonces, ¿por qué no considerar esto?
Kaushal28
Clasificado - sí. Destrozado - no
Vladislav Gladkikh
Entonces, ¿qué significa romper una disposición de puntos? Estoy realmente confundido aquí. Gracias
Kaushal28
Una disposición de puntos puede romperse si cualquier subconjunto de esta disposición puede aislarse y colocarse en una clase. Supongamos que desea probar si un determinado tipo de clasificadores puede romper un determinado arreglo (no todos los arreglos posibles pero solo uno particular) de n puntos. Luego, primero prueba si se puede aislar un solo punto. Luego, si se pueden aislar 2 puntos, entonces si hay 3 puntos, etc., hasta cualquier punto n-1 de esa disposición particular. Ver aquí en.wikipedia.org/wiki/Shattered_set
Vladislav Gladkikh
1
La figura con 8 subtramas es una muy buena ilustración de lo que está destrozando. Aquí tiene 3 puntos, 2 clases, entonces 2 ^ 3 = 8 posibles etiquetados de estos 3 puntos. Los 8 etiquetados se pueden hacer y aislar con una línea, por lo tanto, este conjunto se puede romper con una línea. La figura con 4 puntos: tiene algunos etiquetados que pueden aislarse con una línea (digamos, dos a la izquierda son rojos, dos a la derecha son azules) pero también tiene un etiquetado que no puede aislarse con una línea (como en la Figura: superior y azul inferior; izquierda y derecha quedan) Como tiene un etiquetado que no se puede aislar con una línea, este conjunto no se rompe.
Vladislav Gladkikh