Tukivektorikone

Tukivektorikone () 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.
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 formula_1 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 formula_2 tasoa formula_3 siten, että näytevektorille formula_4 pätee
formula_5.
Sovitaan, että luokan formula_6 pisteitä vastaa formula_7:n arvo formula_8 ja luokan formula_9 formula_10. Muodostetaan yhtälö
formula_11,
joka pätee kummankin luokan pisteille. Jos opetustieto koostuu formula_12 eri pisteestä, jotka ovat formula_4, kun formula_14, ja formula_15 ovat niiden vastaavat luokat (joko formula_8 tai formula_10), niin vaadimme että luokat erottava taso formula_3
toteuttaa ehdon
formula_19.
Näytepisteen euklidinen etäisyys tasoon formula_3 on
formula_21.
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 formula_22 ja formula_23 peitteiden pinnalla. Päätöstason normaalivektori formula_24 on pisteiden formula_22 ja formula_23 erotus vektorin suuntainen, ja formula_9 on näiden pisteiden keskiarvo.
Ratkaiseminen neliöllisellä optimoinnilla.
Optimimarginaaliluokitin määritetään ratkaisemalla seuraava neliöllinen optimointiongelma. Ratkaistaan päätöstaso minimoimalla lauseke formula_28
tason normaalivektorin formula_24 suhteen ehdolla
formula_30.
Muuttuja formula_9 ratkaistaan ehdosta.
Päätöstason yksiselitteiseen määrittämiseen tarvitsee tuntea kaksi tasoa lähinnä olevaa pistettä formula_32 ja formula_33. Pisteen formula_34 euklidinen etäisyys tasoon formula_24 on
formula_36,
missä formula_37 on normalisointitermi.
Taso formula_3 on yhdensuuntainen tason formula_39 kanssa, kun formula_40, josta seuraa että formula_41 voidaan valita siten, että formula_42 pisteille formula_32 ja formula_33. Tällöin euklidisten etäisyyksien summaksi saadaan 
formula_45.
Tämän seurauksena rajoittamalla reunaehdot annetun tehtävän mukaisesti ja minimoimalla formula_37, 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 formula_47, mikä on näytteen etäisyys päätöspintaan. Vakio formula_48, kun näyte luokittuu oikein.
Kahteen luokkaan luokitteleva joustavan marginaalin luokitin määritetään ratkaisemalla neliöllinen optimointiongelma
formula_49
muuttujien formula_24, formula_9 ja formula_47 suhteen 
kun reunaehdot ovat
 formula_53
ja
 formula_54
kun formula_55. Ongelma voidaan ratkaista ratkaisemalla Lagrangen menetelmällä konstruoitu duaaliongelma
 formula_56
missä formula_57 on regularisointitermi ja reunaehdot ovat
 formula_58
ja
 formula_59
missä formula_60 ovat Lagrangen kertoimet ja formula_61.
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 formula_62, joka implisiittisesti määrittelee kuvauksen.
"Mercerin teorian" perusteella kernelifunktiolle formula_63 on olemassa sisätuloavaruus jos matriisi formula_64 on positiivisemidefiniitti ja formula_63 on symmetrinen funktio, kun formula_66 kaikille formula_67. 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 formula_68 luokitellaan luokkaan formula_8, kun
formula_70
ja muussa tapauksessa luokkaan formula_10.
Havaitaan, että kun formula_72, niin formula_4 on tukivektori. Näin ollen luokittelu riippuu ainoastaan tukivektoreista.
Kernelifunktiota.
Yleisimpiä kernelifunktiota ovat
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.