Support vektor maskine

Support vector machine ( SVM, support vector machine ) er et sæt af lignende overvågede læringsalgoritmer , der bruges til klassificerings- og regressionsanalyseproblemer . Det tilhører familien af lineære klassifikatorer og kan også betragtes som et særligt tilfælde af Tikhonov-regularisering . En særlig egenskab ved støttevektormaskinen er, at den empiriske klassifikationsfejl kontinuerligt aftager, og gapet øges, hvorfor metoden også er kendt som den maksimale gap-klassificeringsmetode .

Hovedideen med metoden er at oversætte de originale vektorer til et højere dimensionelt rum og søge efter et adskillende hyperplan med det største hul i dette rum. To parallelle hyperplaner er bygget på begge sider af hyperplanet, der adskiller klasserne. Det adskillende hyperplan vil være det hyperplan, der skaber den største afstand til to parallelle hyperplaner. Algoritmen er baseret på den antagelse, at jo større forskel eller afstand mellem disse parallelle hyperplaner er, jo mindre vil den gennemsnitlige klassifikationsfejl være.

Udtalelse af problemet

Ofte i maskinlæringsalgoritmer bliver det nødvendigt at klassificere data. Hvert dataobjekt er repræsenteret som en vektor (punkt) i det dimensionelle rum (et ordnet sæt tal). Hvert af disse punkter tilhører kun én af de to klasser. Spørgsmålet er, om punkterne kan adskilles af et hyperplan af dimension ( -1). Dette er et typisk tilfælde af lineær adskillelighed . Der kan være mange ønskede hyperplaner, så det menes, at maksimering af afstanden mellem klasserne bidrager til en mere sikker klassifikation. Det vil sige, er det muligt at finde et sådant hyperplan , så afstanden fra det til det nærmeste punkt er maksimalt. Dette svarer [1] til, at summen af afstande til hyperplanet fra to punkter tættest på det, der ligger på modsatte sider af det, er maksimalt. Hvis et sådant hyperplan findes, kaldes det et optimalt adskillende hyperplan , og dets tilsvarende lineære klassifikator kaldes en optimal adskillende klassifikator . $s$ $s$ $s$

Formel beskrivelse af problemet

Vi mener, at punkterne ser sådan ud:

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

hvor tager værdien 1 eller −1, afhængig af hvilken klasse punktet tilhører . Hver er en dimensionel reel vektor, normalt normaliseret med eller . Hvis punkterne ikke normaliseres, så vil et punkt med store afvigelser fra de gennemsnitlige punktkoordinater påvirke klassificereren for meget. Vi kan tænke på dette som en træningsprøve, hvor hvert element allerede er givet en klasse, som det tilhører. Vi ønsker, at støttevektormaskinalgoritmen klassificerer dem på samme måde. For at gøre dette bygger vi et adskillende hyperplan, som ser ud som: $c_{i}$ ${\mathbf {x}}_{i}$ ${\mathbf {x}}_{i}$ $s$ $[0, 1]$ $[-1,1]$

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

Vektoren er vinkelret på det adskillende hyperplan. Parameteren er i absolut værdi lig med afstanden fra hyperplanet til origo. Hvis parameteren b er nul, passerer hyperplanet gennem origo, hvilket begrænser løsningen. $\mathbf {w}$ ${\frac {b}{\|{\mathbf {w}}\|}}$

Da vi er interesserede i den optimale adskillelse, er vi interesserede i de støttevektorer og hyperplaner, der er parallelle med den optimale og tættest på støttevektorerne for de to klasser. Det kan vises, at disse parallelle hyperplaner kan beskrives med følgende ligninger (op til normalisering).

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

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

Hvis træningsprøven er lineært adskillelig , kan vi vælge hyperplanerne, så intet punkt i træningsprøven ligger mellem dem og derefter maksimere afstanden mellem hyperplanerne. Strimlens bredde mellem dem er let at finde ud fra geometriske betragtninger, den er lig med [2] , så vores opgave er at minimere . For at udelukke alle punkter fra striben skal vi sørge for alt det ${\frac {2}{\|{\mathbf {w}}\|}}$ $\|{\mathbf {w}}\|$ $jeg$

\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}} \ret.

Dette kan også skrives som:

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

Tilfældet med lineær adskillelighed

Problemet med at konstruere et optimalt adskillende hyperplan er reduceret til at minimere under betingelse (1). Dette er et kvadratisk optimeringsproblem, der ser sådan ud: $\|{\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.

Ved Kuhn-Tucker-sætningen svarer dette problem til det dobbelte problem med at finde sadelpunktet for Lagrange-funktionen

\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)\til \min _{{w,b}}\max _{{\ lambda ))\\{\mathbf {\lambda _{i))}\geq 0,\quad 1\leq i\leq n\\\end{array))\right.(2)

hvor er vektoren af dobbelte variable. ${\mathbf {\lambda }}=({\mathbf {\lambda _{1}}},\ldots,{\mathbf {\lambda _{n}}})$

