Tukivektorikone

Wikipedia

Tukivektorikone (engl. Support Vector Machine) on 1990-luvulla keksitty neuroverkkotyyppi ^[1], joka lähestyy aihepiiriä tilastollisen riskin minimoimisen näkökulmasta. Tukivektorikoneen mahdollinen hyöty on parempi yleistämiskyky verrattuna perinteisiin neuroverkkoihin. Yleistämiskyky tarkoittaa kykyä arvioida uutta tietoa, jota koneelle ei ole opetuksen aikana näytetty. Tukivektorikoneisiin perustuvat luokittelumenetelmät pystyvät käsittelemään korkeaulotteisia avaruuksia hyvin, koska luokittelija pystyy karsimaan epäoleellisen opetustiedon. Epäoleellisuus määritellään siten, että piste on sitä epäoleellisempi mitä kauempana se on tietyn luokan reuna-alueesta. Tukivektorikonetta voi käyttää sekä piirteiden luokitteluun että funktioiden arvioimiseen.

[muokkaa] Tukivektoriluokittelija

Tukivektoriluokittelijan perusajatus on jakaa piirreavaruus kahteen tai useampaan luokkaan (avaruuden osajoukkoon). Tukivektorikoneen pitää opetuksen jälkeen osata arvioida luokka mille tahansa avaruuden pisteelle. Luokittelija suunnitellaan tietyn opetusaineiston perusteella, ja siksi sen hyvyys on riippuvainen opetusaineiston hyvyydestä. Samaan luokkaan kuuluvien pisteiden ei tarvitse muodostaa yhtenäisiä alueita, vaan ne voivat olla ripoteltuna mielivaltaisesti ympäri avaruutta. Suunnittelumenetelmä etsii opetusaineistosta ne vektorit, jotka määrittävät eri luokkien reuna-alueet. Kyseisiä vektoreita kutsutaan tukivektoreiksi. Opetuksen jälkeen sama tulos voitaisiin saavuttaa pelkästään tukivektoreiden perusteella, joten menetelmä osaa karsia epäoleellisen opetustiedon pois.

[muokkaa] Joustava marginaaliluokittelija

Joustava marginaaliluokittelija (C-SVM) on samankaltainen luokittelija kuin optimimarginaaliluokittelija, mutta sallii joidenkin pisteiden luokittelun menevän väärin. Tämä on käytännön kannalta haluttava asia, koska täydellinen luokittelu on usein mahdotonta ja oikein luokittelu suurella todennäköisyydellä on riittävää.

Joustava marginaaliluokittelija $R n$ -avaruudessa voidaan määrittää ratkaisemalla neliöllisen optimoinnin ongelma joka on muotoa

Minimoi

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

muuttujien $\bold{w}$ , $b$ ja $γ i$ suhteen kun reunaehdot ratkaisulle ovat

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

kaikilla arvoilla $i = 1, \dots, l$ . Tämä ratkaisu on kuitenkin erikoistapaus euklidiselle $R n$ -avaruudelle, ja seuraava tehtävänasettelu perustuu ratkaisuun implisiittisessä piirreavaruudesta.

Monesti on piirrevaruus tuntematon, mutta siitä tunnetaan ydinfunktio $K(\bold{x}, \bold{y})$ joka kuvaa vektorit $\bold{x}$ ja $\bold{y}$ sitä vastaavaan implisiittiseen sisätuloavaruuteen ja laskee siellä sisätulon näille kahdelle vektorille. Kuvausfunktiota lähtöavaruudesta piirreavaruuteen ei kuitenkaan välttämättä tunneta, ja siksi kyseistä piirreavaruutta kutsutaan implisiittiseksi. Mercerin teorian perusteella voidaan tietää, että tietylle ydinfunktiolle $K$ on olemassa tarkoitukseen sopiva sisätuloavaruus mikäli 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 implisiittisessä piirreavaruudessa lineaarisesti, mutta lähtöavaruuden näkökulmasta on kyseessä epälineaarinen luokittelu. Käytännön kannalta Mercerin teoria mahdollistaa epälineaaristen luokittelijoiden rakentamisen intuitiivisella tavalla.

Tehtävän asettelussa minimoidaan kohdefunktio

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

vektorin $\bold{\alpha}$ suhteen, kun reunaehdot ovat

$0 \le \bold{\alpha} \le C \bold{1}$ $\bold{y}^T \bold{\alpha} = 0$

missä $\bold{1} = [1, \dots, 1]^T \in R^l$ ja $\bold{y} = [y_1, \dots, y_l]^T$ .

Tämän jälkeen voidaan mielivaltaisen pisteen $\bold{x}$ luokittelu implisiittisessä piirreavaruudessa laskea epäsuorasti vektorin $\bold{\alpha}$ ja ydinfunktion $K$ avulla kaavalla

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

Kun $d > 0$ , piste $\bold{x}$ kuuluu luokkaan $+ 1$ ja muussa tapauksessa toiseen luokkaan $- 1$ . Oleellista on erityisesti se, että mikäli $α i > 0$ on $\bold{x_i}$ tukivektori. Kaikki muut kuin tukivektorit voidaan jättää huomioimatta luokittelussa, koska niillä ei ole vaikutusta $d$ :n arvoon.

[muokkaa] Ydinfunktiota

Yleisiä perusvalintoja ydinfunktioksi $K$ ovat esimerkiksi polynomiaalinen ydinfunktio $(\bold{x}^T \bold{y} + 1)^p$ , kun $p$ on positiivinen kokonaisluku, ja RBF-ydinfunktio $\exp(-\frac{1}{2 \sigma^2} \|\bold{x} - \bold{y}\|^2)$ , kun $σ > 0$ . Polynomiaalisesta ydinfunktiosta erottelee piirteet lineaarisesti lähtöavaruudessa kun taas RBF-ydinfunktio erottelee piirteet lineaarisesti tietyssä ääretönulotteisessa vektoriavaruudessa. Lähtöavaruuden näkökulmasta RBF-ydinfunktio erottelee piirteitä epälineaarisesti ja se on siten kykeneväinen erottelemaan tiettyjä luokkia mitä polynomiaalisella luokittelijalla ei pystyisi erottelemaan ollenkaan.