Podpora vektorového stroje

Support vector machine ( SVM, support vector machine ) je sada podobných algoritmů učení pod dohledem používaných pro problémy klasifikace a regresní analýzy . Patří do rodiny lineárních klasifikátorů a lze jej také považovat za speciální případ Tichonovovy regularizace . Speciální vlastností podpůrného vektorového stroje je to, že empirická klasifikační chyba se neustále zmenšuje a mezera se zvětšuje, proto je tato metoda také známá jako metoda klasifikátoru maximální mezery .

Hlavní myšlenkou metody je převést původní vektory do vícerozměrného prostoru a hledat oddělující nadrovinu s největší mezerou v tomto prostoru. Dvě paralelní nadroviny jsou postaveny na obou stranách nadroviny, která odděluje třídy. Oddělující nadrovina bude ta nadrovina, která vytváří největší vzdálenost ke dvěma rovnoběžným nadrovinám. Algoritmus je založen na předpokladu, že čím větší je rozdíl nebo vzdálenost mezi těmito paralelními nadrovinami, tím menší bude průměrná chyba klasifikátoru.

Prohlášení o problému

V algoritmech strojového učení je často nutné data klasifikovat. Každý datový objekt je reprezentován jako vektor (bod) v -rozměrném prostoru (uspořádaná množina čísel). Každý z těchto bodů patří pouze do jedné ze dvou tříd. Otázkou je, zda lze body oddělit nadrovinou dimenze ( −1). Toto je typický případ lineární oddělitelnosti . Může existovat mnoho požadovaných nadrovin, takže se má za to, že maximalizace mezery mezi třídami přispívá k spolehlivější klasifikaci. To znamená, zda je možné najít takovou nadrovinu , aby vzdálenost od ní k nejbližšímu bodu byla maximální. To je ekvivalentní [1] skutečnosti, že součet vzdáleností k nadrovině od dvou nejbližších bodů, které leží na jejích opačných stranách, je maximální. Pokud taková nadrovina existuje, nazývá se optimální oddělovací nadrovina a její odpovídající lineární klasifikátor se nazývá optimální oddělovací klasifikátor . $p$ $p$ $p$

Formální popis problému

Věříme, že body vypadají takto:

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

kde má hodnotu 1 nebo −1, podle toho, do které třídy bod patří . Každý je -rozměrný skutečný vektor, obvykle normalizovaný pomocí nebo . Pokud body nejsou normalizovány, pak bod s velkými odchylkami od průměrných souřadnic bodu příliš ovlivní klasifikátor. Můžeme si to představit jako trénovací vzorek, kde je každému prvku již přiřazena třída, do které patří. Chceme, aby je podpůrný vektorový strojový algoritmus klasifikoval stejným způsobem. K tomu vytvoříme oddělovací nadrovinu, která vypadá takto: $c_{i}$ ${\mathbf {x}}_{i}$ ${\mathbf {x}}_{i}$ $p$ $[0, 1]$ $[-1,1]$

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

Vektor je kolmý na oddělující nadrovinu. Parametr se v absolutní hodnotě rovná vzdálenosti od nadroviny k počátku. Pokud je parametr b nulový, nadrovina prochází počátkem, což omezuje řešení. $\mathbf {w}$ ${\frac {b}{\|{\mathbf {w}}\|}}$

Protože nás zajímá optimální separace, zajímají nás podpůrné vektory a nadroviny, které jsou rovnoběžné s optimální a nejblíže podpůrným vektorům těchto dvou tříd. Lze ukázat, že tyto paralelní nadroviny lze popsat následujícími rovnicemi (až do normalizace).

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

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

Pokud je trénovací vzorek lineárně oddělitelný , pak můžeme volit nadroviny tak, aby mezi nimi neležel žádný bod trénovacího vzorku a pak maximalizovat vzdálenost mezi nadrovinami. Šířku pásu mezi nimi lze snadno zjistit z geometrických úvah, je rovna [2] , naším úkolem je tedy minimalizovat . Abychom z pruhu vyloučili všechny body, musíme se o to všechno ujistit ${\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}} \že jo.

To lze také napsat jako:

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

Případ lineární oddělitelnosti

Problém konstrukce optimální oddělovací nadroviny je redukován na minimalizaci , za podmínky (1). Toto je problém kvadratické optimalizace, který vypadá takto: $\|{\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}}\vpravo.

Podle Kuhn-Tuckerovy věty je tento problém ekvivalentní duálnímu problému nalezení sedlového bodu Lagrangeovy funkce

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

kde je vektor duálních proměnných. ${\mathbf {\lambda }}=({\mathbf {\lambda _{1}}},\ldots ,{\mathbf {\lambda _{n}}})$

Tento problém redukujeme na ekvivalentní problém kvadratického programování obsahující pouze duální proměnné:

