Dimension VC
1678961
29661354
2008-05-17T14:33:16Z
Xiawi
134142
lien rouge --> apprentissage automatique
{{ébauche|informatique}}
{{à vérifier}}
Dans la [[apprentissage automatique|théorie de l'apprentissage automatique]], la '''Dimension VC''' (pour '''dimension de Vapnik-Chervonenkis''') est une [[mesure]] de la [[capacité]] d'un [[algorithme de classification statistique]], définie comme le [[Nombre cardinal|cardinal]] du plus grand ensemble de points que l'algorithme peut [[pulvérisation|pulvériser]]. C'est un concept central dans la [[théorie de Vapnik-Chervonenkis]]. Il a été défini par [[Vladimir Vapnik]] et [[Alexey Chervonenkis]].
De manière informelle, la capacité d'un modèle de classification correspond à sa complexité. Par exemple, considérons comme modèle de classification la fonction de Heaviside d'un polynôme de degré élevé : si en un point donné la valeur du polynôme est positive, ce point est étiqueté positif; sinon, il est étiqueté négatif. Un polynôme de degré assez grand peut être très sinueux et bien correspondre à un échantillon de points d'apprentissage. Mais du fait de cette sinuosité élevée, on peut penser que ce modèle de classification donnera des évaluations fausses pour d'autres points. Un tel polynôme aura une ''capacité'' élevée. Si maintenant, nous remplaçons dans ce modèle ce polynôme de degré élevé par une fonction linéaire, le modèle obtenu peut ne pas bien correspondre à l'échantillon d'apprentissage, car sa ''capacité'' est faible. Nous décrivons cette notion de ''capacité'' de manière plus rigoureuse ci-dessous.
== Définition ==
On dit qu'un modèle de classification <math>f</math>, prenant comme paramètre un [[vecteur]] θ, ''pulvérise'' un ensemble de données (<math>x_1,x_2,\ldots,x_n</math>) si, pour tout [[étiquetage]] de cet ensemble de données, il existe un θ tel que le modèle <math>f</math> ne fasse aucune erreur dans l'évaluation de cet ensemble de données.
On appellera alors dimension VC d'un modèle <math>f</math> le cardinal du plus grand ensemble pulvérisé par <math>f</math>.
En notant <math>D_f</math> la dimension VC du modèle <math>f</math>, on a donc :
<math>D_f = max \{\quad k \quad | \quad card(S)=k \quad et \quad f \quad pulv\acute{e}rise \quad S\quad\}</math>
Par exemple, prenons comme modèle de classification une [[Droite (mathématiques)|droite]] (c'est le modèle employé par un [[perceptron]]). On étudie si la ligne peut séparer les données positives (+) des données négatives (-). Si on prend 3 points non alignés, la ligne peut les pulvériser. Cependant, la ligne ne peut pas pulvériser 4 points. Il est important de se rappeler qu'on peut choisir les positions des points qu'on va pulvériser avec la droite, mais qu'on ne peut pas ensuite modifier ces positions lorsqu'on permute leur étiquetage. Ci-dessous, pour la pulvérisation de 3 points, on montre seulement 3 des 8 étiquetages possibles (1 seule possibilté de les étiqueter tous les 3 positifs, 3 possibilités d'en étiqueter 2 sur 3 positifs, 3 possibilités d'en étiqueter 1 sur 3 positif, 1 possibilité de n'en étiqueter aucun positif).
{| border="0" cellpadding="4" cellspacing="0"
| align="center" bgcolor=#ddffdd | [[Image:VC1.png]]
| align="center" bgcolor=#ddffdd | [[Image:VC2.png]]
| align="center" bgcolor=#ddffdd |
| align="center" bgcolor=#ffdddd | [[Image:VC4.png]]
|-
| colspan="3" align="center" bgcolor=#ddffdd | '''Pulvérisation de 3 points'''
| align="center" bgcolor=#ffdddd | '''Lorsqu'il y a 4 points, la pulvérisation est impossible'''
|}
== Applications ==
La dimension VC est utilisée en [[apprentissage automatique|théorie de l'apprentissage automatique]] pour calculer la valeur de la marge d'erreur probable maximum d'un test de modèle de classification.
Pour le test d'un modèle de classification sur des données extraites de l'échantillon d'apprentissage de manière [[variable indépendante et identiquement distribuée|indépendante et identiquement distribuée]], cette valeur est calculée d'après la formule suivante :
Erreur d'apprentissage + <math>\sqrt{h(\log(2N/h)+1)-\log(\eta/4)\over N}</math>
avec la probabilité de <math>1-\eta</math>, où <math>h</math> est la dimension VC du modèle de classification, et <math>N</math> la taille de l'échantillon d'apprentissage.
Cette formule n'est valide que lorsque <math>h<N</math>.
== Liens internes ==
* [[Vladimir Vapnik]]
* [[Alexey Chervonenkis]]
* [[Réseau de neurones]]
* [[Théorie de Vapnik-Chervonenkis]]
== Sources ==
{{Traduction/Référence|en|VC Dimension|}}
* {{en}} [http://www-2.cs.cmu.edu/~awm/tutorials/vcdim.html cours sur la dimension VC] de [[Andrew W. Moore|Andrew Moore]]
* {{en}} V. Vapnik et A. Chervonenkis. "On the uniform convergence of relative frequencies of events to their probabilities." (De la convergence uniforme des fréquences relatives des événements vers leur probabilité) ''Theory of Probability and its Applications'' (Théorie de la probabilité et ses applications), 16(2):264--280, 1971.
* {{en}} A. Blumer, A. Ehrenfeucht, D. Haussler, et [[Manfred K. Warmuth|M. K. Warmuth]]. "Learnability and the Vapnik-Chervonenkis dimension." (Capacité d'apprentissage et dimension de Vapnik-Chervonenkis) ''Journal of the ACM'', 36(4):929--865, 1989.
{{Portail|mathématiques|informatique}}
[[Catégorie:Intelligence artificielle]]
[[en:VC dimension]]
[[es:Dimensión VC]]