Tukivektorikone

Tukivektorikone (engl. Support Vector Machine) on 1990-luvulla kehitetty lineaarinen luokitinmalli, joka soveltuu luokitteluun ja käyränsovitustehtävään. Tukivektorikone voidaan toteuttaa neuroverkolla. Tukivektorikoneen yleistämiskyky on MLP-neuroverkkoon verrattuna parempi. Yleistämiskyky kuvaa luokittimen kykyä luokitella ennalta tuntemattomat näytteet oikein.

Perusteet

Päätöstaso (keskellä) ja marginaalitasot

Tukivektorikoneen perusajatus on sovittaa kahden näytejoukon väliin sellainen taso, että sen kanssa yhdensuuntaisten marginaalitasojen välimatka on mahdollisimman suuri eikä yksikään näyte jää marginaalitasojen väliin. Marginaalitasojen välimatkaa rajoittavia näytevektoreita kutsutaan tukivektoreiksi. Luokittelun tulos riippuu ainoastaan näistä tukivektoreista.

Tukivektorikoneen tulee opetuksen jälkeen osata luokitella mielivaltainen näyte. Luokitin opetetaan opetusaineiston perusteella, ja siksi sen hyvyys osaltaan riippuu opetusaineiston hyvyydestä.

Kun opetusjoukot eivät ole separoituvia, käytetään tukivektorikonetoteutusta, jota kutsutaan joustavan marginaalin luokittimeksi. Menetelmä etsii opetusaineistosta ne näytevektorit, jotka määrittävät eri luokkien rajat.

Optimimarginaaliluokitin

Optimimarginaaliluokitin on tukivektorikoneen toteutus separoituville näytejoukoille. Optimimarginaaliluokitin määrää päätöstason $\bold{w}^T\bold{x} + b = 0$ kahden separoituvan näytejoukon välille. Lisäksi vaaditaan että kummankin luokan päätöstasoa lähimmän pisteen ja päätöstason välinen etäisyys on mahdollisimman suuri. Tämä tarkoittaa sitä että kummankin luokan lyhin etäisyys pintaan nähden on sama, koska kokonaisuuden kannalta lyhin etäisyys määrittyy lähempänä olevan luokan perusteella.

Luokat ovat lineaarisesti separoituvia silloin kun kahden eri luokan yksikäsitteinen erottaminen yhdellä tasolla on mahdollista.

Etsitään piirreavaruuden $R^N$ tasoa $(\bold{w},b)$ siten, että näytevektorille $\bold{x}_i$ pätee

$\begin{cases} \bold{w}^T\bold{x}_i + b > 0 \quad , \mbox{kun } \bold{x}_i \mbox{ kuuluu luokkaan a} \\ \bold{w}^T\bold{x}_i + b < 0 \quad , \mbox{kun } \bold{x}_i \mbox{ kuuluu luokkaan b} \end{cases}$.

Sovitaan, että luokan $a$ pisteitä vastaa $y$:n arvo $+1$ ja luokan $b$ $-1$. Muodostetaan yhtälö

$y (\bold{w}^T\bold{x} + b) > 0$,

joka pätee kummankin luokan pisteille. Jos opetustieto koostuu $l$ eri pisteestä, jotka ovat $\bold{x}_i$, kun $i = 1, \dots, l$, ja $y_i$ ovat niiden vastaavat luokat (joko $+1$ tai $-1$), niin vaadimme että luokat erottava taso $(\bold{w},b)$ toteuttaa ehdon

$y_i (\bold{w}^T\bold{x}_i + b) > 0 \quad \forall i = 1, \dots, l$.

Näytepisteen euklidinen etäisyys tasoon $(\bold{w},b)$ on

$\min_{i=1}^l \frac{|\bold{w}^T \bold{x}_i + b|}{\|\bold{w}\|}$.

Päätöstason löytämiseksi on olemassa useita ratkaisutapoja. Kirjallisuudessa usein esiintyvä ratkaisutapa perustuu neliölliseen optimointiin. Toinen tapa on etsiä kummallekin luokalle konveksipeitteet, ja sen jälkeen etsiä konveksipeitteiden välinen lyhin etäisyys ja tätä vastaavat pisteet $p_a$ ja $p_b$ peitteiden pinnalla. Päätöstason normaalivektori $\bold{w}$ on pisteiden $p_a$ ja $p_b$ erotus vektorin suuntainen, ja $b$ on näiden pisteiden keskiarvo.

Ratkaiseminen neliöllisellä optimoinnilla

Optimimarginaaliluokitin määritetään ratkaisemalla seuraava neliöllinen optimointiongelma. Ratkaistaan päätöstaso minimoimalla lauseke $\frac{1}{2}\|\bold{w}\|^2$ tason normaalivektorin $\bold{w}$ suhteen ehdolla

$y_i (\bold{w}^T\bold{x}_i + b) \ge 1 \quad \forall i = 1, \dots, l$.

Muuttuja $b$ ratkaistaan ehdosta.

Päätöstason yksiselitteiseen määrittämiseen tarvitsee tuntea kaksi tasoa lähinnä olevaa pistettä $\bold{x}_n$ ja $\bold{x}_m$. Pisteen $i$ euklidinen etäisyys tasoon $\bold{w}$ on

$\delta_i = \frac{|\bold{w}^T \bold{x}_i + b|}{\|\bold{w}\|}$,

missä $\|\bold{w}\|$ on normalisointitermi.

