Vapnik-Chervonenkis dimenzió

A Vapnik-Chervonenkis dimenzió vagy VC-dimenzió egy két osztályú osztályozási probléma megoldására szolgáló algoritmuscsalád jellemzője, amely a család összetettségét vagy kapacitását jellemzi. Ez a statisztikai gépi tanulás Vapnik-Chervonenkis elméletének egyik kulcsfogalma, és Vladimir Vapnik és Alexey Chervonenkis nevéhez fűződik .

Maguk Vapnik és Chervonenkis inkább kombinatorikus dimenziónak nevezik ezt a mennyiséget , mivel kiderült, hogy az algebraisták már a gépi tanulás elméletének felfedezése előtt ismerték .

Definíció

Legyen adott egy halmaz és néhány indikátorfüggvénycsalád (osztályozó algoritmusok, döntési szabályok) , ahol a függvények argumentuma, a függvényt meghatározó paraméterek vektora. Minden ilyen függvény a halmaz minden eleméhez rendel egyet a két adott osztály közül. Egy család VC-dimenziója a legnagyobb szám , így a halmaz elemeinek van egy részhalmaza , amely függvények minden lehetséges módon két osztályra oszthatók. Ha léteznek ilyen részhalmazok tetszőlegesen nagy esetén, akkor a VC-dimenziót egyenlőnek tételezzük fel a végtelennel. $x$ ${\mathcal {F}}=\{f(x,\alpha )\}$ $x\X-ben$ $\alpha$ $f(x,\alpha )$ $x$ ${\mathcal {F}}$ $h$ $h$ $x$ ${\mathcal {F}}$ $h$

A VC-dimenzió általánosítható egy valós értékeket felvevő függvénycsalád esetére is . VC-dimenziója az indikátorfüggvények családjának VC-dimenziója , ahol a függvények tartománya . [egy] $\{g(x,\alpha )\}$ $\{I(g(x,\alpha )>\beta )\}$ $\beta$ $g$

Példák

Példaként tekintsük a síkon lévő pontok egyenes vonallal történő két osztályra osztásának problémáját - ez az úgynevezett lineáris osztályozó . Egy tetszőleges három pontból álló halmaz, amely nem egy egyenesen fekszik, minden lehetséges módon felosztható egy egyenessel két osztályra ( az alábbi ábrán látható módok közül hármat mutatnak be), de már nincs négy vagy több pont. Ezért a lineáris osztályozó VC-dimenziója a síkon egyenlő hárommal. $2^{3}=8$


Példák három pont két osztályra osztására			Ennek a négy pontnak a szétválasztása lehetetlen

Általános esetben a lineáris osztályozók VC-dimenziója a -dimenziós térben . $n$ $n+1$

Lásd még

Támogatja a vektoros gépet

Linkek

Információ a www.machinelearning.ru webhelyről

Jegyzetek

↑ Hastie, T., Tibshirani R., Friedman J. 7.9. fejezet. Vapnik–Chervonenkis dimenzió // A statisztikai tanulás elemei: adatbányászat, következtetés és előrejelzés . — 2. kiadás. - Springer-Verlag, 2009. - 746 p. - ISBN 978-0-387-84857-0 . .

Gépi tanulás és adatbányászat
Feladatok	Osztályozási feladat Tanulás tanár nélkül Tanár által segített tanulás Regresszió analízis AutoML Egyesületi szabályzat Funkció kivonás Tulajdonságok képzése Rangsorképzés Nyelvtani levezetés Online tanulás
Tanulás tanárral	k-legközelebbi szomszéd módszer Naiv Bayes osztályozó döntési fa Támogatja a vektoros gépet Lineáris regresszió Logisztikus regresszió perceptron Modellegyüttesek Zsákolás fellendítése véletlenszerű erdő Releváns vektoros módszer
klaszteranalízis	k-módszer Fuzzy klaszterezési módszer Hierarchikus klaszterezés EM algoritmus NYÍR GYÓGYMÓD DBSCAN OPTIKA Átlageltolás
Dimenziócsökkentés	Faktoranalízis Főkomponens módszer CCA ICA LDA Nem negatív mátrix kiterjesztése t-SNE
Strukturális előrejelzés	Grafikon valószínűségi modell Bayesi hálózat Rejtett Markov-modell CRF
Anomália észlelése	k-legközelebbi szomszéd módszer Helyi kibocsátási szint
Grafikon valószínűségi modellek	Bayesi hálózat Markov hálózat Rejtett Markov-modell
Neurális hálózatok	Limitált Boltzmann gép önszerveződő térkép Aktiválási funkció Szigma alakú softmax Radiális bázisfüggvény Hátsó szaporítási módszer Mély tanulás Többrétegű perceptron Ismétlődő neurális hálózat hosszú távú rövid távú memória Ellenőrzött visszatérő blokk Konvolúciós Neurális Hálózat U-háló Autoencoder
Megerősítő tanulás	Markov folyamat Bellman egyenlet Mohó algoritmus Q-learning SARSA Időbeli különbség (TD)
Elmélet	Vapnik-Chervonenkis elmélet Elfogultság-diszperziós dilemma Számítógépes tanuláselmélet Empirikus kockázatminimalizálás Occam tanul PAC tanulás Statisztikai tanuláselmélet
Folyóiratok és konferenciák	NeurIPS ICML ML JMLR ArXiv:cs.LG