Vi reducerer dette problem til et tilsvarende kvadratisk programmeringsproblem, der kun indeholder to variable:

\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 )))))\til \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))\right.(3)

Antag, at vi har løst dette problem, så kan det findes ved formlerne: $\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

Som et resultat kan klassifikationsalgoritmen skrives som:

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

I dette tilfælde sker summeringen ikke over hele prøven, men kun over støttevektorerne, for hvilke . ${\mathbf {\lambda _{i))}\neq 0$

Tilfældet med lineær uadskillelighed

For at algoritmen kan fungere, hvis klasserne er lineært uadskillelige, lad os lade den lave fejl på træningssættet. Lad os introducere et sæt yderligere variabler , der karakteriserer størrelsen af fejlen på objekter . Lad os tage (2) som udgangspunkt, blødgøre ulighedsbegrænsningerne og også indføre en straf for den totale fejl i den minimerede funktionelle: $\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}\til \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{array}}\right.

Koefficient er en metodeindstillingsparameter, der giver dig mulighed for at justere forholdet mellem maksimering af bredden af skillestrimlen og minimering af den samlede fejl. $C$

På samme måde reducerer vi ifølge Kuhn-Tucker- sætningen problemet til at finde sadelpunktet for Lagrange-funktionen :

\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)\til \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\\\venstre[{\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\\\venstre[{\begin{array}{lcr} \mathbf {\eta _{i)) =0\\\mathbf {\xi _{i)) =0,\\\end{array))\right.\quad 1\leq i\leq n\end{ array}}\right.

I analogi reducerer vi dette problem til et tilsvarende:

\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 }}})\til \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.

I praksis, for at bygge en støttevektormaskine, er det dette problem, der er løst, og ikke (3), da det generelt ikke er muligt at garantere den lineære adskillelse af punkter i to klasser. Denne variant af algoritmen kaldes soft-margin SVM-algoritmen, mens man i det lineært adskillelige tilfælde taler om en hard margin (hard-margin SVM).

For klassifikationsalgoritmen bibeholdes formel (4), med den eneste forskel, at nu ikke kun referenceobjekter, men også krænkende objekter har værdier, der ikke er nul. I en vis forstand er dette en ulempe, da støjspidser ofte er lovovertræderne, og beslutningsreglen, der er bygget på dem, i virkeligheden er afhængig af støj. ${\mathbf {\lambda _{i))}$

Konstanten C vælges normalt i henhold til kriteriet for en glidende kontrol. Dette er en besværlig metode, da problemet skal løses på ny for hver værdi af C.

Hvis der er grund til at tro, at prøven er næsten lineært adskillelig, og kun outlier-objekter er klassificeret forkert, kan outlier-filtrering anvendes. Først løses problemet for nogle C, og en lille brøkdel af objekter med den største fejlværdi fjernes fra prøven . Derefter løses problemet på ny på en trunkeret prøve. Det kan være nødvendigt at udføre flere sådanne iterationer, indtil de resterende objekter er lineært adskillelige. ${\mathbf {\xi _{i))}$

Kerner

Algoritmen til at konstruere det optimale adskillende hyperplan, foreslået i 1963 af Vladimir Vapnik og Aleksey Chervonenkis , er en lineær klassifikationsalgoritme. Men i 1992 foreslog Bernhard Boser, Isabelle Guyon og Vapnik en metode til at skabe en ikke-lineær klassificering baseret på overgangen fra skalære produkter til vilkårlige kerner, det såkaldte kernetrick (foreslået for første gang af M. A. Aizerman , E. M. Braverman og L. I. Rozonoer for metoden til potentielle funktioner), som gør det muligt at bygge ikke-lineære separatorer. Den resulterende algoritme ligner meget den lineære klassifikationsalgoritme, med den eneste forskel, at hvert skalarprodukt i ovenstående formler erstattes af en ikke-lineær kernefunktion (skalært produkt i et rum med en højere dimension). Et optimalt adskillende hyperplan kan allerede eksistere i dette rum. Da dimensionen af det resulterende rum kan være større end dimensionen af det oprindelige, vil transformationen, der matcher skalarprodukterne, være ikke-lineær, hvilket betyder, at funktionen svarende til det optimale adskillende hyperplan i det oprindelige rum også vil være ikke-lineær.

Hvis det oprindelige rum har en tilstrækkelig høj dimension, kan prøven være lineært adskillelig.

De mest almindelige kerner:

