Fentiek értelmében optimális lineáris szeparálásnak azt a megoldást tekintjük, amikor az elválasztó egyenes (sík, hipersík) a két osztályba tartozó tanítópontok között a pontoktól a lehető legnagyobb távolságra helyezkedik el. A pontok között középre elhelyezett szeparáló felületet a tanítópontoktól egy margó (margin), azaz egy biztonsági sáv választja el, ezért az így megoldható feladatokat maximális tartalékot vagy maximális margót biztosító lineárisan szeparálható osztályozási feladatoknak is nevezzük. A következőkben ennek a feladatnak a megoldását mutatjuk be.

Legyenek adottak az ${\left\{x_i,d_i\right\}}_{i=1}^P$ tanítópontok, ahol az $x_i\in R^N$ N-dimenziós bemeneti pontok két osztály valamelyikéből származhatnak, vagyis a kívánt válaszok a két lehetséges érték egyikét veszik fel: $d_i\in \left\{-\mathrm{1,1}\right\}$ . Egy olyan $g\text{(}x\text{)}=w^{T}x+b$ szeparáló függvényt keresünk, amely a tanítópontokat hiba nélkül osztályozza:

$\begin{array}{l}{w}^T{x}_i+b\ge a>0\text{ ha }{d}_i=+\text{1}\\ w^T{x}_i+b\le -a<0\text{ ha }{d}_i=-\text{1}\end{array}$ i=1,2,…, P (6.23)

továbbá, ahol a hipersíkhoz legközelebb álló tanítópontoknak a síktól vett távolsága maximális. A (6.23) egyenlőtlenségben a valamilyen kis pozitív konstans, d_i pedig az x_i-hez tartozó kívánt válasz.

A hipersík paramétereinek megfelelő skálázásával biztosítható, hogy

$\begin{array}{l}{w}^T{x}_i+b\ge +1\text{ ha }{d}_i=+\text{1}\\ w^T{x}_i+b\le -1\text{ ha }{d}_i=-\text{1}\end{array}$ (6.24)

legyen, vagyis a síkhoz legközelebb eső pontokban az elválasztó függvény abszolút értéke 1 legyen. Így a feladat az alábbi tömörebb formában is felírható:

$d_i\text{(}{w}^T{x}_i+b\text{)}\ge 1i=\text{1}\text{, 2}\text{, }\dots \text{,}P$ (6.25)

Jelölje az optimális szeparáló lineáris felület paramétereit $w_{}^{\ast }$ és $b^{\ast }$ , és határozzuk meg egy x pontnak ettől a hipersíktól való távolságát. A 6.3 ábrát követve jelölje $x_p$ az $x$ pont merőleges vetületét a szeparáló felületre. Ekkor a pont felírható a vetület és a szeparáló felület normálvektora segítségével:

$x=x_p+r\frac{w^{\ast }}{\Vert w^{\ast }\Vert }$ . (6.26)

Mivel $g(x_p)=0$ , $g\text{(}x\text{)}=w^{\ast }{}^{T}x+b^{\ast }=r\Vert w^{\ast }\Vert$ , vagyis az x pontnak az optimális szeparáló hipersíktól való távolságára

$r=\frac{g\text{(}x\text{)}}{\Vert w^{\ast }\Vert }$ (6.27)

adódik, ahol $\Vert w^{\ast }\Vert$ a $w^{\ast }$ vektor euklideszi normáját jelöli. Az optimális hipersík a síkhoz legközelebbi tanítópontok távolságának maximumát biztosítja.

Az egységnyi távolságúra skálázott feladatban a határoló felülethez legközelebb eső pontokra $g\text{(}{x}_s^{+}\text{)}=1$ vagy $g\text{(}{x}_s^{-}\text{)}=-1$ . Ekkor a szeparáló hipersíkhoz legközelebb eső, különböző osztályba tartozó bemeneti vektorok közötti, a síkra merőlegesen mért távolság

$\rho =\frac{g\text{(}{x}_s^{+}\text{)}}{\Vert w^{\ast }\Vert }-\frac{g\text{(}{x}_s^{-}\text{)}}{\Vert w^{\ast }\Vert }=\frac{1}{\Vert w^{\ast }\Vert }-\frac{-1}{\Vert w^{\ast }\Vert }=\frac{2}{\Vert w^{\ast }\Vert }$ . (6.28)

Az optimális hipersík által biztosított margó tehát:

$r=\frac{\rho }{2}=\frac{1}{\Vert w^{\ast }\Vert }$ . (6.29)

Az egyenlet szerint az osztályozási tartalék akkor lesz maximális, ha $\Vert w^{\ast }\Vert$ minimális értékű.

A megoldandó feladat ezek után a következőképpen fogalmazható meg: adott egy lineárisan szeparálható mintapont készlet

$S=\left(\text{(}{x}_1,d_1\text{)},\dots ,\text{(}{x}_P,d_P\text{)}\right)$ , (6.30)

és keressük azt a minimális normájú w* vektort és azt a b* skalár értéket, melyekkel a tanítópontok mindegyikét helyesen osztályozzuk, vagyis keressük a

$w^{\ast }=\text{arg}\underset{w}{\text{min}}\text{(}{w}^{T}w\text{)}$ (6.31)

megoldását, azzal a feltételellel, hogy

$d_i\text{(}{w}^{\ast }{}^T{x}_i+b^{\ast }\text{)}\ge 1i=\text{1}\text{, 2}\text{, }\dots \text{,}P$ . (6.32)

A feladatot tehát feltételes szélsőérték-keresési problémaként tudjuk megfogalmazni, ahol a feltételek egyenlőtlenségek formájában vannak megadva. A feltételes szélsőérték-keresési feladat megoldását egy Lagrange kritérium (ld. Függelék) megoldásával kereshetjük:

