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 
eskuinera|thumb|150px|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 
eskuinera|thumb|200px|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)

## Erreferentziak 
## Kanpo estekak 
*  SVMlight, SVMrekin lan egiteko softwarea