Màquina de vector de suport

Una màquina de vector de suport (SVM per les seves sigles en anglès) es un concepte al món estadístic i de les ciències de la computació sobre un conjunt d'algorisme que son capaços de analitzar dades i reconèixer patrons mitjançant l'ús de mètodes d'aprenentatge supervisat. Aquests mètodes son utilitzats principalment en problemes de classificació o de anàlisi de la regressió. Una màquina de vectors agafa com a entrada un set de dades i prediu, per cadascuna d'aquestes entrades a quina de les dues possibles classes pertany. Mitjançant l'entrenament amb dades d'entrada prèviament classificades, s'estableix un model que separa les dues classes entrants. Aquest model N-dimensional estableix una frontera entre les dues tipologies establertes, aquesta es situa en el punt en el que la diferència entre classes sigui el més gran possible i el marge d'error sigui zero (dataset separable) o mínim (dataset no separable). S'anomenen vectors de suport als punts que conformen les dues línies paral·leles al hiperplà, essent aquesta distància la major possible (marge).

Història

Màquines de vectors suport representen una extensió de models no lineals de l'algorisme desenvolupat per Vladimir Vapnik i Lerner.1 El SVM algorisme es basa en la teoria de l'aprenentatge estadístic i les revisions de Chervonenkis-Vapnik Comentaris en Química Computacional, Volum 23 editat per B. Kenny Lipkowitz i Thomas R. Cundari. La teoria de l'aprenentatge estadístic, que descriu propietats de les màquines d'aprenentatge que els permetin fer prediccions fiables, va ser examinat per Vapnik. La formulació actual, l'algorisme de SVM va ser desenvolupat en AT & T Bell Laboratories per Vladimir Vapnik, tot i que actualment a l'any 1995 Corinna Cortes va extendre la teoría aplicant un procés de marge suau.

Definició formal

Una màquina de suport de vectors consisteix en un hiperplà o un conjunt d'aquests en un conjunt espaial N-dimensional o amb infinites dimensions. Intuïtivament aquest hiperplà estarà situat al punt on la distància als punts d'entrenament més propers d'ambdues classes sigui major. Tot i que en un principi el problema hagi estat declarat en un espai de dimensions finites, és possible que el conjunt de dades en aquest espai no sigui separable linealment. És per aquesta raó que l'espai es mapeja a un de dimensions majors per ajudar a que sigui separable en el nou espai. Per mantenir una càrrega computacional raonable els esquemes de mapeig de les màquines SVM són dissenyats per asegurar que els productes vectorials es puguin calcular en els termes de l'espai original, definint-los en termes d'una funció anomenada funció de kernel (nucli del SVM) adaptada per a cada tipus de problema.

Els hiperplànols en un espai dimensional major es defineixen com un conjunt de punts el qual es seu Espai prehilbertià amb un vector de l'espai sigui constant. Els vectors que defineixen l'hiperplà poden ser escollits perquè siguin combinacions lineals de les imatges dels vectors característics del dataset d'entrada. Aquest hiperplà es defineix amb la següent relació: $\sum_i{ \alpha_i K(x_i,x)} = constant$

Marge Suau

