La dimension VC est le nombre de bits d'information (échantillons) dont on a besoin pour trouver un objet (fonction) spécifique parmi un ensemble de objets (fonctions)N .
VC dimension provient d'un concept similaire dans la théorie de l'information. La théorie de l'information est partie de l'observation de Shannon de ce qui suit:
Si vous avez objets et parmi ces objets, vous en recherchez un spécifique. De combien de bits d'information avez-vous besoin pour trouver cet objet ? Vous pouvez diviser votre ensemble d'objets en deux moitiés et demander "Dans quelle moitié se trouve l'objet que je recherche?" . Vous recevez "oui" si c'est dans la première moitié ou "non", si c'est dans la seconde moitié. En d'autres termes, vous recevez 1 bit d'information . Après cela, vous posez la même question et divisez votre ensemble encore et encore, jusqu'à ce que vous trouviez enfin l'objet souhaité. De combien de bits d'information avez-vous besoin ( réponses oui / non )? C'est clairementNNlog2(N) bits d'information - de manière similaire au problème de recherche binaire avec le tableau trié.
Vapnik et Chernovenkis ont posé une question similaire dans le problème de reconnaissance des formes. Supposons que vous ayez un ensemble de fonctions pour l'entrée donnée , chaque fonction génère oui ou non (problème de classification binaire supervisé) et parmi ces fonctions vous recherchez une fonction spécifique, qui vous donne des résultats corrects oui / non pour un ensemble de données donné . Vous pouvez poser la question: "Quelles fonctions retournent non et quelles fonctions retournent oui pour un donnéNxND={(x1,y1),(x2,y2),...,(xl,yl)}xià partir de votre ensemble de données. Puisque vous savez quelle est la vraie réponse à partir des données de formation dont vous disposez, vous pouvez jeter toutes les fonctions qui vous donnent une mauvaise réponse pour certains . De combien de bits d'information avez-vous besoin? Ou en d'autres termes: de combien d'exemples de formation avez-vous besoin pour supprimer toutes ces mauvaises fonctions? . Ici, c'est une petite différence avec l'observation de Shannon en théorie de l'information. Vous ne divisez pas votre ensemble de fonctions exactement à la moitié (peut-être qu'une seule fonction sur vous donne une réponse incorrecte pour certains ), et peut-être, votre ensemble de fonctions est très grand et il suffit que vous trouviez une fonction qui est -close à votre fonction souhaitée et vous voulez être sûr que cette fonction estxiNxiϵϵ -close avec probabilité ( - framework PAC ), le nombre de bits d'information (nombre d'échantillons) dont vous aurez besoin sera .1−δ(ϵ,δ)log2N/δϵ
Supposons maintenant que parmi l'ensemble des fonctions, il n'y a pas de fonction qui ne commette pas d'erreurs. Comme précédemment, il vous suffit de trouver une fonction qui est -close avec une probabilité . Le nombre d'échantillons dont vous auriez besoin est .Nϵ1−δlog2N/δϵ2
Notez que les résultats dans les deux cas sont proportionnels à - similaire au problème de recherche binaire.log2N
Supposons maintenant que vous ayez un ensemble infini de fonctions et parmi ces fonctions, vous voulez trouver la fonction qui est -close à la meilleure fonction avec la probabilité . Supposons (pour la simplicité de l'illustration) que les fonctions sont affines continues (SVM) et que vous avez trouvé une fonction qui est -close à la meilleure fonction. Si vous bougiez un peu votre fonction, cela ne changerait pas les résultats de la classification, vous auriez une fonction différente qui classe avec les mêmes résultats que la première. Vous pouvez prendre toutes ces fonctions qui vous donnent les mêmes résultats de classification (erreur de classification) et les compter comme une seule fonction car elles classent vos données avec exactement la même perte (une ligne dans l'image).ϵ1−δϵ
___________________ Les deux lignes (fonction) classeront les points avec le même succès ___________________
De combien d'échantillons avez-vous besoin pour trouver une fonction spécifique à partir d'un ensemble d'ensembles de telles fonctions (rappelez-vous que nous avions divisé nos fonctions en ensembles de fonctions où chaque fonction donne les mêmes résultats de classification pour un ensemble donné de points)? C'est ce que dit la dimension - est remplacé par car vous avez un nombre infini de fonctions continues qui sont divisées en un ensemble de fonctions avec la même erreur de classification pour des points spécifiques. Le nombre d'échantillons dont vous auriez besoin est si vous avez une fonction qui reconnaît parfaitement etVClog2NVCVC−log(δ)ϵVC−log(δ)ϵ2 si vous n'avez pas une fonction parfaite dans votre ensemble de fonctions d'origine.
C'est-à-dire que la dimension vous donne une limite supérieure (qui ne peut pas être améliorée btw) pour un certain nombre d'échantillons dont vous avez besoin afin d'obtenir une erreur avec une probabilité .VCϵ1−δ