$L\left(w,b\text{,}\alpha \right)=\frac{1}{2}{w}^{T}w-{\displaystyle \sum _{i=1}^P{\alpha }_i\left[d_i\text{(}{w}^T{x}_i+b\text{)}-1\right]}$ , (6.33)

ahol az ${\alpha }_i\ge 0$ együtthatók a Lagrange multiplikátorok. Az optimalizálási feladatnak ezt a felírását elsődleges alaknak (primal problem) nevezzük.

A optimalizálási feladat megoldásához a Karush-Kuhn-Tucker (KKT) elmélet (ld. Függelék) szerint a fenti Lagrange kritériumot kell minimalizálni $w$ és $b$ szerint és maximalizálni ${\alpha }_i$ szerint, vagyis a Lagrange kritérium által definiált kritériumfelület nyeregpontját (saddle point) kell meghatározni. A megoldás két lépesben érhető el:

Az $L\left(w,b\text{,}\alpha \right)$ Lagrange kritérium $w$ és $b$ szerinti parciális deriválásából az optimumra az alábbi két feltételt kapjuk:

$\begin{array}{ccc}\frac{\partial L\left(w,b\text{,}\alpha \right)}{\partial w}=0& \to & w={\displaystyle \sum _{i=1}^P{\alpha }_i}{d}_i{x}_i\end{array}$ , (6.34)

$\begin{array}{ccc}\frac{\partial L\left(w,b\text{,}\alpha \right)}{\partial b}=0& \to & {\displaystyle \sum _{i=1}^P{\alpha }_i}{d}_i=0\end{array}$ ${\alpha }_i\ge 0$ (6.35)

Látható, hogy ha a Lagrange multiplikárokat ismerjük, a feladatot megoldottuk, hiszen $w$ csak az ${\alpha }_i$ Lagrange multiplikátoroktól és a tanítópont-értékektől függ.

A feltételes optimalizálási feladat megoldásához felírható annak duális alakja, melyben már csak az ${\alpha }_i$ Lagrange multiplikátorok az ismeretlenek. Mivel az

$L\left(w,b\text{,}\alpha \right)=\frac{1}{2}{w}^{T}w-{\displaystyle \sum _{i=1}^P{\alpha }_i{d}_i{w}^T{x}_i}-b{\displaystyle \sum _{i=1}^P{\alpha }_i{d}_i}+{\displaystyle \sum _{i=1}^P{\alpha }_i}$ (6.36)

kifejtésében a harmadik tag (1.35) alapján nulla, és mivel (6.34) alapján

$w^{T}w={\displaystyle \sum _{i=1}^P{\alpha }_i{d}_i{w}^T{x}_i}={\displaystyle \sum _{i=1}^P{\displaystyle \sum _{j=1}^P{\alpha }_i{\alpha }_j{d}_i{d}_j{x}_i^T{x}_j}}$ (6.37)

az $L\left(w,b\text{,}\alpha \right)=Q(\alpha )$ duális optimalizálási feladat az alábbi:

$Q(\alpha )={\displaystyle \sum _{i=1}^P{\alpha }_i}-\frac{1}{2}{\displaystyle \sum _{i=1}^P{\displaystyle \sum _{j=1}^P{\alpha }_i{\alpha }_j{d}_i{d}_j{x}_i^T{x}_j}}$ (6.38)

a

${\displaystyle \sum _{i=1}^P{\alpha }_i{d}_i=0}$ (6.39)

és a

${\alpha }_i\ge 0$ , $i=\mathrm{1,....,}P$ (6.40)

feltételekkel.

A duális probléma egy olyan, a keresett ${\alpha }_i$ értékekben másodfokú szélsőérték-keresési feladat, mely mellett a megoldásnak egy egyenlőség, (6.39) és egy egyenlőtlenség, (6.40) típusú mellékfeltételt is ki kell elégítenie. Az ilyen típusú optimalizálási feladatok kvadratikus programozással (quadratic programming, QP) oldhatók meg. Az optimumhoz tartozó Lagrange multiplikátorok – az ${\alpha }_i^{\ast }$ értékek – ismeretében, felhasználva az optimális súlyvektorra vonatkozó (6.34) összefüggést, a lineáris kétosztályos osztályozó szupport vektor gép válasza felírható, mint

$y\text{(}x\text{)}=\text{sign}\left[{\displaystyle \sum _{i=1}^P{\alpha }_i^{\ast }{d}_i{x}_i^{T}x}+b^{\ast }\right]$ . (6.41)

Vegyük észre, hogy a válasz összefüggésében a bemeneti mintavektorok nem közvetlenül, hanem egy skalár szorzat részeként szerepelnek, tehát a (1.11) összefüggéshez hasonlóan itt is kernel megoldást kaptunk. A megoldás érdekessége, hogy az ${\alpha }_i^{\ast }$ -k nagyrésze általában 0, így mind a súlyvektor kifejezésében, mind a szupport vektor gép válaszában a tanítópontoknak csak egy része – a P tanítópontból csak P_s – vesz részt.

Azokat a tanítópontokat, amelyek résztvesznek a megoldás kialakításában, amelyekhez tartozó Lagrange multiplikátorok értéke nem nulla, szupport vektoroknak (support vectors) nevezzük.^[2] A szupport vektor gépek tehát olyan kernel gépek, ahol a kernel tér tényleges dimenziója nem a tanítópontok számával (P), hanem a szupport vektorok számával (P_s) egyezik meg. Ez jelentős egyszerűsítést jelenthet a válasz számításában, különösen, ha P_s<<P. A szupport vektor gépeknek ezt a tulajdonságát ritkasági (sparseness) tulajdonságnak nevezzük.

Azt is észrevehetjük, hogy azon tanitópontokra, ahol ${\alpha }_i^{\ast }>0$ , teljesül a

