Dimensió de Vapnik–Chervonenkis

Diagrama de classificació binària.

En la teoria de Vapnik–Chervonenkis, la dimensió de Vapnik–Chervonenkis (VC) és una mesura de la capacitat (complexitat, poder expressiu, riquesa o flexibilitat) d'un conjunt de funcions que es poden aprendre mitjançant un algorisme de classificació binària estadística. Es defineix com la cardinalitat del conjunt més gran de punts que l'algorisme pot trencar, el que significa que l'algoritme sempre pot aprendre un classificador perfecte per a qualsevol etiquetatge d'almenys una configuració d'aquests punts de dades. Va ser definit originalment per Vladimir Vapnik i Alexey Chervonenkis.^[1]

De manera informal, la capacitat d'un model de classificació està relacionada amb la complexitat que pot ser. Per exemple, considereu el llindar d'un polinomi d'alt grau: si el polinomi es valora per sobre de zero, aquest punt es classifica com a positiu, en cas contrari com a negatiu. Un polinomi d'alt grau pot ser ondulat, de manera que pot adaptar-se bé a un conjunt determinat de punts d'entrenament. Però es pot esperar que el classificador cometi errors en altres punts, perquè és massa ondulant. Aquest polinomi té una gran capacitat. Una alternativa molt més senzilla és llindar una funció lineal. És possible que aquesta funció no s'ajusti bé al conjunt d'entrenament, perquè té una capacitat baixa.^[2][3][4][5]

Usos en teoria de l'aprenentatge estadístic: La dimensió VC pot predir un límit superior probabilístic de l'error de prova d'un model de classificació. Vapnik^[6] va demostrar que la probabilitat que l'error de la prova (és a dir, el risc amb la funció de pèrdua 0-1) s'allunyi d'un límit superior (en dades extretes iid de la mateixa distribució que el conjunt d'entrenament) ve donada per:

${\displaystyle \Pr \left({\text{error de test}}\leqslant {\text{error d'entrenament}}+{\sqrt {{\frac {1}{N}}\left[D\left(\log \left({\tfrac {2N}{D}}\right)+1\right)-\log \left({\tfrac {\eta }{4}}\right)\right]}}\,\right)=1-\eta ,}$

on ${\displaystyle D}$ és la dimensió VC del model de classificació, ${\displaystyle 0<\eta \leqslant 1}$, i ${\displaystyle N}$ és la mida del conjunt d'entrenament (restricció: aquesta fórmula és vàlida quan ${\displaystyle D\ll N}$ . Quan ${\displaystyle D}$ és més gran, l'error de prova pot ser molt més gran que l'error d'entrenament. Això es deu a un sobreajust).

La dimensió VC també apareix als límits de complexitat de la mostra. Un espai de funcions binàries amb dimensió VC ${\displaystyle D}$ es pot aprendre amb:

${\displaystyle N=\Theta \left({\frac {D+\ln {1 \over \delta }}{\varepsilon }}\right)}$

mostres, on ${\displaystyle \varepsilon }$ és l'error d'aprenentatge i ${\displaystyle \delta }$ és la probabilitat de fallada. Així, la complexitat de la mostra és una funció lineal de la dimensió VC de l'espai d'hipòtesi.

Referències

1. Vapnik, V. N.; Chervonenkis, A. Ya.. On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities (en anglès). Cham: Springer International Publishing, 2015, p. 11–30. DOI 10.1007/978-3-319-21852-6_3. ISBN 978-3-319-21852-6. 
2. «Vapnik–Chervonenkis classes» (en anglès). http://maxim.ece.illinois.edu.+[Consulta: 2 abril 2023].
3. «Support Vector Machine» (en anglès). https://cml.rhul.ac.uk.+[Consulta: 2 abril 2023].
4. «Lecture 19: The Proof of the Vapnik-Chervonenkis (VC) Inequality» (en anglès). https://nowak.ece.wisc.edu.+[Consulta: 2 abril 2023].
5. Mattioli, Gabriele. «Vapnik–Chervonenkis theory, explained» (en anglès). https://www.cantorsparadise.com,[phone].+[Consulta: 2 abril 2023].
6. Vapnik, 2000.