Vapnik-Chervonenkis (VC) dimensija ir hipotēzes kopas kapacitātes mērs, lai tas atbilstu dažādām datu kopām. To ieviesa Vladimirs Vapņiks un Aleksejs Červoņenkis 1970. gados, un tas ir kļuvis par fundamentālu jēdzienu statistikas mācīšanās teorijā. VC dimensija ir modeļa sarežģītības mērs, kas var palīdzēt mums saprast, cik labi tas var atbilst dažādām datu kopām.
Hipotēžu kopas H VC dimensija ir lielākais punktu skaits, ko var sagraut H. Hipotēžu kopa H sagrauj punktu kopu S, ja katram iespējamajam punktu apzīmējumam S eksistē hipotēze H, ka pareizi klasificē punktus. Citiem vārdiem sakot, hipotēžu kopa sagrauj punktu kopu, ja tā atbilst jebkuram iespējamam šo punktu marķējumam.
VC robežas – dimensija
VC dimensija nodrošina gan augšējo, gan apakšējo robežu apmācību piemēru skaitam, kas nepieciešams, lai sasniegtu noteiktu precizitātes līmeni. Apmācības piemēru skaita augšējā robeža ir logaritmiska VC dimensijā, bet apakšējā robeža ir lineāra.
VC pielietojumi – dimensija
VC dimensijai ir plašs lietojumu klāsts mašīnmācība un statistika. Piemēram, to izmanto, lai analizētu neironu tīklu, atbalsta vektora mašīnu un lēmumu koku sarežģītību. VC dimensiju var izmantot arī, lai izstrādātu jaunus mācīšanās algoritmus, kas ir izturīgi pret troksni un var labi vispārināt neredzamus datus.
VC dimensiju var attiecināt uz sarežģītākiem mācīšanās scenārijiem, piemēram, vairāku klašu klasifikāciju un regresiju. VC dimensijas jēdzienu var izmantot arī citās datorzinātņu jomās, piemēram, skaitļošanas ģeometrijā un grafu teorijā.
Koda ieviešana VC — Dimensija
VC dimensija ir teorētiska koncepcija, ko nevar tieši aprēķināt no datiem. Tomēr mēs varam novērtēt VC dimensiju konkrētai hipotēzes kopai, saskaitot punktu skaitu, ko kopa var sagraut. Programmā Python mēs varam ieviest funkciju, kas, izmantojot šo pieeju, aprēķina noteiktas hipotēžu kopas VC dimensiju.
Funkcija izmanto hipotēzes kopu kā ievadi un aprēķina VC dimensiju, izmantojot brutālā spēka pieeju, pārbaudot visas iespējamās punktu un etiķešu kombinācijas. Tas izmanto itertools moduli, lai ģenerētu visas iespējamās punktu un etiķešu kombinācijas, un pēc tam pārbauda, vai hipotēžu kopa var sagraut katru kombināciju. Funkcija atgriež hipotēžu kopas aprēķināto VC dimensiju.
Ilustrēsim šīs funkcijas lietošanu ar dažiem piemēriem:
1. piemērs:
Pieņemsim, ka mums ir hipotēžu kopa, kas sastāv no visām lineārajām funkcijām formā f(x) = ax + b, kur a un b ir reāli skaitļi. Mēs varam definēt šo hipotēzi Python šādi:
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>>> > > print>(vc_dimension(linear_function))> |
>
>
Izvade:
2>
1. piemērā funkcija lineārā_funkcija īsteno vienkāršu lineāro funkciju hipotēžu kopu, kas atgriež 1, ja ievades punkta y-koordināta ir lielāka vai vienāda ar x-koordinātu un 0 pretējā gadījumā. Pēc tam funkcija vc_dimension tiek izmantota, lai novērtētu šīs hipotēzes kopas VC dimensiju, kas ir 2.
2. piemērs:
Pieņemsim, ka mums ir hipotēžu kopa, kas sastāv no visām kvadrātfunkcijām formā f(x) = ax2+ bx + c, kur a, b un c ir reāli skaitļi. Mēs to varam definēt hipotēze iestatiet Python šādi:
Python
linux komandas, kuras
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>>>*>*>2>)> > > print>(vc_dimension(quadratic_function))> |
>
>
Izvade:
3>
2. piemērā funkcija kvadrātiskā_funkcija īsteno sarežģītāku kvadrātiskās funkcijas hipotēzes kopu, kas atgriež 1, ja ievades punkta y-koordināta ir lielāka vai vienāda ar x-koordinātas kvadrātu un 0 pretējā gadījumā. Pēc tam funkcija vc_dimension tiek izmantota, lai novērtētu šīs hipotēzes kopas VC dimensiju, kas ir 3.
Secinājums
VC dimensija ir statistikas mācīšanās teorijas pamatjēdziens, kas mēra hipotēžu kopas sarežģītību. Tas nodrošina gan augšējās, gan apakšējās robežas apmācības piemēru skaitam, kas nepieciešams, lai sasniegtu noteiktu precizitātes līmeni. Programmā Python mēs varam novērtēt dotās hipotēzes kopas VC dimensiju, izmantojot brutālā spēka pieeju, kas pārbauda visas iespējamās punktu un etiķešu kombinācijas. VC dimensijai ir plašs lietojumu klāsts mašīnmācībā un statistikā, un to var attiecināt uz sarežģītākiem mācību scenārijiem.