Dimenze Vapnik-Chervonenkis

Vapnik-Chervonenkisova dimenze nebo VC-dimenze je charakteristika rodiny algoritmů pro řešení klasifikačního problému se dvěma třídami, charakterizující složitost nebo kapacitu této rodiny. Je to jeden z klíčových konceptů Vapnik-Chervonenkis teorie statistického strojového učení a je pojmenován po Vladimir Vapnik a Alexey Chervonenkis .

Vapnik a Chervonenkis sami raději nazývají tuto veličinu kombinatorickou dimenzí , protože se ukázalo, že byla známa algebraistům ještě před objevem jejich teorie strojového učení .

Definice

Nechť je dána množina a nějaká rodina indikátorových funkcí (klasifikační algoritmy, rozhodovací pravidla) , kde je argument funkcí, je vektor parametrů definujících funkci. Každá taková funkce přiřadí každému prvku množiny jednu ze dvou daných tříd. VC-dimenze rodiny je největší číslo , takže existuje podmnožina prvků množiny , které funkce z lze rozdělit do dvou tříd všemi možnými způsoby. Pokud takové podmnožiny existují pro libovolně velké , pak se předpokládá, že VC-rozměr je rovna nekonečnu. $X$ ${\mathcal {F}}=\{f(x,\alpha )\}$ $x\in X$ $\alpha$ $f(x,\alpha)$ $X$ ${\mathcal {F}}$ $h$ $h$ $X$ ${\mathcal {F}}$ $h$

Dimenze VC lze také zobecnit na případ rodiny funkcí nabývajících skutečných hodnot. Jeho VC-dimenze je definována jako VC-dimenze rodiny indikátorových funkcí , kde rozsah funkcí . [jeden] $\{g(x,\alpha )\}$ $\{I(g(x,\alpha )>\beta )\}$ $\beta$ $G$

Příklady

Jako příklad si uveďme problém dělení bodů v rovině do dvou tříd přímkou – jedná se o tzv. lineární klasifikátor . Množinu libovolných tří bodů, které neleží na jedné přímce, lze rozdělit přímkou do dvou tříd všemi možnými způsoby ( způsoby zobrazené na obrázku níže znázorňují tři z nich), ale již neexistuje množina čtyři nebo více bodů. Proto je VC-rozměr lineárního klasifikátoru v rovině roven třem. $2^{3}=8$


Příklady rozdělení tří bodů do dvou tříd			Pro tyto čtyři body je oddělení nemožné

V obecném případě je VC-dimenze lineárních klasifikátorů v -rozměrném prostoru . $n$ $n+1$

Viz také

Podpora vektorového stroje

Odkazy

Informace z webu www.machinelearning.ru

Poznámky

↑ Hastie, T., Tibshirani R., Friedman J. Kapitola 7.9. Dimenze Vapnik–Chervonenkis // Prvky statistického učení: dolování dat, odvození a predikce . — 2. vyd. - Springer-Verlag, 2009. - 746 s. - ISBN 978-0-387-84857-0 . .

Strojové učení a dolování dat
Úkoly	Klasifikační problém Učení bez učitele Učení za pomoci učitele Regresní analýza AutoML Pravidla asociace Extrakce funkcí Trénink vlastností Žebříčkový trénink Gramatické odvozování Online učení
Učení s učitelem	metoda k-nejbližšího souseda Naivní Bayesův klasifikátor rozhodovací strom Podpora vektorového stroje Lineární regrese Logistická regrese perceptron Soubory modelů Pytlování posilování náhodný les Relevantní vektorová metoda
shluková analýza	metoda k-means Metoda fuzzy shlukování Hierarchické shlukování EM algoritmus BŘÍZA LÉK DBSCAN OPTIKA Střední posun
Redukce rozměrů	Faktorová analýza Metoda hlavní součásti CCA ICA LDA Nezáporná expanze matice t-SNE
Strukturální prognózy	Graf pravděpodobnosti modelu Bayesovská síť Skrytý Markovův model CRF
Detekce anomálií	metoda k-nejbližšího souseda Místní úroveň emisí
Grafové pravděpodobnostní modely	Bayesovská síť Markovská síť Skrytý Markovův model
Neuronové sítě	Limitovaný Boltzmannův stroj samoorganizující se mapa Aktivační funkce Sigmoid softmax Radiální základní funkce Metoda zpětného šíření Hluboké učení Vícevrstvý perceptron Rekurentní neuronová síť dlouhodobá krátkodobá paměť Řízený rekurentní blok Konvoluční neuronová síť U-Net Autokodér
Posílení učení	Markovský proces Bellmanova rovnice Chamtivý algoritmus Q-učení SARSA Časový rozdíl (TD)
Teorie	Vapnik-Chervonenkis teorie Dilema zkreslení Počítačová teorie učení Empirická minimalizace rizika Occam se učí PAC učení Statistická teorie učení
Časopisy a konference	NeurIPS ICML ML JMLR ArXiv:cs.LG