Support vector machines

Support vector machines (SVM) neboli metoda podpůrných vektorů je metoda strojového učení s učitelem, sloužící zejména pro klasifikaci a také pro regresní analýzu. Na jejím vynalezení se podílel zejména Vladimir Vapnik.

Popis metody

Základem metody SVM je lineární klasifikátor do dvou tříd. Cílem úlohy je nalézt nadrovinu, která prostor příznaků optimálně rozděluje tak, že trénovací data náležející odlišným třídám leží v opačných poloprostorech. Optimální nadrovina je taková, že hodnota minima vzdáleností bodů od roviny je co největší. Jinými slovy, okolo nadroviny je na obě strany co nejširší pruh bez bodů (maximální odstup, angl. maximal margin, česky je tento pruh někdy nazýván také pásmo necitlivosti nebo hraniční pásmo). Na popis nadroviny stačí pouze body ležící na okraji tohoto pásma a těch je obvykle málo - tyto body se nazývají podpůrné vektory (angl. support vectors) a odtud název metody.

Důležitou součástí techniky Support vector machines je jádrová transformace (angl. kernel transformation) prostoru příznaků dat do prostoru transformovaných příznaků typicky vyšší dimenze. Tato jádrová transformace umožňuje převést původně lineárně neseparovatelnou úlohu na úlohu lineárně separovatelnou, na kterou lze dále aplikovat optimalizační algoritmus pro nalezení rozdělující nadroviny. Trik je v tom, že nadrovina je popsána a při výpočtech je použitý pouze skalární součin, a skalární součin transformovaných dat <f(x), f(x1)> ve vysokorozměrném prostoru se nepočítá explicitně, ale počítá se K(x, x1), tj. hodnota jádrové funkce K na datech v původním prostoru parametrů.

Používají se různé kernelové transformace. Intuitivně, vyjadřují podobnost dat, tj. svých dvou vstupních argumentů. Výhodou této metody (a jiných metod založených na jádrové transformaci) je, že transformace se dá definovat pro různé typy objektů, nejen body v Rⁿ. Např. pro grafy, stromy, posloupnosti DNA atd.

Lineární SVM

Lineární SVM je jednodušší varianta SVM metody, při které zůstáváme v původním prostoru příznaků a nedochází k žádné jádrové transformaci. Výsledkem potom je čistě lineární klasifikátor.

Separabilní případ

Optimální rozdělující nadrovina a hraniční pásmo pro lineární SVM. Body na okrajích pásma jsou podpůrné vektory.

Nejjednodušším případem použití SVM je lineární klasifikátor pro lineárně separabilní data, tedy data, ve kterých lze obě třídy od sebe rozdělit nadrovinou. Mějme množinu trénovacích dat v podobě dvojic $({\vec {x}}_{i},y_{i})$, kde ${\vec {x}}_{i}$ je vektor a ${y_{i}}$ je informace od učitele nabývající hodnoty +1 nebo -1.

Nadrovinu, rozdělující body do dvou tříd, lze popsat rovnicí

${\vec {w}}\cdot {\vec {x}}+b=0,$

(1)

kde ${\vec {w}}$ je normála nadroviny, ${||{\vec {w}}||}$ její Eukleidovská norma a ${|b|/||{\vec {w}}||}$ vzdálenost nadroviny od počátku souřadnic.

Nejkratší vzdálenosti nejbližších bodů na každé straně nadroviny od ní značíme ${d_{+}}$ a ${d_{-}}$. Součet ${d_{+}+d_{-}}$ pak představuje šířku hraničního pásma. Cílem trénování SVM pak je nalézt takovou rozdělující nadrovinu, aby hraniční pásmo bylo nejširší možné. Body, ležící na hranici tohoto pásma a jejichž odebráním by se poloha optimální nadroviny změnila, jsou podpůrné vektory (angl. support vectors).

Formulace úlohy

Předpokládejme, že pro všechny body platí

${\vec {x}}_{i}\cdot {\vec {w}}+b\geq +1\quad {\text{pro }}y_{i}=+1,$

