Suport mașină vectorială

Mașină vectorială de suport ( SVM, mașină vectorială de suport ) este un set de algoritmi de învățare supravegheat similari utilizați pentru probleme de clasificare și analiză de regresie . Ea aparține familiei clasificatoarelor liniare și poate fi considerată și ca un caz special de regularizare Tikhonov . O proprietate specială a mașinii vector suport este că eroarea de clasificare empirică scade în mod continuu și decalajul crește, motiv pentru care metoda este cunoscută și ca metoda de clasificare a decalajului maxim .

Ideea principală a metodei este de a traduce vectorii originali într-un spațiu de dimensiuni mai mari și de a căuta un hiperplan de separare cu cel mai mare decalaj din acest spațiu. Două hiperplanuri paralele sunt construite pe ambele părți ale hiperplanului care separă clasele. Hiperplanul de separare va fi hiperplanul care creează cea mai mare distanță până la două hiperplane paralele. Algoritmul se bazează pe presupunerea că, cu cât diferența sau distanța dintre aceste hiperplane paralele este mai mare, cu atât eroarea medie a clasificatorului va fi mai mică.

Enunțul problemei

Adesea, în algoritmii de învățare automată, devine necesară clasificarea datelor. Fiecare obiect de date este reprezentat ca un vector (punct) în spațiul -dimensional (un set ordonat de numere). Fiecare dintre aceste puncte aparține doar uneia dintre cele două clase. Întrebarea este dacă punctele pot fi separate printr-un hiperplan de dimensiune ( -1). Acesta este un caz tipic de separabilitate liniară . Pot exista multe hiperplanuri dorite, așa că se crede că maximizarea decalajului dintre clase contribuie la o clasificare mai sigură. Adică, este posibil să găsim un astfel de hiperplan , astfel încât distanța de la acesta până la cel mai apropiat punct să fie maximă. Acest lucru este echivalent [1] cu faptul că suma distanțelor până la hiperplan de la două puncte cele mai apropiate de acesta, situate pe părțile opuse ale acestuia, este maximă. Dacă un astfel de hiperplan există, se numește hiperplan de separare optim , iar clasificatorul liniar corespunzător se numește clasificator de separare optim . $p$ $p$ $p$

Descrierea formală a problemei

Credem că punctele arată astfel:

\{({\mathbf {x}}_{1},c_{1}),({\mathbf {x}}_{2},c_{2}),\ldots ,({\mathbf {x} }_{n},c_{n})\}

unde ia valoarea 1 sau −1, în funcție de clasa căreia îi aparține punctul . Fiecare este un vector real -dimensional , de obicei normalizat prin sau . Dacă punctele nu sunt normalizate, atunci un punct cu abateri mari de la coordonatele punctului mediu va afecta prea mult clasificatorul. Ne putem gândi la aceasta ca la un eșantion de antrenament în care fiecărui element i se oferă deja o clasă căreia îi aparține. Vrem ca algoritmul mașinii vectorului suport să le clasifice în același mod. Pentru a face acest lucru, construim un hiperplan de separare, care arată astfel: $c_{i}$ ${\mathbf {x}}_{i}$ ${\mathbf {x}}_{i}$ $p$ $[0, 1]$ $[-1,1]$

{\mathbf {w}}\cdot {\mathbf {x}}-b=0.

Vectorul este perpendicular pe hiperplanul de separare. Parametrul este egal în valoare absolută cu distanța de la hiperplan la origine. Dacă parametrul b este zero, hiperplanul trece prin origine, ceea ce limitează soluția. $\mathbf {w}$ ${\frac {b}{\|{\mathbf {w}}\|}}$

Deoarece ne interesează separarea optimă, ne interesează vectorii suport și hiperplanele care sunt paralele cu cea optimă și cele mai apropiate de vectorii suport ai celor două clase. Se poate arăta că aceste hiperplane paralele pot fi descrise prin următoarele ecuații (până la normalizare).

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

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