$d_i\text{(}{w}^{\ast }{}^T{x}_i+b^{\ast }\text{)}=1$ (6.42)

összefüggés, vagyis ezek a tanitópontok – tehát a szupport vektorok – lesznek az elválasztó hipersíkhoz legközelebb lévő mintapontok. Itt w* már az optimális Lagrange együtthatókkal meghatározható súlyvektor:

$w^{\ast }={\displaystyle \sum _{i=1}^{P_s}{\alpha }_i^{\ast }}{d}_i{x}_i$ , (6.43)

A szupport vektoroknál (6.42) alapján a (6.24) és a (6.25) egyenlőtlenségek egyenlőségként állnak fenn. Az optimális eltolásérték (bias) ( $b^{\ast }$ ) a $d_i\text{(}{w}^{\ast T}{x}_i+b^{\ast }\text{)}=1$ egyenletből számítható, ahol $x_i^{}$ egy szupport vektor.

Az előzőekben tárgyalt maximális margójú lineáris szeparálásra képes megoldás az alapelvek bemutatására alkalmas. A gyakorlatban azonban ritkán találkozunk olyan feladatokkal, melyek úgy szeparálhatók lineárisan, hogy még osztályozási tartalék is biztosítható. Általában vagy csak olyan lineáris szeparálás lehetséges, ahol a két osztály között csak nagyon kis biztonsági sáv alakítható ki, vagy lineáris szeparálás hibamentesen nem is lehetséges. A kis biztonsági sávot növelhetnénk, ha nem ragaszkodnánk ahhoz, hogy minden tanítópont a sávon kívül helyezkedjen el. Ha a pontok többsége a sávon kívül lesz, de néhány mintapontnál megengedjük, hogy a sávon belülre kerüljenek (sőt esetleg azt is megengedjük, hogy egyes mintapontok az elválasztó hipersík „rossz” oldalára kerüljenek), akkor ezen az áron a sáv mérete esetleg jelentősen növelhető. A következőkben olyan lineáris megoldást mutatunk be, ahol megfelelő kompromisszum alapján dől el a biztonsági sáv mérete és a hibás osztályozás valószínűsége.

Ha megengedjük, hogy a biztonsági sávban is legyenek tanítópontok, miközben továbbra is cél a lehető legnagyobb margó biztosítása, ún. lágy vagy szoft margójú megoldásról beszélünk. Azoknál a pontoknál, amelyek a biztonsági sávon belül helyezkednek el a maximális margójú osztályozást biztosító

$d_i\text{(}{w}^T{x}_i+b\text{)}\ge 1$ (6.46)

egyenlőtlenség nem áll fenn. Az ilyen mintapontokra vonatkozó, az előző egyenlőtlenségnek megfelelő formális kapcsolat ún. gyengítő (slack) ξ_i változók bevezetésével lehetséges. A gyengítő változók bevezetése lehetővé teszi, hogy a (6.46) összefüggés az egyes tanítópontoknál különböző mértékben gyengítve érvényesüljön. Ennek megfelelően az összes pontra most a következő egyenlőtlenség írható fel:

$d_i\text{(}{w}^T{x}_i+b\text{)}\ge 1-{\xi }_i,$ i=1,2,…,P (6.47)

Azon tanítópontoknál, ahol ${\xi }_i=0$ , visszakapjuk az alapfeladatot. Ha $0<{\xi }_i\le 1$ , az adott tanítópont a hipersík megfelelő oldalán, de a biztonsági sávban vagy a sávhatáron helyezkedik el, ha pedig ${\xi }_i>1$ az adott tanítópont a sík ellenkező oldalán (a hibás oldalon) van. Ezt illusztrálja a 6.4 ábra.

Az optimális hipersíkot úgy kell meghatározni, hogy a hibás osztályozások száma minimális legyen, miközben továbbra is törekszünk a lehető legnagyobb margó elérésére. A minimalizálandó kifejezés − amit a továbbiakban J(w)-vel jelölünk − ennek megfelelően két tagból áll:

$J\text{(}w\text{)}=\frac{1}{2}{w}^{T}w+C{\displaystyle \sum _{i=1}^P{\xi }_i}$ , (6.48)

ahol C a két tag közötti kompromisszumot beállító együttható. Ha C=0, visszakapjuk az előző, gyengítő változó nélküli esetet. Ha C értéke kicsi, a minimalizálandó összefüggésben a második tag súlya kicsi, vagyis nem nagyon büntetjük, ha egy tanítópont a margón belülre, netán a rossz oldalra kerül. Ez azt jelenti, hogy a biztonsági sáv szélesebb lehet, de több pont kerül a sávon belülre vagy a rossz oldalra. Ha C értékét növeljük, ezeket az eseteket jobban büntetjük, ami keskenyebb biztonsági sávot eredményez, hiszen ekkor nyilván kevesebb pont eshet a sávon belülre.

A megoldás most is a megfelelő Lagrange kritérium felírását igényli, hiszen itt is feltételes szélsőérték-keresési feladattal állunk szemben. Egyfelől (6.48) minimumát kívánjuk elérni, de közben a (6.47) által a tanítópontokra megfogalmazott egyenlőtlenségeket is teljesíteni kívánjuk. Ennek megfelelően a következő Lagrange kritériumot tudjuk felírni.

$L\left(w\text{,}\xi \text{,}\alpha ,\gamma ,b\right)=\frac{1}{2}{w}^{T}w+C{\displaystyle \sum _{i=1}^P{\xi }_i}-{\displaystyle \sum _{i=1}^P{\alpha }_i\text{{}{d}_{\text{i}}\text{(}{w}^T{x}_i+b\text{)}-1+{\xi }_i\text{}}}-{\displaystyle \sum _{i=1}^P{\gamma }_{\text{i}}{\xi }_i}$ (6.49)

