Dimenzija Vapnik-Chervonenkis (VC) je merilo zmogljivosti niza hipotez, da ustreza različnim nizom podatkov. Uvedla sta ga Vladimir Vapnik in Alexey Chervonenkis v sedemdesetih letih prejšnjega stoletja in je postal temeljni koncept v statistični teoriji učenja. Dimenzija VC je merilo kompleksnosti modela, ki nam lahko pomaga razumeti, kako dobro se lahko prilega različnim nizom podatkov.
Dimenzija VC niza hipotez H je največje število točk, ki jih lahko razbije H. Množica hipotez H razbije niz točk S, če za vsako možno oznako točk v S obstaja hipoteza v H, ki pravilno razvrsti točke. Z drugimi besedami, niz hipotez razbije niz točk, če se lahko prilega kakršnemu koli možnemu označevanju teh točk.
Meje VC – Dimenzija
Dimenzija VC zagotavlja zgornjo in spodnjo mejo števila primerov usposabljanja, potrebnih za doseganje dane stopnje natančnosti. Zgornja meja števila primerov usposabljanja je logaritemska v dimenziji VC, medtem ko je spodnja meja linearna.
Aplikacije VC – Dimension
Dimenzija VC ima široko paleto aplikacij strojno učenje in statistiko. Uporablja se na primer za analizo kompleksnosti nevronskih mrež, podpornih vektorskih strojev in odločitvenih dreves. Dimenzijo VC je mogoče uporabiti tudi za oblikovanje novih učnih algoritmov, ki so odporni na hrup in lahko dobro posplošijo na nevidne podatke.
Dimenzijo VC je mogoče razširiti na bolj zapletene scenarije učenja, kot sta večrazredna klasifikacija in regresija. Koncept dimenzije VC je mogoče uporabiti tudi na drugih področjih računalništva, kot sta računalniška geometrija in teorija grafov.
Implementacija kode za VC – Dimenzija
Dimenzija VC je teoretični koncept, ki ga ni mogoče neposredno izračunati iz podatkov. Vendar pa lahko ocenimo razsežnost VC za dani niz hipotez s štetjem števila točk, ki jih niz lahko razbije. V Pythonu lahko s tem pristopom implementiramo funkcijo, ki izračuna dimenzijo VC danega niza hipotez.
Funkcija sprejme niz hipotez kot svoj vhod in izračuna dimenzijo VC z uporabo brutalnega pristopa preverjanja vseh možnih kombinacij točk in oznak. Uporablja modul itertools za ustvarjanje vseh možnih kombinacij točk in oznak ter nato preveri, ali lahko nabor hipotez razbije vsako kombinacijo. Funkcija vrne ocenjeno dimenzijo VC nabora hipotez.
Ponazorimo uporabo te funkcije z nekaj primeri:
Primer 1:
Recimo, da imamo nabor hipotez, ki je sestavljen iz vseh linearnih funkcij oblike f(x) = ax + b, kjer sta a in b realni števili. To hipotezo v Pythonu lahko definiramo na naslednji način:
Python
import> itertools> > > def> vc_dimension(hypothesis_set):> >'''> >Estimates the VC dimension of a hypothesis set using the brute-force approach.> >'''> >n>=> 4> >while> True>:> >points>=> [(i, j)>for> i>in> range>(n)>for> j>in> range>(>2>)]> >shattered_sets>=> 0> >for> combination>in> itertools.combinations(points, n):> >is_shattered>=> True> >for> labeling>in> itertools.product([>0>,>1>], repeat>=>n):> >hypotheses>=> [hypothesis_set(point)>for> point>in> combination]> >if> set>(hypotheses) !>=> set>(labeling):> >is_shattered>=> False> >break> >if> is_shattered:> >shattered_sets>+>=> 1> >else>:> >break> >if> not> is_shattered:> >break> >n>+>=> 1> >return> n>->1> if> shattered_sets>=>=> 2>*>*>n>else> n>->2> > > # Example 1: linear function hypothesis set> def> linear_function(point):> >x, y>=> point> >return> int>(y>>=> x)> > > print>(vc_dimension(linear_function))> |
>
>
bah če drugače
Izhod:
2>
V primeru 1 funkcija linear_function izvaja nabor hipotez preproste linearne funkcije, ki vrne 1, če je koordinata y vhodne točke večja ali enaka koordinati x, in 0 v nasprotnem primeru. Funkcija vc_dimension se nato uporabi za oceno dimenzije VC tega niza hipotez, ki je 2.
Primer 2:
Recimo, da imamo nabor hipotez, ki je sestavljen iz vseh kvadratnih funkcij oblike f(x) = ax2+ bx + c, kjer so a, b in c realna števila. To lahko definiramo hipoteza nastavite v Pythonu na naslednji način:
Python
import> itertools> > > def> vc_dimension(hypothesis_set):> >'''> >Estimates the VC dimension of a hypothesis set using the brute-force approach.> >'''> >n>=> 5> >while> True>:> >points>=> [(i, j)>for> i>in> range>(n)>for> j>in> range>(>2>)]> >shattered_sets>=> 0> >for> combination>in> itertools.combinations(points, n):> >is_shattered>=> True> >for> labeling>in> itertools.product([>0>,>1>], repeat>=>n):> >hypotheses>=> [hypothesis_set(point)>for> point>in> combination]> >if> set>(hypotheses) !>=> set>(labeling):> >is_shattered>=> False> >break> >if> is_shattered:> >shattered_sets>+>=> 1> >else>:> >break> >if> not> is_shattered:> >break> >n>+>=> 1> >return> n>->1> if> shattered_sets>=>=> 2>*>*>n>else> n>->2> > > # Example 2: quadratic function hypothesis set> def> quadratic_function(point):> >x, y>=> point> >return> int>(y>>=> x>*>*>2>)> > > print>(vc_dimension(quadratic_function))> |
>
>
Izhod:
3>
V primeru 2 funkcija quadratic_function implementira bolj zapleten nabor hipotez o kvadratni funkciji, ki vrne 1, če je y-koordinata vhodne točke večja ali enaka kvadratu x-koordinate, in 0 v nasprotnem primeru. Funkcija vc_dimension se nato uporabi za oceno dimenzije VC tega niza hipotez, ki je 3.
Zaključek
Dimenzija VC je temeljni koncept v teoriji statističnega učenja, ki meri kompleksnost nabora hipotez. Zagotavlja zgornjo in spodnjo mejo števila primerov usposabljanja, potrebnih za doseganje dane stopnje natančnosti. V Pythonu lahko ocenimo dimenzijo VC danega nabora hipotez z uporabo brutalnega pristopa, ki preverja vse možne kombinacije točk in oznak. Dimenzija VC ima široko paleto aplikacij v strojnem učenju in statistiki ter jo je mogoče razširiti na bolj zapletene scenarije učenja.