Dacă eșantionul de antrenament este separabil liniar , atunci putem alege hiperplanele astfel încât niciun punct al eșantionului de antrenament să nu se afle între ele și apoi să maximizăm distanța dintre hiperplane. Lățimea benzii dintre ele este ușor de găsit din considerente geometrice, este egală cu [2] , deci sarcina noastră este de a minimiza . Pentru a exclude toate punctele din bandă, trebuie să ne asigurăm de toate acestea ${\frac {2}{\|{\mathbf {w}}\|}}$ $\|{\mathbf {w}}\|$ $i$

\left[{\begin{array}{lcr}{\mathbf {w}}\cdot {\mathbf {x_{i}}}-b\geq 1,\ c_{i}=1{\mathrm {}} \\{\mathbf {w}}\cdot {\mathbf {x_{i}}}-b\leq -1,\ c_{i}=-1{\mathrm {}}\\\end{array}} \dreapta.

Acest lucru poate fi scris și ca:

c_{i}({\mathbf {w}}\cdot {\mathbf {x_{i}}}-b)\geq 1,\quad 1\leq i\leq n.\qquad \qquad (1)

Cazul separabilității liniare

Problema construirii unui hiperplan de separare optim se reduce la minimizarea , în condiția (1). Aceasta este o problemă de optimizare pătratică care arată astfel: $\|{\mathbf {w}}\|$

\left\{{\begin{array}{lcr}\|{\mathbf {w}}\|^{2}\to \min \\c_{i}({\mathbf {w}}\cdot {\ mathbf {x_{i}}}-b)\geq 1,\quad 1\leq i\leq n.\\\end{array}}\right.

După teorema Kuhn-Tucker, această problemă este echivalentă cu problema duală a găsirii punctului de șa al funcției Lagrange

\left\{{\begin{array}{lcr}{\mathbf {L}}({\mathbf {w}},{\mathbf {b}};{\mathbf {\lambda }})={\frac {1}{2}}\|{\mathbf {w}}\|^{2}-\sum _{{i=1}}^{n}{\mathbf {\lambda _{i}}}( c_{i}(({\mathbf {w}}\cdot {\mathbf {x_{i}}})-b)-1)\la \min _{{w,b}}\max _{{\ lambda ))\\{\mathbf {\lambda _{i))}\geq 0,\quad 1\leq i\leq n\\\end{array))\right.(2)

unde este vectorul variabilelor duale. ${\mathbf {\lambda }}=({\mathbf {\lambda _{1}}},\ldots ,{\mathbf {\lambda _{n}}})$

Reducem această problemă la o problemă de programare pătratică echivalentă care conține doar variabile duale:

\left\{{\begin{array}{lcr}-{\mathbf {L}}({\mathbf {\lambda }})=-\sum _{{i=1}}^{n}{\mathbf {\lambda _{i))}+{\frac {1}{2}}\sum _{{i=1}}^{n}\sum _{{j=1}}^{n}{\ mathbf {\lambda _{i))}{\mathbf {\lambda _{j))}c_{i}c_{j}({\mathbf {x_{i))}\cdot {\mathbf {x_{j )))))\la \min _{{\lambda }}\\{\mathbf {\lambda _{i}}}\geq 0,\quad 1\leq i\leq n\\\sum _{{ i =1))^{n}{\mathbf {\lambda _{i))}c_{i}=0\\\end{array))\dreapta.(3)

Să presupunem că am rezolvat această problemă, atunci poate fi găsită prin formulele: $\mathbf {w}$ ${\mathbf {b}}$

{\mathbf {w}}=\sum _{{i=1}}^{n}{\mathbf {\lambda _{i}}}c_{i}{\mathbf {x_{i}}}

{\mathbf {b}}={\mathbf {w}}\cdot {\mathbf {x_{i}}}-c_{i},\quad {\mathbf \lambda }_{i}>0

Ca rezultat, algoritmul de clasificare poate fi scris astfel:

a(x)=semn\left(\sum _{{i=1}}^{n}{\mathbf {\lambda _{i}}}c_{i}{\mathbf {x_{i}}}\ cdot {\mathbf {x}}-b\right)(4)

În acest caz, însumarea nu are loc pe întregul eșantion, ci doar pe vectorii suport pentru care . ${\mathbf {\lambda _{i))}\neq 0$

Cazul inseparabilității liniare

Pentru ca algoritmul să funcționeze dacă clasele sunt liniar inseparabile, să-i permitem să facă greșeli pe setul de antrenament. Să introducem un set de variabile suplimentare care caracterizează magnitudinea erorii asupra obiectelor . Să luăm (2) ca punct de plecare, să reducem constrângerile de inegalitate și să introducem, de asemenea, o penalizare pentru eroarea totală în funcționalitatea minimizată: $\xi _{i}\geq 0$ ${\mathbf {x}}_{i},\quad 1\leq i\leq n$

\left\{{\begin{array}{lcr}{\frac {1}{2}}\|{\mathbf {w}}\|^{2}+C\sum _{{i=1}} ^{n}\xi _{i}\to \min _{{w,b,\xi _{i}}}\\c_{i}({\mathbf {w}}\cdot {\mathbf {x_ {i}}}-b)\geq 1-\xi _{i},\quad 1\leq i\leq n\\\xi _{i}\geq 0,\quad 1\leq i\leq n\ \\end{matrice}}\dreapta.

Coeficientul este un parametru de setare a metodei care vă permite să ajustați raportul dintre maximizarea lățimii benzii de separare și minimizarea erorii totale. $C$

În mod similar, conform teoremei Kuhn-Tucker , reducem problema la găsirea punctului de șa al funcției Lagrange :

\left\{{\begin{array}{lcr}\mathbf {L} (\mathbf {w},\mathbf {b},\mathbf {\xi} ;\mathbf {\lambda},\mathbf {\eta } )={\frac {1}{2}}\|\mathbf {w} \|^{2}-\sum _{i=1}^{n}\mathbf {\lambda _{i )) (c_{i}((\mathbf {w} \cdot \mathbf {x_{i)) )-b)-1)-\sum _{i=1}^{n}\mathbf {\xi _ {i)) (\mathbf {\lambda _{i)) +\mathbf {\eta _{i)) -C)\la \min _{w,b,\xi }\max _{\lambda,\ eta }\\\mathbf {\xi _{i)) \geq 0,\mathbf {\lambda _{i)) \geq 0,\mathbf {\eta _{i)) \geq 0,\quad 1\ leq i\leq n\\\left[{\begin{array}{lcr}\mathbf {\lambda _{i))=0\\c_{i}(\mathbf {w} \cdot \mathbf {x_{ i}} -b)=1-\xi _{i},\\\end{array}}\right.\quad 1\leq i\leq n\\\left[{\begin{array}{lcr} \mathbf {\eta _{i)) =0\\\mathbf {\xi _{i)) =0,\\\end{array))\right.\quad 1\leq i\leq n\end{ matrice}}\dreapta.

Prin analogie, reducem această problemă la una echivalentă:

\left\{{\begin{array}{lcr}-{\mathbf {L}}({\mathbf {\lambda }})=-\sum _{{i=1}}^{n}{\mathbf {\lambda _{i))}+{\frac {1}{2}}\sum _{{i=1}}^{n}\sum _{{j=1}}^{n}{\ mathbf {\lambda _{i))}{\mathbf {\lambda _{j))}c_{i}c_{j}({\mathbf {x_{i))}\cdot {\mathbf {x_{j }}})\la \min _{{\lambda }}\\0\leq {\mathbf {\lambda _{i}}}\leq {\mathbf {C}},\quad 1\leq i\leq n\\\sum _{{i=1}}^{n}{\mathbf {\lambda _{i}}}c_{i}=0\\\end{array}}\right.

În practică, pentru a construi o mașină vectorială suport, această problemă este rezolvată, și nu (3), deoarece în general nu este posibil să se garanteze separabilitatea liniară a punctelor în două clase. Această variantă a algoritmului se numește algoritm SVM soft-margin, în timp ce în cazul separabil liniar se vorbește de margine rigidă (SVM hard-margin).

Pentru algoritmul de clasificare se reține formula (4), cu singura diferență că acum nu numai obiectele de referință, ci și obiectele care încalcă au valori diferite de zero. Într-un anumit sens, acesta este un dezavantaj, deoarece vârfurile de zgomot sunt adesea infractorii, iar regula de decizie construită pe acestea, de fapt, se bazează pe zgomot. ${\mathbf {\lambda _{i))}$

Constanta C este de obicei aleasă după criteriul unui control glisant. Aceasta este o metodă laborioasă, deoarece problema trebuie rezolvată din nou pentru fiecare valoare a lui C.

Dacă există motive să credem că eșantionul este aproape separabil liniar și numai obiectele aberante sunt clasificate incorect, atunci poate fi aplicată filtrarea valorii aberante. În primul rând, problema este rezolvată pentru unele C și o mică parte a obiectelor cu cea mai mare valoare de eroare este eliminată din eșantion . După aceea, problema este rezolvată din nou pe o probă trunchiată. Poate fi necesar să faceți mai multe astfel de iterații până când obiectele rămase sunt separabile liniar. ${\mathbf {\xi _{i))}$

Kernels

Algoritmul pentru construirea hiperplanului de separare optim, propus în 1963 de Vladimir Vapnik și Aleksey Chervonenkis , este un algoritm de clasificare liniară. Cu toate acestea, în 1992, Bernhard Boser, Isabelle Guyon și Vapnik au propus o metodă de creare a unui clasificator neliniar bazat pe tranziția de la produse scalare la nuclee arbitrare, așa-numitul truc kernel (propus pentru prima dată de M. A. Aizerman , E. M. Braverman și L. I. Rozonoer pentru metoda funcțiilor potențiale), care permite construirea de separatoare neliniare. Algoritmul rezultat este foarte asemănător cu algoritmul de clasificare liniară, singura diferență fiind că fiecare produs scalar din formulele de mai sus este înlocuit cu o funcție de nucleu neliniară (produs scalar într-un spațiu cu o dimensiune mai mare). Un hiperplan de separare optim poate exista deja în acest spațiu. Deoarece dimensiunea spațiului rezultat poate fi mai mare decât dimensiunea celui inițial, transformarea care se potrivește cu produsele scalare va fi neliniară, ceea ce înseamnă că și funcția corespunzătoare hiperplanului de separare optim din spațiul original va fi neliniară.

Dacă spațiul original are o dimensiune suficient de mare, atunci proba poate fi separabilă liniar.

Cele mai comune nuclee:

Polinom (omogen): $k({\mathbf {x)),{\mathbf {x}}')=({\mathbf {x}}\cdot {\mathbf {x'}})^{d}$
Polinom (eterogen): $k({\mathbf {x)),{\mathbf {x}}')=({\mathbf {x}}\cdot {\mathbf {x'}}+1)^{d}$
Funcția de bază radială : , pentru $k({\mathbf {x)),{\mathbf {x}}')=\exp(-\gamma \|{\mathbf {x}}-{\mathbf {x'}}\|^{2} )$ $\gamma > 0$
Funcția de bază gaussiană radială: $k({\mathbf {x)),{\mathbf {x}}')=\exp \left(-{\frac {\|{\mathbf {x}}-{\mathbf {x'}}\| ^{2}}{2\sigma ^{2}}}\dreapta)$
Sigmoid : , pentru aproape toți și $k({\mathbf {x)),{\mathbf {x}}')=\tanh(\kappa {\mathbf {x}}\cdot {\mathbf {x'}}+c)$ $\kappa >0$ $c<0$

