Tuki vektorikonetta

Tukivektorikone ( SVM, tukivektorikone ) on joukko samanlaisia valvottuja oppimisalgoritmeja , joita käytetään luokittelu- ja regressioanalyysiongelmiin . Se kuuluu lineaaristen luokittimien perheeseen ja sitä voidaan pitää myös Tihonov-regulaation erikoistapauksena . Tukivektorikoneen erityinen ominaisuus on, että empiirinen luokitteluvirhe pienenee jatkuvasti ja aukko kasvaa, minkä vuoksi menetelmä tunnetaan myös maksimaalisen aukon luokittelumenetelmänä .

Menetelmän pääideana on kääntää alkuperäiset vektorit korkeamman ulottuvuuden avaruuteen ja etsiä erottelevaa hypertasoa, jossa on suurin aukko tässä tilassa. Kaksi rinnakkaista hypertasoa on rakennettu luokat erottavan hypertason molemmille puolille. Erotteleva hypertaso on se hypertaso, joka luo suurimman etäisyyden kahteen rinnakkaiseen hypertasoon. Algoritmi perustuu oletukseen, että mitä suurempi ero tai etäisyys näiden rinnakkaisten hypertasojen välillä on, sitä pienempi luokittelijan keskimääräinen virhe on.

Ongelman selvitys

Usein koneoppimisalgoritmeissa tietojen luokittelu on välttämätöntä. Jokainen tietoobjekti esitetään vektorina (pisteenä) -ulotteisessa avaruudessa (järjestetty numerosarja). Kukin näistä pisteistä kuuluu vain toiseen kahdesta luokasta. Kysymys kuuluu, voidaanko pisteet erottaa hypertasolla, jonka ulottuvuus on ( −1). Tämä on tyypillinen lineaarisen erotettavuuden tapaus . Haluttuja hypertasoja voi olla monia, joten uskotaan, että luokkien välisen eron maksimoiminen edistää luokittelun luotettavuutta. Eli onko mahdollista löytää tällainen hypertaso niin, että etäisyys siitä lähimpään pisteeseen on suurin. Tämä vastaa [1] sitä tosiasiaa, että etäisyyksien summa hypertasoon kahdesta sitä lähimmästä pisteestä, jotka sijaitsevat sen vastakkaisilla puolilla, on maksimi. Jos tällainen hypertaso on olemassa, sitä kutsutaan optimaaliseksi erottavaksi hypertasoksi ja sitä vastaavaa lineaarista luokittelijaa kutsutaan optimaaliseksi erottavaksi luokittelijaksi . $s$ $s$ $s$

Virallinen kuvaus ongelmasta

Uskomme, että pisteet näyttävät tältä:

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

missä saa arvon 1 tai −1, riippuen kumpaan luokkaan piste kuuluu . Jokainen on -ulotteinen reaalivektori , joka on tavallisesti normalisoitu tai . Jos pisteitä ei normalisoida, niin piste, jossa on suuria poikkeamia keskimääräisistä pistekoordinaateista, vaikuttaa luokittimeen liikaa. Voimme ajatella tätä harjoitusnäytteenä, jossa jokaiselle elementille on jo annettu luokka, johon se kuuluu. Haluamme, että tukivektorikonealgoritmi luokittelee ne samalla tavalla. Tätä varten rakennamme erottavan hypertason, joka näyttää tältä: $c_{i}$ ${\mathbf {x}}_{i}$ ${\mathbf {x}}_{i}$ $s$ $[0, 1]$ $[-1,1]$

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

Vektori on kohtisuorassa erottavaan hypertasoon nähden. Parametri on absoluuttisesti yhtä suuri kuin etäisyys hypertasosta origoon. Jos parametri b on nolla, hypertaso kulkee origon läpi, mikä rajoittaa ratkaisua. $\mathbf {w}$ ${\frac {b}{\|{\mathbf {w}}\|}}$

Koska olemme kiinnostuneita optimaalisesta erottelusta, olemme kiinnostuneita tukivektoreista ja hypertasoista, jotka ovat yhdensuuntaisia optimaalisen kanssa ja lähinnä kahden luokan tukivektoreita. Voidaan osoittaa, että nämä rinnakkaiset hypertasot voidaan kuvata seuraavilla yhtälöillä (normalisointiin asti).

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

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