(2)

${\vec {x}}_{i}\cdot {\vec {w}}+b\leq -1\quad {\text{pro }}y_{i}=-1,$

(3)

což lze sloučit do jediné nerovnice

$y_{i}({\vec {x}}_{i}\cdot {\vec {w}}+b)-1\geq 0\quad \forall i.$

(4)

Body, pro které platí rovnost v (2), leží na nadrovině $H_{1}:{\vec {w}}\cdot {\vec {x}}+b=1$.

Body, pro které platí rovnost v (3), leží na nadrovině $H_{2}:{\vec {w}}\cdot {\vec {x}}+b=-1$.

Nadroviny $H_{1}$ a $H_{2}$ jsou kolmé na stejný normálový vektor ${\vec {w}}$ a jejich vzdálenost od rozdělující nadroviny je $1/||{\vec {w}}||$. Šířka hraničního pásma tedy je $2/||{\vec {w}}||$ a nadroviny s nejširším pásmem můžeme určit minimalizací $||{\vec {w}}||$ vzhledem k podmínkám (4).

Pozn.: Z praktických důvodů se místo $||{\vec {w}}||$ minimalizuje $||{\vec {w}}||^{2}/2$.

Lagrangeovská formulace

Lagrangeovská formulace úlohy má dvě hlavní výhody:

• Namísto podmínky (4) je omezení na samotné Lagrangeovy multiplikátory, s čímž se lépe pracuje.
• Trénovací data se ve všech výrazech vyskytují jen ve skalárních součinech, což je velmi důležité u nelineárního případu.

Zavedené nezáporné Lagrangeovy multiplikátory $\lambda _{i},i=1,\dots ,l$, jeden pro každou nerovnost v (4).

Lagrangeova funkce:

$L_{P}={\frac {1}{2}}||{\vec {w}}||^{2}-\sum _{i=1}^{l}\lambda _{i}y_{i}({\vec {x}}_{i}\cdot {\vec {w}}+b)+\sum _{i=1}^{l}\lambda _{i}$

(5)

Je třeba minimalizovat $L_{P}$ vzhledem k ${\vec {w}}$, ${\displaystyle }$ a derivace $L_{P}$ vzhledem ke všem $\lambda _{i}$ musejí být nulové, vše za omezení $\lambda _{i}\geq 0$.

Jedná se o konvexní problém kvadratického programování, proto lze místo toho řešit duální problém - hledání maxima $L_{P}$ za následujících podmínek: že gradient $L_{P}$ vzhledem k ${\vec {w}}$ a $b$ je nulový, a že $\lambda _{i}\geq 0$.

Aby gradient podle ${\vec {w}}$ a $b$ byl nulový, musí platit

${\vec {w}}=\sum _{i}\lambda _{i}y_{i}{\vec {x}}_{i}\;$

(6)

$\sum _{i}\lambda _{i}y_{i}=0\;$

(7)

Dosazením do (5) se získá duální Lagrangeova funkce ($L_{P}$ - primární, $L_{D}$ - duální)

$L_{D}=\sum _{i}\lambda _{i}-{\frac {1}{2}}\sum _{i,j}\lambda _{i}\lambda _{j}y_{i}y_{j}\mathbf {x} _{i}\cdot \mathbf {x} _{j}\;$

(8)

Trénování SVM spočívá v maximalizaci $L_{D}$ vzhledem k $\lambda _{i}$, při omezení (8) a $\lambda _{i}\geq 0$, s řešením daným (6).

Máme jedno $\lambda _{i}$ pro každý trénovací bod, přičemž body, pro které $\lambda _{i}>0$ jsou podpůrné vektory a leží v nadrovinách $H_{1}$ nebo $H_{2}$, zatímco všechny ostatní mají $\lambda _{i}=0$ a leží buď v jedné z nadrovin, nebo na té straně od nich, pro kterou platí ostrá nerovnost v (4).

Podpůrné vektory jsou nejdůležitějšími body trénovací množiny - pokud by se všechny ostatní body odstranily, novým natrénováním by se získala tatáž rozdělující nadrovina.

