Vapnik-Chervonenkis- dimensionen eller VC-dimensionen er en karakteristik af en familie af algoritmer til løsning af et klassifikationsproblem med to klasser, der karakteriserer kompleksiteten eller kapaciteten af denne familie. Det er et af nøglebegreberne i Vapnik-Chervonenkis teori om statistisk maskinlæring og er opkaldt efter Vladimir Vapnik og Alexey Chervonenkis .
Vapnik og Chervonenkis foretrækker selv at kalde denne mængde for kombinatorisk dimension , da det viste sig, at det var kendt af algebraister allerede før opdagelsen af deres teori om maskinlæring .
Lad et sæt og en familie af indikatorfunktioner (klassificeringsalgoritmer, beslutningsregler) gives , hvor er argumentet for funktionerne, er vektoren af parametre, der definerer funktionen. Hver sådan funktion tildeler hvert element i sættet en af de to givne klasser. VC-dimensionen af en familie er det største tal , således at der er en delmængde af elementerne i mængden , som fungerer fra kan opdeles i to klasser på alle mulige måder. Hvis sådanne delmængder eksisterer for arbitrært store , antages VC-dimensionen at være lig med uendelig.
VC-dimensionen kan også generaliseres til tilfældet med en familie af funktioner, der tager reelle værdier. Dens VC-dimension er defineret som VC-dimensionen af familien af indikatorfunktioner , hvor rækken af funktioner . [en]
Som et eksempel kan du overveje problemet med at dele punkter på et plan i to klasser med en ret linje - dette er den såkaldte lineære klassifikator . Et sæt af vilkårlige tre punkter, der ikke ligger på en ret linje, kan opdeles med en lige linje i to klasser på alle mulige måder ( måderne vist i figuren nedenfor viser tre af dem), men der er ikke længere et sæt af fire eller flere point. Derfor er VC-dimensionen af den lineære klassifikator på planet lig med tre.
Eksempler på at dele tre point i to klasser |
Adskillelse er umulig for disse fire punkter |
I det generelle tilfælde er VC-dimensionen af lineære klassifikatorer i det dimensionelle rum .
Machine learning og data mining | |
---|---|
Opgaver | |
At lære med en lærer | |
klyngeanalyse | |
Dimensionalitetsreduktion | |
Strukturel prognose | |
Anomali detektion | |
Grafer sandsynlighedsmodeller | |
Neurale netværk | |
Forstærkende læring |
|
Teori | |
Tidsskrifter og konferencer |
|