\left\{{\begin{array}{lcr}-{\mathbf {L}}({\mathbf {\lambda }})=-\sum _{{i=1}}^{n}{\mathbf {\lambda _{i))}+{\frac {1}{2}}\součet _{{i=1}}^{n}\součet _{{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\\\součet _{{ i =1))^{n}{\mathbf {\lambda _{i))}c_{i}=0\\\end{array))\right.(3)

Předpokládejme, že jsme tento problém vyřešili, pak jej lze nalézt podle vzorců: $\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

V důsledku toho lze klasifikační algoritmus zapsat jako:

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

V tomto případě sumace neprobíhá přes celý vzorek, ale pouze přes podpůrné vektory, pro které . ${\mathbf {\lambda _{i))}\neq 0$

Případ lineární neoddělitelnosti

Aby algoritmus fungoval, pokud jsou třídy lineárně neoddělitelné, dovolme mu dělat chyby na trénovací množině. Představme si sadu dalších proměnných charakterizujících velikost chyby na objektech . Vezměme (2) jako výchozí bod, zmírníme omezení nerovností a také zavedeme penalizaci za celkovou chybu do minimalizovaného funkcionálu: $\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}}\vpravo.

Koeficient je parametr nastavení metody, který umožňuje upravit poměr mezi maximalizací šířky oddělovacího proužku a minimalizací celkové chyby. $C$

Podobně podle Kuhn-Tuckerovy věty redukujeme problém na nalezení sedlového bodu Lagrangeovy funkce :

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

Analogicky redukujeme tento problém na ekvivalentní:

\left\{{\begin{array}{lcr}-{\mathbf {L}}({\mathbf {\lambda }})=-\sum _{{i=1}}^{n}{\mathbf {\lambda _{i))}+{\frac {1}{2}}\součet _{{i=1}}^{n}\součet _{{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\\\součet _{{i=1}}^{n}{\mathbf {\lambda _{i}}}c_{i}=0\\\end{array}}\vpravo.

V praxi je pro sestavení podpůrného vektorového stroje vyřešen tento problém a ne (3), protože obecně není možné zaručit lineární oddělitelnost bodů do dvou tříd. Tato varianta algoritmu se nazývá soft-margin SVM algoritmus, zatímco v lineárně separovatelném případě se mluví o hard-margin SVM (hard-margin SVM).

Pro klasifikační algoritmus je zachován vzorec (4), jen s tím rozdílem, že nyní mají nejen referenční objekty, ale i objekty porušující nenulové hodnoty. V určitém smyslu je to nevýhoda, protože špičky hluku jsou často pachateli a rozhodovací pravidlo na nich postavené ve skutečnosti spoléhá na hluk. ${\mathbf {\lambda _{i))}$

Konstanta C se obvykle volí podle kritéria klouzavého řízení. Je to pracná metoda, protože problém se musí řešit znovu pro každou hodnotu C.

Pokud existuje důvod se domnívat, že vzorek je téměř lineárně oddělitelný a pouze odlehlé objekty jsou klasifikovány nesprávně, lze použít filtrování odlehlých hodnot. Nejprve se problém vyřeší pro některé C a ze vzorku se odstraní malá část objektů s největší chybovou hodnotou . Poté je problém znovu vyřešen na zkráceném vzorku. Může být nutné provést několik takových iterací, dokud nebudou zbývající objekty lineárně oddělitelné. ${\mathbf {\xi _{i))}$

Jádra

Algoritmus pro konstrukci optimální oddělovací nadroviny, navržený v roce 1963 Vladimirem Vapnikem a Aleksey Chervonenkisem , je lineární klasifikační algoritmus. V roce 1992 však Bernhard Boser, Isabelle Guyon a Vapnik navrhli metodu pro vytvoření nelineárního klasifikátoru založeného na přechodu od skalárních součinů k libovolným jádrům, tzv. kernel trick (poprvé navrhli M. A. Aizerman , E. M. Braverman a L. I. Rozonoer pro metodu potenciálních funkcí), která umožňuje stavět nelineární separátory. Výsledný algoritmus je velmi podobný lineárnímu klasifikačnímu algoritmu, pouze s tím rozdílem, že každý skalární součin ve výše uvedených vzorcích je nahrazen nelineární funkcí jádra (skalární součin v prostoru s vyšší dimenzí). V tomto prostoru již může existovat optimální separační nadrovina. Protože dimenze výsledného prostoru může být větší než dimenze původního, bude transformace odpovídající skalárním součinům nelineární, což znamená, že funkce odpovídající optimální oddělovací nadrovině v původním prostoru bude také nelineární.

Pokud má původní prostor dostatečně velký rozměr, pak může být vzorek lineárně oddělitelný.

Nejběžnější jádra:

Polynom (homogenní): $k({\mathbf {x)),{\mathbf {x}}')=({\mathbf {x}}\cdot {\mathbf {x'}})^{d}$
Polynom (heterogenní): $k({\mathbf {x)),{\mathbf {x}}')=({\mathbf {x}}\cdot {\mathbf {x'}}+1)^{d}$
Radiální základní funkce : , for $k({\mathbf {x)),{\mathbf {x}}')=\exp(-\gamma \|{\mathbf {x}}-{\mathbf {x'}}\|^{2} )$ $\gamma > 0$
Radiální funkce Gaussovy báze: $k({\mathbf {x)),{\mathbf {x}}')=\exp \left(-{\frac {\|{\mathbf {x}}-{\mathbf {x'}}\| ^{2}}{2\sigma ^{2}}}\right)$
Sigmoid : , pro téměř všechny a $k({\mathbf {x)),{\mathbf {x}}')=\tanh(\kappa {\mathbf {x}}\cdot {\mathbf {x'}}+c)$ $\kappa >0$ $c<0$

