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

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

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

${\displaystyle {\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 ${\displaystyle \mathbf {x} _{i}}$ puntuari dagokion klasea adierazten duen. ${\displaystyle \mathbf {x} _{i}}$ puntu bakoitza p dimentsioko bektore erreala da. Helburua ${\displaystyle c_{i}=1}$ dagokien puntuak eta ${\displaystyle c_{i}=-1}$ dagokienak banatuko dituen marjina maximodun hiperplanoa aurkitzea da. Edozein hiperplanoa honela defini daiteke:

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

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

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

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

${\displaystyle \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 ${\displaystyle {\tfrac {2}{\|\mathbf {w} \|}}}$ dela ondoriozta dezakegu, eta beraz ${\displaystyle \|\mathbf {w} \|}$ minimizatzea da xedea. Ez dugunez marjinan punturik erortzerik nahi, honako baldintza gehi daiteke:

i bakoitzarentzako:

${\displaystyle \mathbf {w} \cdot \mathbf {x} _{i}-b\geq 1\qquad }$, ${\displaystyle c_{i}=1}$ den kasurako, edo

${\displaystyle \mathbf {w} \cdot \mathbf {x} _{i}-b\leq -1\qquad }$, ${\displaystyle c_{i}=-1}$ den kasurako

Hau honela berridatz daiteke:

${\displaystyle c_{i}(\mathbf {w} \cdot \mathbf {x} _{i}-b)\geq 1,\quad \forall i\in \{1,n\}}$

Ebazpena

Bi klaseetako puntuak bananduko dituen hiperplanoaren funtzioa honakoa da beraz:

${\displaystyle 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^[1][2]:

${\displaystyle \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: ${\displaystyle K(\mathbf {x} _{i},\mathbf {x} _{j})=\mathbf {x} _{i}\cdot \mathbf {x} _{j}}$
• Polinomiala: ${\displaystyle 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): ${\displaystyle K(\mathbf {x} _{i},\mathbf {x} _{j})=e^{(-\gamma \cdot ||\mathbf {x} _{i}-\mathbf {x} _{j}||^{2})}}$
• Sigmoidea: ${\displaystyle K(\mathbf {x} _{i},\mathbf {x} _{j})=\tanh(\gamma \cdot \mathbf {x} _{i}^{T}\cdot \mathbf {x} _{j}+r)}$

Erreferentziak

Kanpo estekak

• (Ingelesez) SVMlight, SVMrekin lan egiteko softwarea

• Datuak: Q282453
• Multimedia: Support vector machine / Q282453