Karushovy-Kuhnovy-Tuckerovy podmínky

Karushovy-Kuhnovy-Tuckerovy (KKT) podmínky jsou nutné podmínky pro optimální řešení v úloze nelineárního programování za předpokladu splnění určitých podmínek regularity. Pro konvexní problémy jsou zároveň i postačujícími podmínkami.

SVM představují konvexní problém a podmínky regularity jsou pro ně splněné vždy. KKT podmínky jsou tím pádem nutné a postačující, aby ${\vec {w}},b,\lambda$ byly řešením.

Pro primární problém KKT podmínky vypadají následovně:

${\begin{aligned}{\frac {\partial }{\partial w_{\nu }}}L_{P}=w_{\nu }-\sum _{i}\lambda _{i}y_{i}x_{i\nu }=0&\qquad \nu =1,\dots ,d\\{\frac {\partial }{\partial b}}L_{P}=-\sum _{i}\lambda _{i}y_{i}=0\\y_{i}(\mathbf {x} _{i}\cdot \mathbf {w} +b)-1\geq 0&\qquad i=1,\dots ,l\\\lambda _{i}\geq 0&\qquad \forall i\\\lambda _{i}(y_{i}(\mathbf {w} \cdot \mathbf {x} _{i}+b)-1)=0&\qquad \forall i\end{aligned}}$

KKT podmínky hrají roli při numerickém řešení SVM úlohy (viz sekce Metody řešení).

Testovací fáze

V testovací fázi klasifikujeme neznámé body, u nichž nevíme, do které třídy skutečně náležejí. Toto zjistíme tak, že spočítáme $\operatorname {sgn}({\vec {w}}\cdot {\vec {x}}+b)$ a výsledné znaménko nám řekne, na které straně rozdělující nadroviny daný bod leží. Podle toho ho přiřadíme do odpovídající třídy.

Neseparabilní případ

Složitější variantou lineárních SVM je případ, kdy se snažíme lineárně oddělit data, která nejsou plně lineárně separovatelná. Například se může jednat o zašuměná data, kde se jednotlivé třídy částečně překrývají a není proto možné najít jednoznačnou hranici. V takovémto případě chceme najít takovou rozdělující nadrovinu, aby k chybné klasifikaci docházelo co nejméně.

V takovéto situaci se provádí zmírnění podmínek (2) a (3) s přidanou cenou za jejich porušení, a to zavedením přídavné proměnné $\xi$:

${\vec {x}}_{i}\cdot {\vec {w}}+b\geq +1-\xi _{i}\quad {\text{pro }}y_{i}=+1,$

(14)

${\vec {x}}_{i}\cdot {\vec {w}}+b\geq -1-\xi _{i}\quad {\text{pro }}y_{i}=-1,$

(15)

$\xi _{i}\geq 0\quad \forall i$

(16)

Pro přiřazení ceny navíc za chyby se pak minimalizovaná funkce stanoví místo $||{\vec {w}}||^{2}/2$ jako $||{\vec {w}}||^{2}/2+C\cdot \sum _{i}\xi _{i}$, kde $C$ je volitelný parametr a větší $C$ znamená větší penalizaci chyb.

Duální problém pak je:

Maximalizovat

$L_{D}=\sum _{i}\lambda _{i}-{\frac {1}{2}}\sum _{i,j}\lambda _{i}\lambda _{j}y_{i}y_{j}{\vec {x}}_{i}\cdot {\vec {x}}_{j}$

(17)

za podmínek

$0\leq \lambda _{i}\leq C$

(18)

$\sum _{i}\lambda _{i}y_{i}=0.$

(19)

Řešení je opět

${\vec {w}}=\sum _{i=1}^{N_{S}}\lambda _{i}y_{i}{\vec {x}}_{i},$

(20)

kde $N_{S}$ je počet podpůrných vektorů.

Jediný rozdíl oproti předchozímu případu je tedy ten, že $\lambda _{i}$ nyní jsou shora omezené $C$.

Primární Lagrangeova funkce je