Polynomium (homogent): $k({\mathbf {x)),{\mathbf {x}}')=({\mathbf {x}}\cdot {\mathbf {x'}})^{d}$
Polynomium (heterogent): $k({\mathbf {x)),{\mathbf {x}}')=({\mathbf {x}}\cdot {\mathbf {x'}}+1)^{d}$
Radial basisfunktion : , for $k({\mathbf {x)),{\mathbf {x}}')=\exp(-\gamma \|{\mathbf {x}}-{\mathbf {x'}}\|^{2} )$ $\gamma > 0$
Radial Gaussisk basisfunktion: $k({\mathbf {x)),{\mathbf {x}}')=\exp \left(-{\frac {\|{\mathbf {x}}-{\mathbf {x'}}\| ^{2}}{2\sigma ^{2}}}\right)$
Sigmoid : , for næsten alle og $k({\mathbf {x)),{\mathbf {x}}')=\tanh(\kappa {\mathbf {x}}\cdot {\mathbf {x'}}+c)$ $\kappa >0$ $c<0$

Se også

Vapnik-Chervonenkis dimension

Noter

↑ Vyugin, 2013 , s. 86-90.
↑ K. V. Vorontsov. Foredrag om Support Vector Machines Arkiveret 27. september 2007 på Wayback Machine

Litteratur

Vladimir Vyugin. Matematisk grundlag for teorien om maskinlæring og prognoser. — MTsMNO, 2013. — 390 s. - ISBN 978-5-4439-0111-4 .
Nello Cristianini, John Shawe-Taylor. En introduktion til understøttelse af vektormaskiner og andre kernebaserede læringsmetoder . - Cambridge University Press, 2000. - ISBN 978-1-139-64363-4 .
Alexander Statnikov, Constantin F. Aliferis, Douglas P. Hardin. En blid introduktion til støtte for vektormaskiner i biomedicin: teori og metoder. - World Scientific, 2011. - ISBN 978-981-4324-38-0 .
Alexey Nefedov. Support Vector Machines: A Simple Tutorial . – 2016.

Links

data mining. 10. Forelæsning: Metoder til klassificering og prognose. Support vektor maskine // Intuit.ru
Yuri Lifshits. Support Vector Machine (Slides) - Foredrag 7 fra Algoritmer til Web-kurset

Typer af kunstige neurale netværk

Feed-forward-netværk ( Netværk af radiale basisfunktioner )
Enkeltlags perceptron
Flerlagsperceptron ( Rosenblatt • Rumelhart )
Hopfield netværk
Markov kæde
Boltzmann maskine
Begrænset Boltzmann-maskine
Autoencoder ( Denoise autoencoder • Sparse autoencoder • Variationel autoencoder )
Dybt net af tillid
Konvolutionelt neuralt netværk
Deep Convolutional Neural Network
Udrulning af neuralt netværk
Deep Convolutional Inverse Graphic Network
Generativt modstridende netværk
Tilbagevendende neurale netværk
Rekursive neurale netværk
lang korttidshukommelse
Kontrolleret tilbagevendende blokering
Neurale Turing-maskiner
Tovejsnetværk ( Bidirektionalt tilbagevendende neuralt netværk • Tovejsnetværk med langtidshukommelse • Tovejskontrollerede tilbagevendende neuroner )
Deep Residual Network
Neural ekko netværk
Ekstrem læringsmetode
Metode til ustabile tilstande
Support vektor maskine
Kohonen netværk
Selvorganiserende kort over Kohonen
Kapsel neuralt netværk
Associativ hukommelse på neurale netværk

Machine learning og data mining
Opgaver	Klassificeringsproblem Læring uden lærer Lærerassisteret læring Regressions analyse AutoML Foreningens regler Feature Extraction Træning af træk Ranking træning Grammatisk afledning Online læring
At lære med en lærer	k-nærmeste nabo metode Naiv Bayes Classifier beslutningstræ Support vektor maskine Lineær regression Logistisk regression perceptron Ensembler af modeller Bagning boostning tilfældig skov Relevant vektormetode
klyngeanalyse	k-betyder metode Fuzzy klyngemetode Hierarkisk klyngedannelse EM algoritme BIRKE HELBREDE DBSCAN OPTIK Middel-forskydning
Dimensionalitetsreduktion	Faktoranalyse Hovedkomponentmetode CCA ICA LDA Ikke-negativ matrixudvidelse t-SNE
Strukturel prognose	Graf probabilistisk model Bayesiansk netværk Skjult Markov-model CRF
Anomali detektion	k-nærmeste nabo metode Lokalt emissionsniveau
Grafer sandsynlighedsmodeller	Bayesiansk netværk Markov netværk Skjult Markov-model
Neurale netværk	Begrænset Boltzmann-maskine selvorganiserende kort Aktiveringsfunktion Sigmoid softmax Radial basisfunktion Rygformeringsmetode Dyb læring Flerlagsperceptron Tilbagevendende neurale netværk lang korttidshukommelse Kontrolleret tilbagevendende blokering Konvolutionelt neuralt netværk U-net Autoencoder
Forstærkende læring	Markov proces Bellmans ligning Grådig algoritme Q-læring SARSA Temporal forskel (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beregningsmæssig læringsteori Empirisk risikominimering Occams læring PAC læring Statistisk læringsteori
Tidsskrifter og konferencer	NeurIPS ICML ML JMLR ArXiv:cs.LG