Jétudie lapprentissage automatique à partir des conférences dAndrew Ng Stanford et je viens de découvrir la théorie des dimensions du CV. Daprès les conférences et ce que jai compris, la définition de dimension VC peut être donnée comme,
Si vous pouvez trouver un ensemble de $ n $ points, de sorte quil puisse être brisé par le classifieur (ie classer correctement tous les étiquetages $ 2 ^ n $ possibles) et vous ne pouvez trouver aucun ensemble de $ n + 1 $ points pouvant être brisé (cest-à-dire que pour tout ensemble de $ n + 1 $ points, il y a au moins un ordre détiquetage afin que le classificateur ne peut pas séparer correctement tous les points), alors la dimension VC est $ n $.
Le professeur a également pris un exemple et la bien expliqué. Ce qui est:
Soit,
$ H = \ {{set \ of \ linear \ classifiers \ in \ 2 \ Dimensions \}} $
Alors, 3 points peuvent être classée correctement par $ H $ en séparant lhyperplan comme indiqué dans la figure suivante.
Et cest pourquoi la dimension VC de $ H $ est 3. Parce que pour 4 points quelconques dans le plan 2D, un classificateur linéaire peut pas briser toutes les combinaisons de points. Par exemple,
Pour cet ensemble de points, il ny a pas dhyperplan séparateur pouvant être dessiné pour classer cet ensemble. La dimension VC est donc 3.
Je comprends lidée jusque là. Mais que se passe-t-il si nous « suivons le type de motif?
Ou le motif où trois points coïncident les uns sur les autres, Ici aussi, nous ne pouvons pas dessiner un hyper plan de séparation entre 3 points. Mais ce motif nest toujours pas pris en compte dans la définition de la dimension VC. Pourquoi? Le même point est également discuté des conférences que je « regarde Ici à 16:24 mais le professeur ne mentionne pas la raison exacte derrière cela.
Tout exemple intuitif dexplication sera apprécié. Merci
Commentaires
- extraits de datascience.stackexchange.com/a/16146/23305
Réponse
La définition de la dimension VC est: if il existe un ensemble de n points qui peuvent être brisés par le classificateur et il ny a pas de ensemble de n + 1 points pouvant être brisés par le classifieur, alors la dimension VC du classifieur est n.
La définition ne dit pas: si tout ensemble de n points peut être brisé par le classificateur. ..
Si la dimension VC dun classificateur est 3, il nest pas nécessaire de briser tous les possibles arrangements de 3 points.
Si de tous les arrangements de 3 points, vous pouvez trouver au moins un tel arrangement qui peut être brisé par le classificateur, et ne peut pas trouver 4 points qui peuvent être brisés, alors la dimension VC est 3.
Commentaires
- Alors dans ce cas, nous pouvons obtenir au moins un motif de nimporte quel nombre de points qui peuvent être classés par ligne droite. Par exemple, pensez à 4 points. Deux points rouges à gauche et deux points bleus à droite permettraient de classer, et la dimension VC serait 4. Alors pourquoi ne pas en tenir compte?
- Classé – oui. Brisé – non
- Alors, quelle est la signification de briser un arrangement de points? Je ' je suis vraiment confus ici. Merci
- Un arrangement de points peut être brisé si un sous-ensemble de cet arrangement peut être isolé et placé dans une classe. Disons que vous voulez tester si un certain arrangement (pas tous les arrangements possibles mais seulement un arrangement particulier) de n points peut être brisé par un certain type de classificateurs. Ensuite, vous testez dabord si un seul point peut être isolé. Ensuite, si 2 points peuvent être isolés, alors sil y a 3 points, etc., jusquà nimporte quel n-1 points de cet arrangement particulier. Voir ici en.wikipedia.org/wiki/Shattered_set
- La figure avec 8 sous-graphiques est une très bonne illustration de ce qui est bouleversant. Ici vous avez 3 points, 2 classes, donc 2 ^ 3 = 8 étiquetages possibles de ces 3 points. Les 8 étiquetages peuvent être faits et isolés avec une ligne, donc cet ensemble peut être brisé par une ligne. Le chiffre avec 4 points: il a des étiquettes qui peuvent être isolées avec une ligne (disons, deux à gauche sont rouges, deux à droite sont bleues) mais a également un étiquetage qui ne peut pas être isolé avec une ligne (comme dans la figure: supérieur et bleu inférieur; gauche et droite sont à gauche). Comme il a un étiquetage qui ne peut pas être isolé avec une ligne, cet ensemble nest pas brisé.
Réponse
Les points doivent remplir des points en condition générale avant denvisager la dimension VC. 