$L_{P}={\frac {1}{2}}||{\vec {w}}||^{2}+C\sum _{i}\xi _{i}-\sum _{i}\lambda _{i}\{y_{i}({\vec {x}}_{i}\cdot {\vec {w}}+b)-1+\xi _{i}\}+\sum _{i}\mu _{i}\xi _{i},$

(21)

kde $\mu _{i}$ jsou Lagrangeovy multiplikátory zavedené pro zajištění $\xi _{i}\geq 0$.

KKT podmínky pro primární problém pak jsou

${\frac {\partial L_{P}}{\partial w_{\nu }}}=w_{\nu }-\sum _{i}\lambda _{i}y_{i}x_{i\nu }=0$

(22)

${\frac {\partial L_{P}}{\partial b}}=-\sum _{i}\lambda _{i}y_{i}=0$

(23)

${\frac {\partial L_{P}}{\partial \xi _{i}}}=C-\lambda _{i}-\mu _{i}=0$

(24)

$y_{i}(\mathbf {x} _{i}\cdot \mathbf {w} +b)-1+\xi _{i}\geq 0$

(25)

$\xi _{i}\geq 0$

(26)

$\lambda _{i}\geq 0$

(27)

$\mu _{i}\geq 0$

(28)

$\lambda _{i}\{y_{i}({\vec {x}}_{i}\cdot {\vec {w}}+b)-1+\xi _{i}\}=0$

(29)

$\mu _{i}\xi _{i}=0$

(30)

kde $i$ jde od 1 do počtu trénovacích bodů, $\nu$ jde od 1 do dimenze dat.

Práh $b$ lze určit na základě podmínek (29) a (30) dosazením jednoho z trénovacích bodů.

Nelineární SVM

Ilustrace jádrové transformace: původní data ve 2D prostoru (vlevo) nejsou lineárně separabilní. Po transformaci do 3D prostoru (vpravo) je lze oddělit rovinou. Použita jádrová funkce $K(x_{i},x_{j})=(x_{i}\cdot x_{j})^{2}$, zobrazení $\Phi ({\vec {x}})=(x_{1}^{2},{\sqrt {2}}x_{1}x_{2},x_{2}^{2})$.

V lineárním případě se jednalo o data, která byla plně nebo téměř lineárně separovatelná. Obecně toto však často neplatí a z toho důvodu byly zavedeny nelineární SVM. Základní myšlenkou je použití tzv. jádrového triku (anglicky kernel trick), s jehož pomocí se provádí transformace dat z původního prostoru příznaků do prostoru vyšší dimenze, ve kterém již jsou lineárně separabilní.

Jinými slovy, provádíme zobrazení trénovacích dat z původního prostoru do jiného eukleidovského prostoru ${\mathcal {H}}$, ve kterém toto už platit bude:

$\Phi :\mathbf {R} ^{d}\mapsto {\mathcal {H}}$

(31)

Prostor ${\mathcal {H}}$ je obvykle mnohem větší, i až nekonečné, dimenze než původní prostor, dále značený ${\mathcal {L}}$, a v ${\mathcal {L}}$ většinou neexistuje vektor, jehož obrazem by byl vektor ${\vec {w}}$.

Jelikož v rovnicích (17-19) se trénovací data vyskytují jen v podobě skalárních součinů mezi sebou, nemusíme vůbec znát zobrazení $\Phi$, stačí pouze znát vztah pro skalární součin $\Phi (x_{i})\cdot \Phi (x_{j})$. Využívá se tzv. jádrová funkce (angl. kernel function}) $K(x_{i},x_{j})=\Phi (x_{i})\cdot \Phi (x_{j})$.

V testovací fázi lze použití ${\vec {w}}$ také obejít - pro určení, do které třídy bod spadá, počítáme funkci signum z výrazu

$f(x)=\sum _{i=1}^{N_{S}}\lambda _{i}y_{i}\Phi ({\vec {s}}_{i})\cdot \Phi ({\vec {x}})+b=\sum _{i=1}^{N_{S}}\lambda _{i}y_{i}K({\vec {s}}_{i},{\vec {x}})+b,$

