Le livre "Introduction to Machine learning" d'Ethem Alpaydın déclare que la dimension VC d'un rectangle aligné sur l'axe est 4. Mais comment un rectangle peut-il briser un ensemble de quatre points colinéaires avec des points alternatifs positifs et négatifs ??
Quelqu'un peut-il expliquer et prouver la dimension VC d'un rectangle?
tl; dr: la définition de la dimension VC est incorrecte.
La dimension VC des rectangles est la cardinalité de l'ensemble maximal de points qui peut être brisé par un rectangle.
La dimension VC des rectangles est 4 car il existe un ensemble de 4 points qui peuvent être brisés par un rectangle et tout ensemble de 5 points ne peut pas être brisé par un rectangle. Donc, même s'il est vrai qu'un rectangle ne peut pas briser un ensemble de quatre points colinéaires avec alternance positive et négative, la dimension VC est toujours de 4 car il existe une configuration de 4 points qui peut être brisée.
La dimension VC d'un algorithme est le nombre maximal de points tel que
il existe une disposition des points telle que
pour tous les étiquetages de ces points, l'algorithme ne fait aucune erreur
Et en effet, il y a une disposition de quatre points (comme un diamant) de telle sorte qu'un rectangle peut diviser n'importe quel ensemble de points positifs des autres. Qu'il existe une disposition de quatre points où le rectangle échouera n'est pas pertinent.
Considérez-le comme un jeu entre vous et un adversaire. Vous choisissez l'emplacement des points et l'adversaire les marque de toute façon. S'il gagne en trouvant un étiquetage qui ne peut pas être brisé, alors la dimension VC est inférieure au nombre de points mais si vous gagnez, la dimension VC est égale ou supérieure au nombre de points. Dans votre question, vous n'êtes pas obligé de sélectionner cet arrangement, vous pouvez trouver un meilleur arrangement de points, ce qui vous permet de gagner.
la source