Vapnik-Chervonenkis dimension

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 .

Definition

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. $x$ ${\mathcal {F}}=\{f(x,\alpha )\}$ $x\i X$ $\alfa$ $f(x,\alpha )$ $x$ ${\mathcal {F}}$ $h$ $h$ $x$ ${\mathcal {F}}$ $h$

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] $\{g(x,\alpha )\}$ $\{I(g(x,\alpha )>\beta )\}$ $\beta$ $g$

Eksempler

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. $2^{3}=8$


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 . $n$ $n+1$

Se også

Support vektor maskine

Noter

↑ Hastie, T., Tibshirani R., Friedman J. Kapitel 7.9. Vapnik–Chervonenkis Dimension // Elementerne i statistisk læring: Data mining, inferens og forudsigelse . — 2. udg. - Springer-Verlag, 2009. - 746 s. - ISBN 978-0-387-84857-0 . .

Machine learning og data mining
Opgaver	Klassificeringsproblem Læring uden lærer Lærerassisteret læring Regressions analyse AutoML Foreningens regler Feature Extraction Træning af træk Ranking træning Grammatisk afledning Online læring
At lære med en lærer	k-nærmeste nabo metode Naiv Bayes Classifier beslutningstræ Support vektor maskine Lineær regression Logistisk regression perceptron Ensembler af modeller Bagning boostning tilfældig skov Relevant vektormetode
klyngeanalyse	k-betyder metode Fuzzy klyngemetode Hierarkisk klyngedannelse EM algoritme BIRKE HELBREDE DBSCAN OPTIK Middel-forskydning
Dimensionalitetsreduktion	Faktoranalyse Hovedkomponentmetode CCA ICA LDA Ikke-negativ matrixudvidelse t-SNE
Strukturel prognose	Graf probabilistisk model Bayesiansk netværk Skjult Markov-model CRF
Anomali detektion	k-nærmeste nabo metode Lokalt emissionsniveau
Grafer sandsynlighedsmodeller	Bayesiansk netværk Markov netværk Skjult Markov-model
Neurale netværk	Begrænset Boltzmann-maskine selvorganiserende kort Aktiveringsfunktion Sigmoid softmax Radial basisfunktion Rygformeringsmetode Dyb læring Flerlagsperceptron Tilbagevendende neurale netværk lang korttidshukommelse Kontrolleret tilbagevendende blokering Konvolutionelt neuralt netværk U-net Autoencoder
Forstærkende læring	Markov proces Bellmans ligning Grådig algoritme Q-læring SARSA Temporal forskel (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beregningsmæssig læringsteori Empirisk risikominimering Occams læring PAC læring Statistisk læringsteori
Tidsskrifter og konferencer	NeurIPS ICML ML JMLR ArXiv:cs.LG

Vapnik-Chervonenkis dimension

Definition

Eksempler

Se også

Links

Noter