Una màquina de vector de suport (SVM o support-vector machines en anglès) és un concepte al món estadístic i de les ciències de la computació sobre un conjunt d'algorismes que són capaços d'analitzar dades i reconèixer patrons mitjançant l'ús de mètodes d'aprenentatge supervisat. Aquests mètodes són utilitzats principalment en problemes de classificació o d'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 se situa en el punt en el qual 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 a l'hiperplà, essent aquesta distància la major possible (marge).

Història Les màquines de vectors suport representen una extensió de models no lineals de l'algorisme desenvolupat per Vladimir Vapnik i Lerner. L'algorisme SVM 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 a AT&T Bell Laboratories per Vladimir Vapnik, tot i que actualment l'any 1995 Corinna Cortes va estendre la teoria aplicant un procés de marge suau.Corinna Cortes and V. Vapnik, "Support-Vector Networks", Machine Learning, 20, 1995. http://www.springerlink.com/content/k238jx04hm87j80g/

Definició formal Una màquina de vectors de suport consisteix en un hiperplà o un conjunt d'aquests en un conjunt espacial 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 ha 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 mapa a un de dimensions majors per ajudar a fer 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 a assegurar 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 hiperplans en un espai dimensional major es defineixen com un conjunt de punts el punt dels quals el seu producte amb un vector en aquell espai és constant (espai prehilbertià). 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ó:

Tingues en compte que si esdevé petit mentre creix més enllà, lluny de , cada terme en la suma mesura el grau de proximitat del punt de prova al punt emmagatzemat original corresponent . D'aquesta manera, la suma de nuclis (kernels,) pot fer-se servir per mesurar la mínima distància de cada punt de prova a la dada assenyalada original, dins un o l'altre dels conjunts per ser discriminats. Nota el fet que el conjunt de punts mapejats a qualsevol hiperplà pot generar un resultat complicat, permetent molta més discriminació complexa entre conjunts que no són convexs en absolut en l'espai original.

Motivació miniatura|alt=Exemple d'hiperplà|H1 no separa bé les dues classes, per tant no sería un bon hiperplà. H2 les separa, però no és el més indicat, ja que la distància dels punts de les classes al pla és molt petit. La millor opció és H3 (vermell) que està més espaiada de les dues classes. Classificar dades és una tasca comuna en l'aprenentatge màquina. Suposem que ens donen alguns punts de dades i que cadascuna pertany a una de dues classes, l'objectiu és decidir per a cada nova dada, a quina de les dues classes estarà. En el cas de les màquines de vectors de suport, un punt de dades és vist com un vector p-dimensional (una llista de p nombres) i volem saber si podem separar aquests punts amb un (p-1) hiperplà tridimensional. Això s'anomena un classificador lineal. Hi ha molts hiperplans que poden classificar les dades. Una elecció raonable és aquell hiperplà que separa millor les dues classes. Per tant, triarem l'hiperplà el qual la distància d'ell fins al punt de dades més proper a cada costat es maximitza. Si existeix aquest hiperplà, es coneix com a hiperplà de màxim marge i el classificador lineal que defineix és conegut com a hiperplà de màxim marge o d'estabilitat òptima.Support vector machines: The linearly separable case, Cambridge Univerity Press, 2008. http://nlp.stanford.edu/IR-book/html/htmledition/support-vector-machines-the-linearly-separable-case-1.html

Marge suau L'any 1995, Corinna Cortes i Vladimir Vapnik suggeriren una nova extensió en la qual s'establia un marge màxim en què els exemples mal etiquetats podien ser corregits. Si no existeix un hiperplà que pugui separar ambdues classes, el mètode del marge suau escollirà un hiperpla que divideixi els exemples amb la claredat més gran 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) i permet ajustar el grau de classificació errònia sobre les dades

La funció objectiu s'incrementa per una funció que penalitza les no-zero , 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:

subjecte a (per cada )

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

amb .

Forma Dual per qualsevol .

El principal avantatge d'una funció de penalització lineal és que les variables desapareixen del problema, la constant C que apareix només és una restricció addicional sobre els multiplicadors de Lagrange. Per a la formulació anterior i el seu gran impacte en la pràctica, Cortés i Vapnik rebre el premi ACM Paris Kanellakis 2008. Les funcions de penalització no lineals s'utilitzen per reduir l'efecte dels valors extrems en el classificador, però si no es va amb compte, és considerablement més difícil trobar una solució global.

Tipus de funcions de nucli (kernel) Lineal Polinòmic RBF Sigmoid (per completar)