A l'any 1995, Corinna Cortes i Vladimir Vapnik sugeriren una nova extensió en la qual s'establia un marge màxim en que els exemples mal etiquetats podien ser corregits. Si no existeix un hiperplà que pugui separar ambdues clases, el mètode del marge suau escollirà un hiperplà que divideixi els exemples amb la major claretat possible, intentant maximitzar la distància als punts més clarament separats. Aquest mètode introdueix variables que permeten controlar el sistema (variables d'ajustament) $\xi_i$ i permet ajustar el grau de classificació errònia sobre les dades $x_i$ $y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1 - \xi_i \quad 1 \le i \le n. \quad\quad(2)$

La funció objectiu s'incrementa per una funció que penalitza les no-zero $\xi_i$, l'optimització es converteix en un compromís entre un marge gran i un error de classificació petit. Si la funció de penalització és lineal, el problema d'optimització és:

$\min_{\mathbf{w},\mathbf{\xi}, b } \left\{\frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^n \xi_i \right\}$

subjecte a (per cada $i=1,\dots n$)

$y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1 - \xi_i, ~~~~\xi_i \ge 0 .$

Aquesta restricció en (2), juntament amb l'objectiu de minimitzar el $\|\mathbf{w}\|$ es pot resoldre utilitzant multiplicadors de Lagrange, com es va indicar anteriorment. Quedant el següent problema:

$\min_{\mathbf{w},\mathbf{\xi}, b } \max_{\boldsymbol{\alpha},\boldsymbol{\beta} } \left \{ \frac{1}{2}\|\mathbf{w}\|^2 +C \sum_{i=1}^n \xi_i - \sum_{i=1}^{n}{\alpha_i[y_i(\mathbf{w}\cdot \mathbf{x_i} - b) -1 + \xi_i]} - \sum_{i=1}^{n} \beta_i \xi_i \right \}$

amb $\alpha_i, \beta_i \ge 0$.

Tipus de funcions de nucli (kernel)

Lineal	$K_{lin}(x_{i}) = a \cdot x_{k}$
Polinòmic	$K_{poly}(x_1,x_2)=(sx_1^T x_2 + r)^d$
RBF	$K_{RBF}=exp(-\gamma |x_i - x_j| ^2 )$
Sigmoid	(per completar)

SVM Lineal

Donades unes dades d'entrenament, un conjunt de n punts $\mathcal{D}$, de la forma:

$\mathcal{D} = \left\{ (\mathbf{x}_i, y_i)\mid\mathbf{x}_i \in \mathbb{R}^p,\, y_i \in \{-1,1\}\right\}_{i=1}^n$

a on y_i pot prendre els valors 1 o −1, indicant la classe a la que el punt $\mathbf{x}_i$ pertany. Cadascún $\mathbf{x}_i$ es un vector de p-dimensions real. Volem trobar el hiperplà que divideix els punts a l'espai en dues regions, una amb el conjunt $y_i=1$ i l'altre amb $y_i=-1$ en el qual el marge del plà al punt mes proper del sub-conjunt sigui màxim. Qualsevol hiperplà pot esser denotat com un conjunt de punts $\mathbf{x}$ satisfent: $\mathbf{w}\cdot\mathbf{x} - b=0,\,$ on $\cdot$ denota el producte escalar i ${\mathbf{w}}$ el vector normal a l'hiperplà. El paràmetre $\tfrac{b}{\|\mathbf{w}\|}$ determina el desplaçament del propi hiperplà des de l'origen de coordenades al llarg del vector normal ${\mathbf{w}}$.

Volem escollir ${\mathbf{w}}$ i $b$ per tal de maximitzar la distància entre els hiperplàns paralels que separen els conjunts de dades. Aquests plànols descriuem com:

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

i

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

Si les dades d'entrenament son linealment separables, podem sel·leccionar dos hiperplans en els que en el marge entre ells no existeixi cap punt del conjunt d'entrenament, i intentar maximitzar la seva distància. Geomètricament, la distància entre aquests dos hiperplans serà $\tfrac{2}{\|\mathbf{w}\|}$ Per tant, volem minimitzar $\|\mathbf{w}\|$. Per tal de que els punts del conjunt no estiguin al marge entre els dos hiperplans, afegim la restricció $i$ per cadascins d'ells:

$\mathbf{w}\cdot\mathbf{x}_i - b \ge 1\qquad\text{ per }\mathbf{x}_i$ els punts de la primera classe

ó

$\mathbf{w}\cdot\mathbf{x}_i - b \le -1\qquad\text{ per }\mathbf{x}_i$ els punts de la segona classe.

Reescrivim la formulació com:

$y_i(\mathbf{w}\cdot\mathbf{x}_i - b) \ge 1, \quad \text{ per a tots } 1 \le i \le n.\qquad\qquad(1)$

Agrupem les dades per trobar el nostre problema d'optimització: Minimitzar (en ${\mathbf{w},b}$)

$\|\mathbf{w}\|$

subjecte a (per qualsevol $i = 1, \dots, n$)

$y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1. \,$

Enllaços externs

• www.kernel-machines.org: Informació general i col·lecció de recerca sobre SVM
• www.support-vector-machines.org: (Literatura, Revisions, Software i Enllaços sobre màquines SVM - Lloc orientat a l'aprenentatge academic)
• "Vídeo": Animació de SVM amb nucli polinòmic
• "Document PDF":Un tutorial per iniciar-se a les màquines SVM per Tristan Fletcher.
• "LIBSVM": "Llibreria per a la implementació de sistemes SVM, escrita en C i fortament acceptada per la comunitat" - Escrita per Chih-Chung Chang and Chih-Jen Lin