Jos harjoitusnäyte on lineaarisesti erotettavissa , voimme valita hypertasot siten, että mikään harjoitusnäytteen piste ei ole niiden välissä ja maksimoida hypertasojen välinen etäisyys. Niiden välisen nauhan leveys on helppo löytää geometrisista syistä, se on yhtä suuri kuin [2] , joten tehtävämme on minimoida . Kaikkien pisteiden sulkemiseksi pois nauhasta meidän on varmistettava kaikki tämä ${\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}} \oikein.

Tämä voidaan kirjoittaa myös näin:

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

Lineaarisen erotettavuuden tapaus

Optimaalisen erottelevan hypertason rakentamisen ongelma on vähennetty minimiin , ehdolla (1). Tämä on neliöllinen optimointiongelma, joka näyttää tältä: $\|{\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.

Kuhn-Tuckerin lauseen mukaan tämä ongelma vastaa kaksoisongelmaa Lagrange-funktion satulapisteen löytämisessä.

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

missä on kaksoismuuttujien vektori. ${\mathbf {\lambda }}=({\mathbf {\lambda _{1}}},\ldots ,{\mathbf {\lambda _{n}}})$

Pelistämme tämän ongelman vastaavaksi toisen asteen ohjelmointitehtäväksi, joka sisältää vain kaksi muuttujaa:

\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 )))))\to \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)

Oletetaan, että olemme ratkaisseet tämän ongelman, niin se voidaan löytää kaavoilla: $\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

Tämän seurauksena luokitusalgoritmi voidaan kirjoittaa seuraavasti:

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

Tässä tapauksessa summaamista ei tapahdu koko näytteelle, vaan vain tukivektoreille, joille . ${\mathbf {\lambda _{i))}\neq 0$

Lineaarisen erottamattomuuden tapaus

Jotta algoritmi toimisi, jos luokat ovat lineaarisesti erottamattomia, annetaan sen tehdä virheitä harjoitusjoukossa. Otetaan käyttöön joukko lisämuuttujia, jotka kuvaavat objektien virheen suuruutta . Otetaan (2) lähtökohtana, pehmennetään epätasa-arvorajoituksia ja lisätään myös sakko kokonaisvirheestä minimoituun funktioon: $\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{array}}\right.

Kerroin on menetelmän asetusparametri, jonka avulla voit säätää erotuskaistan leveyden maksimoimisen ja kokonaisvirheen minimoimisen välistä suhdetta. $C$

Samoin Kuhn-Tuckerin lauseen mukaan pelkistetään ongelma Lagrange-funktion satulapisteen löytämiseen :

\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)\to \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{ array}}\right.

Analogisesti vähennämme tämän ongelman vastaavaan:

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

Käytännössä tukivektorikoneen rakentamiseksi ratkaistaan tämä ongelma, ei (3), koska pisteiden lineaarista erotettavuutta kahteen luokkaan ei yleensä voida taata. Tätä algoritmin muunnelmaa kutsutaan soft-margin SVM-algoritmiksi, kun taas lineaarisesti erotettavissa olevassa tapauksessa puhutaan kovasta marginaalista (hard-margin SVM).

Luokittelualgoritmille säilytetään kaava (4) sillä ainoalla erolla, että nyt ei vain viiteobjekteilla, vaan myös rikkovilla objekteilla on nollasta poikkeavat arvot. Tietyssä mielessä tämä on haitta, koska melupiikit ovat usein rikoksentekijöitä ja niihin rakennettu päätössääntö itse asiassa nojaa meluun. ${\mathbf {\lambda _{i))}$

Vakio C valitaan yleensä liukuohjauksen kriteerin mukaan. Tämä on työläs menetelmä, koska tehtävä on ratkaistava uudelleen jokaiselle C:n arvolle.