(32)

kde ${\vec {s}}_{i}$ jsou podpůrné vektory.

Příklady nelineárních SVM

Mezi často používané jádrové funkce patří například:

• Polynom stupně $p$:

$K(\mathbf {x} ,\mathbf {y} )=(\mathbf {x} \cdot \mathbf {y} +1)^{p}$

(33)

• Radiální bázové funkce:

$K(\mathbf {x} ,\mathbf {y} )=e^{-||\mathbf {x} -\mathbf {y} ||^{2}/2\sigma ^{2}}$

(34)

• Dvouvrstvá neuronová síť:

$K(\mathbf {x} ,\mathbf {y} )=\tanh(\kappa \mathbf {x} \cdot \mathbf {y} -\delta )$

(35)

Metody řešení

Problém optimalizace pomocí podpůrných vektorů lze řešit analyticky jen pokud je množství trénovacích dat velmi malé nebo v separovatelném případě pokud je předem známo, která data se stanou podpůrnými vektory. Při většině reálných použití je třeba rovnice (17-19) řešit numericky (se skalárními součiny nahrazenými $K(x,y)$).

Pro jednodušší úlohy postačují standardní metody řešení konvexních úloh kvadratického programování s lineárními vazbovými podmínkami, pro složitější úlohy pak existují speciální techniky řešení.

Základní postup:

1. Volba jádrové funkce a jejích parametrů.
2. Volba parametru $C$ reprezentujícího kompromis mezi minimalizací chyby na trénovací množině a maximalizací šířky hraničního pásma.
3. Vyřešení duálního problému pomocí vhodné techniky kvadratického programování:
   1. Určení podmínek optimality (KKT), které musí řešení splňovat.
   2. Definování strategie dosažení optimality zvyšováním duální váhové funkce vzhledem k vazbovým podmínkám.
   3. U rozsáhlejších úloh: volba algoritmu dekompozice tak, aby bylo třeba pracovat jen s částí dat najednou.
4. Výpočet parametru $b$ na základě podpůrných vektorů.
5. Klasifikace nových bodů.

Algoritmy dekompozice pro rozměrné úlohy:

Příkladem je "hroudová" metoda (angl. "chunking" method) - SVM se nejdříve natrénuje na malé podmnožině dat, na zbytku se otestuje a udělá se seznam chybných rozhodnutí seřazený podle toho, jak moc byly porušeny KKT podmínky. Další trénovací množina se vytvoří z prvních $N$ bodů ze seznamu a ze všech $N_{S}$ už nalezených podpůrných vektorů, kde $N+N_{S}$ je určeno heuristicky. Proces pokračuje dokud pro všechny body není rozhodnuto správně.

Tato metoda vyžaduje, aby počet podpůrných vektorů $N_{S}$ byl dostatečně malý na to, aby se Hessova matice o rozměru $N_{S}\times N_{S}$ vešla do paměti počítače. Pro ještě rozměrnější úlohy existují jiné algoritmy.

SVM regrese

Kromě klasifikace se SVM využívají také pro regresní analýzu.

SVM regrese využívá $\varepsilon$-necitlivou ztrátovou funkci (angl. $\varepsilon$-insensitive loss function) - pokud rozdíl mezi očekávanou a skutečnou hodnotou je méně než $\varepsilon$, není to považováno za chybu. Tedy chceme, aby platilo

$-\varepsilon \leq \mathbf {w} \cdot \mathbf {x_{i}} -b-y_{i}\leq \varepsilon .$

(36)

Opět se minimalizuje $||{\vec {w}}||$ a jsou zavedené přídavné proměnné (angl. slack variables) $\xi _{i}$ a ${\hat {\xi }}_{i}$.

Pro lineární $\varepsilon$-necitlivou funkci je pak úkolem minimalizovat

$\min _{w,b,\xi ,{\hat {\xi }}}C\sum _{i}(\xi _{i}+{\hat {\xi }}_{i})+{\frac {1}{2}}||\mathbf {w} ||^{2}$