A kritérium a (6.47) által a tanítópontokra megfogalmazott gyengített feltételek figyelembevételén kívül egy új taggal is bővült. Az utolsó tag – amely szintén egy Lagrange multiplikátoros tag − azt fejezi ki, hogy törekszünk arra, hogy a ${\xi }_i$ értékek lehetőleg nullák, de legalábbis minél kisebbek legyenek. Itt ${\gamma }_{\text{i}}$ -k a megfelelő Lagrange multiplikátorok. A módosított Lagrange kritériumot w, b és ${\xi }_i$ -k szerint minimalizálni, míg ${\alpha }_i$ -k és ${\gamma }_{\text{i}}$ -k szerint maximalizálni kell. A feladatot most is két lépésben oldhatjuk meg. Először a Lagrange kritérium w , b és $\xi$ szerinti deriváltját írjuk fel.

$\begin{array}{ccc}\frac{\partial L\left(w\text{,}\xi \text{,}\alpha ,\gamma ,b\right)}{\partial w}=0& \to & w={\displaystyle \sum _{i=1}^P{\alpha }_i}{d}_i{x}_i\end{array}$ , (6.50)

$\begin{array}{ccc}\frac{\partial L\left(w\text{,}\xi \text{,}\alpha ,\gamma ,b\right)}{\partial b}=0& \to & {\displaystyle \sum _{i=1}^P{\alpha }_i}{d}_i=0\end{array}$ (6.51)

$\begin{array}{ccc}\frac{\partial L\left(w\text{,}\xi \text{,}\alpha ,\gamma ,b\right)}{\partial \xi }=0& \to & {\gamma }_i\end{array}+{\alpha }_i=C$ . (6.52)

Ezt követően a gradiensek értékének nullává tételével kapott összefüggéseket behelyettesítve a Lagrange kritériumba kapjuk a (6.38) összefüggéssel megegyező duális feladatot:

$Q\left(\alpha \right)={\displaystyle \sum _{i=1}^P{\alpha }_i}-\frac{1}{2}{\displaystyle \sum _{i=1}^P{\displaystyle \sum _{j=1}^P{\alpha }_i{\alpha }_j{d}_i{d}_j{x}_{{}_i}^T{x}_j}}$ , (6.53)

ahol

$\begin{array}{ccc}{\displaystyle \sum _{i=1}^P{d}_i{\alpha }_i=\mathrm{0,}}& 0\le {\alpha }_i\le C\text{, }& i=\mathrm{1,}\mathrm{2,}\mathrm{....},P\end{array}$ , (6.54)

és melyből az ${\alpha }_i$ -k most is kvadratikus programozással határozhatók meg. Figyeljük meg, hogy a gyengítő változók bevezetése az optimalizálási feladat duális alakját csak a Lagrange multiplikátorokra vonatkozó feltételekben módosítja. Az osztályozó eredménye is megegyezik a lineárisan szeparálható feladatra megadottakkal (6.41). Ennek megfelelően itt is lesznek nulla értékű ${\alpha }_i$ -k, melyekhez tartozó tanítópontok nem vesznek részt a kimenet előállításában. Ha pedig ${\alpha }_i\ne 0$ , a megfelelő tanítópontok szupport vektorok lesznek, melyekre a

$d_i\text{(}{w}^{\ast }{}^T{x}_i+b^{\ast }\text{)}-\text{1}+{\xi }_i=0$ (6.55)

egyenlőség áll fenn. Ez azt jelenti, hogy most a szupport vektorok sem feltétlenül a margó határán helyezkednek el. A margóhoz viszonyított helyzetüket a ${\xi }_i$ értékek befolyásolják.

A (6.48) minimalizálandó kritériumban szereplő $C$ konstanst hiperparaméternek is szokás nevezni. Szerepe – ahogy az előbb említettük – az, hogy a súlyvektor hosszának, illetve a tanító mintákra számított osztályozási hibának a viszonyát beállítsa. C meghatározása nem könnyű feladat, általában kereszt kiértékeléssel történhet.

A valós osztályozási feladatok túlnyomó része nem szeparálható lineárisan. A lineárisan nem szeparálható feladatoknál – ahogy ezt már többször láttuk – egy megfelelő (és általában dimenziónövelő) $x\to \phi (x)$ nemlineáris transzformációval lineárisan szeparálhatóvá alakítjuk a feladatot. Az SVM előnyeinek kihasználására az így kapott jellemzőtérben az előzőeknek megfelelő optimális (maximális margójú) megoldást keressük.

A nemlineárisan szeparálható feladat SVM-el történő megoldásában tehát két lépés szerepel:

Ez utóbbi lépést azonban itt sem a jellemzőtérben, hanem az ebből származtatott kernel térben oldjuk meg.

A nemlineáris megoldás a lineáris eset megoldásából egyszerűen az $x\to \phi (x)$ helyettesítéssel nyerhető. Az optimális hipersíkot a következő alakban keressük:

$w^T\phi (x)+b=0$ (6.56)

Ennek alapján a korábbi lineárisan szeparálható esetre kapott eredményünknek megfelelően az optimális súlyvektor:

$w^{\ast }={\displaystyle \sum _{i=1}^P{\alpha }_{{}_i}^{\ast }}{d}_i\phi \text{(}{x}_i\text{)}$ , (6.57)

ahol $\phi (x_i)$ az $x_i$ mintához tartozó jellemző (feature) vektor. Az optimális eltolásérték (bias) ( $b^{\ast }$ ) a $w^{\ast T}\phi \text{(}{x}_s^{+}\text{)}+b^{\ast }=+1$ vagy a $w^{\ast T}\phi \text{(}{x}_s^{-}\text{)}+b^{\ast }=-1$ egyenletből számítható, ahol $x_s^{+}\text{ill}\text{. }{x}_s^{-}$ egy-egy megfelelő osztályba tartozó szupport vektor. A jellemzőtérben megkonstruált szeparáló felületet tehát a következő egyenlet adja meg:

