Dimensionen Vapnik-Chervonenkis (VC) är ett mått på kapaciteten hos en hypotesuppsättning att passa olika datamängder. Det introducerades av Vladimir Vapnik och Alexey Chervonenkis på 1970-talet och har blivit ett grundläggande begrepp inom statistisk inlärningsteori. VC-dimensionen är ett mått på komplexiteten hos en modell, vilket kan hjälpa oss att förstå hur väl den kan passa olika datamängder.
VC-dimensionen för en hypotesuppsättning H är det största antalet punkter som kan krossas av H. En hypotesuppsättning H splittrar en uppsättning punkter S om det för varje möjlig märkning av punkterna i S finns en hypotes i H som klassificerar poängen korrekt. Med andra ord, en hypotesuppsättning krossar en uppsättning punkter om den kan passa någon möjlig märkning av dessa punkter.
Bounds of VC – Dimension
VC-dimensionen ger både övre och nedre gränser för antalet träningsexempel som krävs för att uppnå en given noggrannhetsnivå. Den övre gränsen för antalet träningsexempel är logaritmisk i VC-dimensionen, medan den nedre gränsen är linjär.
funktioner i en pandaserie
Tillämpningar av VC – Dimension
VC-dimensionen har ett brett utbud av applikationer inom maskininlärning och statistik. Till exempel används den för att analysera komplexiteten hos neurala nätverk, stödja vektormaskiner och beslutsträd. VC-dimensionen kan också användas för att designa nya inlärningsalgoritmer som är robusta mot brus och kan generalisera bra till osynliga data.
VC-dimensionen kan utvidgas till mer komplexa inlärningsscenarier, såsom flerklassklassificering och regression. Konceptet med VC-dimensionen kan också appliceras på andra områden inom datavetenskap, såsom beräkningsgeometri och grafteori.
Kodimplementering för VC – Dimension
VC-dimensionen är ett teoretiskt begrepp som inte direkt kan beräknas från data. Vi kan dock uppskatta VC-dimensionen för en given hypotesmängd genom att räkna antalet punkter som kan krossas av mängden. I Python kan vi implementera en funktion som beräknar VC-dimensionen för en given hypotesuppsättning med detta tillvägagångssätt.
Funktionen tar en hypotesuppsättning som indata och beräknar VC-dimensionen med hjälp av brute-force-metoden att kontrollera alla möjliga kombinationer av punkter och etiketter. Den använder modulen itertools för att generera alla möjliga kombinationer av punkter och etiketter och kontrollerar sedan om hypotesuppsättningen kan krossa varje kombination. Funktionen returnerar den uppskattade VC-dimensionen för hypotesuppsättningen.
Låt oss illustrera användningen av denna funktion med några exempel:
Exempel 1:
Antag att vi har en hypotesmängd som består av alla linjära funktioner av formen f(x) = ax + b, där a och b är reella tal. Vi kan definiera denna hypotesuppsättning i Python enligt följande:
Pytonorm
infoga vattenstämpel i word
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))> |
fjäderstövel
>
>
Produktion:
2>
I exempel 1 implementerar funktionen linear_function en enkel linjär funktionshypotesuppsättning som returnerar 1 om y-koordinaten för ingångspunkten är större än eller lika med x-koordinaten, och 0 annars. Funktionen vc_dimension används sedan för att uppskatta VC-dimensionen för denna hypotesuppsättning, som är 2.
Exempel 2:
Antag att vi har en hypotesmängd som består av alla andragradsfunktioner av formen f(x) = ax2+ bx + c, där a, b och c är reella tal. Vi kan definiera detta hypotes ställ in i Python enligt följande:
Pytonorm
css gräns
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))> |
>
>
java-sträng till heltal
Produktion:
3>
I exempel 2 implementerar quadratic_function-funktionen en mer komplex kvadratisk funktionshypotesuppsättning som returnerar 1 om y-koordinaten för ingångspunkten är större än eller lika med kvadraten på x-koordinaten, och 0 annars. Funktionen vc_dimension används sedan för att uppskatta VC-dimensionen för denna hypotesuppsättning, som är 3.
Slutsats
VC-dimensionen är ett grundläggande begrepp inom statistisk inlärningsteori som mäter komplexiteten hos en hypotesuppsättning. Det ger både övre och nedre gränser för antalet träningsexempel som krävs för att uppnå en viss noggrannhetsnivå. I Python kan vi uppskatta VC-dimensionen för en given hypotesuppsättning med hjälp av en brute-force-metod som kontrollerar alla möjliga kombinationer av punkter och etiketter. VC-dimensionen har ett brett utbud av tillämpningar inom maskininlärning och statistik och kan utökas till mer komplexa inlärningsscenarier.