Vezi și

Dimensiunea Vapnik-Chervonenkis

Note

↑ Vyugin, 2013 , p. 86-90.
↑ K. V. Vorontsov. Prelegeri despre suport Vector Machines Arhivat 27 septembrie 2007 la Wayback Machine

Literatură

Vladimir Vyugin. Fundamentele matematice ale teoriei învățării automate și previziunii. — MTsMNO, 2013. — 390 p. - ISBN 978-5-4439-0111-4 .
Nello Cristianini, John Shawe-Taylor. O introducere în sprijinirea mașinilor vectoriale și a altor metode de învățare bazate pe kernel . - Cambridge University Press, 2000. - ISBN 978-1-139-64363-4 .
Alexander Statnikov, Constantin F. Aliferis, Douglas P. Hardin. O introducere blândă în sprijinirea mașinilor vectoriale în biomedicină: teorie și metode. - World Scientific, 2011. - ISBN 978-981-4324-38-0 .
Alexei Nefedov. Suport mașini vectoriale: un tutorial simplu . — 2016.

Link -uri

extragerea datelor. 10. Prelegere: Metode de clasificare și prognoză. Suport mașină vectorială // Intuit.ru
Yuri Lifshits. Support Vector Machine (diapozitive) - Cursul 7 din cursul Algoritmi pentru web