Jos on syytä uskoa, että näyte on lähes lineaarisesti erotettavissa ja vain outlier-objektit luokitellaan väärin, voidaan käyttää outlier-suodatusta. Ensin ongelma ratkaistaan jollekin C:lle ja pieni osa objekteista, joilla on suurin virhearvo, poistetaan näytteestä . Sen jälkeen ongelma ratkaistaan uudelleen katkaistulla näytteellä. Saattaa olla tarpeen tehdä useita tällaisia iteraatioita, kunnes loput objektit ovat lineaarisesti erotettavissa. ${\mathbf {\xi _{i))}$

Ytimet

Vladimir Vapnikin ja Aleksei Chervonenkiksen vuonna 1963 ehdottama algoritmi optimaalisen erottavan hypertason muodostamiseksi on lineaarinen luokittelualgoritmi. Kuitenkin vuonna 1992 Bernhard Boser, Isabelle Guyon ja Vapnik ehdottivat menetelmää epälineaarisen luokittelun luomiseksi, joka perustuu siirtymiseen skalaarituloksista mielivaltaisiin ytimiin, niin sanottua ydintemppua (jota ehdottivat ensimmäistä kertaa M. A. Aizerman , E. M. Braverman ja L. I. Rozonoer mahdollisten funktioiden menetelmälle), joka mahdollistaa epälineaaristen erottimien rakentamisen. Tuloksena oleva algoritmi on hyvin samanlainen kuin lineaarinen luokittelualgoritmi, sillä ainoa ero on, että jokainen skalaaritulo yllä olevissa kaavoissa korvataan epälineaarisella ydinfunktiolla (skalaaritulo avaruudessa, jolla on suurempi ulottuvuus). Tässä tilassa voi jo olla optimaalinen erottava hypertaso. Koska tuloksena olevan avaruuden mitta voi olla suurempi kuin alkuperäisen, skalaarituloja vastaava muunnos on epälineaarinen, mikä tarkoittaa, että alkuperäisen avaruuden optimaalista erottavaa hypertasoa vastaava funktio on myös epälineaarinen.

Jos alkuperäinen tila on riittävän suuri, näyte voi olla lineaarisesti erotettavissa.

Yleisimmät ytimet:

Polynomi (homogeeninen): $k({\mathbf {x)),{\mathbf {x}}')=({\mathbf {x}}\cdot {\mathbf {x'}})^{d}$
Polynomi (heterogeeninen): $k({\mathbf {x)),{\mathbf {x}}')=({\mathbf {x}}\cdot {\mathbf {x'}}+1)^{d}$
Radiaalinen kantafunktio : , for $k({\mathbf {x)),{\mathbf {x}}')=\exp(-\gamma \|{\mathbf {x}}-{\mathbf {x'}}\|^{2} )$ $\gamma > 0$
Radiaalinen Gaussin perusfunktio: $k({\mathbf {x)),{\mathbf {x}}')=\exp \left(-{\frac {\|{\mathbf {x}}-{\mathbf {x'}}\| ^{2}}{2\sigma ^{2}}}\oikea)$
Sigmoidi : , melkein kaikille ja $k({\mathbf {x)),{\mathbf {x}}')=\tanh(\kappa {\mathbf {x}}\cdot {\mathbf {x'}}+c)$ $\kappa >0$ $c<0$

Katso myös

Vapnik-Chervonenkis ulottuvuus

Muistiinpanot

↑ Vyugin, 2013 , s. 86-90.
↑ K. V. Vorontsov. Luennot tukivektorikoneista, arkistoitu 27. syyskuuta 2007 Wayback Machinessa

Kirjallisuus

Vladimir Vyugin. Koneoppimisen ja ennustamisen teorian matemaattiset perusteet. — MTsMNO, 2013. — 390 s. - ISBN 978-5-4439-0111-4 .
Nello Cristianini, John Shawe-Taylor. Johdatus vektorikoneiden ja muiden ydinpohjaisten oppimismenetelmien tukemiseen . - Cambridge University Press, 2000. - ISBN 978-1-139-64363-4 .
Alexander Statnikov, Constantin F. Aliferis, Douglas P. Hardin. Hellävarainen johdatus vektorikoneiden tukemiseen biolääketieteessä: teoria ja menetelmät. - World Scientific, 2011. - ISBN 978-981-4324-38-0 .
Aleksei Nefedov. Tuki Vector Machines: yksinkertainen opetusohjelma . – 2016.

