Statisztikus tanuláselmélet: Szupport vektor gépek
1. Bevezető
A mesterséges intelligencia (MI) technológiák ma már a mindennapjaink részét képezik, számos szolgáltatás alapjául szolgálnak – az egészségügytől az iparig –, és a gazdasági fejlődés egyik lehetséges motorjai, állapítja meg egy az MI-t az Európai Unió (EU) szemszögéből vizsgáló tanulmány [4]. Az MI fogalmának meghatározására sokfajta megközelítés létezik [3], de abban szinte minden kutató egyetért, hogy a gépi tanulás a terület kulcsfontosságú módszere, amely a legtöbb MI megoldás esszenciális részét képezi [4].
A gépi tanulás matematikai megalapozása rendkívül fontos a terület hosszútávú fejlődése szempontjából. Noha sok heurisztikus megoldást is használnak a gyakorlatban, a gépi tanulás elmélete mostanra gazdag múlttal rendelkezik, amelynek fontos része a statisztikus tanuláselmélet. Tanulmányunk első részében a statisztikus tanuláselmélet egyik klasszikus módszerébe, a szupport vektor gépek elméletébe adunk bevezetést, a gépi tanulás egyik alapproblémáján, a (bináris) osztályozáson keresztül. A megoldást első lépésként lineárisan szeparálható problémák esetére vezetjük be, amit a tanulmányunk folytatásában kernel módszerek segítségével terjesztünk majd ki nemlineáris problémákra.
2. Bináris osztályozás
Az osztályozás (más néven klasszifikáció vagy mintafelismerés) a statisztikus tanuláselmélet egyik alapvető problémája. Fő feladata bemenet és (véges értékkészletű) kimenet (címke) párokból álló megfigyelések alapján az adatgeneráló mechanizmus modellezése. A modell segíségével általánosíthatunk, azaz ismeretlen bemenetek esetén is becsülni tudjuk a megfelelő kimenetet. Egy osztályozási feladat bináris, ha a címke csak kétféle lehet.
Az osztályozásnak számtalan alkalmazása van, amelyek közül most hármat említünk. Tanulmányunk során az első példán keresztül szemléltetünk majd néhány alapfogalmat.
Betegség diagnosztizálása: Az egészségügyben az orvos feladata, hogy diagnosztizáljon egy adott betegséget a páciens tünetei és leletei alapján. Ez egy tipikus osztályozási feladat, amely során a cél a betegség meglétének eldöntése a rendelkezésére álló adatok (magyarázóváltozók) alapján (például: nem, kor, súly, vérnyomás, pulzus, EKG, CT).
Szerszámgép karbantartása: Annak érdekében, hogy a szerszámgépek váratlan meghibásodásának számát csökkentsék, a gépek részegységeinek állapotát rendeszeresen mérik. A meghibásodás előrejelzése a mért értékek alapján egy osztályozási feladat, amely megoldása elengedhetetlen hatékony karbantartási stratégiák kialakításához.
Levélszemét (spam) felismerése: A levelezőrendszerek a bejövő üzeneteket számos tényező (például: szöveges tartalom, címzettek, csatolmányok, linkek, a rendszer címjegyzéke, a feladó címéről feladott levelek száma és hasonlósága) alapján osztályozzák, hogy a veszélyes és nem kívánt emailek elkülönüljenek a levelezőkliens beérkező leveleitől.
Adott egy vektor magyarázó változókból, \(X_i \in \mathbb{X} \subseteq \mathbb{R}^d\), és bináris osztályváltozókból, \(Y_i \in \mathbb{Y} = \{ -1, +1\}\), álló független azonos eloszlású minta \(\{(X_i,Y_i)\}_{i=1}^n\) egy ismeretlen \(\mathbb{P}\) eloszlásból. Tekintsük az \(\mathbb{R}^d \to \mathbb{Y}\) típusú (mérhető) osztályozó függvényeket és egy (mérhető) nemnegatív \(\ell\colon \mathbb{Y} \times \mathbb{Y} \to [0,\infty)\) típusú veszteségfüggvényt. Ebben a cikkben az \(\ell(y_1, y_2) = \mathbb{I}(y_1 \neq y_2)\) ún. \(0/1\)-veszteségfüggvényre szorítkozunk, ahol \(\mathbb{I}\) egy indikátor, de az eredmények általánosíthatóak más, bonyolultabb veszteségfüggvényekre is. Általában az osztályozás célja egy minimális kockázatú osztályozó \(f_*\) becslése, ahol \[\displaystyle R(f) \doteq \mathbb{E}\big[\ell(f(X), Y)\big],\] az ún. kockázatfüggvény és \((X,Y) \overset{d}{=} (X_1,Y_1)\). A \(0/1\)-veszteségfüggvény esetén könnyen látható, hogy \(R(f)= \mathbb{P}(f(X) \neq Y)\), azaz a kockázat megegyezik a félreosztályozás valószínűségével. Ha \(\mathbb{P}\) ismert volna, akkor egy optimális osztályozó – az ún. Bayes optimális osztályozó – meghatározható lenne a feltételes várható érték segítségével: \[\displaystyle f^*(x) = \mathop{\mathrm{sign}}(\eta(x)),\] ahol \(\eta(x) \doteq \mathbb{E}[Y\vert X=x]\), amit tipikusan regressziós függgvénynek neveznek. Az egészségügyi példában a már megfigyelt páciensek egészségügyi adatai (nem, kor, EKG…) alkotják a magyarázó változókat és egy adott betegség előfordulásának indikátorai a kimeneti változókat. Feltehető, hogy ezek az adatok egy euklideszi térbe ágyazhatók be, ugyanis a megfigyelések egy része euklideszi térből vesz fel értéket, a magyarázó változók további része pedig vektorrá transzformálható valamilyen módon, például segéd indikátorváltozók bevezetésével. Egy leegyszerűsített modellben az ismeretlen eloszlást minden ember egészségügyi adata és betegsége határozná meg. Ha a \(0/1\) veszteségfüggvényt használjuk és az ehhez tartozó kockázatot, azaz a betegségek félrediagnosztizálásanak valószínűségét szeretnénk minimalizálni, akkor egy Bayes optimális osztályozó pontosan akkor diagnosztizál egy pácienst betegnek, ha a betegség feltételes valószínűsége a páciens egészségügyi adataira nézve nagyobb, mint annak a valószínűsége, hogy a páciens egészséges. Ezt az optimális függvényt becsüljük az osztályozáskor a megfigyelt adatok alapján.
A \(\mathbb{P}\) együttes eloszlás általában ismeretlen, ezért a kockázatfüggvényt becsülnünk kell. A legismertebb becslés az ún. tapasztalati kockázat, a megfigyelt veszteségek átlaga: \[\displaystyle \widehat{R}(f) \doteq \frac{1}{n}\sum_{i=1}^n \ell( f(X_i), Y_i).\]
A nagy számok (erős) törvényének értelmében minden \(f\) osztályozóra \(\widehat{R}(f)\) konvergál az \(R(f)\) értékhez, \(1\) valószínűséggel. A tapasztalati kockázat minimalizálásának módszere értelemszerűen az \(\widehat{R}\) függvény minimumhelyét keresi. Általában azonban minden \(f\) osztályozóhoz található egy \(\tilde{f}\) osztályozó, ami a mintapontokban megegyezik \(f\)-fel, azaz \(f(X_i) = \tilde{f}(X_i)\) minden \(i =1, \dots, n\), de mindenhol máshol \(f\neq \tilde{f}\), ezért önmagában a minta alapján nem lehet egyértelműen meghatározni a tapasztalati kockázatot minimalizáló osztályozót. Általában a tapasztalati kockázatminimalizálás esetében egy előre rögzített modellosztályra szorítkozunk. A modellosztályt gyakran egy véges dimenziós paramétervektor segítségével adjuk meg. Példaként tekinthetjük a lineáris (pontosabban az affin) osztályozókat, melyeket szeparáló hipersíkok definiálnak: \(\mathcal{F} = \{f \colon f(x) \doteq \mathop{\mathrm{sign}}(w^{\top} x + b), w \in \mathbb{R}^d, b \in \mathbb{R}\}\).
Legyen \((f_n)\) a Bayes optimális osztályozó egy becslése (ahol \(n\) a megfigyelések száma). Azt mondjuk, hogy az \((f_n)\) becslés (erősen) konzisztens, ha \(R(f_n) \to R(f^*)\), ahogy \(n \to \infty\), \(1\) valószínűséggel (mivel \(f_n\) függ a megfigyelésektől, ezért \(R(f_n)\) véletlen).
Ismeretlen eloszlás mellett adott mintaméretre hatékony osztályozót nehéz találni, az ún. „nincs ingyen ebéd” elve érvényesül [2, Theorem 7.1]:
1. tétel. Legyen \(\mathbb{X}\) egy végtelen halmaz. Ekkor minden \((f_n)\) becsléshez, \(n\) mintamérethez és \(\varepsilon > 0\) hibavalószínűséghez létezik egy \(\mathbb{P}\) eloszlás, amelyre \(R(f^*) = 0\) és \(\mathbb{E}[R(f_n)] \geq 1/2-\varepsilon\).
Ha a megfigyelésektől teljesen függetlenül, véletlenszerűen (\(1/2\) – \(1/2\) valószínűséggel) rendelnénk minden ponthoz egy osztályt, akkor lenne \(1/2\) az osztályozónk kockázata. A fenti tétel azt mondja, hogy egy adott becsléshez tudunk olyan „rossz” eloszlást konstruálni, amelyre a becslésünk kockázata tetszőlegesen közel lehet ehhez a teljesen véletlenített osztályozóhoz, noha van az adott problémára tökéletes, nulla kockázatú megoldás.
Megjegyezzük, hogy ez a tétel nem jelenti azt, hogy lehetetlen olyan becslést találni, amely univerzálisan minden eloszlásra konzisztens lenne, azaz \(R(f_n) \to R(f^*)\) teljesülne. Azt viszont igen, hogy a konzisztens becslések esetében is a konvergencia sebessége az eloszlás függvényében változik és lehet tetszőlegesen lassú. Egy meglepően egyszerű univerzálisan konzisztens módszert ad a \(k\)-legközelebbi szomszéd (\(k\)-NN) becslés. Jelölje \[\displaystyle N_k(x) \doteq \Big\{ j \in[n] \colon \sum_{i=1}^n \mathbb{I}(\lVert x- X_j\rVert > \lVert x-X_i\rVert)< k \Big\},\] ahol \([n] \doteq \{1, 2, \dots, n\}\). Tehát egy tetszőleges \(x\) pont esetén az \(N_k(x)\) halmaz a \(\{X_i\}_{i=1}^n\) halmazban az \(x\) pont \(k\) legközelebbi szomszédainak indexeit tartalmazza. Továbbá legyen \[\displaystyle f_{\text{kNN}}(x) \doteq \mathop{\mathrm{sign}}\Big(\frac{1}{k} \sum_{j\in N_k(x)} Y_j \Big).\]
A szomszédok számát a minta elemszámának függvényében növelhetjük, hogy egy konzisztens becslést kapjunk. Ha a \((k_n)\) sorozat olyan, hogy \(k_n \to \infty\) és \(k_n/n\to 0\), ha \(n \to \infty,\) akkor a \(k_n\)-NN becslés kockázata tart az optimális \(R(f^*)\) kockázat értékhez [2].
Az 1. Tétel miatt azonban nem várható el, hogy egy tetszőleges eloszlásból vett véges mintára is mindig használható becslést kapjunk, ezért érdemes megkötésekkel élnünk a lehetséges modelleket illetően. Általában a becslést egy \(\mathcal{F}\) modellosztályban fogjuk keresni. Mivel a tapasztalati kockázatminimalizálás már előfeltételezi egy modellosztály létezését, ezért ez a feltevés a gyakorlatban alapvető, mindazonáltal érdemes észben tartani, hogy ennek a feltevésnek lehet torzító hatása. Ezt nevezik a feladatban rejlő induktív torzításnak. Egy \(\mathcal{F}\)-ből származó becslés kockázattöbbletét felbonthatjuk két részre. \[\displaystyle R(f_n) – R(f^*) = \underbrace{ R(f_n) – \inf_{f\in\mathcal{F}} R(f)}_{\text{becslési hiba}}+\underbrace{\inf_{f\in\mathcal{F}} R(f) – R(f^*)}_{\text{approximációs hiba}},\]
Ha \(f^* \in \mathcal{F}\), akkor az approximációs hiba \(0\), azonban ez elég ritkán teljesül a gyakorlatban. Ha bővítjük a modellosztályt, akkor az approximációs hiba csökken, viszont a becslési hiba növekedhet. A túl nagy modellosztály eredményezhet túltanulást, ilyenkor a modellbecslés a mintában lévő zajra is illeszkedik. Megfordítva, ha túl szűk modellosztályt választunk, akkor a becslési hibánk lecsökken, nem lesz nagy különbség a modellosztályban található legkisebb kockázatú becslés kockázata és az általunk talált becslés kockázata között, azonban az approximációs hiba ilyenkor megnő. Ezt a szintén nem előnyös jelenségét alultanulásnak nevezik. Ha növeljük a mintaméretet, akkor a becslési hibát tudjuk csökkenteni, viszont az approximációs tag csak a modellosztálytól függ.
A strukturális kockázatminimalizálás elve szerint érdemes a modellosztályt úgy bővíteni a mintamérettel együtt, hogy a becslési hiba és az approximációs hiba is csökkenjen, lásd az 1. ábrát. Az approximációs hiba modellosztálytól való függésére több „mérőszámot” is megalkottak. Ezek a mérőszámok elsősorban a modellosztály kifejezőképességét hívatottak leírni. Ebben a cikkben az ún. Vapnik–Cservonenkisz-dimenziót (VC-dimenziót) mutatjuk be és ennek alkalmazását a bináris osztályozás esetére, lásd [7].
Legyen \(\mathcal{C}\) egy halmazrendszer. Azt mondjuk, hogy \(\mathcal{C}\) szétzúzza az \(A\) halmazt, ha \[\displaystyle \forall \, S\subseteq A\colon \exists \,C \in \mathcal{C}\colon S=A\cap C.\]
Hasonlóan, bináris osztályozók egy \(\mathcal{F}\) osztálya szétzúzza az \(A\) halmazt, ha az osztályozók által generált \(\mathcal{C}_\mathcal{F} \doteq \{ C\colon \exists f \in \mathcal{F}, C = f^{-1}(\{1\})\}\) halmazrendszer szétzúzza \(A\)-t.
2. definíció. (VC-dimenzió) Legyen \(\mathcal{F}\) osztályozóknak egy családja. Az \(\mathcal{F}\) halmaz \(V_\mathcal{F}\) VC-dimenziója az a legnagyobb \(n \in \mathbb{N}\), amire létezik egy \(n\)-elemű \(\mathcal{F}\) által szétzúzott \(A\) halmaz. Ha ez a maximum nem létezik, akkor \(\mathcal{F}\) VC-dimenziója végtelen.
Megmutatható, hogy a lineáris osztályozók VC-dimenziója az \(\mathbb{R}^d\) térben \(d+1\) (lásd 2. ábra). A tetszőlegesen nagy fokú polinomok által generált osztályozók VC-dimenziója pedig végtelen. A VC-dimenzió segítségével jól bemutatható a strukturális kockázatminimalizálás. Legyen \(\ell\colon \mathbb{Y} \to \mathbb{Y} \to [0, \beta]\) egy korlátos veszteségfüggvény, \(\delta > 0\) és \[\displaystyle \varepsilon(n, V_\mathcal{F}, \beta, \delta) \doteq \beta \sqrt{\frac{V_\mathcal{F}\log\big(\frac{2n}{V_\mathcal{F}}+1 \big)- \log\big(\frac{\delta}{2}\big) }{n}}.\] Ekkor megmutatható, hogy
| \(\displaystyle \mathbb{P}\left(R(f) \leq \widehat{R}(f) + \varepsilon(n, h, \beta, \delta)\right)\geq 1-\delta.\) | (1) |
Az ilyen típusú korlátokat nagy valószínűséggel megközelítőleg helyes – angol nevéből PAC – korlátoknak nevezik. A PAC korlátok nagyon elterjedtek a gépi tanulásban, és a gyakorlatban is jól használhatók. Fontos előnyük, hogy véges mintára is érvényes garanciával szolgálnak. Az (1) egyenlőtlenség alapján érdemes az \(\widehat{R}(f) + \varepsilon(n, h, \beta, \delta)\) tagot együttesen minimalizálni a tapasztalati kockázat helyett. Legyen \(\mathcal{F}_1 \subseteq \mathcal{F}_2 \subseteq \ldots\) modellosztályoknak egy bővülő sorozata. Természetesen ekkor a modellosztályok VC-dimenziója is monoton növő. A strukturális kockázatminimalizálás során azt a modellosztályt és azon belül azt a modellt keressük, amelyre a fenti együttes hibatag minimális.
3. Szupport vektor gépek
Fontos példaként vizsgáljuk meg a lineáris osztályozóknak egy paraméteres részhalmazát: a \(\delta\)-margójú szeparáló hipersíkokat. Legyenek \(\mathcal{X} =\{x_1, \dots, x_r\}\) tetszőleges pontok \(\mathbb{R}^d\)-ben egy \(R\) sugarú origó középpontú gömbben. Tekintsük az \[\displaystyle \mathcal{F}_\delta(\mathcal{X}) \doteq \big\{ f(x) = \mathop{\mathrm{sign}}(w^{\top} x + b_0 )\colon k \in [r], \min_{k \in[r]} |w^{\top} x_k + b| =1, \lVert w\rVert \leq 1/\delta \big\}.\] modellosztályt, amely az \(\mathcal{X}\)-beli pontoktól legalább \(\delta\) távolságra lévő egyenesek által meghatározott osztályozókat tartalmazza. A \(\min_{k \in[r]}\vert w^{\top} x_k + b\vert =1\) kitétel egyértelműsíti a hipersíkok paraméterezését, a statisztikus tanuláselméletben ezt a paraméterezést szokás kanonikus paraméterezésnek nevezni (tehát itt \(w\) tipikusan nem egységvektor). Az \(\mathcal{F}_\delta(\mathcal{X})\) halmaz VC-dimenziójára adható egy felső korlát a \(\delta\) függvényében [5,6].
3. tétel. Legyen \(\mathcal{X} \subseteq \mathbb{R}^d\) egy véges halmaz. Tegyük fel, hogy \(\mathcal{X} \subseteq B(\mathbf{x},R)\) egy valamilyen \(\mathbf{x} \in \mathbb{R}^d\) elemre. Tekintsük az \(\mathcal{F}_\delta(\mathcal{X})\) osztályozókat az \(\mathcal{X}\) halmazon. Ekkor \[\displaystyle V_{\mathcal{F}_\delta(\mathcal{X})} \leq \min\Big(\Big\lceil\frac{R^2}{\delta^2}\Big\rceil, n \Big) + 1.\]
Ez az állítás motiválja, hogy érdemes a margót növelni, ha a függvényosztály komplexitását csökkenteni szeretnénk. Megjegyezzük azonban, hogy az (1) egyenletben szereplő korlát csak akkor érvényes, ha a strukturális kockázat minimalizálásban szereplő függvényosztályok nem függnek a mintától [6].
Vizsgáljuk meg azt az esetet, amikor az osztályok lineárisan szeparálhatók, azaz \(R(f_*) = 0\). Ilyenkor mindig található egy olyan lineáris osztályozó is, aminek a tapasztalati hibája \(0\). Egy optimalizálási feladat segítségével megkereshető a maximális margójú hipersík is. Belátható, hogy ez egyértelműen létezik.
Egy \(x \in \mathbb{R}^d\) pont algebrai távolsága egy \((w,b)\) paraméterekkel meghatározott hipersíktól az \(r\) valós szám, ha \(\displaystyle x = x_p + (w/\lVert{w}\rVert)r\) fennáll egy \(x_p\) hipersíkon lévő pontra, azaz \(w^{\top} x_p + b =0\). Az algebrai távolság a kanonikus paraméterezés mellett fordítottan arányos a \(w\) vektor normájával, ugyanis
| \(\displaystyle d(x)\) | \(\displaystyle \doteq\frac{1}{\Vert w\Vert} \big(w^{\top} x + b\big) = \frac{1}{\Vert w\Vert} \bigg(w^{\top}\bigg(x_p + \frac{w}{\Vert w\Vert}r\bigg) + b\bigg)\) |
| \(\displaystyle = \frac{1}{\Vert w\Vert} \big(w^{\top} x_p + b\big) + \frac{1}{\Vert w\Vert} \bigg(\frac{w^{\top} w}{\Vert w\Vert}r\bigg) = r.\) |
Az \(x\) pont euklideszi távolsága a \((w,b)\) által meghatározott egyenestől (hipersíktól) értelemszerűen \(\vert d(x)\vert\). A hipersík margója a mintákra nézve \(\delta_* \doteq \min_{k \in [n]} \vert d(x_k)\vert\). Azokat az \(\{x_k\}\) magyarázóvektorokat, amelyekre \(\vert d(x_k)\vert = \delta_*\), szupport vektoroknak nevezzük. Belátható, hogy ugyanezekre a vektorokra teljesül a \(\vert w^{\top} x_k + b\vert = 1\) egyenlőség. Ezen meggondolások alapján a \(\lVert{w}\rVert\) mennyiséget kell maximalizálni a kanonikus paraméterezés által meghatározott peremfeltételek mellett, lásd a 3. ábrát. Evvel ekvivalens módon az alábbi konvex kvadratikus optimalizálási problémát kell megoldanunk:
| \(\mathop{\hbox{minimalizáljuk}}\limits_{w \in \mathbb{R}^d, b \in \mathbb{R}}\) | \(\frac{1}{2}\Vert w\Vert^2\) | |
| feltéve, hogy | \(y_k \big(w^{\top} x_k + b\big) \geq 1\) | minden \(k=1,\dots,n\) |
A nemlineáris optimalizálás elméletéből ismert Karush–Kuhn–Tucker-feltételek [1] alapján belátható, hogy az optimális \(w\) megoldáshoz legalább két szupport vektor, \(x^{+}\) és \(x^{-}\), tartozik, ugyanis ellenkező esetben a margót növelni lehetne. Ezekre a vektorokra teljesülnek a \(w^{\top} x^{\pm} + b = \pm 1\) egyenletek, amelyek segítségével az optimális \(b\) paraméter is meghatározható. Ezt a módszert a szigorú margójú szupport vektor gépek módszerének nevezzük, és az így kapott osztályozót (lineáris) szupport vektor osztályozónak hívjuk.
Természetesen a gyakorlatban ritka az, hogy a mintában szereplő adatok lineárisan szeparálhatók. Ezt a problémát először úgy oldjuk fel, hogy ugyan továbbra is egy lineáris osztályozót konstruálunk, de segédváltozókat adva a korábbi optimalizálási probléma peremfeltételeihez megengedjük, hogy az osztályozó hibázzon a mintapontokban. A hibákat egy \(\lambda > 0\) segédparaméterrel súlyozzuk a költségfüggvényben. A relaxált megoldást szolgáltató új feladat szintén konvex kvadratikus, így hatékonyan megoldható:
| \(\mathop{\hbox{minimalizáljuk}}\limits_{w,\xi \in\mathbb{R}^d, b\in\mathbb{R}}\) | \(\frac{1}{2}\|w\|^2+\lambda \sum_{k=1}^{n}\xi_k\) | (2) | |
| feltéve, hogy | \(y_k \big(w^{\top} x_k + b\big) \geq 1-\xi_k\) | minden \(k=1,\dots, n\) | |
| \(\xi_k \geq 0\) | minden \(k=1, \dots, n\) |
Ebben az esetben a \(b\) paraméter egy olyan \(j\) indexű peremfeltételből fejezhető ki, amelyre \(\xi_j > 0\). Ezt a feladatot szokás gyenge margójú lineáris szupport vektor osztályozásnak nevezni. Vegyük észre, hogy a gyenge margójú esetben a margó értelmezése nem teljesen egyértelmű, a margót megsértő adatpontok miatt. A \(\lambda\) regularizációs paramétert a gyakorlatban általában keresztvalidáció segítségével hangolják be.
A segédváltozók bevezetése ugyan kiterjeszti a megoldást olyan esetekre is, amikor a két osztályból kapott minták szigorú értelemben nem választhatók ketté egy hipersíkkal – mert a két osztály mintái összekeveredtek – de (2) még mindig a lineáris osztályozók terében keres modellt. Tanulmányunk folytatásában megmutatjuk majd, hogy a nemlineáris problémák esetét hogyan lehet visszavezetni a lineáris osztályozók elméletére a kernel módszerek segítségével. Az alapötlet az lesz, hogy transzformáljuk az adatainkat egy nagy (akár végtelen) dimenziós térbe, amelyben már azok lineárisan szeparálhatóak.
Irodalomjegyzék
[1] Boyd, S. P., and Vandenberghe, L. Convex Optimization. Cambridge University Press, 2004.
[2] Devroye, L., Györfi, L., and Lugosi, G. A Probabilistic Theory of Pattern Recognition, vol. 31. Springer Science & Business Media, 2013.
[3] Russel, S. J., and Norvig, P. Artificial Intelligence: A Modern Approach, 4th ed. Prentice Hall Series in Artificial Intelligence. Pearson, 2020.
[4] Samoili, S., Cobo, M. L., Gómez, E., De Prato, G., Martínez, Plumed, F., and Delipetrev, B. AI Watch: Defining artificial intelligence. Towards an operational definition and taxonomy of artificial intelligence. JRC Research Reports of the European Commission, JRC118163 (2020).
[5] Schölkopf, B., and Smola, A. J. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, 2002.
[6] Shawe-Taylor, J., Bartlett, P. L., Williamson, R. C., and Anthony, M. Structural risk minimization over data-dependent hierarchies. IEEE Transactions on Information Theory 44, 5 (1998), 1926–1940.
[7] Vapnik, V. Statistical Learning Theory. Wiley-Interscience, 1998.
Tamás Ambrus és Csáji Balázs Csanád
HUN-REN SZTAKI és ELTE Matematikai Intézet
