VC-Dimension du k-plus proche voisin

Quelle est la dimension VC de l'algorithme k le plus proche voisin si k est égal au nombre de points d'apprentissage utilisés?

Contexte: Cette question a été posée dans un cours que j'ai suivi et la réponse donnée était 0. Je ne comprends cependant pas pourquoi c'est le cas. Mon intuition est que la dimension VC devrait être 1, car il devrait être possible de choisir deux modèles (c'est-à-dire des ensembles de points d'entraînement) de sorte que chaque point soit étiqueté comme appartenant à une classe selon le premier modèle et comme appartenant à une autre classe selon le deuxième modèle, il devrait donc être possible de briser un seul point. Où est l'erreur dans mon raisonnement?

Vous dites que l'algorithme est: k l'algorithme du plus proche voisin avec k = nombre de points d'apprentissage utilisés. Je définis cela comme jms-k-le plus proche voisin .

Étant donné que la dimension VC est le plus grand nombre de points d'apprentissage pouvant être brisé par l'algorithme avec l' erreur de train 0, la dimension VC de jms-k-le plus proche voisin ne peut être que k ou 0.

1 instance de formation => k = 1: Pendant la formation, le voisin le plus proche jms-1 stocke exactement cette instance. Lors de l'application sur exactement le même ensemble de formation, l'instance unique est la plus proche de l'instance de formation stockée (car elles sont identiques), donc l'erreur de formation est 0.

Je suis donc d'accord, la dimension VC est au moins 1.

2 instances de formation => k = 2: Il ne peut y avoir de problème que si les étiquettes sont différentes. Dans ce cas, la question est de savoir comment la décision pour une étiquette de classe est prise. Le vote majoritaire ne conduit pas à un résultat (VC = 0?), Si nous utilisons un vote majoritaire pondéré inversement par la distance, la dimension VC est 2 (en supposant qu'il n'est pas autorisé d'avoir deux fois la même instance de formation avec des étiquettes différentes, en ce sens cas, la dimension VC de tous les algorithmes serait 0 (je suppose)).

Il n'y a pas d'algorithme k-voisin standard, il s'agit plutôt d'une famille avec la même idée de base mais des saveurs différentes en ce qui concerne les détails d'implémentation.

Ressources utilisées: diapositives de dimension VC par Andrew Moore