Linkit

tiedon louhinta. 10. Luento: Luokittelu- ja ennustamismenetelmät. Tuki vektorikonetta // Intuit.ru
Juri Lifshits. Tuki vektorikonetta (diat) - Luento 7 Web-kurssin algoritmeista

Keinotekoisten neuroverkkojen tyypit

Feed-forward-verkko ( Säteittäisten perustoimintojen verkko )
Yksikerroksinen perceptroni
Monikerroksinen Perceptron ( Rosenblatt • Rumelhart )
Hopfieldin verkko
Markovin ketju
Boltzmannin kone
Rajoitettu Boltzmann-kone
Autoencoder ( Denoise autoencoder • Sparse autoencoder • Variational autoencoder )
Syvä luottamuksen verkko
Konvoluutiohermoverkko
Syvä konvoluutiohermoverkko
Käyttöönoton hermoverkko
Deep Convolutional Inverse Graphic Network
Generatiivinen kontradiktorinen verkosto
Toistuva neuroverkko
Rekursiiviset hermoverkot
pitkä lyhytaikainen muisti
Hallittu toistuva esto
Neuraaliset Turingin koneet
Kaksisuuntainen verkko ( Kaksisuuntainen toistuva hermoverkko • Kaksisuuntainen verkko pitkällä lyhytaikaisella muistilla • Kaksisuuntaisesti ohjatut toistuvat neuronit )
Deep Residual Network
Neuraalinen kaikuverkko
Extreme Learning Method
Epävakaiden tilojen menetelmä
Tuki vektorikonetta
Kohosen verkko
Kohosen itseorganisoituva kartta
Kapselin hermoverkko
Assosiatiivinen muisti neuroverkoissa

Koneoppiminen ja tiedon louhinta
Tehtävät	Luokittelu ongelma Oppiminen ilman opettajaa Opettajan avustama oppiminen Taantumisanalyysi AutoML Yhdistyksen säännöt Ominaisuuksien erottaminen Ominaisuuksien koulutus Ranking koulutus Kieliopillinen johtaminen Verkko-oppiminen
Opettajan kanssa oppimista	k-lähimmän naapurin menetelmä Naiivi Bayesin luokitin päätöspuu Tuki vektorikonetta Lineaarinen regressio Logistinen regressio perceptron Mallien kokoonpanot Pussittaminen tehostaa satunnainen metsä Asiaankuuluva vektorimenetelmä
ryhmäanalyysi	k-keinomenetelmä Sumea klusterointimenetelmä Hierarkkinen klusterointi EM-algoritmi KOIVU PARANTAA DBSCAN OPTIIKKA Keskimääräinen siirto
Mittasuhteiden vähentäminen	Tekijäanalyysi Pääkomponenttimenetelmä CCA ICA LDA Ei-negatiivinen matriisin laajennus t-SNE
Rakenteellinen ennustaminen	Graafinen todennäköisyysmalli Bayesin verkko Piilotettu Markovin malli CRF
Anomalian havaitseminen	k-lähimmän naapurin menetelmä Paikallinen päästötaso
Piirrä todennäköisyysmallit	Bayesin verkko Markovin verkko Piilotettu Markovin malli
Neuroverkot	Rajoitettu Boltzmann-kone itseorganisoituva kartta Aktivointitoiminto Sigmoidi softmax Radiaalinen kantafunktio Takaisin lisäysmenetelmä Syväoppiminen Monikerroksinen perceptroni Toistuva neuroverkko pitkä lyhytaikainen muisti Hallittu toistuva esto Konvoluutiohermoverkko U-verkko Autoenkooderi
Vahvistusoppiminen	Markovin prosessi Bellmanin yhtälö Ahne algoritmi Q-oppiminen SARSA Aikaero (TD)
Teoria	Vapnik-Chervonenkis teoria Bias-dispersion dilemma Laskennallinen oppimisteoria Empiirinen riskin minimointi Occam oppii PAC-oppiminen Tilastollinen oppimisteoria
Lehdet ja konferenssit	NeurIPS ICML ML JMLR ArXiv:cs.LG