${\displaystyle \sum _{i=1}^P{\alpha }_{{}_i}^{\ast }}{d}_i{\phi }^{{\rm T}}\text{(}{x}_i\text{)}\phi \text{(}x\text{)}+b^{\ast }=0$ . (6.58)

Látható, hogy a megoldáshoz most is csak az ${\alpha }_i$ Lagrange multiplikátorok meghatározása szükséges, amit a (6.38) összefüggésnek megfelelő duális feladat kvadratikus programozással történő megoldásával nyerhetünk. A különbség mindössze annyi, hogy a duális feladatnál x helyére mindenhol $\phi \text{(}x\text{)}$ kell kerüljön. Ha a jellemzőtérben maximális margójú megoldás kapható, akkor a Lagrange multiplikátorokra az $0\le {\alpha }_i$ feltétel, ha csak a gyengített változat, akkor az $0\le {\alpha }_i\le C$ feltétel teljesül.

A ${\phi }^{{\rm T}}\text{(}{x}_i\text{)}\phi \text{(}x\text{)}$ szorzatot a kernel trükknek megfelelően egy magfüggvényként írjuk fel, azaz

$K\text{(}{x}_i,x\text{)}={\phi }^{{\rm T}}\text{(}{x}_i\text{)}\phi \text{(}x\text{)}$ . (6.59)

A nemlineáris osztályozó tehát:

$y\text{(}x\text{)}=\text{sign}\left[{\displaystyle \sum _{i=1}^P{\alpha }_{{}_i}^{\ast }{d}_{i}K\text{(}{x}_i,x\text{)}}+b^{\ast }\right]$ (6.60)

alakban adja meg egy x bemenetre a választ. Az összegzés az összes tanítópontra vonatkozik, valójában azonban csak a szupport vektorokra kell elvégezni, hiszen a többi esetben ${\alpha }_i=0$ . A szupport vektor gépek tehát nemlineáris esetben is ritka (sparse) megoldást eredményeznek.

A szupport vektor gépes megoldás előnye a kerneles megoldások előnyéhez hasonlóan itt is azáltal jelentkezik, hogy a feladatot nem a jellemzőtérben oldjuk meg, hanem a kernel térben, azáltal, hogy a $\phi \text{(}x\text{)}$ nemlineáris transzformációt nem közvetlenül, hanem csak a kernel függvényen keresztül, közvetve definiáljuk.

A 6.5 ábrán a nemlineáris SVM osztályozás illusztrálására gyakran használt kettős spirál feladat egy megoldását mutatjuk be. A szeparálandó két osztály két egymásba tekeredő spirál pontjaival van megadva, melyek tanítópontokként szerepelnek. A két osztályba tartozó tanítópontokat (+), illetve (o) jelek jelölik az ábrán. A feladat tehát olyan elválasztó görbe meghatározása, mely a két spirál pontjait szeparálja. A feladatot, mint benchmark problémát gyakran használják osztályozó rendszerek, köztük neuronhálók teljesítőképességének összehasonlítására. Ezt az indokolja, hogy bár a feladat nagyon egyszerűnek tűnik, megoldása nem könnyű, pl. egy MLP számára különösen nehéz.

6.1 példa

Példaként oldjuk meg a XOR problémát szupport vektor géppel. Minthogy a feladat lineárisan nem szeparálható, csak a nemlineáris változat használható. Első lépésként meg kell választani a kernel függvényt. A feladat viszonylagos egyszerűsége miatt az eddig említett kernel függvények bármelyike használható. Jelen esetben használjunk polinomiális kernelt: K(x,x)=(x^Tx+1)². A polinomiális kernel előnye, hogy ebben az egyszerű esetben még a jellemzőtérre való leképezést biztosító ϕ(x) függvények is meghatározhatók. A jellemzővektorra a következő adódik:

$\phi \text{(}x\text{)}={\text{[1}\text{, }\sqrt{\text{2}}{x}_{\text{1}}\text{,}\sqrt{\text{2}}{x}_{\text{2}}\text{,}\sqrt{\text{2}}{x}_{\text{1}}{x}_{\text{2}}\text{,}{x}_1^2\text{,}{x}_2^2\text{]}}^T$ (6.61)

Látható, hogy a jellemzőtér egy 6-dimenziós tér (5 dimezió + az eltolás). Az osztályozási feladat megoldásához fel kell írnunk és meg kell oldanunk a duális egyenletet.

$Q\left(\alpha \right)={\alpha }_1+{\alpha }_2+{\alpha }_3+{\alpha }_4-\frac{1}{2}{\displaystyle \sum _{i=1}^4{\displaystyle \sum _{j=1}^4{\alpha }_i{\alpha }_j{d}_i{d}_{j}K\text{(}{x}_{{}_i}^T{x}_j\text{)}}}$ , (6.62)

a következő feltételek mellett:

$\begin{array}{ccc}{\displaystyle \sum _{i=1}^4{d}_i{\alpha }_i={\alpha }_1-{\alpha }_2+{\alpha }_3-{\alpha }_4=\mathrm{0,}\text{és }}& 0\le {\alpha }_i\text{, }& i=\mathrm{1,}\mathrm{2,}\mathrm{....}\mathrm{,4}\end{array}$ (6.63)

A kvadratikus egyenlet felírásánál feltételeztük, hogy a bemenetek és a kimenetek nem bináris, hanem bipoláris megadásúak, vagyis a XOR probléma leképezése a következő:

A kvadratikus programozási feladat megoldásához fel kell írni a kernel mátrixot. Mivel a XOR problémánál összesen 4 pontunk van, melyek mind tanítópontok, a kernel mátrixra a következő adódik:

