Az 5.21. ábrán egy olyan adathalmaz ábrázolása látható, amely két különböző osztályba tartozó eseteket tartalmaz (az osztályokat négyzetek és körök reprezentálják). Az adathalmaz lineárisan szeparálható, azaz találhatunk olyan hipersíkot, amelynek egyik oldalán van az összes négyzet, a másik oldalán pedig az összes kör. Mint azonban az 5.21. ábrán is látható, végtelen sok ilyen hipersík lehetséges. Noha ezek a tanulóhalmazon mért hibája nulla, nincs garancia arra, hogy a hipersíkok egyformán jól fognak teljesíteni korábban még nem látott esetekre. Az osztályozó ki kell, hogy válassza a hipersíkok egyikét a döntési határ reprezentálásához annak alapján, hogy várhatólag milyen jól teljesítenek a teszteseteken.

Hogy tisztább képet kapjunk arról, hogy a hipersíkok különböző megválasztása milyen hatással van az általánosítási hibára, tekintsük az 5.22. ábrán látható két döntési határt, B 1 -et és B 2 -t. Mindkét döntési határ szét tudja választani a tanulóeseteket a megfelelő osztályokra, félreosztályozási hiba elkövetése nélkül. Mindegyik B i döntési határhoz tartozik két hipersík, amelyeket b i1 és b i2 jelöl. b i1 -et úgy kapjuk meg, hogy addig tolunk el a döntési határtól egy vele párhuzamos hipersíkot, amíg az nem érinti a legközelebbi négyzetet, míg b i2 -t úgy kapjuk, hogy a hipersíkot addig toljuk el, míg az nem érinti a legközelebbi kört. A két hipersík közötti távolságot nevezzük az osztályozó margójának. Vegyük észre az 5.22. ábrán látható rajzról, hogy B 1 margója jelentősen nagyobb, mint B 2 -é. A példában B 1 bizonyul a tanulópéldányok maximális margójú hipersíkjának.

A maximális margó indoklása

A nagy margóval rendelkező döntési határoknak általában jobb az általánosítási hibájuk, mint a kis margóval rendelkezőknek. Intuitívan, ha a margó kicsi, akkor a döntési határ bármilyen kis perturbációjának elég jelentős hatása lehet az osztályozásra. A kis margóval rendelkező döntési határokat létrehozó osztályozók ezért hajlamosabbak a modell túlillesztésre és korábban nem látott eseteken gyakran rosszul általánosítanak.

Egy formálisabb magyarázatot ad a lineáris osztályozó margójának és általánosítási hibájának kapcsolatára a strukturális kockázat minimalizálásként (SRM -- structural risk minimization) ismert statisztikai tanulási elv. Ez az elv egy felső korlátot ad egy osztályozó általánosítási hibájára ( R ) a tanulóhalmazon mért hiba ( R e ), a tanulóesetek számának ( N ) és a modell egyébként kapacitásnak nevezett bonyolultságának ( h ) segítségével. Pontosabb, 1−η a valószínűsége annak, hogy az osztályozó általánosítási hibája legrosszabb esetben

R≤ R e +φ( h N , log(η) N ), (5.27)

ahol φ egy monoton növekvő függvénye a h kapacitásnak. Az előbbi egyenlőtlenség elég ismerősnek tűnhet az Olvasó számára, mert a 4.4.4. szakaszban (a 185. oldalon) a legrövidebb leíró hossz (MDL) elvéhez megadott egyenletre hasonlít. Ebből a szempontból az SRM egy másik módja annak, hogy az általánosítási hibát a tanulóhalmazon mért hiba és a modell komplexitása közötti kompromisszumként fejezzük ki.

A lineáris modell kapacitása fordítottan arányos a margóval. A kis margóval rendelkező modelleknek nagyobb kapacitása van, mert rugalmasabbak és sok tanulóhalmazra tudnak illeszkedni, a nagy margóval rendelkező modellektől eltérően. Az SRM-elv szerint mivel azonban a kapacitás nő, az általánosítási hibahatár is nőni fog. Ezért a döntési határaik margóit maximalizáló lineáris osztályozók tervezése kívánatos annak biztosításához, hogy minimális legyen a legrosszabb esetre vett általánosítási hiba. Az egyik ilyen osztályozó a lineáris SVM, amelyet a következő szakasz ismertet.

A lineáris SVM egy olyan osztályozó, amely egy a legnagyobb margóval rendelkező hipersíkot keres, éppen ezért nevezik gyakran maximális margójú osztályozónak (maximal margin classifier). Ahhoz, hogy megértsük, hogyan tanul meg az SVM egy ilyen határt, néhány a lineáris osztályozó döntési határáról és margójáról szóló bevezető fejtegetéssel kezdjük.

