Dimensió VC

La dimensió VC (de l'anglés Vapnik-Chervonenkis dimension) és una mida de la capacitat dels algoritmes de classificació estadística, definida com la cardinalidad del major conjunt de punts que l'algoritme pot separar. És un concepte central en la teoria Vapnik-Chervonenkis, i va anar originalment definit per Vladimir Vapnik i Alexey Chervonenkis.

Separació

Un model de classificació $f$ en algun vector de paràmetros $\theta$ és cridat separador d'un conjunt de punts ($x_1,x_2,\dots ,x_n$) si, per a totes les assignació de les etiquetes d'eixos punts, existix una $\theta$ tal que el model $f$ no té errors quan evalua eixe conjunt de punts.

La dimensió VC del model $f$ és el màxim $h$ per al qual algun punt del conjunt de senyes de cardinalidad $h$ pot ser separat per $f$.

Per eixemple, considerant una llínea recta com a model de classificació: el model amprat per un perceptrón. La llínea deuria separar els punts de classe "+" (positius) dels de classe "-" (negatius). Quan hi ha 3 punts que no siguen colineales, la llínea pot separar-los. No obstant, la llínea no pot separar 4 punts. És important recordar que un pot elegir una configuració de punts que poden ser separables per una recta, pero no podríem separar totes les permutació. Només 3 de les 8 permutació possibles són mostrades per a 3 punts.

Archiu:VC1.svg	Archiu:VC2.svg	Archiu:VC3.svg	Archiu:VC4.svg
Separació de 3 punts			Separació impossible en 4 punts

Use

La dimensió VC té utilitat en teoria d'aprenentage estadístic, perque pot predir el llímit superior provabilístic sobre l'error en el conjunt de prova.

El llímit sobre l'error en el conjunt de prova del model (en les senyes d'entrenament és independent i complix una distribució aleatòria de la mateixa distribució) està donat per

Error d'entrenament + $\sqrt{\frac{h(\log (2N/h)+1)-\log (\eta /4)}{N}}$

en provabilitat $1-\eta$, a on $h$ és la dimensió VC del model de classificació, i $N$ és el tamany del conjunt d'entrenament.