Tipuri de rețele neuronale artificiale

Rețea feed-forward ( Rețeaua de funcții de bază radială )
Perceptron cu un singur strat
Perceptron multistrat ( Rosenblatt • Rumelhart )
Rețeaua Hopfield
lanțul Markov
Masina Boltzmann
Mașină Boltzmann limitată
Autoencoder ( Denoise autoencoder • Sparse autoencoder • Variational autoencoder )
Rețea profundă de încredere
Rețeaua neuronală convoluțională
Rețeaua neuronală convoluțională profundă
Implementarea rețelei neuronale
Deep Convolutional Inverse Graphic Network
Rețeaua adversară generativă
Rețea neuronală recurentă
Rețele neuronale recursive
memorie pe termen lung și scurt
Bloc recurent controlat
Neural Turing Machines
Rețea bidirecțională ( Rețea neuronală recurentă bidirecțională • Rețea bidirecțională cu memorie lungă pe termen scurt • Neuroni recurenți controlați bidirecționali )
Rețea reziduală adâncă
Rețea de ecou neuronal
Metoda de învățare extremă
Metoda stărilor instabile
Suport mașină vectorială
Rețeaua Kohonen
Harta auto-organizată a lui Kohonen
Rețea neuronală capsule
Memoria asociativă pe rețelele neuronale

