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. Según las conferencias y lo que entendí, la definición de dimensión de VC se puede dar como,
Si puede encontrar un conjunto de $ n $ puntos, de modo que el clasificador pueda romperlo (es decir clasifique correctamente todos los $ 2 ^ n $ posibles de etiquetado) y no puede encontrar ningún conjunto de $ n + 1 $ puntos que pueda romperse (es decir, para cualquier conjunto de $ n + 1 $ puntos hay al menos un orden de etiquetado para que el clasificador no puede separar todos los puntos correctamente), entonces la dimensión de VC es $ n $.
También el profesor tomó un ejemplo y lo explicó muy bien. Que es:
Sea,
$ H = \ {{conjunto \ de \ clasificadores \ lineales \ en \ 2 \ Dimensiones \}} $
Entonces, 3 puntos pueden ser clasificados por $ H $ correctamente separando el hiperplano como se muestra en la siguiente figura.
Y es por eso que la dimensión VC de $ H $ es 3. Porque para 4 puntos cualesquiera en el plano 2D, un clasificador lineal puede no romper todas las combinaciones de los puntos. Por ejemplo,
Para este conjunto de puntos, no se puede dibujar un hiperplano separador para clasificar este conjunto. Entonces la dimensión de VC es 3.
Tengo la idea hasta aquí. Pero, ¿qué pasa si «seguimos el tipo de patrón?
O el patrón donde tres puntos coinciden entre sí, aquí tampoco podemos dibujar un hiperplano separador 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 las conferencias que «estoy viendo Aquí a las 16:24 pero el profesor no menciona la razón exacta detrás de esto.
Se agradecerá cualquier ejemplo intuitivo de explicación. Gracias
Comentarios
- extraído de datascience.stackexchange.com/a/16146/23305
Respuesta
La definición de dimensión VC es: if existe un conjunto de n puntos que el clasificador puede romper y no hay conjunto de n + 1 puntos que pueden ser destrozados por el clasificador, entonces la dimensión VC del clasificador es n.
La definición no dice: si cualquier conjunto de n puntos puede ser destruido por el clasificador. ..
Si la dimensión de VC de un clasificador es 3, no tiene que romper todas las arreglos de 3 puntos.
Si de todos los arreglos de 3 puntos puede encontrar al menos un tal arreglo que puede ser destrozado por el clasificador, y no puede encontrar 4 puntos que puedan romperse, entonces la dimensión de VC es 3.
Comentarios
- 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 se considera esto?
- Clasificado: sí. Destrozado: no
- Entonces, ¿cuál es el significado de rompiendo un arreglo de puntos? Estoy ' realmente confundido aquí. Gracias
- Un arreglo de puntos puede romperse si cualquier subconjunto de este arreglo se puede aislar y poner en una clase. Digamos que desea probar si una determinada disposición (no todas las disposiciones posibles, sino solo una disposición en particular) de n puntos puede ser destruida por un cierto tipo de clasificadores. Luego, primero prueba si se puede aislar algún punto. Luego, si se pueden aislar 2 puntos, si hay 3 puntos, etc., hasta los n-1 puntos de esa disposición en particular. Vea aquí en.wikipedia.org/wiki/Shattered_set
- La figura con 8 subtramas es una muy buena ilustración de lo que se está rompiendo. Aquí tienes 3 puntos, 2 clases, por lo que 2 ^ 3 = 8 posibles etiquetas de estos 3 puntos. Las 8 etiquetas se pueden hacer y aislar con una línea, por lo que este conjunto puede romperse con una línea. La figura con 4 puntos: tiene algunas etiquetas que se pueden aislar con una línea (digamos, dos a la izquierda son rojas, dos a la derecha son azules) pero también tiene una etiqueta que no se puede aislar con una línea (como en la Figura: superior y azul inferior; izquierda y derecha son izquierdas). Como tiene un etiquetado que no se puede aislar con una línea, este conjunto no se rompe.
Respuesta
Los puntos deben cumplir con los puntos en condiciones generales antes de considerar la dimensión VC. 