Màquina de vector de suport
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.[1]
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.[2]
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ó
![Exemple d'hiperplà](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b5/Svm_separating_hyperplanes_%28SVG%29.svg/220px-Svm_separating_hyperplanes_%28SVG%29.svg.png)
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.[3]
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
![Hiperplà de màxim marge](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2a/Svm_max_sep_hyperplane_with_margin.png/220px-Svm_max_sep_hyperplane_with_margin.png)
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 es requereix 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 (originalment proposat per en Mark A. Aizerman)[4] a hiperplans de marge màxim.[5] 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.
Si el kernel usat és una RNA de base radial Gaussiana, el corresponent espai de característiques és un espai Hilbert de dimensions infinites. Els classificadors de marge màxim estan ben regularitzats, pel qual les dimensions infinites no espatllen els resultats. Alguns kernels comuns:
- Polinomial (homogeni):
- Polinomial (heterogeni):
- RNA de base radial Gaussiana: per a . A vegades, parametritzat usant
- Tangent hiperbòlica: per a algun (no cada) i .
El kernel està relacionat a la transformació a partir de l'equació . El valor w està també en l'espai transformat, amb . Els productes escalars amb w per classificació poden, un altre cop, ser computats pel kernel trick, per exemple . Però, en general, no existeix un valor w' tal que .
Propietats
Els SVMs pertanyen a una família de classificadors lineals generalitzats i poden ser interpretats com una extensió del perceptró. Poden ser també considerats un cas especial de Regularització de Tíjonov. Una propietat especial és que simultàniament minimitzen l'error de classificació empíric i maximitzen el marge geomètric; de manera que també són coneguts com a classificadors de marge màxim.
Selecció de paràmetres
L'efectivitat de SVM depèn de la selecció del kernel, els seus paràmetres i el paràmetre de marge suau C.
Una elecció típica és un kernel Gaussià, el qual té un sol paràmetre γ. La millor combinació de C i γ és sovint seleccionada per a una cerca a la xarxa amb seqüències de creixement exponencial de C i γ, per exemple,
Típicament, cada combinació d'opcions de paràmetres es comprova fent servir la validació creuada, i els paràmetres amb la millor precisió són els escollits. El model final, que es fa servir per la prova i classificació de les noves dades, és aleshores entrenada en tot el conjunt d'entrenament fent servir els paràmetres seleccionats.[6]
Desventatges
Possibles desavantatges de SVM:
- Probabilitat de pertinença de classes sense calibrar.
- SVM és només directament aplicable a tasques de classe dos. Per tant, s'han d'aplicar els algoritmes que redueixen la tasca de classe-múltiple a diversos problemes binaris.
- Els paràmetres d'un model resolt són difícils d'interpretar.
Extensions
SVM multiclasse
SVM multiclasse pretén assignar etiquetes a instàncies fent servir màquines de vectors de suport, on les etiquetes s'extreuen d'un conjunt finit de diversos elements.
L'enfocament dominant per fer això és reduir el problema multiclasse únic en diversos de classificació binària.[7][8] Mètodes habituals per tal reducció inclouen:
- Construir classificadors binaris que distingeixin entre una de les etiquetes i la resta (“una contra totes”) o entre cada parell de classes (“una contra una”). La classificació de noves instàncies, pel cas d'“una contra totes”, la fa l'estratègia “el guanyador s'ho emporta tot”, en la que el classificador amb la funció de sortida més alta assigna la classe (és important que les funcions de sortida siguin calibrades per produir resultats comparables). Per l'aproximació “una contra una”, la classificació la fa l'estratègia de vots del “màxim de victòries”, en la qual cada classificador assigna la instància a una de les dues classes, aleshores, el vot per la classe assignada s'incrementa en un. Finalment, la classe amb més vots determina la classificació d'instància.
- Graf Acíclic Dirigit SVM (DAGSVM)[9]
- Codis de sortida de correcció d'error.[10]
Crammer i Singer van proposar un mètode SVM multiclasse que transforma el problema de classificació multiclasse en un únic problema d'optimització, en lloc de descompondre'l en múltiples problemes de classificació binària.[11]
Màquines transductives de vectors de suport
Les màquines transductives de vectors de suport s'estenen a SVMs en què poden, a més, tractar parcialment les dades etiquetades en un aprenentatge semisupervisat seguint els principis de la transducció. Aquí, a més del conjunt d'entrenament , l'aprenent també és donat a un conjunt d'exemples d'assaig per a ser classificat. . Formalment, una màquina transductiva de vectors de suport es defineix pel següent problema d'optimització primari:[12]
Minimitzar (a w, b, y*) subjecte a (per qualsevol i qualsevol )
Les màquines transductives de vectors de suport van ser introduïdes per en Vladimir N. Vapnik el 1998.
SVM estructurat
Els SVMs han estat generalitzats a SVMs estructurats, on l'espai de l'etiqueta és estructurat i de possible mida infinita.
Regressió
Una versió de SVM per regressió va ser proposada l'any 1996 per en Vladimir N. Vapnik, en Harris Drucker, en Christopher J.C.Burges, la Linda Kaufman i l'Alexander J.Smola. Aquest mètode s'anomena Regressió de vectors de suport (SVR). El model produït per la classificació de vectors de suport depèn únicament d'un subconjunt de dades d'entrenament, perquè la funció de cost per construir el model no es preocupa pels punts d'entrenament que es troben més enllà del marge. Anàlogament, el model produït per SVR depèn només, també, d'un subconjunt de dades d'entrenament, perquè la funció de cost per construir el model ignora qualsevol dada d'entrenament propera al model de predicció (dins d'un llindar). Una altra versió de SVM coneguda com a màquina de vectors de suport de mínims quadrats (LS-SVM) ha estat proposada per en Suykens i en Vandewalle.
Implementació
Els paràmetres de l'hiperplà de màxim marge es deriven de la resolució de l'optimització. Hi ha diversos algorismes especialitzats per resoldre ràpidament el problema de programació quadràtica que sorgeix de la SVM. Majoritàriament depenen de l'heurística per trencar el problema en segments més petits i manejables. Un mètode comú és l'optimització mínima seqüencial de Platt[13] (SMO algorithm en anglès), que descompon el problema en subproblemes de dues dimensions que es poden resoldre analíticament, eliminant la necessitat d'un algorisme d'optimització numèrica. Un altre enfocament és utilitzar un mètode de punt interior que utilitza iteracions de Newton, com per trobar una solució de les condicions Karush-Kuhn-Tucker dels problemes primal i dual.[14] En lloc de resoldre una seqüència de problemes aquest enfocament directament resol el problema en el seu conjunt, sense necessitat de fer subproblemes.
Aplicacions
SVM es poden utilitzar per resoldre diversos problemes del món real:
- SVM són útils en la categorització de text i hipertext. La seva aplicació pot reduir significativament la necessitat d'instàncies de formació d'etiquetes en la configuració inductiva i transductiva estàndard.
- La classificació d'imatges també es pot fer mitjançant SVM. ELs resultats experimentals mostren que els SVM aconsegueixen significativament major precisió de la recerca d'esquemes tradicionals de refinament de consulta després de tan sols trea o quatre rondes de retroalimentació pertinent (Validació Creuada).
- SVM són útils també en la medicina, per classificar les proteïnes amb un màxim del 90% dels compostos classificats correctament.
- Els caràcters escrits a mà poden ser reconeguts gràcies als SVM.
Referències
- ↑ Corinna Cortes and V. Vapnik, "Support-Vector Networks", Machine Learning, 20, 1995. http://www.springerlink.com/content/k238jx04hm87j80g/[Enllaç no actiu]
- ↑ Press, WH; Teukolsky, SA; Vetterling, WT [et al.].. «Section 16.5. Support Vector Machines». A: Numerical Recipes: The Art of Scientific Computing. 3a ed.. New York: Cambridge University Press, 2007. ISBN 978-0-521-88068-8.
- ↑ 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
- ↑ 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.
- ↑ 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
- ↑ Hsu, Chih-Wei; Chang, Chih-Chung; and Lin, Chih-Jen (2003).A Practical Guide to Support Vector Classification (Technical report). Department of Computer Science and Information Engineering, National Taiwan University.
- ↑ Duan, Kai-Bo; and Keerthi, S. Sathiya (2005). "Which Is the Best Multiclass SVM Method? An Empirical Study". Proceedings of the Sixth International Workshop on Multiple Classifier Systems. Lecture Notes in Computer Science 3541: 278. doi:10.1007/11494683_28. ISBN 978-3-540-26306-7.
- ↑ Hsu, Chih-Wei; and Lin, Chih-Jen (2002). "A Comparison of Methods for Multiclass Support Vector Machines". IEEE Transactions on Neural Networks.
- ↑ Platt, John; Cristianini, N.; and Shawe-Taylor, J. (2000)."Large margin DAGs for multiclass classification". In Solla, Sara A.; Leen, Todd K.; and Müller, Klaus-Robert; eds. Advances in Neural Information Processing Systems. MIT Press. pp. 547–553.
- ↑ Dietterich, Thomas G.; and Bakiri, Ghulum; Bakiri (1995). "Solving Multiclass Learning Problems via Error-Correcting Output Codes" Arxivat 2013-05-09 a Wayback Machine.. Journal of Artificial Intelligence Research, Vol. 2 2: 263–286. arXiv:cs/9501101. Bibcode:1995cs........1101D.
- ↑ Crammer, Koby; and Singer, Yoram (2001)."On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines". J. of Machine Learning Research 2: 265–292.
- ↑ Joachims, Thorsten; "Transductive Inference for Text Classification using Support Vector Machines", Proceedings of the 1999 International Conference on Machine Learning (ICML 1999), pp. 200-209.
- ↑ C. Platt, John. «Using Analytic QP and Sparseness to Speed Training of Support Vector Machines» (en anglès). http://research.microsoft.com/.+[Consulta: 20 novembre 2013].
- ↑ Ferris, Michael C; Munson, Todd S. «Interior-point methods for massive support vector machines» (en anglès) p. 783–804. 3 Society for Industrial and Applied Mathematics, 2002. [Consulta: 20 novembre 2013].
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" Arxivat 2011-10-05 a Wayback Machine.: 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 i Chih-Jen Lin