Vapnik-Chervonenkis dimension

Vapnik-Chervonenkis- dimensionen eller VC-dimensionen är en egenskap hos en familj av algoritmer för att lösa ett klassificeringsproblem med två klasser, vilket kännetecknar komplexiteten eller kapaciteten hos denna familj. Det är ett av nyckelbegreppen i Vapnik-Chervonenkis teori om statistisk maskininlärning och är uppkallad efter Vladimir Vapnik och Alexey Chervonenkis .

Vapnik och Chervonenkis själva föredrar att kalla denna kvantitetskombinatoriska dimension , eftersom det visade sig att den var känd för algebraister redan innan upptäckten av deras teori om maskininlärning .

Definition

Låt en uppsättning och någon familj av indikatorfunktioner (klassificeringsalgoritmer, beslutsregler) ges , där är argumentet för funktionerna, är vektorn av parametrar som definierar funktionen. Varje sådan funktion tilldelar varje element i mängden en av de två givna klasserna. VC-dimensionen av en familj är det största antalet , så att det finns en delmängd av elementen i mängden , som fungerar från kan delas in i två klasser på alla möjliga sätt. Om sådana delmängder existerar för godtyckligt stora , antas VC-dimensionen vara lika med oändligheten. $X$ ${\mathcal {F}}=\{f(x,\alpha )\}$ $x\i X$ $\alfa$ $f(x,\alfa )$ $X$ ${\mathcal {F}}$ $h$ $h$ $X$ ${\mathcal {F}}$ $h$

VC-dimensionen kan också generaliseras till fallet med en familj av funktioner som tar verkliga värden. Dess VC-dimension definieras som VC-dimensionen för familjen av indikatorfunktioner , där funktionsomfånget . [ett] $\{g(x,\alpha )\}$ $\{I(g(x,\alpha )>\beta )\}$ $\beta$ $g$

Exempel

Som ett exempel, överväg problemet med att dela punkter på ett plan i två klasser med en rak linje - detta är den så kallade linjära klassificeraren . En uppsättning av tre punkter som inte ligger på en rät linje kan delas med en rät linje i två klasser på alla möjliga sätt ( sätten som visas i figuren nedan visar tre av dem), men det finns inte längre en uppsättning av fyra eller fler poäng. Därför är VC-dimensionen för den linjära klassificeraren på planet lika med tre. $2^{3}=8$


Exempel på att dela upp tre poäng i två klasser			Separation är omöjlig för dessa fyra punkter

I det allmänna fallet är VC-dimensionen för linjära klassificerare i dimensionsrymden . $n$ $n+1$

Se även

Stöd vektor maskin

Länkar

Information från webbplatsen www.machinelearning.ru

Anteckningar

↑ Hastie, T., Tibshirani R., Friedman J. Kapitel 7.9. Vapnik–Chervonenkis dimension // Elementen för statistiskt lärande: Datautvinning, slutledning och förutsägelse . — 2:a uppl. - Springer-Verlag, 2009. - 746 sid. - ISBN 978-0-387-84857-0 . .

Maskininlärning och datautvinning
Uppgifter	Klassificeringsproblem Lärande utan lärare Lärarassisterat lärande Regressionsanalys AutoML Föreningens regler Särdragsextraktion Egenskapsträning Ranking utbildning Grammatisk härledning Online lärande
Att lära sig med en lärare	k-närmaste granne metod Naiv Bayes klassificerare beslutsträd Stöd vektor maskin Linjär regression Logistisk tillbakagång perceptron Ensembler av modeller Säckväv förstärkning slumpmässig skog Relevant vektormetod
klusteranalys	k-betyder metod Fuzzy klustringsmetod Hierarkisk klustring EM algoritm BJÖRK BOTA DBSCAN OPTIK Genomsnittlig förskjutning
Dimensionalitetsreduktion	Faktoranalys Huvudkomponentmetoden CCA ICA LDA Icke-negativ matrisexpansion t-SNE
Strukturell prognos	Graph probabilistisk modell Bayesiskt nätverk Dold Markov-modell CRF
Anomali upptäckt	k-närmaste granne metod Lokal utsläppsnivå
Grafisk probabilistiska modeller	Bayesiskt nätverk Markov nätverk Dold Markov-modell
Neurala nätverk	Begränsad Boltzmann-maskin självorganiserande karta Aktiveringsfunktion Sigmoid softmax Radiell basfunktion Ryggförökningsmetod Djup lärning Flerskiktsperceptron Återkommande neurala nätverk långtidsminne Kontrollerat återkommande block Konvolutionellt neuralt nätverk U-Net Autokodare
Förstärkningsinlärning	Markov process Bellmans ekvation Girig algoritm Q-lärande SARSA Temporell skillnad (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beräkningslärandeteori Empirisk riskminimering Occam lär sig PAC-inlärning Statistisk inlärningsteori
Tidskrifter och konferenser	NeurIPS ICML ML JMLR ArXiv:cs.LG