Învățare automată și extragerea datelor
Sarcini	Problema de clasificare Învățați fără profesor Învățare asistată de profesor Analiza regresiei AutoML Regulile de asociere Extragerea caracteristicilor Antrenamentul trăsăturilor Antrenament de clasare Derivarea gramaticală Învățare online
Învățarea cu un profesor	metoda k-cel mai apropiat vecin Clasificator naiv Bayes arborele de decizie Suport mașină vectorială Regresie liniara Regresie logistică perceptron Ansambluri de modele Bagare stimularea pădure la întâmplare Metoda vectorială relevantă
analiza grupului	metoda k-means Metoda de grupare fuzzy Gruparea ierarhică algoritmul EM MESTEACĂN VINDECA DBSCAN OPTICA Schimbare medie
Reducerea dimensionalității	Analiza factorilor Metoda componentei principale CCA ICA LDA Expansiunea nenegativă a matricei t-SNE
Prognoza structurală	Modelul probabilistic grafic Rețeaua bayesiană Modelul Markov ascuns CRF
Detectarea anomaliilor	metoda k-cel mai apropiat vecin Nivelul de emisie local
Modele grafice probabilistice	Rețeaua bayesiană Rețeaua Markov Modelul Markov ascuns
Rețele neuronale	Mașină Boltzmann limitată hartă de auto-organizare Funcția de activare Sigmoid softmax Funcția de bază radială Metoda de propagare înapoi Invatare profunda Perceptron multistrat Rețea neuronală recurentă memorie pe termen lung și scurt Bloc recurent controlat Rețeaua neuronală convoluțională U-Net Autoencoder
Consolidarea învățării	procesul Markov Ecuația Bellman Algoritmul lacom Q-learning SARSA Diferența temporală (TD)
Teorie	Teoria Vapnik-Chervonenkis Dilema părtinire-dispersie Teoria învățării computaționale Minimizarea riscului empiric Occam învață Învățarea PAC Teoria învăţării statistice
Reviste și conferințe	NeurIPS ICML ML JMLR ArXiv:cs.LG