Viz také

Dimenze Vapnik-Chervonenkis

Poznámky

↑ Vyugin, 2013 , str. 86-90.
↑ K. V. Voroncov. Přednášky o podpůrných vektorových strojích Archivovány 27. září 2007 na Wayback Machine

Literatura

Vladimír Vyugin. Matematické základy teorie strojového učení a prognózování. — MTsMNO, 2013. — 390 s. - ISBN 978-5-4439-0111-4 .
Nello Cristianini, John Shawe-Taylor. Úvod do podpory vektorových strojů a dalších výukových metod založených na jádře . - Cambridge University Press, 2000. - ISBN 978-1-139-64363-4 .
Alexander Statnikov, Constantin F. Aliferis, Douglas P. Hardin. Jemný úvod k podpoře vektorových strojů v biomedicíně: Teorie a metody. - World Scientific, 2011. - ISBN 978-981-4324-38-0 .
Alexej Nefedov. Podpora vektorových strojů: Jednoduchý návod . — 2016.

Odkazy

data mining. 10. Přednáška: Metody klasifikace a prognózování. Podpora vektorového stroje // Intuit.ru
Yuri Lifshits. Support Vector Machine (slides) - 7. přednáška z kurzu Algorithms for the Web

Typy umělých neuronových sítí

Dopředná síť ( Network of Radial Base Functions )
Jednovrstvý perceptron
Vícevrstvý perceptron ( Rosenblatt • Rumelhart )
Hopfieldova síť
Markovský řetěz
Boltzmannův stroj
Limitovaný Boltzmannův stroj
Autoencoder ( Denoise autoencoder • Sparse autoencoder • Variační autoencoder )
Hluboká síť důvěry
Konvoluční neuronová síť
Hluboká konvoluční neuronová síť
Nasazení neuronové sítě
Hluboká konvoluční inverzní grafická síť
Generative Adversarial Network
Rekurentní neuronová síť
Rekurzivní neuronové sítě
dlouhodobá krátkodobá paměť
Řízený rekurentní blok
Neural Turing Machines
Obousměrná síť ( Obousměrná rekurentní neuronová síť • Obousměrná síť s dlouhodobou krátkodobou pamětí • Obousměrně řízené rekurentní neurony )
Hluboká zbytková síť
Neuronová echo síť
Metoda extrémního učení
Metoda nestabilních stavů
Podpora vektorového stroje
Kohonen síť
Samoorganizující se mapa Kohonenu
Neuronová síť kapsle
Asociativní paměť na neuronových sítích

Strojové učení a dolování dat
Úkoly	Klasifikační problém Učení bez učitele Učení za pomoci učitele Regresní analýza AutoML Pravidla asociace Extrakce funkcí Trénink vlastností Žebříčkový trénink Gramatické odvozování Online učení
Učení s učitelem	metoda k-nejbližšího souseda Naivní Bayesův klasifikátor rozhodovací strom Podpora vektorového stroje Lineární regrese Logistická regrese perceptron Soubory modelů Pytlování posilování náhodný les Relevantní vektorová metoda
shluková analýza	metoda k-means Metoda fuzzy shlukování Hierarchické shlukování EM algoritmus BŘÍZA LÉK DBSCAN OPTIKA Střední posun
Redukce rozměrů	Faktorová analýza Metoda hlavní součásti CCA ICA LDA Nezáporná expanze matice t-SNE
Strukturální prognózy	Graf pravděpodobnosti modelu Bayesovská síť Skrytý Markovův model CRF
Detekce anomálií	metoda k-nejbližšího souseda Místní úroveň emisí
Grafové pravděpodobnostní modely	Bayesovská síť Markovská síť Skrytý Markovův model
Neuronové sítě	Limitovaný Boltzmannův stroj samoorganizující se mapa Aktivační funkce Sigmoid softmax Radiální základní funkce Metoda zpětného šíření Hluboké učení Vícevrstvý perceptron Rekurentní neuronová síť dlouhodobá krátkodobá paměť Řízený rekurentní blok Konvoluční neuronová síť U-síť Autokodér
Posílení učení	Markovský proces Bellmanova rovnice Chamtivý algoritmus Q-learning SARSA Časový rozdíl (TD)
Teorie	Vapnik-Chervonenkis teorie Dilema zkreslení Teorie počítačového učení Empirická minimalizace rizika Occam se učí PAC učení Statistická teorie učení
Časopisy a konference	NeurIPS ICML ML JMLR ArXiv:cs.LG