Euskarri bektoredun makina

Euskarri bektoredun makinak (ingelesez, Support Vector Machine, SVM) sailkapenerako eta erregresiorako erabiltzen den algoritmo sorta da. Jatorriz ikasketa gainbegiratuan, sailkapen bitar eta linealerako erabiltzen den arren, beste aukera asko eskaintzen dutela frogatu izan da.

Oinarriak

H3k ez ditu bi klaseak banatzen; beste biek bai, baina H2k du marjina handiena

Ikasketa automatikoan sarritan beharrezkoa izaten da sailkapen teknikak erabiltzea. Horretarako, bektore-espazio ereduan oinarritzen dira euskarri bektoredun makinak. Sarrera moduan, n dimentsioko eredu horretan adieraz daitezkeen hainbat datu jasotzen dira, kategoria bietako batean sailkatuta daudenak. Teknika honek bilatzen duen helburua n dimentsioko eredu horretan dauden puntu hauek bananduko dituen n - 1 dimentsioko hiperplanoa bilatzea da. Honi sailkatzaile lineal deritzo. Dena dela, datuak bi eremutan banatzeko hiperplano hau ez da bakarra, aukera asko izan baititzake; euskarri bektoredun makinek, ordea, gertueneko puntuetarako distantzia (zeina marjina deitzen den) handiena duena aukeratzen dute emaitza bezala.

Azalpen formala

Marjina maximodun hiperplanoa

Eman dezagun entrenamendurako hainbat datu ditugula, tankera honetako puntu sorta:

$\mathcal{D} = \{ (\mathbf{x}_i, c_i)|\mathbf{x}_i \in \mathbb{R}^p, c_i \in \{-1,1\}\}_{i=1}^n$

non c_i horren balioa 1 edo −1 izan daitekeen, eta $\mathbf{x}_i$ puntuari dagokion klasea adierazten duen. $\mathbf{x}_i$ puntu bakoitza p dimentsioko bektore erreala da. Helburua $c_i = 1$ dagokien puntuak eta $c_i = -1$ dagokienak banatuko dituen marjina maximodun hiperplanoa aurkitzea da. Edozein hiperplanoa honela defini daiteke:

$\mathbf{w}\cdot\mathbf{x} - b=0.$

$\mathbf{w}$ bektore normal bat da, hiperplanoarekiko perpendikularra. $\tfrac{b}{\|\mathbf{w}\|}$ parametroak hiperplanoak jatorriarekiko duen desplazamendua adierazten du, $\mathbf{w}$ bektorearen norabideari jarraiki.

Hiperplanoa eta gertueneko puntu(ar)en arteko marjina maximo egingo dituen $\mathbf{w}$ eta $\mathbf{b}$ balioak aurkitzea da helburua. Marjina definitzen duten hiperplanoa honela defini daitezke:

$\mathbf{w}\cdot\mathbf{x} - b=1$ eta

$\mathbf{w}\cdot\mathbf{x} - b=-1.$

Kontuan izan datuak linealki bana badaitezke, marjinak definitzen dituzten bi hiperplano artean ez dela punturik egongo. Geometria baliatuz, bi hiperplano hauen arteko distantzia $\tfrac{2}{\|\mathbf{w}\|}$ dela ondoriozta dezakegu, eta beraz $\|\mathbf{w}\|$ minimizatzea da xedea. Ez dugunez marjinan punturik erortzerik nahi, honako baldintza gehi daiteke:

i bakoitzarentzako:

$\mathbf{w}\cdot\mathbf{x}_i - b \ge 1\qquad$, $c_i = 1$ den kasurako, edo

$\mathbf{w}\cdot\mathbf{x}_i - b \le -1\qquad$, $c_i = -1$ den kasurako

Hau honela berridatz daiteke:

$c_i(\mathbf{w}\cdot\mathbf{x}_i - b) \ge 1, \quad \forall i \in \{1, n\}$

Ebazpena

Bi klaseetako puntuak bananduko dituen hiperplanoaren funtzioa honakoa da beraz:

$f(x) = \mathbf{w} \cdot \mathbf{x} + \mathbf{b}$

Funtzio honen bitartez marjina maximoa duena ebaztea oso zaila da, konputazio koste handia suposatzen baitu. Hori konpontzeko, honako funtzio hau minimizatzearen bitartez lortzen da baliokidea:

$\min \frac{1}{2} ||\mathbf{w}||^2 + C \sum_{i = 1}^l \xi_i^d$

Sailkapen linealetatik haratago

Vladimir Vapnikek 1963an proposatutako algoritmoak sailkatzaile lineala definitzen du, eta ondorioz, ezin ditu arazo ez-linealak ebatzi. 1992an, ordea, Bernhard Boser, Isabelle Guyon eta Vapnik berak espazioaren egokitzapena egiten duen kernel funtzio baten erabilpena proposatu zuten. Orduz geroztik, kernel funtzioak erabiltzen dira arazo ez-linealak ebazteko. Kernel funtzio erabilienak honako hauek dira:

• Lineala: $K(\mathbf{x}_{i}, \mathbf{x}_{j}) = \mathbf{x}_{i} \cdot \mathbf{x}_{j}$
• Polinomiala: $K(\mathbf{x}_{i}, \mathbf{x}_{j}) = (\gamma \cdot \mathbf{x}_{i}^{T} \cdot \mathbf{x}_{j} + r)^{d}, \gamma > 0$
• Radial Basis Function (RBF): $K(\mathbf{x}_{i}, \mathbf{x}_{j}) = e^{(-\gamma \cdot ||\mathbf{x}_{i} - \mathbf{x}_{j}||^{2})}$
• Sigmoidea: $K(\mathbf{x}_{i}, \mathbf{x}_{j}) = \tanh (\gamma \cdot \mathbf{x}_{i}^{T} \cdot \mathbf{x}_{j} + r)$

Kanpo loturak

• (Ingelesez) SVMlight, SVMrekin lan egiteko softwarea