El libro "Introducción al aprendizaje automático" de Ethem Alpaydın afirma que la dimensión VC de un rectángulo alineado a ejes es 4. Pero, ¿cómo puede un rectángulo romper un conjunto de cuatro puntos colineales con puntos alternativos positivos y negativos?
¿Alguien puede explicar y probar la dimensión VC de un rectángulo?
tl; dr: la definición de dimensión de VC es incorrecta.
La dimensión VC de los rectángulos es la cardinalidad del conjunto máximo de puntos que un rectángulo puede romper.
La dimensión VC de los rectángulos es 4 porque existe un conjunto de 4 puntos que puede ser destruido por un rectángulo y cualquier conjunto de 5 puntos no puede ser destruido por un rectángulo. Entonces, si bien es cierto que un rectángulo no puede romper un conjunto de cuatro puntos colineales con alternancia positiva y negativa, la dimensión VC sigue siendo 4 porque existe una configuración de 4 puntos que puede romperse.
La dimensión VC de un algoritmo es ese número máximo de puntos tal que
existe un diseño de los puntos tal que
para todos los etiquetados de esos puntos, el algoritmo no comete errores
Y, de hecho, hay un diseño de cuatro puntos (como un diamante) de modo que un rectángulo puede dividir cualquier conjunto de puntos positivos de los demás. Que exista un diseño de cuatro puntos donde el rectángulo fallará es irrelevante.
Considéralo como un juego entre tú y un oponente. Tú eliges la ubicación de los puntos y el oponente los etiqueta de la forma que quiera. Si gana al encontrar un etiquetado que no se puede romper, entonces la dimensión VC es menor que la cantidad de puntos, pero si gana, la dimensión VC es igual o mayor que la cantidad de puntos. En su pregunta, no está obligado a seleccionar ese arreglo, puede encontrar un mejor arreglo de puntos, lo que le permite ganar.
fuente