Dimensión VC del vecino k más cercano

¿Cuál es la dimensión VC del algoritmo vecino k más cercano si k es igual al número de puntos de entrenamiento utilizados?

Contexto: esta pregunta se formuló en un curso que tomé y la respuesta dada fue 0. Sin embargo, no entiendo por qué este es el caso. Mi intuición es que la Dimensión VC debería ser 1, porque debería ser posible elegir dos modelos (es decir, conjuntos de puntos de entrenamiento) para que cada punto se etiquete como perteneciente a una clase de acuerdo con el primer modelo y como perteneciente a otra clase de acuerdo con el segundo modelo, por lo tanto, debería ser posible romper un solo punto. ¿Dónde está el error en mi razonamiento?

Usted dice que el algoritmo es: k-algoritmo vecino más cercano con k = número de puntos de entrenamiento utilizados. Lo defino como jms-k-next-neighbor .

Dado que la dimensión VC es el mayor número de puntos de entrenamiento que el algoritmo puede romper con el error de tren 0, la dimensión VC de jms-k-vecino más cercano solo puede ser k o 0.

1 instancia de entrenamiento => k = 1: Durante el entrenamiento, el jms-1-vecino más cercano almacena exactamente esta instancia. Durante la aplicación en exactamente el mismo conjunto de entrenamiento, una instancia es la más cercana a la instancia de entrenamiento almacenada (porque son las mismas), por lo que el error de entrenamiento es 0.

Así que estoy de acuerdo, la dimensión VC es al menos 1.

2 instancias de entrenamiento => k = 2: solo puede haber un problema si las etiquetas son diferentes. En este caso, la pregunta es cómo se toma la decisión de una etiqueta de clase. El voto mayoritario no conduce a un resultado (VC = 0?), Si utilizamos el voto mayoritario ponderado inversamente por distancia, la dimensión VC es 2 (suponiendo que no se permita tener la misma instancia de entrenamiento dos veces con etiquetas diferentes, en ese sentido caso, la dimensión VC de todos los algoritmos sería 0 (supongo)).

No hay un algoritmo vecino estándar k-más cercano, es más una familia con la misma idea básica pero con diferentes sabores cuando se trata de detalles de implementación.

Recursos utilizados: diapositivas de dimensión VC por Andrew Moore