Lineáris döntési határ

Tekintsünk egy N számú tanulóesetből álló bináris osztályozási problémát. Mindegyik esetet egy ( x i , y i ) n -es jelöli ( i=1,2,…,N ), ahol x i = ( x i1 , x i2 ,…, x id ) T az i -edik eset attribútumhalmazának felel meg. Megállapodás szerint jelölje y i ∈{−1,1} az osztálycímkét. A lineáris osztályozó döntési határa a következő alakban írható fel:

w⋅x+b=0, (5.28)

ahol w és b a modell paraméterei.

Az 5.23. ábra egy négyzetekből és körökből álló kétdimenziós tanulóhalmazt mutat. Folytonos vonal szemlélteti a tanulóeseteket a megfelelő osztályokra kettéválasztó döntési határt. Bármely a döntési határ mentén elhelyezkedő eset ki kell hogy elégítse az (5.28) egyenletet. Például ha x a és x b a döntési határon elhelyezkedő pontok, akkor

w⋅ x a +b=0,

w⋅ x b +b=0.

A két egyenlet egymásból kivonása a következőt eredményezi:

w⋅( x b − x a )=0,

ahol x b − x a a döntési határral párhuzamos vektor, amely x a -ból x b -be mutat. Mivel a belső szorzat nulla, w iránya merőleges kell hogy legyen a döntési határra, mint az az 5.23. ábrán látható.

Bármely a döntési határ felett elhelyezkedő x s négyzetre megmutatható, hogy

w⋅ x s +b=k, (5.29)

ahol k≥0 . Hasonlóképpen bármely a döntési határ alatt elhelyezkedő x c körre megmutatható, hogy

w⋅ x c +b=k', (5.30)

ahol k'≤0 . Ha +1 osztályúnak címkézünk minden négyzetet és −1 osztályúnak minden kört, akkor az alábbi módon tudjuk prediktálni bármely z teszteset osztálycímkéjét:

