Subclasă | Algoritm de clasificare ( d ) |
---|---|
Acronim | (în) SVM |
Inventatori | Vladimir Vapnik , Alexeï Tchervonenkis |
Descris de | Automatizare și telecomandă ( în ) |
Vectorul suport mașini sau separatori marja largă (engleză mașini vector suport , SVM) sunt un set de tehnici de coordonare supravegheat de învățare pentru a rezolva problemele de discriminare și de regresie . SVM-urile sunt o generalizare a clasificatorilor liniari .
Separatorii de marjă largă au fost dezvoltați în anii 1990 din considerațiile teoretice ale lui Vladimir Vapnik privind dezvoltarea unei teorii statistice a învățării: teoria Vapnik-Chervonenkis . Au adoptat rapid capacitatea lor de a lucra cu date de dimensiuni mari , numărul scăzut de hiperparametru , garanțiile lor teoretice și rezultate bune în practică.
SVM a fost aplicat în numeroase domenii ( bioinformatică , recuperare de informații , viziune computerizată , finanțe ...). Conform datelor, performanța mașinilor vectoriale de sprijin este de aceeași ordine, sau chiar mai bună, decât cea a unei rețele neuronale sau a unui model de amestec gaussian .
Separatorii de marjă mare se bazează pe două idei cheie: noțiunea de marjă maximă și noțiunea de funcție de nucleu. Aceste două concepte existau de câțiva ani înainte de a fi puse împreună pentru a construi SVM-uri.
Ideea hiperplanelor cu marjă maximă a fost explorată încă din 1963 de Vladimir Vapnik și A. Lerner, iar în 1973 de Richard Duda și Peter Hart în cartea lor Clasificare tipar . Bazele teoretice ale SVM-urilor au fost explorate de Vapnik și colegii săi în anii 1970 odată cu dezvoltarea teoriei Vapnik-Chervonenkis și a teoriei învățării Valiant și PAC .
Nici ideea funcțiilor kernelului nu este nouă: teorema lui Mercer datează din 1909 , iar utilitatea funcțiilor kernelului în contextul învățării automate a fost arătată încă din 1964 de Aizermann, Bravermann și Rozoener.
Cu toate acestea, abia în 1992 aceste idei au fost pe deplin înțelese și reunite de Boser, Guyon și Vapnik într-un articol, care este articolul fondator al separatorilor de marje largi. Ideea variabilelor de primăvară, care a făcut posibilă rezolvarea unor limitări practice importante, nu a fost introdusă decât în 1995 . De la această dată, care corespunde publicării cărții lui Vapnik, SVM-urile câștigă popularitate și sunt utilizate în multe aplicații.
Un brevet SUA asupra SVM-urilor a fost depus în 1997 de către inventatorii originali.
Separatoarele cu marjă largă sunt clasificatori care se bazează pe două idei cheie, care permit rezolvarea problemelor de discriminare neliniară și reformularea problemei de clasificare ca o problemă de optimizare pătratică .
Prima idee cheie este conceptul de marjă maximă . Marja este distanța dintre limita de separare și cele mai apropiate probe . Acestea se numesc vectori de suport . În SVM, granița de separare este aleasă ca cea care maximizează marja. Această alegere este justificată de teoria Vapnik-Chervonenkis (sau teoria statistică a învățării), care arată că frontiera de separare a marjei maxime are cea mai mică capacitate . Problema este de a găsi această margine de divizare optimă, dintr-un set de antrenament. Acest lucru se face prin formularea problemei ca o problemă de optimizare pătratică, pentru care există algoritmi cunoscuți.
Pentru a putea face față cazurilor în care datele nu sunt separabile liniar, a doua idee cheie a SVM-urilor este transformarea spațiului de reprezentare a datelor de intrare într-un spațiu de dimensiune mai mare (posibil de dimensiune infinită), este probabil să existe o separare liniară. Acest lucru se realizează grație unei funcții de nucleu , care trebuie să respecte condițiile teoremei lui Mercer și care are avantajul că nu necesită cunoașterea explicită a transformării pentru a fi aplicată pentru schimbarea spațiului. Funcțiile kernel fac posibilă transformarea unui produs dot într-un spațiu mare, care este scump, într-o simplă evaluare unică a unei funcții. Această tehnică este cunoscută sub numele de trucul kernelului .
SVM-urile pot fi utilizate pentru a rezolva probleme de discriminare, adică a decide la ce clasă aparține un eșantion sau regresie , adică a prezice valoarea numerică a unei variabile. Rezolvarea acestor două probleme implică construirea unei funcții care să potrivească un vector de intrare cu o ieșire :
Ne limităm pentru moment la o problemă de discriminare cu două clase (discriminare binară), adică vectorul de intrare fiind într-un spațiu X prevăzut cu un produs scalar . Putem lua de exemplu .
Cazul simplu este cazul unei funcții discriminante liniare, obținută prin combinația liniară a vectorului de intrare , cu un vector de greutate :
Se decide apoi că este clasa 1 dacă și clasa -1 în caz contrar. Este un clasificator liniar .
Limita de decizie este un hiperplan , numit hiperplan separator , sau separator . Scopul unui algoritm de învățare supravegheat este de a învăța funcția h (x) printr-un set de instruire:
×în cazul în care sunt etichetele, este dimensiunea setului de formare, dimensiunea vectorilor de intrare. Dacă problema este separabilă liniar, atunci trebuie să aveți:
Imaginați-vă un plan (spațiu bidimensional) în care sunt distribuite două grupuri de puncte. Aceste puncte sunt asociate cu un grup: punctele (+) pentru y > x și punctele (-) pentru y < x . Putem găsi un separator liniar evident în acest exemplu, linia de ecuație y = x . Se spune că problema este separabilă liniar .
Pentru probleme mai complicate, de obicei nu există un separator liniar. Imaginați-vă, de exemplu, un plan în care punctele (-) sunt grupate în interiorul unui cerc, cu punctele (+) în jur: niciun separator liniar nu poate separa corect grupurile: problema nu este separabilă liniar . Nu există hiperplan de separare.
Se plasează de acum înainte în cazul în care problema este separabilă liniar. Chiar și în acest caz simplu, alegerea hiperplanului separator nu este evidentă. De fapt, există un număr infinit de hiperplanuri separatoare, ale căror performanțe de învățare sunt identice ( riscul empiric este același), dar ale căror performanțe de generalizare pot fi foarte diferite. Pentru a rezolva această problemă, s-a demonstrat că există un singur hiperplan optim, definit ca hiperplanul care maximizează marja dintre eșantioane și hiperplanul de separare.
Există motive teoretice pentru această alegere. Vapnik a arătat că capacitatea claselor de separare a hiperplanului scade odată cu creșterea marjei acestora.
Marja este distanța dintre hiperplan și cele mai apropiate mostre. Acestea se numesc vectori de suport . Hiperplanul care maximizează marja este dat de:
Prin urmare, este vorba de a găsi w și w 0 care îndeplinesc aceste condiții, pentru a determina ecuația hiperplanului de separare:
Marja este cea mai mică distanță dintre probele de antrenament și hiperplanul de separare care îndeplinește condiția de separabilitate (adică așa cum s-a explicat anterior). Distanța unui eșantion x k de hiperplan este dată de proiecția sa ortogonală pe vectorul de greutate:
.Hiperplanul de separare (w, w 0 ) al marjei maxime este, prin urmare, dat de:
Pentru a facilita optimizarea , alegem să normalizăm w și w 0 , astfel încât eșantioanele de la margine ( pentru vectorii de susținere de pe frontiera pozitivă și pentru cei situați pe frontiera opusă) să satisfacă:
Prin urmare, pentru toate probele,
Această normalizare este uneori numită formă canonică a hiperplanului sau hiperplan canonic .
Cu această scalare, marja merită acum , deci este o chestiune de maximizare . Așa-numita formulare primară a SVM-urilor este apoi exprimată în următoarea formă:
Acest lucru poate fi rezolvat prin metoda clasică a multiplicatorilor Lagrange , unde Lagrangianul este dat de:
Lagrangianul trebuie minimizat față de w și w 0 și maximizat față de α.
Formulare dualăPrin anularea derivatelor parțiale ale Lagrangianului, în conformitate cu condițiile lui Kuhn-Tucker , se obține:
Prin reinjectarea acestor valori în ecuație , obținem dubla formulare :
Ceea ce oferă multiplicatorii Lagrange optimi .
Pentru a obține soluția de hiperplan, înlocuim w cu valoarea sa optimă w * , în ecuația hiperplanului , care dă:
ConsecințeNoțiunea de marjă maximă și procedura de căutare a hiperplanului de separare prezentate pentru moment fac posibilă soluționarea problemelor de discriminare liniar separabile. Aceasta este o limitare severă care te condamnă să poți rezolva doar problemele jucăriilor sau cele foarte specifice. Pentru a rezolva problema lipsei separatorului liniar, ideea de nucleu truc (în engleză kernel method ) este să reconsiderăm problema într-un spațiu de dimensiune mai mare, eventual dimensiune infinită. În acest spațiu nou, este probabil probabil că există o separare liniară.
Mai formal, aplicăm o transformare neliniară vectorilor de intrare x . Spațiul de sosire se numește spațiul de redescriere . În acest spațiu, căutăm apoi hiperplanul
cine verifică
, pentru toate punctele setului de antrenament, adică hiperplanul de separare în spațiul de redescriere.Folosind aceeași procedură ca în cazul fără transformare, ajungem la următoarea problemă de optimizare:
Problema cu această formulare este că implică un produs scalar între vectori în spațiul de redescriere, de dimensiuni ridicate, care este costisitor din punct de vedere al calculelor. Pentru a rezolva această problemă, folosim un truc cunoscut sub numele de trucul Kernel , care constă în utilizarea unei funcții kernel , care verifică:
de aici expresia hiperplanului separator ca funcție a funcției kernel:
Interesul funcției kernel este dublu:
În practică, nu cunoaștem transformarea , în schimb construim direct o funcție de nucleu. Acesta trebuie să respecte anumite condiții, trebuie să corespundă unui produs scalar într-un spațiu de dimensiuni mari. Mercer teorema explicită condițiile pe care trebuie să le îndeplinească pentru a fi o funcție de bază: trebuie să fie simetrice, pozitiv semi-definită.
Cel mai simplu exemplu de funcție de nucleu este nucleul liniar:
Prin urmare, revenim la cazul unui clasificator liniar , fără schimbarea spațiului. Abordarea trucului Kernel generalizează astfel abordarea liniară. Kernelul liniar este uneori folosit pentru a evalua dificultatea unei probleme.
Nucleele obișnuite utilizate cu SVM sunt:
În general, de asemenea, nu este posibil să găsiți un separator liniar în spațiul de redescriere. De asemenea, este posibil ca eșantioanele să fie etichetate greșit și ca hiperplanul separator să nu fie cea mai bună soluție la problema clasificării.
În 1995, Corinna Cortes și Vladimir Vapnik au propus o tehnică numită marjă flexibilă , care tolerează clasamente proaste. Tehnica caută un hiperplan de separare care să minimizeze numărul de erori datorită introducerii variabilelor de primăvară ( slack variables în engleză), care fac posibilă relaxarea constrângerilor asupra vectorilor de învățare:
Cu constrângerile anterioare, problema de optimizare este modificată de un termen de penalizare, care penalizează variabilele de primăvară:
unde este o constantă care permite controlul compromisului între numărul de erori de clasificare și lățimea marginii. Trebuie ales de utilizator, în general printr-o căutare exhaustivă în spațiul parametrilor, utilizând de exemplu validarea încrucișată pe setul de antrenament. Alegerea automată a acestui parametru de regularizare este o problemă statistică majoră.
Au fost propuse mai multe metode pentru a extinde diagrama de mai sus în cazul în care mai mult de două clase urmează să fie separate. Aceste scheme sunt aplicabile oricărui clasificator binar și, prin urmare, nu sunt specifice SVM-urilor. Cele două cele mai cunoscute sunt numite unu versus toți și unul contra unu . În mod oficial, probele de învățare și testare pot fi clasificate aici în clase .
Metoda one-versus-all (uneori numită one-versus-the-rest ) constă în construirea clasificatorilor binari prin atribuirea etichetei 1 probelor uneia dintre clase și a etichetei -1 tuturor celorlalte. În faza de testare, clasificatorul care dă cea mai mare valoare de încredere (de exemplu, marja) câștigă votul.
Metoda unu contra unu constă în construirea clasificatorilor binari prin compararea fiecărei clase. În faza de testare, eșantionul care urmează să fie clasificat este analizat de fiecare clasificator și un vot majoritar face posibilă determinarea clasei sale. Dacă observăm eșantionul care urmează să fie clasificat și clasificatorul SVM care separă clasa și clasa și returnează eticheta atribuită eșantionului care urmează a fi clasificat, atunci eticheta atribuită poate fi notată formal . Aceasta este clasa care va fi atribuită cel mai adesea atunci când a fost analizată de toți . Poate exista o ambiguitate în rezultatul numărării, dacă nu există vot majoritar
O generalizare a acestor metode a fost propusă în 1995 sub denumirea de ECOC , constând în reprezentarea seturilor de clasificatori binari drept coduri cărora li se pot aplica tehnici de corectare a erorilor .
Toate aceste metode suferă de două defecte. În versiunea one-versus-all, nimic nu indică faptul că valorile rezultatului clasificării clasificatorilor sunt comparabile (fără normalizare, deci posibile probleme de scară). În plus, problema nu mai este echilibrată, de exemplu cu M = 10, doar 10% din exemplele pozitive sunt utilizate pentru 90% din exemplele negative.
Vladimir Vapnik , Harris Drucker, Chris Burges, Linda Kaufman și Alex Smola au propus în 1996 o metodă de utilizare a SVM-urilor pentru rezolvarea problemelor de regresie.
Găsim o prezentare în franceză a clasificării pe mașini vectoriale de suport în: