Dimensiunea Vapnik-Chervonenkis

Dimensiunea Vapnik-Chervonenkis sau dimensiunea VC este o caracteristică a unei familii de algoritmi pentru rezolvarea unei probleme de clasificare cu două clase, care caracterizează complexitatea sau capacitatea acestei familii. Este unul dintre conceptele cheie din teoria Vapnik-Chervonenkis a învățării automate statistice și poartă numele lui Vladimir Vapnik și Alexey Chervonenkis .

Vapnik și Chervonenkis înșiși preferă să numească această dimensiune dimensiune combinatorie , deoarece s-a dovedit că ea era cunoscută de algebriști chiar înainte de descoperirea teoriei lor despre învățarea automată .

Definiție

Să fie date o mulțime și o familie de funcții indicator (algoritmi de clasificare, reguli de decizie) , unde este argumentul funcțiilor, este vectorul parametrilor care definesc funcția. Fiecare astfel de funcție atribuie fiecărui element al mulțimii una dintre cele două clase date. Dimensiunea VC a unei familii este cel mai mare număr , astfel încât există o submulțime de elemente ale mulțimii , din care funcționează poate fi împărțită în două clase în toate modurile posibile. Dacă astfel de submulțimi există pentru arbitrar mare , atunci dimensiunea VC se presupune a fi egală cu infinitul. $X$ ${\mathcal {F}}=\{f(x,\alpha )\}$ $x\în X$ $\alfa$ $f(x,\alpha)$ $X$ ${\mathcal {F}}$ $h$ $h$ $X$ ${\mathcal {F}}$ $h$

Dimensiunea VC poate fi generalizată și în cazul unei familii de funcții care iau valori reale. Dimensiunea sa VC este definită ca dimensiunea VC a familiei de funcții indicator , unde gama de funcții . [unu] $\{g(x,\alpha )\}$ $\{I(g(x,\alpha )>\beta )\}$ $\beta$ $g$

Exemple

Ca exemplu, luați în considerare problema împărțirii punctelor de pe un plan în două clase printr-o linie dreaptă - acesta este așa-numitul clasificator liniar . Un set de orice trei puncte care nu se află pe o singură linie dreaptă poate fi împărțit printr-o linie dreaptă în două clase în toate modurile posibile ( modurile prezentate în figura de mai jos arată trei dintre ele), dar nu mai există un set de patru sau mai multe puncte. Prin urmare, dimensiunea VC a clasificatorului liniar pe plan este egală cu trei. $2^{3}=8$


Exemple de împărțire a trei puncte în două clase			Separarea este imposibilă pentru aceste patru puncte

În cazul general, dimensiunea VC a clasificatoarelor liniare în spațiul -dimensional este . $n$ $n+1$

Vezi și

Suport mașină vectorială

Link -uri

Informații de pe site-ul www.machinelearning.ru

Note

↑ Hastie, T., Tibshirani R., Friedman J. Capitolul 7.9. Dimensiunea Vapnik–Chervonenkis // Elementele învățării statistice: extragerea datelor, inferența și predicția . — Ed. a II-a. - Springer-Verlag, 2009. - 746 p. - ISBN 978-0-387-84857-0 . .

Învățare automată și extragerea datelor
Sarcini	Problema de clasificare Învățați fără profesor Învățare asistată de profesor Analiza regresiei AutoML Regulile de asociere Extragerea caracteristicilor Antrenamentul trăsăturilor Antrenament de clasare Derivarea gramaticală Învățare online
Învățarea cu un profesor	metoda k-cel mai apropiat vecin Clasificator naiv Bayes arborele de decizie Suport mașină vectorială Regresie liniara Regresie logistică perceptron Ansambluri de modele Bagare stimularea pădure la întâmplare Metoda vectorială relevantă
analiza grupului	metoda k-means Metoda de grupare fuzzy Gruparea ierarhică algoritmul EM MESTEACĂN VINDECA DBSCAN OPTICA Schimbare medie
Reducerea dimensionalității	Analiza factorilor Metoda componentei principale CCA ICA LDA Expansiunea nenegativă a matricei t-SNE
Prognoza structurală	Modelul probabilistic grafic Rețeaua bayesiană Modelul Markov ascuns CRF
Detectarea anomaliilor	metoda k-cel mai apropiat vecin Nivelul de emisie local
Modele grafice probabilistice	Rețeaua bayesiană Rețeaua Markov Modelul Markov ascuns
Rețele neuronale	Mașină Boltzmann limitată hartă de auto-organizare Funcția de activare Sigmoid softmax Funcția de bază radială Metoda de propagare înapoi Invatare profunda Perceptron multistrat Rețea neuronală recurentă memorie pe termen lung și scurt Bloc recurent controlat Rețeaua neuronală convoluțională U-Net Autoencoder
Consolidarea învățării	procesul Markov Ecuația Bellman Algoritmul lacom Q-learning SARSA Diferența temporală (TD)
Teorie	Teoria Vapnik-Chervonenkis Dilema părtinire-dispersie Teoria învățării computaționale Minimizarea riscului empiric Occam învață Învățarea PAC Teoria învăţării statistice
Reviste și conferințe	NeurIPS ICML ML JMLR ArXiv:cs.LG