$K=\left[\begin{array}{cccc}9& 1& 1& 1\\ 1& 9& 1& 1\\ 1& 1& 9& 1\\ 1& 1& 1& 9\end{array}\right]$ (6.64)

A kvadratikus programozás eredményeképpen azt kapjuk, hogy mind a négy α azonos értékű lesz, és mind különbözik nullától: ${\alpha }_{{}_1}^{\ast }={\alpha }_{{}_2}^{\ast }={\alpha }_{{}_3}^{\ast }={\alpha }_{{}_4}^{\ast }=1/8$ . Ez azt jelenti, hogy az összes pont szupport vektor, ami a feladat ismeretében nem meglepő. A szupport vektoroknál a háló válasza alapján az eltolásérték is meghatározható, ami b*=0-ra adódik. A háló válasza a kernel térben tehát:

$y\text{(}x\text{)}=\text{sign}\left[\mathrm{0,125}{\displaystyle \sum _{i=1}^4{d}_i{\text{(}{x}_i^{T}x+1\text{)}}^{\text{2}}}\right]$ (6.65)

A szupport vektor gépeknél a jellemzőtérbeli reprezentáció és megoldás általában nem határozható meg, és nincs is rá szükség. Ebben az egyszerű példában azonban ismerjük a jellemzőtérre való leképezést biztosító $\phi \text{(}x\text{)}$ függvényeket, és a Lagrange multiplikátorok ismeretében a w* jellemzőtérbeli súlyvektor is meghatározható:

$w^{\ast }={\displaystyle \sum _{i=1}^4{\alpha }_i^{\ast }}{d}_i{x}_i={\text{[}\begin{array}{cccccc}0& 0& 0& 1/\sqrt{2}& 0& 0\end{array}\text{]}}^T$ (6.66)

Ennek ismeretében a megoldás a jellemzőtérben is megkapható. A döntési függvény:

g(x)=x₁x₂. (6.67)

Arra az érdekes eredményre jutottunk, hogy bár a választott kernel által meghatározott nemlineáris transzformáció hatdimenziós jellemzőteret definiál, a döntés egyetlen dimenzió alapján meghozható, melyet a két bementi komponens szorzata határoz meg. Ez egyben arra is példa, hogy előfordulhat olyan eset, amikor a „dimenziónövelő” nemlineáris transzformáció valójában kisebb dimenziójú térbe képez le, mert a lineáris szeparálás ott is lehetséges. Ez természetesen általánosan nem igaz, de feladattól függően, ha megfelelő nemlineáris transzformációt választunk, előfordulhat. A nemlineáris SVM a jellemzőtérben biztosítja a maximális margót, ami itt $\sqrt{2}$ -re adódik.

A szupport vektor gépekaz osztályozási feladatokon túl regressziós feladatokra is alkalmazhatók. A regressziósvagy függvényapproximációs feladatok esetén azonban nem definiálható az osztályozásnál értelmezett margó, azaz az osztályozási tartalék fogalma. Ennek megfelelően szükség van a regressziós feladat egy olyan értelmezésére, felírására, ami lehetővé teszi az SVM kiegészítő feltételének felhasználását.

Hasonlóan az osztályozónál bemutatottakhoz itt is lehetőség lenne először a lineáris esetet, majd annak nemlineáris kiterjesztését tárgyalni, de a tömörebb tárgyalás kedvéért itt közvetlenül a nemlineáris (azaz a jellemzőtérben lineáris) regressziót mutatjuk be.

Az osztályozós és a regressziós feladatok között a kapcsolat viszonylag könnyen megteremthető, ha a függvényapproximációs feladatoknál az átlagos négyzetes hiba helyett egy ún. ε-érzéketlenségi sávvalrendelkező abszolútérték hibafüggvényt (ε-insensitive loss function) alkalmazunk az eltérés mérésére.