SVM Lineal miniatura|alt=Hiperplà de màxim marge|Hiperplà màxim marge i els espais per a un SVM entrenat amb mostres de dues classes. Les mostres al marge s'anomenen els vectors de suport. Donades unes dades d'entrenament, un conjunt de n punts , de la forma:

a on yi pot prendre els valors 1 o −1, indicant la classe a la qual pertany el punt . Cadascun és un vector de p-dimensions real. Volem trobar el hiperplà que divideix els punts a l'espai en dues regions, una amb el conjunt i l'altre amb en el qual el marge del pla al punt més proper del subconjunt sigui màxim. Qualsevol hiperplà pot esser denotat com un conjunt de punts satisfent: on denota el producte escalar i el vector normal a l'hiperplà. El paràmetre determina el desplaçament del mateix hiperplà des de l'origen de coordenades al llarg del vector normal .

Volem escollir i per tal de maximitzar la distància entre els hiperplàns paralels que separen els conjunts de dades. Aquests plànols descriuem com:

i

Si les dades d'entrenament són linealment separables, podem seleccionar dos hiperplans en els quals 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à

Per tant, volem minimitzar . Perquè els punts del conjunt no estiguin al marge entre els dos hiperplans, afegim la restricció per cadascins d'ells: els punts de la primera classe o els punts de la segona classe.

Reescrivim la formulació com:

Agrupem les dades per trobar el nostre problema d'optimització: Minimitzar (en )

subjecte a (per qualsevol )

Forma Primària El problema d'optimització és difícil de resoldre, ja que depèn de , que consisteix en una arrel quadrada. Afortunadament, és possible alterar l'equació substituint per (el factor de 1/2 s'utilitza per conveniència matemàtica) sense canviar la solució. Aquest problema d'optimització s'anomena programació quadràtica.

Més clarament: per qualsevol .

Mitjançant la introducció de multiplicadors de Lagrange , el problema restringit anterior es pot expressar com . D'aquesta manera tots els punts que es poden separar com no m'importa hem d'establir el corresponent a zero.

Actualment aquest problema pot ser resolt mitjançant tècniques de programació quadràtica estàndard i programes. La condició estacionària de Karush-Kuhn-Tucker implica que la solució es pot expressar com una combinació lineal dels vectors d'entrenament .

Llavors només algunes seran més grans que zero. són els vectors de suport, que es troben al marge i satisfan . D'aquesta manera es deriva que els vectors de suport també satisfan

que permet definir el desplaçament b. A la pràctica, és més robust calcular b, sobre tots vectors de suport Nsv:

Forma Dual La regla de classificació en la seva forma doble sense restriccions revela el marge màxim de l'hiperplà i, per tant, la tasca de classificació és només una funció dels vectors de suport, que són el subconjunt de les dades d'entrenament que es troben al marge. Utilitzant que i substituint es pot mostrar que el doble de la SVM es redueix al següent problema d'optimització:

per a i per restricció de la minimització en b . Aquí el nucli està definit per . W es pot calcular gràcies al terme

Hiperplans parcials i imparcials Per raons de simplicitat, de vegades cal que l'hiperplà passi a través de l'origen de coordenades. Tals hiperplans es diuen imparcials, mentre que hiperplans generals no necessàriament passen per l'origen es diuen parcials. Un hiperplà imparcial pot ser executat ficant b = 0 en el problema d'optimització primal.

Classificació No Lineal L'algoritme d'hiperplà òptim original proposat per Vapnik l'any 1963 va ser un classificador lineal. No obstant això, l'any 1992, en Bernhard E. Boser, la Isabelle M. Guyon i en Vladimir N. Vapnik van suggerir una manera de crear classificadors no-lineals aplicant el kernel trick (proposat originàriament per en Mark A. Aizerman)Aizerman, Mark A.; Braverman, Emmanuel M.; and Rozonoer, Lev I. (1964). "Theoretical foundations of the potential function method in pattern recognition learning". Automation and Remote Control 25: 821–837. a hiperplans de marge màxim.Boser, Bernhard E.; Guyon, Isabelle M.; and Vapnik, Vladimir N.; A training algorithm for optimal margin classifiers. In Haussler, David (editor); 5th Annual ACM Workshop on COLT, pages 144–152, Pittsburgh, PA, 1992. ACM Press L'algoritme resultant és similar, excepte que cada producte escalar és reemplaçat per una funció kernel no-lineal. Això permet a l'algoritme adaptar l'hiperplà de marge màxim en un espai de característiques transformat. La transformació pot ser no-lineal i l'espai transformat, d'alta dimensió; encara que el classificador és un hiperplà en l'espai de característiques d'alta dimensió, pot ser no-lineal en l'espai d'entrada original.