Taso $(\bold{w},b)$ on yhdensuuntainen tason $(c \bold{w}, c b)$ kanssa, kun $c > 0$, josta seuraa että $c$ voidaan valita siten, että $|c \bold{w}^T \bold{x}_i + c b| = 1$ pisteille $\bold{x}_n$ ja $\bold{x}_m$. Tällöin euklidisten etäisyyksien summaksi saadaan

$\delta_n + \delta_m = \frac{|c \bold{w}^T \bold{x}_n + c b|}{\|c \bold{w}\|} + \frac{|c \bold{w}^T \bold{x}_m + c b|}{\|c \bold{w}\|} = \frac{2}{\|c \bold{w}\|}$.

Tämän seurauksena rajoittamalla reunaehdot annetun tehtävän mukaisesti ja minimoimalla $\|\bold{w}\|$, marginaalitasoilla sijaitsevien pisteiden m ja n etäisyys maksimoituu.

Joustavan marginaalin luokitin

Joustavan marginaalin luokitin (C-SVM) optimimarginaaliluokittimen yleistys ei-separoituville näytejoukoille. Lähes kaikissa käytännön luokittelutehtävissä näytejoukot ovat ei-separoituvia. Ei-separoituvuus huomioidaan määrittämällä jokaiselle väärään luokkaan luokittuvalle näytteelle ns. slack-vakio $\gamma_i$, mikä on näytteen etäisyys päätöspintaan. Vakio $\gamma_i = 0$, kun näyte luokittuu oikein.

Kahteen luokkaan luokitteleva joustavan marginaalin luokitin määritetään ratkaisemalla neliöllinen optimointiongelma

$\min \frac{1}{2}\|\bold{w}\|^2 + C \sum_{i=1}^l \gamma_i$

muuttujien $\bold{w}$, $b$ ja $\gamma_i$ suhteen kun reunaehdot ovat

$y_i (\bold{w}^T\bold{x}_i + b) \ge 1 - \gamma_i$

ja

$\gamma_i \ge 0$

kun $i = 1, \dots, l$. Ongelma voidaan ratkaista ratkaisemalla Lagrangen menetelmällä konstruoitu duaaliongelma

$\min \frac{1}{2} \sum_{i=1}^l \sum_{j=1}^l \alpha_i \alpha_j K(\bold{x_i}, \bold{x_j}) - C \sum_{i=1}^l \bold{\alpha}_i$

missä $C$ on regularisointitermi ja reunaehdot ovat

$\bold{\alpha}_i \ge 0$

ja

$\bold{y}^T \bold{\alpha} = 0$

missä $\bold{\alpha}_i$ ovat Lagrangen kertoimet ja $\bold{y} = [y_1, \dots, y_l]^T$.

Epälineaarinen tukivektorikone

Coverin teoreeman mukaan kaksi ei-separoituvaa näytejoukkoa separoituvat suuremmalla todennäköisyydellä, kun ne kuvataan epälineaarisesti korkeampiulotteiseen avaruuteen. Tukivektorikoneen suorituskykyä voidaan parantaa kuvaamalla piirreavaruus kernelifunktiolla $K(\bold{x}, \bold{y})$, joka implisiittisesti määrittelee kuvauksen.

Mercerin teorian perusteella kernelifunktiolle $K$ on olemassa sisätuloavaruus jos matriisi $M$ on positiivisemidefiniitti ja $K$ on symmetrinen funktio, kun $M_{i j} = K(\bold{x}_i, \bold{x}_j)$ kaikille $i, j = 1, \dots, l$. Luokittelu suoritetaan sisätuloavaruudessa lineaarisesti, mutta päätöspinta kuvautuu piirreavaruuteen epälineaariseksi, kuten ympyräksi tai ellipsiksi radiaalisella kernelifunktiolla. Mercerin teoria mahdollistaa epälineaarisen luokittimen määrittämisen intuitiivisesti.

Mielivaltainen piste $\bold{x}$ luokitellaan luokkaan $+1$, kun

$d = \sum_{i=1}^l \alpha_i K(\bold{x}_i, \bold{x}) > 0$

ja muussa tapauksessa luokkaan $-1$.

Havaitaan, että kun $\alpha_i > 0$, niin $\bold{x}_i$ on tukivektori. Näin ollen luokittelu riippuu ainoastaan tukivektoreista.

Kernelifunktiota

Yleisimpiä kernelifunktiota ovat

• polynominen kernelifunktio $K(\bold{x}_i, \bold{x}) = (\bold{x}^T \bold{x}_i + 1)^p$, kun $p$ on positiivinen kokonaisluku
• radiaalinen kernelifunktio $K(\bold{x}_i, \bold{x}) = \exp(-\frac{1}{2 \sigma^2} \|\bold{x} - \bold{x}_i\|^2)$, kun $\sigma > 0$

Polynominen kernelifunktio erottelee piirteet lineaarisesti lähtöavaruudessa kun taas radiaalinen funktio erottelee piirteet lineaarisesti tietyssä korkeaulotteisessa avaruudessa. Lähtöavaruuden näkökulmasta radiaalinen kernelifunktio erottelee näytteet epälineaarisesti ja se voi näin ollen sen suorituskyky on joissain tilainteissa polynomista luokitinta parempi.

Tukivektorikonetoteutuksia

• SVM light

Katso myös

• Neuroverkot
• Hahmontunnistus

Lähteet

• Simon Haykin, Neural Networks - A comprehensive foundation 2nd edition, Prentice-Hall, 1999