y={ 1, ha  w⋅  z  +  b  ≥  0, −1, ha  w⋅  z  +  b  ≤  0. (5.31)

A lineáris osztályozó margója

Tekintsük a döntési határhoz legközelebbi négyzetet és kört. Mivel a négyzet a döntési határ felett helyezkedik el, ki kell hogy elégítse az (5.29) egyenletet valamilyen pozitív k értékre, míg a kör ki kell hogy elégítse az (5.30) egyenletet valamilyen k' negatív értékre. Átskálázhatjuk úgy a döntési határ w és b paramétereit, hogy a két párhuzamos hipersík, b i1 és b i2 kifejezhető az alábbi módon:

b i1 :w⋅x+b=1, (5.32)

b i2 :w⋅x+b=−1. (5.33)

A döntési határ margóját a két hipersík közötti távolság adja meg. A margó kiszámításához legyen x₁ egy b_i1-en elhelyezkedő adatpont, x₂ pedig egy adatpont b_i2-n, ahogyan azt az 5.23. ábra mutatja. Ezeket a pontokat az (5.32) és az (5.33) egyenletekbe helyettesítve a d margó meghatározható a második egyenletnek az első egyenletből kivonásával:

w⋅( x 1 − x 2 )=2

‖ w ‖×d=2

d= 2 ‖ w ‖ . (5.34)

A lineáris SVM modell tanulása

Az SVM tanulási fázisa magában foglalja a döntési határ w és b paramétereinek a tanulóadatokból történő megbecslését. A paramétereket úgy kell megválasztani, hogy az alábbi két feltétel teljesüljön:

w⋅ x i +b≥  1,  ha   y i =1,

w⋅ x i +b≤−1,  ha   y i =−1. (5.35)

Ezek a feltételek azokat a követelményeket fogalmazzák meg, hogy minden az y=1 osztályba tartozó tanulópéldány (azaz négyzet) a w⋅x+b=1 hipersíkon vagy felette kell hogy elhelyezkedjen, míg az y=−1 osztályba tartozó példányok (azaz a körök) a w⋅x+b=−1 hipersíkon vagy alatta kell hogy elhelyezkedjenek. Mindkét egyenlőtlenség a következő módon foglalható össze tömörebb alakban:

y i (w⋅ x i +b)≥1,    i=1,2,…,N. (5.36)

Bár az előző feltételek alkalmazhatók bármely lineáris osztályozóra (a perceptronokat is beleértve), az SVM egy további követelményt támaszt, azt, hogy a döntési határ margója maximális kell, hogy legyen. A margó maximalizálása azonban ekvivalens az alábbi célfüggvény minimalizálásával:

f(w)= ‖ w ‖ 2 2 . (5.37)

5.1. Definíció

(lineáris SVM: szeparálható eset) AZ SVM tanulási feladat az alábbi feltételes optimalizálási problémaként formalizálható:

min w    ‖ w ‖ 2 2

feltéve,hogy   y i (w⋅ x i +b)≥1,    i=1,2,…,N.

Mivel a célfüggvény kvadratikus és a korlátozások lineárisak a w és b paraméterekben, ezt konvex optimalizálásnak nevezzük, amely a szokásos Lagrange-multiplikátor módszerrel oldható meg. Az alábbiakban tömören vázoljuk az optimalizálási probléma megoldásának alapötletét. Egy részletesebb tárgyalást az E. függelék tartalmaz.

Először a célfüggvényt egy olyan alakba kell átírnunk, amely figyelembe veszi a megoldásokra előírt korlátozásokat. Az új célfüggvény az optimalizálási probléma úgynevezett Lagrange-függvénye:

L P = 1 2 ‖ w ‖ 2 − ∑ i=1 N λ i ( y i (w⋅ x i +b)−1), (5.38)

ahol a λ i paramétereket Lagrange-multiplikátoroknak nevezzük. A Lagrange-függvény első tagja az eredeti célfüggvénnyel azonos, míg a második tag az egyenlőtlenség alakú korlátozásokat tartalmazza. Annak megértéséhez, hogy miért kell a célfüggvényt módosítani, tekintsük az (5.37) egyenletben adott eredeti célfüggvényt. Könnyű megmutatni, hogy a függvényt w=0 minimalizálja, azaz a nullvektor, amelynek minden eleme nulla. Egy ilyen megoldás azonban sérti az 5.1. definícióban adott korlátozásokat, mert nincs b -re megengedett megoldás. A megoldások w -re és b -re nem megengedettek, ha megsértik az egyenlőtlenség alakú korlátozásokat, azaz ha y i (w⋅ x i +b)−1≤0 . Az (5.38) egyenletben megadott Lagrange-függvény ezt a korlátozást úgy tartalmazza, hogy az eredeti célfüggvényből kivonásra kerül ez a tag. Feltéve, hogy λ i ≥0 , nyilvánvaló, hogy bármely nem megengedett megoldás csak növelheti a Lagrange-függvény értékét.

A Lagrange-függvény minimalizálásához vennünk kell és nullává kell tegyük L P w és b szerinti deriváltját:

∂ L p ∂w =0⇒w= ∑ i=1 N λ i y i x i , (5.39)

∂ L p ∂b =0⇒ ∑ i=1 N λ i y i =0. (5.40)

Mivel a Lagrange-multiplikátorok ismeretlenek, továbbra sem tudjuk meghatározni w -t és b -t. Ha az 5.1. definíció egyenlőtlenség alakú korlátozások helyett csak egyenlőség alakú korlátozásokat tartalmaz, akkor felhasználhatjuk az egyenlőség alakú korlátozásokból az N egyenletet az (5.39) és (5.40) egyenletekkel együtt, hogy megengedett megoldásokat találjunk w -re, b -re és λ i -re. Megjegyezzük, hogy az egyenlőség alakú korlátozások Lagrange-multiplikátorai szabad paraméterek, amelyek bármilyen értéket felvehetnek.

Az egyenlőtlenség alakú korlátozások kezelésének egyik lehetséges módja ezek átalakítása egyenlőség alakú korlátozásokká. Ez lehetséges, amennyiben a Lagrange-multiplikátorok csak nemnegatívak lehetnek. Az ilyen transzformációk a következő Lagrange-multiplikátorokra vonatkozó korlátozásokhoz vezetnek, amelyek Karush-Kuhn-Tucker (KKT) feltételekként ismeretesek:

λ i ≥0, (5.41)

λ i [ y i (w⋅ x i +b)−1]=0. (5.42)

Első pillantásra úgy tűnhet, hogy annyi Lagrange-multiplikátor van, ahány tanulóeset. Megmutatható, hogy az (5.42) egyenletben megadott korlátozás alkalmazása után sok Lagrange-multiplikátor nulla lesz. A korlátozás azt fejezi ki, hogy a λ i Lagrange-multiplikátor nulla kell, hogy legyen, kivéve ha az x i tanulóeset kielégíti az y i (w⋅ x i +b)=1 egyenletet. Az ilyen tanulóeset, amelyre λ i ≥0 , a b i1 vagy b i2 hipersík mentén fekszik, ezt nevezik tartóvektornak. A nem ezeken a hipersíkokon elhelyezkedő tanulópéldányokra λ i =0 teljesül. Az (5.39) és az (5.42) egyenletek azt is sugallják, hogy a döntési határt definiáló w és b paraméterek csak a tartóvektoroktól függenek.

Az előbbi optimalizálási probléma megoldása továbbra is elég ijesztő feladat, mert nagyszámú paramétert tartalmaz: w , b és λ i . A probléma egyszerűsíthető a Lagrange-függvény egy olyan függvénnyé átalakításával, amelynek csak a Lagrange-multiplikátorok a változói (ez az úgynevezett duális probléma). Ehhez először Az (5.39) és az (5.40) egyenleteket az (5.38) egyenletbe helyettesítjük be. Ez az optimalizálási probléma következő duális megfogalmazásához vezet:

L D = ∑ i=1 N λ i − 1 2 ∑ i,j λ i λ j y i y j x i ⋅ x j . (5.43)

A következők a duális és a primál Lagrange-függvények közötti legfontosabb különbségek:

Nagy adathalmazokra a duális optimalizálási probléma numerikus eljárásokkal oldható meg, mint például a kvadratikus programozás, amely egy a könyv kereteit meghaladó téma. Miután megtaláltuk a λ i -ket, az (5.39) és (5.42) egyenleteket használhatjuk fel, hogy megkapjuk w -re és b -re a megengedett megoldásokat. A döntési határ a következőképpen fejezhető ki:

( ∑ i=1 N λ i y i x i ⋅x)+b=0. (5.44)

Az (5.42) egyenletet a tartóvektorokra megoldva kapjuk meg b -t. Mivel a λ i -k kiszámítása numerikusan történik és lehetnek numerikus hibáik, a b -re kiszámolt érték lehet, hogy nem egyértelmű. Ehelyett az (5.42) egyenletben használt tartóvektoroktól függ. A gyakorlatban b átlagértékét szokás a döntési határ paramétereként választani.

5.5. Példa.

Tekintsük az 5.24 ábrán látható kétdimenziós adathalmazt, amely nyolc tanulópéldányt tartalmaz. Kvadratikus programozás segítségével megoldhatjuk az (5.43) egyenletben meghatározott optimalizálási problémát, hogy minden tanulópéldányra megkapjuk a λ i Lagrange-multiplikátort. A Lagrange-multiplikátorok a táblázat utolsó oszlopában kerülnek leírásra. Vegyük észre, hogy csak az első két példánynak van nullától különböző Lagrange-multiplikátora. Ezek a példányok felelnek meg az adathalmaz tartóvektorainak.

Jelöljék w=( w 1 , w 2 ) és b a döntési határ paramétereit. Az (5.39) egyenlet segítségével az alábbi módon kapható meg w 1 és w 2 :

w 1 = ∑ i λ i y i x i1 =65,5261×1×0,3858+65,5261×−1×0,4871=−6,64.

w 2 = ∑ i λ i y i x i2 =65,5261×1×0,4687+65,5261×−1×0,611=−9,32.

A b torzítás tag az (5.42) egyenlet segítségével kiszámítható minden egyes tartóvektorra:

b (1) =1−w⋅ x 1 =1−(−6,64)(0,3858)−(−9,32)(0,4687)=7,9300.

b (2) =−1−w⋅ x 2 =−1−(−6,64)(0,4871)−(−9,32)(0,611)=7,9289.

Ezeket átlagolva azt kapjuk, hogy b=7,93 . Az 5.24. ábra mutatja az ezeknek a paramétereknek megfelelő döntési határt.

A döntési határ paramétereinek megtalálása után a következőképpen osztályozunk egy z tesztpéldányt:

f(z)=sgn(w⋅z+b)=sgn( ∑ i=1 N λ i y i x i ⋅z+b).

Ha f(z)=1 , akkor a tesztpéldányt pozitív esetként osztályozzuk, egyébként pedig negatív esetként osztályozzuk.

Az 5.25. ábra egy az 5.22. ábrához hasonló adathalmazt mutat, azzal a különbséggel, hogy két új esetet ( P és Q ) tartalmaz. Noha a B 1 döntési határ hibásan osztályozza az új eseteket, míg B 2 helyesen, ez nem jelenti azt, hogy B 2 jobb döntési határ, mint B 1 , mert az új esetek a tanulóadatokban lévő zajnak felelhetnek meg. Továbbra is B 1 -et kellene előnyben részesíteni B 2 -vel szemben, mert szélesebb a margója és így kevésbé hajlamos a túlillesztésre. Azonban az előző szakaszban bemutatott megfogalmazású SVM csak olyan döntési határokat hoz létre, amelyek hibamentesek. Ebben a szakaszban azt vizsgáljuk meg, hogy hogyan módosítható a megfogalmazás a puha margóként (soft margin) ismert módszer használatával egy olyan döntési határ megtanulásához, amely tolerálja a kis hibákat a tanulóhalmazon. Ennél is fontosabb, hogy az ebben a szakaszban bemutatásra kerülő módszer még olyan helyzetekben is lehetővé teszi az SVM számára lineáris döntési határ létrehozását, ahol az osztályok lineárisan nem szeparálhatók. Ennek érdekében az SVM tanuló algoritmusa figyelembe kell, hogy vegye a margó szélessége és a lineáris döntési határ által a tanulóhalmazon elkövetett hibák száma közötti kompromisszumot.

Míg az (5.37) egyenletben adott eredeti célfüggvény továbbra is alkalmazható, a B 1 döntési határ már nem elégít ki minden az(5.36) egyenletben megadott korlátozást. Az egyenlőtlenség alakú korlátozásokat emiatt a nemlineárisan szeparálható adatokhoz igazodva kell gyengíteni. Ez megtehető az optimalizálási probléma korlátozásaiba pozitív értékű ξ kiegészítő változókat (slack variables) bevezetve, ahogy ez a következő egyenletekben látható:

w⋅ x i +b≥1− ξ i , hay i =1,

w⋅ x i +b≤−1+ ξ i , hay i =−1, (5.45)

ahol minden i esetén ξ i ≥0 .

A ξ i kiegészítő változók jelentésének értelmezéséhez tekintsük az 5.26. ábrán látható rajzot. A P kör egyike az (5.35) egyenletben megadott korlátozásokat megsértő példányoknak. Jelöljön w⋅x+b=−1+ξ egy olyan egyenest, amely párhuzamos a döntési határral és amely átmegy a P ponton. Megmutatható, hogy az egyenes és a w⋅x+b=−1 hípersík távolsága ξ/‖ w ‖ . Tehát ξ a döntési határ hibájának egy becslését adja a P tanulóesetre.

A döntési határ megtalálásához elvileg alkalmazhatjuk ugyanazt a célfüggvényt, mint korábban, és előírhatjuk az (5.45) egyenletben adott feltételeket. Mivel azonban nincsenek korlátozások a döntési határ által elkövethető hibák számára, a tanuló algoritmus olyan döntési határt találhat, amelynek nagyon széles a margója, de sok tanulóesetet hibásan osztályoz, ahogy az az 5.27. ábrán látható.

A probléma elkerüléséhez a célfüggvényt módosítani kell, hogy a kiegészítő változók nagy értékeivel büntessük a döntési határt. A módosított célfüggvényt a következő egyenlet adja meg:

f(w)= ‖ w ‖ 2 2 +C ( ∑ i=1 N ξ i ) k ,

ahol C és k a tanulóesetek hibás osztályozásának büntetését reprezentáló, a felhasználó által meghatározott paraméterek. A szakasz hátralevő részében a probléma egyszerűsítéséhez feltételezzük, hogy k=1 . A C paraméter a modell validációs halmazon mért teljesítménye alapján választható meg.

Ebből következik, hogy a korlátozott optimalizálási probléma Lagrange-függvénye a következőképpen írható fel:

L P = 1 2 ‖ w ‖ 2 +C ∑ i=1 N ξ i − ∑ i=1 N λ i { y i (w⋅ x i +b)−1+ ξ i }− ∑ i=1 N μ i ξ i , (5.46)

ahol az első két tag a minimalizálandó célfüggvény, a harmadik tag a kiegészítő változókhoz tartozó egyenlőtlenség alakú korlátozásokat reprezentálja, az utolsó tag pedig a ξ i -k értékeire vonatkozó nemnegativitási követelmények eredménye. Továbbá az egyenlőtlenség alakú korlátozások egyenlőség alakú korlátozásokká alakíthatók át a következő KKT feltételek segítségével:

ξ i ≥0,     λ i ≥0,     μ i ≥0, (5.47)

λ i { y i (w⋅ x i +b)−1+ ξ i }=0, (5.48)

μ i ξ i =0. (5.49)

Megjegyezzük, hogy az (5.48) egyenletben megadott Lagrange-multiplikátor csak akkor nem eltűnő, ha a tanulópéldány a w⋅ x i +b=±1 egyenesek mentén található vagy ξ i ≥0 . Másrészt az (5.49) egyenletben megadott μ i Lagrange-multiplikátorok nullák minden hibásan osztályozott tanulópéldány esetén (azaz amelyekre ξ i ≥0 ).

Az L Lagrange-függvény w , b és ξ i szerinti elsőrendű deriváltjait nullává téve a következő egyenleteket kapjuk:

∂L ∂ w j = w j − ∑ i=1 N λ i y i x ij =0  ⇒ w j = ∑ i=1 N λ i y i x ij (5.50)

∂L ∂b =− ∑ i=1 N λ i y i =0⇒ ∑ i=1 N λ i y i =0 (5.51)

∂L ∂ ξ i =C− λ i − μ i =0  ⇒ λ i + μ i =C (5.52)

Az (5.50), (5.51) és (5.52) egyenletek behelyettesítése a Lagrange-függvénybe a következő duális Lagrange-függvényt eredményezi:

L D = 1 2 ∑ i,j λ i λ j y i y j x i ⋅ x j +C ∑ i ξ i

    − ∑ i λ i { y i ( ∑ j λ j y j x i ⋅ x j +b)−1+ ξ i }

    − ∑ i (C− λ i ) ξ i

= ∑ i=1 N λ i − 1 2 ∑ i,j λ i λ j y i y j x i ⋅ x j , (5.53)

amely azonos a lineárisan szeparálható adatok duális Lagrange-függvényével (lásd az (5.40) egyenletet a 268. oldalon). A λ i Lagrange-multiplikátorokra előírt korlátozások azonban kismértékben eltérnek a lineárisan szeparálható esettől. A lineárisan szeparálható esetben a Lagrange-multiplikátorok nemnegatívak kell, hogy legyenek, azaz λ i ≥0 . Másrészt az (5.52) egyenlet arra enged következtetni, hogy λ i nem haladhatja meg C -t (mivel mind μ i , mind λ i nemnegatív). Ezért a nemlinárisan szeparálható adatokra a Langrage-multiplikátorok csak olyanok lehetnek, amelyekre 0≤ λ i ≤C teljesül.

A duális probléma numerikusan oldható meg, kvadratikus programozási eljárások segítségével előállítva a λ i Langrange-multiplikátorokat. Hogy megkapjuk a döntési határ paramétereit, a multiplikátorok behelyettesíthetők az (5.50) egyenletbe és a KKT feltételekbe.

Az SVM az előző szakaszokban leírt megfogalmazásai egy lináris döntési határt hoznak létre a tanulóesetek osztályoknak megfelelő szétválasztásához. Ez a szakasz egy módszertant mutat be az SVM olyan adatokra alkalmazásához, amelyek döntési határa nemlineáris. A trükk itt az adatok áttranszformálása az eredeti koordinátatérből egy új térbe úgy, hogy a transzformált térben a példányok egy lineáris döntési határral legyenek szétválaszhatók. A transzformáció elvégzése után alkalmazhatjuk az előző szakaszokban bemutatott módszertant ahhoz, hogy egy lineáris döntési határt találjunk a transzformált térben.

Attribútum transzformáció

Annak szemléltetéséhez, hogy attribútum transzformáció hogyan vezethet lineáris döntési határhoz, az 5.28. (a) ábra ( y=1 módon osztályozott) négyzetekből és ( y=−1 módon osztályozott) körökből álló kétdimenziós adathalmazra mutat egy példát. Az adatokat olyan módon állítjuk elő, hogy a körök az ábra közepéhez közel csoportosulnak, a négyzetek pedig a középpontól távolabb szóródnak szét. Az adathalmaz példányai a következő egyenlet alapján osztályozhatók:

y( x 1 , x 2 )=( 1, ha ( x 1 −0,5) 2 + ( x 2 −0,5) 2 ≥0,2, −1, egyébként. (5.54)

Emiatt az adatokhoz a döntési határ az alábbiak szerint írható fel:

( x 1 −0,5) 2 + ( x 2 −0,5) 2 =0,2,

amely a következő kvadratikus egyenletté egyszerűsíthető tovább:

x 1 2 − x 1 + x 2 2 − x 2 =−0,46.

Egy Φ nemlineáris transzformáció szükséges az adatoknak az eredeti tulajdonságtérből abba az új térbe való leképezéséhez, amelyben a döntési határ lineáris. Tegyük fel, hogy a következő transzformációt választjuk:

Φ:( x 1 , x 2 )→( x 1 2 , x 2 2 , 2 x 1 , 2 x 2 , 2 x 1 x 2 ,1). (5.55)

A transzformált térben találhatunk olyan w = ( w 0 , w 1 , … , w 5 ) paramétereket, hogy

w 5 x 1 2 + w 4 x 2 2 + w 3 2 x 1 + w 2 2 x 2 + w 1 2 x 1 x 2 + w 0 =0.

Szemléltetés céljából ábrázoljuk grafikusan x 2 2 − x 2 -t x 1 2 − x 1 függvényében az előzőleg megadott példányokra. Az 5.28. (b) ábra azt mutatja, hogy a transzformált térben minden kör a diagram aljának bal oldalán található. Emiatt szerkeszthető egy lineáris döntési határ, amely a példányokat az osztályoknak megfelelően választja szét.

A módszer egy lehetséges problémája az, hogy felmerülhet a sokdimenziós adatokhoz gyakran kapcsolódó dimenzióprobléma. Ebben a szakaszban később meg fogjuk mutatni, hogy hogyan kerüli el a nemlineáris SVM ezt a problémát (a kernel-trükkként ismert módszer segítségével).

Nemlineáris SVM modell tanulása

Bár az attribútum transzformációs megközelítés ígéretesnek tűnik, számos implementációs kérdést vet fel. Először is nem világos, hogy milyen típusú leképező függvényt kell használni annak biztosításához, hogy lineáris döntési határ legyen alkotható a transzformált térben. Egy lehetőség az adatok egy végtelen dimenziós térbe transzformálása, azonban egy ilyen sokdimenziós tér nem kezelhető olyan egyszerűen. Másodszor, ha ismernénk is a megfelelő leképező függvényt, számításigényes feladat a korlátozott optimalizálási probléma megoldása a sokdimenziós tulajdonságtérben.

Ezeknek a problémáknak a bemutatásához és kezelésük módjainak vizsgálatához tegyük fel, hogy van egy alkalmas Φ(x) függvény adott adatok transzformálásához. A transzformálás után egy lineáris döntési határt kell alkotnunk, amely a példányokat az osztályoknak megfelelően választja szét. A következő a lineáris döntési határ alakja a transzformált térben: w⋅Φ(x)+b=0 .

5.2. Definíció

(nemlineáris SVM) A következő optimalizálási problémaként formalizálható a nemlineáris SVM-hez a tanulási feladat:

min w    ‖ w ‖ 2 2

feltéve,hogy   y i (w⋅Φ( x i )+b)≥1,    i=1,2,…,N.

Vegyük észre a nemlineáris SVM és a lináris SVM tanulási feladata közötti hasonlóságot. (Lásd az 5.1. definíciót a 268. oldalon.) A legfontosabb különbség az, hogy az eredeti x attribútumok használata helyett a tanulási feladat a Φ(x) transzformált attribútumokon kerül végrehajtásra. Az 5.5.2. és 5.5.3. szakaszokban a lineáris SVM-hez alkalmazott megközelítés szerint a következő duális Lagrange-függvényt lehet levezetni a korlátozott optimalizálási problémához:

L D = ∑ i=1 n λ i − 1 2 ∑ i,j λ i λ j y i y j Φ( x i )⋅Φ( x j ) (5.56)

Ha kvadratikus programozási módszerek segítségével megkapjuk a λ i -ket, a w és b paraméterek a következő egyenletek segítségével nyerhetők:

w= ∑ i λ i y i Φ( x i ) (5.57)

λ i { y i ( ∑ j λ j y j Φ( x j )⋅Φ( x i )+b)−1}=0, (5.58)

amelyek hasonlóak a lineáris SVM az (5.39) és (5.40) egyenleteihez. Végül egy z tesztpéldány a következő egyenlet alapján osztályozható:

f(z)=sgn(w⋅Φ(z)+b)=sgn( ∑ i=1 n λ i y i Φ( x i )⋅Φ(z)+b). (5.59)

Megjegyezzük, hogy az (5.57) egyenlet kivétével a hátralévő számítások (az (5.58) és az (5.59) egyenlet) magukban foglalják a transzformált térbeli vektorok Φ( x i )⋅Φ( x j ) belső szorzatának (azaz hasonlóságának) kiszámítását. Az ilyen számítások elég nehézkesek lehetnek és felléphet esetükben a dimenzióprobléma. A probléma egy áttörést jelentő megoldása a kernel-trükkként (kernel trick) ismert módszer.

Kernel-trükk

A belső szorzatot gyakran tekintik két vektor közötti hasonlóság mértékének. A 2.4.5. szakaszban a 75. oldalon bemutatott koszinusz-hasonlóság például két egyre normált vektor belső szorzataként definiálható. Hasonlóképpen a Φ( x i )⋅Φ( x j ) belső szorzat tekinthető két példány, az x i és x j , közötti hasonlóság mértékeként a transzformált térben.

A kernel-trükk egy módszer a transzformált térbeli hasonlóságnak az eredeti attribútumhalmaz felhasználásával történő kiszámításához. Tekintsük az (5.55) egyenletben adott Φ leképező függvényt. Az alábbi módon írható fel az u és v bemeneti vektorok belső szorzata a transzformált térben:

Φ(u)⋅Φ(v)=( u 1 2 , u 2 2 , 2 u 1 u 2 , 2 u 1 , 2 u 2 ,1)⋅( v 1 2 , v 2 2 , 2 v 1 v 2 , 2 v 1 , 2 v 2 ,1)

= u 1 2 v 1 2 + u 2 2 v 2 2 +2 u 1 v 1 u 2 v 2 +2 u 1 v 1 +2 u 2 v 2 +1

= (u⋅v+1) 2 . (5.60)

Ez az elemzés azt mutatja, hogy a transzformált térbeli belső szorzat kifejezhető az eredeti térbeli hasonlósági függvény segítségével:

K(u,v)=Φ(u)⋅Φ(v)= (u⋅v+1) 2 . (5.61)

Kernelfüggvénynek (kernel function) nevezzük a K hasonlósági függvényt, amelynek a kiszámítása az eredeti attribútumtérben történik. A kernel-trükk segít kezelni a nemlineáris SVM implementálásának néhány kérdését. Először is nem kell ismernünk a Φ leképező függvény pontos alakját, mert a nemlineáris SVM-hez használt kernelfüggvények ki kell hogy elégítsék a Mercer-tételként ismert matematikai elvet. Ez az elv azt biztosítja, hogy a kernelfüggvények mindig kifejezhetők két bemeneti vektor belső szorzataként valamilyen sokdimenziós térben. Az SVM kernelek transzformált terét reprodukáló magú Hilbert-térnek (RKHS -- reproducing kernel Hilbert space) nevezzük. Másodszor, a belső szorzat kernelfüggvények segítségével történő kiszámítása jelentősen olcsóbb, mint a Φ(x) transzformált attribútumhalmaz felhasználása esetén. Harmadszor, mivel a számítások az eredeti térben kerülnek elvégzésre, elkerülhetőek a dimenzióproblémával kapcsolatos kérdések.

Az 5.29. ábra (5.61) egyenletben adott polinomiális kernelfüggvényt használó SVM-mel kapott nemlineáris döntési határt mutatja. Egy z tesztpéldányt az alábbi egyenlet szerint osztályozunk:

f(z)=sgn( ∑ i=1 n λ i y i Φ( x i )⋅Φ(z)+b)

=sgn( ∑ i=1 n λ i y i K( x i ,z)+b)

=sgn( ∑ i=1 n λ i y i ( x i ⋅z+1) 2 +b), (5.62)

ahol b az (5.58) egyenlet segítségével kapott paraméter. A nemlineáris SVM által kapott döntési határ elég közel van az 5.28. (a) ábrán látható valós döntési határhoz.

Mercer-tétel

A nemlineáris SVM-hez használt kernelfüggvénnyel szembeni fő követelmény az, hogy léteznie kell egy olyan alkalmas transzformációnak, hogy a kernelfüggvény két vektorra történő kiszámítása ekvivalens a vektorok transzformált térbeli belső szorzatával. A követelmény formálisan a Mercer-tétel alakjában fogalmazható meg.

5.1. Tétel

(Mercer-tétel) Egy K kernelfüggvény akkor és csak akkor fejezhető ki

K(u,v)=Φ(u)⋅Φ(v)

alakban, ha minden olyan g(x) függvény esetén, amelyre ∫ ​ g (x) 2 dx véges, teljesül

∫ ​ K(x,y)  g(x)  g(y)  dx  dy≥0.

Az 5.1. tételt kielégítő kernelfüggvényeket pozitív definit kernelfüggvényeknek nevezzük. Az alábbiakban ilyen függvényekre sorolunk fel példákat:

K(x,y)= (x⋅y+1) p (5.63)

K(x,y)= e −∥x−y ∥ 2 /(2 σ 2 ) (5.64)

K(x,y)=tanh(kx⋅y−δ) (5.65)

Vegyük (5.63) egyenletben adott polinomiális kernelfüggvényt. Legyen g(x) egy függvény, amelynek L 2 normája véges, azaz ∫ ​ g (x) 2 dx≤∞ .

∫ ​ (x⋅y+1) p g(x)g(y)dxdy

= ∫ ​ ∑ i=0 p ( p i ) (x⋅y) i g(x)g(y)dxdy

= ∑ i=0 p ( p i ) ∫ ​ ∑ α 1 , α 2 ,… ( i α 1 α 2 … )[ ( x 1 y 1 ) α 1 ( x 2 y 2 ) α 2 ( x 3 y 3 ) α 3 …]

    g( x 1 , x 2 ,…)  g( y 1 , y 2 ,…)d x 1 d x 2 …d y 1 d y 2 …

= ∑ i=0 p ∑ α 1 , α 2 ,… ( p i )( i α 1 α 2 … ) [ ∫ ​ x 1 α 1 x 2 α 2 …g( x 1 , x 2 ,…)d x 1 d x 2 …] 2 .

Mivel az integrálás eredménye nemnegatív, a polinomiális kernelfüggvény kielégíti a Mercer-tételt.

Az SVM-nek sok kívánatos tulajdonsága van, amelyek az egyik legelterjedtebben használt osztályozó algoritmussá teszik. Az SVM általános jellemzőit az alábbiakban foglaljuk össze: