Tugivektor-masin

**Tugivektor-masinaid** (**TVM**)  kasutatakse juhendatud masinõppes klassifikatsiooni ja regressiooni analüüsiks. Tugivektor vajab treenimiseks eelnevalt märgendatud treenimishulka ning treenitud mudel teeb oma ennustuse märgendamata andmetele olenevalt sellele, kummale poole treenitud hüpertasandit vektor jääb, kusjuures eraldava hüpertasandi kaugus lähimatest treeningandmetest võiks olla võrdne. Eristatakse kõva ja pehme äärega TVM-e: esimesel juhul eeldatakse, et treeningandmeid on võimalik lineaarselt hüpertasandiga eraldada, ja teisel juhul saab TVM-i treenida ka kattuvuse korral.

Tugivektor-masinad leiutasid Vladimir N. Vapnik ja Alexey Chervonenkis 1963. 

Tugivektor-masinaid on modifitseeritud, et need tegeleksid ka märgendamata andmete klasteranalüüsiga  ja tõenäosusjaotuste väljastamisega (Platti skaleerimine). Samuti kasutatakse kernelitrikki olukorras, kus treeningandmeid ei ole võimalik lineaarselt eraldada, kuid leidub funktsioon treeningandmeid eraldava hüpertasandi kirjeldamiseks.

## Lineaarne TVM

Antud on treeningandmed, mis koosnevad treeningolemi  \vec {x_i} ja sellele vastava märgendi y_i paaridest

: (\vec{x}_1, y_1),\, \ldots ,\, (\vec{x}_n, y_n),

kus y_i = \pm 1 vastavalt selle märgendile. Iga \vec x_i on reaalarvuline p-dimensionaalne vektor. TVM treenimise ülesanne on leida maksimaalse eraldatusega hüpertasand, mis eraldab punkte \{\vec x_i | y = 1\} punktidest \{\vec x_i | y = -1\}. Maksimaalse eraldatusega tähendab siin kohal, et hüpertasand on lähimatest vastandmärgenditega treeningolemitest võrdsel ja maksimaalsel kaugusel.

Eraldav hüpertasand koosneb punktidest \vec x_i, mis rahuldavad võrrandit

:\vec w \cdot \vec x_i - b = 0,

kus \vec w on hüpertasandi normaalvektor.

### Kõva äärega TVM
Kui treeningandmed on lineaarselt eraldatavad, me võime valida kaks hüpertasandit, mis mõlemad eraldavad binaarse märgendusega andmed ning on sealjuures suurima võimaliku omavahelise kaugusega. Neid kaht hüpertasandit kirjeldavad kaks võrrandit:
:\vec w \cdot \vec x - b \ge 1 (kõik treeningolemid, mis on kas hüpertasandil või sellest kõrgemal, saavad ennustuseks märgendi 1),
:\vec w \cdot \vec x - b \le -1 (kõik treeningolemid, mis on kas hüpertasandil või sellest madalamal, saavad ennustuseks märgendi -1).

Et kahe hüpertasandi kaugus peab olema maksimaalne ning seda kaugust kirjeldav võrrand on \frac {2}{\lVert \vec w \rVert}, siis me peame minimeerima \lVert \vec w \rVert.

Eelmised kaks võrratust võib ümber kirjutada kujule:
:\forall i \in \{1,\ldots,n\} \ y_i(\vec w \cdot \vec x_i - b) \ge 1,
kus optimeerimisülesandeks jääb \lVert \vec w \rVert minimeerimine eelnevast võrrandist sõltuvalt.

Siinkohal vajab märkimist, et tulemus \vec w sõltub vaid lähimatest punktidest, mida kutsutaksegi *tugivektoriteks*.

### Pehme äärega TVM
Et saaksime kasutada TVM-e juhul, kus treeningandmed ei ole lineaarselt eraldatavad ülekattuvuse tõttu, tutvustame *hinge kaotusfunktsiooni*
:max(0,1-y_i(\vec w \cdot \vec x_i - b)), siis me peame minimeerima \lVert \vec w \rVert. 
Kaotusfunktsiooni väärtus on 0 juhtudel, kus õpitakse ennustama õige märgendiga olemit. Kui aga olem on valel pool hüpertasandit, siis funktsiooni väärtus on proportsionaalne kaugusega sellest tasandist.

Me soovime minimeerida
: \left[\frac 1 n \sum_{i=1}^n \max\left(0, 1 - y_i(\vec{w}\cdot \vec{x}_i - b)\right) \right] + \lambda\lVert \vec{w} \rVert^2,
kus parameeter \lambda määrab ära, kui palju soovitakse karistada vale märgendi ennustamist ning kui tähtis on minimaalne \lVert \vec w \rVert. Juhul kus \lambda on väike, muutub minimeeritava funktsiooni teine liige tühiselt väikseks ning algoritm käitub nagu kõva äärega TVM.

## Viited