(37)

za podmínek

$({\vec {w}}\cdot {\vec {x_{i}}}-b-y_{i})+\xi _{i}\geq -\varepsilon$

$({\vec {w}}\cdot {\vec {x_{i}}}-b-y_{i})-{\hat {\xi }}_{i}\leq \varepsilon$

$\xi _{i},{\hat {\xi }}_{i}\geq 0\quad i=1,\dots ,m$

Pro nelineární regresní funkce se používá podobný postup jako u klasifikace - duální Lagrangeova funkce, jádrová transformace, atd.

Namísto pevně daného parametru $\varepsilon$ je také možné stanovit maximální podíl bodů, pro které nebude platit vztah (36).

Uplatnění SVM

Support Vector Machines mají široké uplatnění, zejména pro klasifikaci. Reálné aplikace zahrnují například oblasti zpracování textu, počítačového vidění (např. rozpoznávání obličejů, rozpoznávání ručně psaného textu) nebo bioinformatiky (např. klasifikace proteinů).

Oproti některým srovnatelným typům klasifikátorů mají SVM několik výhod:

• Trénování vždy najde globální řešení. Na rozdíl od například neuronových sítí u SVM neexistují žádná lokální minima, která by nebyla zároveň globálním minimem.
• Reprodukovatelné výsledky, nezávislé na volbě konkrétního algoritmu nebo např. počátečního bodu.
• Malý počet parametrů modelu, které je třeba určit po výběru typu jádrové funkce (může být zároveň i nevýhodou - viz níže).

SVM s sebou nese i problémy či nevýhody:

• Správná funkce SVM z velké části záleží na vhodné volbě jádrové funkce. Jakmile ji stanovíme, máme jen jeden parametr, tedy penaltu chyb. Správnou jádrovou funkci ale nemusí být snadné najít.
• U velmi rozsáhlých úloh (miliony podpůrných vektorů) je problém s rychlostí a paměťovými nároky. Vhodné algoritmy pro jejich řešení jsou stále ještě předmětem výzkumu.

Myšlenky vycházející ze SVM (málo podpůrných vektorů, maximální odstup a jádrové transformace) byly také použity i pro návrh algoritmů pro další úlohy strojového učení, např. úlohy binární klasifikace na zašuměných datech (tzv. soft margin), diskrétní klasifikace (do více tříd), regrese, jádrová analýza hlavních komponent (PCA), ranking, strukturované učení, učení z jedné třídy (one class support vector, single class data description).

Odkazy

Literatura

• Bernhard Schölkopf, Alex Smola: Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond (Adaptive Computation and Machine Learning), MIT Press, Cambridge, MA, 2002, ISBN 0-262-19475-9.
• Ingo Steinwart, Andreas Christmann: Support Vector Machines, Springer, New York, 2008. ISBN 978-0-387-77241-7. 602 pp.
• Nello Cristianini, John Shawe-Taylor: Kernel Methods for Pattern Analysis, Cambridge University Press, Cambridge, 2004, ISBN 0-521-81397-2
• Christopher J. C. Burges: A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, 2(2):121-167, 1998.
• Vladimir Vapnik: Statistical Learning Theory, Wiley, Chichester, GB, 1998.
• Vladimir Vapnik: The Nature of Statistical Learning Theory, Springer Verlag, New York, NY, USA, 1995.
• K. Bennett, C. Campbell: Support Vector Machines: Hype or Hallelujah?, ACM SIGKDD Explorations Newsletter, 2(2):1-13, New York: ACM, 2000
• R. Freund, F. Girosi, E. Osuna: An Improved Training Algorithm for Support Vector Machines, Neural Networks for Signal Processing [1997] VII. Proceedings of the 1997 IEEE Workshop, pp. 276-285, IEEE, 1997

Externí odkazy

• Obrázky, zvuky či videa k tématu metoda podpůrných vektorů na Wikimedia Commons

Autoritní data	NKC: ph606738 BNF: cb16627142b (data) GND: 4505517-8 LCCN: sh2008009003 NLI: 987007539991605171