$L_{\epsilon }\left(y\right)=\{\begin{array}{cc}0& \text{ha}\left|d-y\left(x\right)\right|<\epsilon \\ \left|d-y\left(x\right)\right|-\epsilon & \text{egyébként}\end{array}$ (6.68)

Az ε érzéketlenségű veszteségfüggvény felhasználásával tulajdonképpen az osztályozási esethez nagyon hasonló probléma áll elő. Azokra a mintákra, melyek az érzéketlenségi sávon belül esnek, a hiba értéke 0, míg a kívül eső pontok hibáját büntetjük. Ez megfeleltethető egy olyan osztályozási feladatnak, ahol a helyes osztályozás hibája 0, míg biztonsági sávba eső vagy a rosszul osztályozott pontokat pedig gyengítő ( $\xi$ ) változók bevezetésével büntetjük. Ennek megfelelően az alábbiakban bemutatott regressziós megoldást a lineárisan nem szeparálható osztályozási feladatra kapott eredményekkel célszerű összevetni. Hibafüggvényként az abszolútérték-függvény használatát az is indokolja, hogy ekkor a megoldás az esetlegesen jelen lévő kilógó adatokra (outlier) kevésbé lesz érzékeny, mint a gyakran alkalmazott négyzetes hibafüggvénynél. Ennek ellenére szokás ε-érzéketlenségi sávú négyzetes hibafüggvényt is alkalmazni. Jelen tárgyalásnál azonban megmaradunk a Vapnik féle alapmegoldásnál, ahol az abszolútérték-függvény szerepel.

Írjuk fel a háló kimenetét. Ez most is nemlineáris bázisfüggvények lineáris kombinációjaként áll elő, azaz a $\phi \left(x\right)$ -ek által reprezentált (M-dimenziós) jellemzőtérben lineáris megoldást keresünk:

$y\left(x\right)={\displaystyle \sum _{j=1}^M{w}_j}{\phi }_j\left(x\right)+b=w^T\phi \left(x\right)+b$ , $w={\left[w_1,w_2\mathrm{,...,}{w}_M\right]}^T$ ,

$\phi \left(x\right)={\left[{\phi }_1\left(x\right),{\phi }_2\left(x\right)\mathrm{,...,}{\phi }_M\left(x\right)\right]}^T$ (6.69)

A kielégítendő feltételek (a gyengítő változók bevezetésével) a következők:

$\begin{array}{c}{d}_i-\text{(}{w}^T\phi \text{(}{x}_i\text{)}+b\text{)}\le \epsilon +{\xi }_i,\\ \text{(}{w}^T\phi \text{(}{x}_i\text{)}+b\text{)}-d_{\text{i}}\le \epsilon +{{\xi }^{\prime }}_i,\\ {\xi }_i\ge \mathrm{0,}\\ {{\xi }^{\prime }}_i\ge \mathrm{0,}\end{array}i=\mathrm{1,}\mathrm{2,}\mathrm{...},P$ (6.70)

A minimalizálandó költségfüggvény:

$J\left(w\text{,}\xi \text{,}{\xi }^{\prime }\right)=\frac{1}{2}{w}^{T}w+C\left({\displaystyle \sum _{i=1}^P\text{(}{\xi }_i+{{\xi }^{\prime }}_i\text{)}}\right)$ (6.71)

a (6.70) egyenlőtlenségek által megfogalmazott mellékfeltételekkel ( $i=\mathrm{1,...,}P$ ):

A megfelelő Lagrange kritérium az ${\alpha }_i,{{\alpha }^{\prime }}_i,{\gamma }_i,{{\gamma }^{\prime }}_i\ge 0$ Lagrange multiplikátorok felhasználásával:

$\begin{array}{l}L\left(w\text{,}b\text{,}\xi \text{,}{\xi }^{\prime }\text{,}\alpha ,{\alpha }^{\prime },\gamma ,{\gamma }^{\prime }\right)=C{\displaystyle \sum _{i=1}^P\left({\xi }_i+{{\xi }^{\prime }}_i\right)}+\frac{1}{2}{w}^{T}w\\ -{\displaystyle \sum _{i=1}^P{\alpha }_i\left[w^T\phi \text{(}{x}_i\text{)}+b-y_i+\epsilon +{\xi }_i\right]}\\ -{\displaystyle \sum _{i=1}^P{{\alpha }^{\prime }}_i\left[y_i-w^T\phi \text{(}{x}_i\text{)}-b+\epsilon +{{\xi }^{\prime }}_i\right]}-{\displaystyle \sum _{i=1}^P\left({\gamma }_i{\xi }_i+{{\gamma }^{\prime }}_i{{\xi }^{\prime }}_i\right)}\end{array}$ (6.72)

A Lagrange függvényt kell w, b és a $\xi$ és ${\xi }^{\prime }$ gyengítő vektorváltozók szerint minimalizálni, $\alpha ,{\alpha }^{\prime }$ , valamint $\gamma$ és ${\gamma }^{\prime }$ szerint maximalizálni. Elvégezve a deriválást, és a deriváltak értékét nullává téve, a következő összefüggéseket kapjuk:

$\begin{array}{l}w={\displaystyle \sum _{i=1}^P\left({\alpha }_i-{{\alpha }^{\prime }}_i\right)}\phi \text{(}{x}_i\text{)}\\ {\gamma }_i=C-{\alpha }_i\\ {{\gamma }^{\prime }}_i=C-{{\alpha }^{\prime }}_i\end{array}$ (6.73)

Behelyettesítve ezeket a Lagrange függvénybe jutunk a duális feladatra:

$\begin{array}{l}Q\left(\alpha ,{\alpha }^{\prime }\right)={\displaystyle \sum _{i=1}^P{d}_i\left({\alpha }_i-{{\alpha }^{\prime }}_i\right)}-\epsilon {\displaystyle \sum _{i=1}^P\left({\alpha }_i+{{\alpha }^{\prime }}_i\right)}\\ -\frac{1}{2}{\displaystyle \sum _{i=1}^P{\displaystyle \sum _{j=1}^P\left({\alpha }_i-{{\alpha }^{\prime }}_i\right)\left({\alpha }_j-{{\alpha }^{\prime }}_j\right)}}K\left(x_i,x_j\right)\end{array}$ (6.74)

a

$\begin{array}{cccc}{\displaystyle \sum _{i=1}^P\left({\alpha }_i-{{\alpha }^{\prime }}_i\right)=\mathrm{0,}}& 0\le {\alpha }_i\le C\text{, }& 0\le {{\alpha }^{\prime }}_i\le C\text{, }& i=\end{array}\mathrm{1,2,....,}P$ (6.75)

megkötésekkel. Az eredmény a kvadratikus programozással meghatározható ${\alpha }_i$ Lagrange multiplikátorok, a kiszámított $b$ és a $K\left(x,x_i\right)$ kernel függvény alapján:

$y\text{(}x\text{)}={\displaystyle \sum _{i=1}^P\left({\alpha }_i-{{\alpha }^{\prime }}_i\right)}K\left(x,x_i\right)+b$ (6.76)

Csakúgy, mint az osztályozási esetben, az SVM modell most is ritka, ugyanis csak azok a tanítópontok vesznek részt a kimenet előállításában, melyekre $\left({\alpha }_i-{{\alpha }^{\prime }}_i\right)\ne 0$ . Fontos megjegyezni, hogy most is a kernel függvényből indulunk ki, így a jellemzőtér bázisfüggvényeit a kernel függvény implicit módon definiálja. Ez a jellemzőtér azonban nagyon nagy dimenziós, akár végtelen dimenziós is lehet, ezért míg lineáris esetben a probléma az eredeti térben is megoldható, nemlineáris esetben a jellemzőtérben már nem minden esetben lehetséges a megoldás.

Figyeljük meg, hogy a regressziós megoldásnál az SVM kialakításában az osztályozós esethez képest eggyel bővül a hiperparaméterek száma, hiszen az ε érzéketlenségi paraméter megadására is szükség van. Az ε hiperparaméternek az approximációra gyakorolt hatása zajmentes tanítópontok esetén szemléletesen is értelmezhető (6.7 ábra).

Az ábrán látható, hogy ha a megoldás köré egy ε szélességű sávot húzunk úgy, hogy az SVM válaszfüggvényét $\pm \epsilon$ -nal eltoljuk, akkor minden tanítópont ezen a sávon belül helyezkedik el. A sávhatárra eső pontok lesznek a szupport vektorok (az ábrán a nagyobb fekete pontok). Az ábra azt is mutatja, hogy kisebb szélességű sáv több, a nagyobb szélességű pedig kevesebb szupport vektort eredményez. Ezt úgy biztosítja az SVM, hogy minél nagyobb ε értéke, annál simább megoldást kapunk. Ezt a hatást illusztrálja a 6.8 ábra is. Ezen az ábrán is szerepel egy ε szélességű sáv, ami azonban most az approximálandó függvényt veszi közre, és annak $\pm \epsilon$ -nal történő eltolásával kapható. Az SVM zajmentes esetben mindig olyan megoldást ad, amely ebbe az ε szélességű sávba belefér, miközben a válasz a lehető legsimább. Látható, hogy a szélesebb sáv simább, a keskenyebb kevésbé sima megoldást eredményez.

Fentiek alapján ε hatása zajmentes esetben jól követhető, és ennek alapján a megfelelő ε érték megválasztható, hiszen minél kisebb ez az érzéketlenségi sáv, annál pontosabban próbálja a modell a tanítópontokra illeszteni a megoldást. A valós feladatokban azonban szinte mindig zajos bemenetekkel van dolgunk.

Ebben az esetben a kis ε arra késztetné a modellt, hogy minden pontot jól (kis hibával) közelítsen, ami túltanuláshoz vezethet, holott a cél itt éppen egy simább függvény illesztése lenne. Nagyobb zaj esetén tehát célszerű nagyobb ε-t, szélesebb érzéketlenségi sávot használni. Zajos tanítópontok mellett ε hatására a 6.9 ábra mutat példát.

Az SVM minél simább válasza annak a következménye, hogy a súlyvektor normáját minimalizáljuk. A költségfüggvényben szereplő $w^{T}w$ tag osztályozós esetben a maximális margóért, regressziós esetben pedig a sima és minél laposabb megoldásért felelős.

A megoldás hibája, valamint komplexitása közötti kompromisszumot regressziós esetben is a C paraméter állítja be, azaz az ε és a C hiperparaméterek értékét összehangoltan kell megválasztani. Általánosságban is elmondható, hogy a szupport vektor gépek hiperparamétereinek (az ε, a C, valamint a kernel függvény paramétereinek – Gauss kernel esetén a $\sigma$ szélességparaméternek) a megválasztása igen összetett feladat, mert az egyes paraméterek nem függetlenek egymástól, így a lehetséges beállítások terében kell egy jó, esetleg optimális kombinációt megtalálni. A kernel paraméterek hatása – ha Gauss kernelt választunk – hasonló a Gauss bázisfüggvényes RBF hálók szélességparaméterének hatásához: a nagy $\sigma$ simább, míg a kis $\sigma$ változékonyabb (erősen lokalizált) közelítést eredményez, ami hatással van például a megfelelő C értékre is. C értékét az előbbi esetben kisebb, míg az utóbbi esetben várhatóan nagyobbra kell megválasztani. A hiperparaméterek megfelelő megválasztásával számos irodalom pl. [Sch02], [Cha02], [Kwo03] foglalkozik.

Bár a gyakorlatban a szupport vektor gépeket ritkán alkalmazzák neurális hálózat alakjában, ez az értelmezés hasznos, mert egyszerűbb tárgyalásmódot tesz lehetővé a pusztán matematikai megközelítésnél.

A szupport vektor gépek tanítása, és használata is megfelelő számítások sorozata, ahol a válasz számításának összefüggése pontosan megfeleltethető egy egy-rejtett-rétegű neurális hálózatnak. A rejtett réteg tipikusan nemlineáris neuronokat tartalmaz. A 6.11 ábra egy szupport vektor gépnek megfeleltethető neurális hálózatot mutat be.

A bemenet egy N-dimenziós vektor. A nemlineáris kernel függvényeket a rejtett réteg neuronjai tartalmazzák. Ezen neuronok száma megegyezik a szupport vektorok számával (P_s). A hálózat válasza ( $y$ ) a rejtett réteg neuronjai kimenetének súlyozott összege. A súlyokat a tanítás során kiszámított Lagrange multiplikátor értékek ( ${\alpha }_i$ ) határozzák meg. Ennek megfelelően, minél kisebb a hálózat, annál kevesebb számításra van szükség a válasz megadásához, így a cél a lehető legkisebb hálózat elérése.

Láthatóan a kernel gép neurális interpretációja egy struktúrájában a bázisfüggvényes hálózatokkal gyakorlatilag tökéletesen megegyező háló. Ez azonban csak formai hasonlóság, a kétféle megközelítés közötti lényeges különbséget nem szabad szem elől téveszteni.

A szupport vektor gépek gyakorlati felhasználásának egyik legnagyobb akadálya az SVM tanításához szükséges kvadratikus programozás nagy algoritmikus komplexitása, valamint a kernel mátrix nagy mérete. Az alábbiakban olyan módszereket mutatunk be röviden, melyek a számítás gyorsítását, valamint a szükséges memória méretének csökkentését célozzák. Ezt a feladatot kétféleképpen oldhatjuk meg. Ezek: