Euskarri bektoredun makina

Wikipedia(e)tik
Hona jo: nabigazioa, Bilatu

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[aldatu | aldatu iturburu kodea]

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[aldatu | aldatu iturburu kodea]

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 ci 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[aldatu | aldatu iturburu kodea]

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[1][2]:

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

Sailkapen linealetatik haratago[aldatu | aldatu iturburu kodea]

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)

Ikasketa erdi-gainbegiratua[aldatu | aldatu iturburu kodea]

Klase anitzeko sailkapena[aldatu | aldatu iturburu kodea]

Erreferentziak[aldatu | aldatu iturburu kodea]

  1. Boser, B.E., Guyon, I., Vapnik, V.: A Training Algorithm for Optimal Margin Classifiers. In: 5th Annual Workshop on Computational Learning Theory, pp. 144-152. ACM Press, Pittsburgh, Pennsylvania, USA (1992)
  2. Cortes, C., Vapnik, V.: Support Vector Networks. Machine Learning. 273--297 (1995)

Kanpo loturak[aldatu | aldatu iturburu kodea]