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.

Tugivektor-masin kahedimensionaalsetel märgendatud andmetel

Lineaarne TVM

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

$({\overrightarrow{x}}_1,y_1),\dots ,({\overrightarrow{x}}_n,y_n)$,

kus $y_i=\pm 1$ vastavalt selle märgendile. Iga ${\overrightarrow{x}}_i$ on reaalarvuline $p$-dimensionaalne vektor. TVM treenimise ülesanne on leida maksimaalse eraldatusega hüpertasand, mis eraldab punkte $\{{\overrightarrow{x}}_i|y=1\}$ punktidest $\{{\overrightarrow{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 ${\overrightarrow{x}}_i$, mis rahuldavad võrrandit

$\overrightarrow{w}\cdot {\overrightarrow{x}}_i-b=0$,

kus $\overrightarrow{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:

$\overrightarrow{w}\cdot \overrightarrow{x}-b\ge 1$ (kõik treeningolemid, mis on kas hüpertasandil või sellest kõrgemal, saavad ennustuseks märgendi 1),

$\overrightarrow{w}\cdot \overrightarrow{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}{\Vert \overrightarrow{w}\Vert }$, siis me peame minimeerima $\Vert \overrightarrow{w}\Vert$.

Eelmised kaks võrratust võib ümber kirjutada kujule:

$\mathrm{\forall }i\in \{1,\dots ,n\}{y}_i(\overrightarrow{w}\cdot {\overrightarrow{x}}_i-b)\ge 1$,

kus optimeerimisülesandeks jääb $\Vert \overrightarrow{w}\Vert$ minimeerimine eelnevast võrrandist sõltuvalt.

Siinkohal vajab märkimist, et tulemus $\overrightarrow{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(\overrightarrow{w}\cdot {\overrightarrow{x}}_i-b))$, siis me peame minimeerima $\Vert \overrightarrow{w}\Vert$.

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

$[\frac{1}{n}\sum _{i=1}^n\max (0,1-y_i(\overrightarrow{w}\cdot {\overrightarrow{x}}_i-b))]+\lambda \Vert \overrightarrow{w}{\Vert }^2$,

kus parameeter $\lambda$ määrab ära, kui palju soovitakse karistada vale märgendi ennustamist ning kui tähtis on minimaalne $\Vert \overrightarrow{w}\Vert$. Juhul kus $\lambda$ on väike, muutub minimeeritava funktsiooni teine liige tühiselt väikseks ning algoritm käitub nagu kõva äärega TVM.