Support vector machines (SVM)
(Algoritmy podpůrných vektorů)
Řada metod strojového učení se vyznačuje jednoduchými a efektivními algoritmy učení, např. jednovrstvé umělé neuronové sítě. Ale z hlediska řešení obecné úlohy najít hranice, které oddělují určité třídy ve vstupním prostoru, jsou velmi silně omezeny schopností naučit se pouze lineární oddělovače (přímky, roviny, nadroviny).
Na druhé straně existují metody jako mnohovrstvé umělé neuronové sítě (např. sigmoidální trénované zpětným šířením chyb - backpropagation), které jsou schopny representovat obecné nelineární funkce. Jejich nevýhodou však je často velmi obtížné učení, protože prakticky vždy existuje riziko uvíznutí v lokálním minimu chybové funkce a navíc je učení silně komplikováno hledáním vysokého počtu vah v mnohadimensionálním prostoru.
K alternativním, relativně novým metodám patří podpůrné vektory {support vector machines, SVM), které tvoří určitou kategorii tzv. jádrových algoritmů (kernel machines). Tyto metody se snaží využít výhody poskytované efektivními algoritmy pro nalezení lineární hranice a zároveň jsou schopny representovat vysoce složité nelineární funkce. Jedním ze základních principů je převod daného původního vstupního prostoru do jiného, vícedimensionálního, kde již lze od sebe oddělit třídy lineárně.
Tato myšlenka je v podstatě jednoduchá, jak ukazuje obrázek obr. 1. V původním dvourozměrném prostoru jsou dvě třídy, oddělené nelineárně kružnicí. Přidáním další dimenze vznikne možnost prvkům třídy uvnitř kružnice přidat další souřadnici, která je posune např. nahoru podél nové osy x3, takže pro oddělení obou tříd již lze použít rovinu rovnoběžnou s rovinou danou osami xx a x2
Otázka je, kam nejlépe lineární hranici umístit tak, aby byla vedena co nejefektivněji z hlediska kategorizace budoucích dat, která nebylo při trénniku možno použít. Samotná optimalizace umístění hranice je záležitost komplikovanější, ale v zásadě řešitelná.
lineární oddělení obou tříd zde není
možné
X.
•Í1+J+-
umělé zvýšení
počtu dimenzí
(zde o xj
X
I
pozice elementů jedné třídy jsou změnény podél nové dimenze
^ ^ '
lineami oddělení obou tříd pomocí ^roviny


^
**:■■
X
Obr. 1. Princip vzniku možnosti lineárního oddělení dvou tříd s nelineárními hranicemi pomocí přidané dimenze.
Obr. 2 znázorňuje dvourozměrný vstupní prostor definovaný atributy x = (jcl5 x2), přičemž pozitivní trénovací příklady, dávající hodnotu y = +1, jsou uvnitř kruhu a negativní fy = -1) vně. Je zřejmé, že lineární oddělovací hranice neexistuje. Když se vstupní data vhodně modifikují, může vzniknout nový vstupní prostor, kde jsou pozitivní i negativní příklady oddělitelné lineárně. Modifikací může být mapování vstupního vektoru x do nového vektoru s jinými hodnotami atributů: F(x).
Konkrétně zde lze každý dvourozměrný vektor změnit přidáním třetího atributu založeného na prvních dvou, takže místo původních dvou atributů (xu x2) budou tři, definované následujícími funkcemi fv f2, f3:
1.5
1
0.5
>f       0
-0.5
-1
-1.5
0   08    ° § o   <y	0	o n	°o°o	o	o   o 0
o O     0°   /	•		•	o \cP0o°  o	
o /     •	♦.				\   9ř
		•			o
					
	•		•     •		o
„ o\					p
0   o\	• •	•	• • • •		o   0
o           ^   \	\   •	•	• •/		Do        ° o 0
o        ■"   Q			•   ^<o		
					0              °
	0    0	0			
§>  o    o	Un	uu			0
o  o      o	°    O	(9	D°            %		n  rŮ
-1.5
-0.5
0.5
1.5
Obr. 2. Dvourozměrný prostor s trénovacími příklady pozitivními # a negativními O. Skutečná oddělovací hranice je představována funk-
ci x.
< 1.
Obr. 3. Tatáž data mapovaná do trojrozměrného
prostoru {x^ ,x1,^J2x]x2). Kruhová rozhodovací hranice z obr. 2 se stane lineární.
Obrázek 3 ukazuje původní data v novém prostoru, a důležité je, že nyní jsou obě třídy lineárně separovatelné. Tento jev je obecný: při mapování do prostoru s dostatečným počtem dimenzí lze nakonec vždy najít lineární oddělovač (nadrovinu). V příkladu byly použity pouze tři dimenze (i když konkrétně zde by se daly použít dokonce jen dvě, tj. fy af2), ale obecně platí, že TV datových bodů je možno vždy (kromě některých speciálních případů) lineárně oddělit v prostoru s N-l nebo více dimenzemi (důkaz zde nebude probírán).
Řešení je ovšem komplikováno faktem, že v c/-rozměrném prostoru je lineární oddělovač definován rovnicí, která má d parametrů, takže hrozí nebezpečí, že dojde ke ztrátě obecnosti klasifikátoru "přetrénováním" pokud d ~ N; dojde totiž k podobnému efektu, jako např. při prokládání datových bodů polynomem vysokého stupně (aproximace neznámé funkce). Uvedená potíž je proto důvodem k tomu, že zmiňovaná metoda jádrových funkcí se snaží najít optimální lineární oddělovač, tj. takový, který poskytuje co nejširší pásmo mezi ním a pozitivními příklady na jedné straně a negativními na druhé (a zároveň podporuje robustnost klasifikace), jak ilustruje následující obr. 4.
support vector
Obr. 4. Pohled na optimální oddělovací hranici (viz obr. 3) vzniklý projekcí do prvních dvou dimenzí.
Optimální lineární oddělovač se v algoritmu support vector machines hledá pomocí metody kvadratického programování. Zde je jistá obdoba s hledáním maxima jako u lineárního programování, problém je však složitější. Předpokládejme, že jsou příklady Xj s klasifikací yt = ±la cílem je najít optimální oddělovač. Problém lze převést na hledání hodnot parametrů a„ které maximalizují výraz
přičemž platí omezení
a. > 0 a  V a.y. = 0.
Výraz vak dvě významné vlastnosti: jednak má jediné globální maximum, které lze efektivně najít, a dále datové body do výrazu vstupují ve formě skalárního součinu jednotlivých dvojic. Tato druhá vlastnost platí i pro rovnici lineárního oddělovače.
Jakmile jsou jednou spočteny optimami parametry a„ je oddělovač dan rovnici
h(x)=sign ^«^(x-x,) l
Vzhledem k omezením při hledání a, platí, že lineární oddělovač má nulové váhy a, pro každý datový bod kromě těch bodů, které jsou nejblíže vlastnímu oddělovači. Tyto nejbližší body se právě nazývají support vectors - v překladu podpůrné vektory vzhledem k tomu, že jejich funkcí je "podpora" oddělovací nadroviny, která na nich spočívá; ostatní body-vektory nejsou pro oddělovač vůbec zapotřebí, takže metoda SVM je schopna najít ty trénovací příklady, které jsou pro nalezení oddělovače tříd podstatné (obvykle učící algoritmy používají všechny trénovací příklady, což při vysokém počtu bodů může vést k nízké efektivitě).
Velkou výhodou je skutečnost, že těchto podpůrných vektorů je obvykle mnohem méně než datových bodů, takže efektivní počet parametrů definujících optimální oddělovač je pak mnohem menší než N.
Běžně nelze očekávat, že lineární oddělovač bude nalezen přímo v originálním vstupním prostoru x (i když to nelze vyloučit). Je ovšem zřejmé, že lineární oddělovače lze hledat ve vícerozměrném prostoru F(x) jednoduše tím, že se nahradí člen x, • x- členem F(x,)-F(x). Tato náhrada má stejný efekt pro každý učící algoritmus, ale zde vzhledem ke skalárnímu součinu existují zvláštní vlastnosti. Platí totiž, že F(x)-F(Xj) není většinou nutné stanovovat přes výpočty F pro všechny body. Ve výše uvedeném příkladu se třemi dimenzemi lze ukázat, že
F(xi)-F(xJ) = (xrxj)2.
Výraz (xi -x )'se nazývá jádrová funkce (kernel function) K(xt, x). V souvislosti s algoritmy SVM je to funkce, která může být aplikována na dvojice vstupních dat k vyhodnocení skalárního součinu v nějakém odpovídajícím prostoru. Z toho tedy plyne, že lze najít lineární oddělovače ve vícerozměrném prostoru F(x) jednoduše náhradou x, • xy jádrovou funkcí Äľ(x„ xy). Jinak řečeno, lze provádět učení ve vícerozměrném prostoru, ale stačí počítat pouze jádrové funkce místo úplného seznamu atributů pro každý datový bod.
Na uvedené jádrové funkci K(xř, x ŕ) = (xf ■ x ř): není nic zvláštního, pouze odpovídá jednomu z možných vícerozměrných prostorů; zároveň je řada dalších jádrových funkcí, které odpovídají jiným prostorům. Existuje tzv. Mercerův teorém, který říká, že jakákoliv "rozumná" jádrová funkce [tj. v principu taková, kde matice Ky =K(xi,xj) je positivně defmitní] odpovídá nějakému prostoru atributů. Tyto prostory mohou být velmi vysoce rozsáhlé, například polynomická jádrová funkce K(xjyX ,.) = (1 + xř -X ) odpovídá prostoru atributů, jehož dimenze roste exponenciálně s d. S použitím takovýchto jádrových funkcí lze nalézt lineární oddělovače efektivně v prostorech majících miliardy (nebo v některých případech nekonečně mnoho) rozměrů.
Nalezené lineární oddělovače lze samozřejmě mapovat zpět do původního prostoru, čímž lze získat libovolně zvlněné, nelineární hranice mezi pozitivními a negativními příklady.
Jakýkoliv algoritmus, který lze převést na uvedený skalární součin, může být náhradou tohoto součinu jádrovou funkcí převeden na jádrovou (kernelized) verzi, např. £-NN (nejbližší soused), perceptronové učení, a další.
Algoritmus využívající jádrové funkce je v praxi využíván např. pro rozeznávání rukou psaných číslic nebo na úlohy s velmi vysokým počtem atributů, úspěšně funguje také jako filtr např. textových dokumentů, které se často vyznačují desítkami tisíc atributů (tj. různých slov), apod.
Existuje dostupný software, např. velmi často se používá program, jehož autorem je Joachim Thorsten; více informací viz URL http : //www. j oachims . org/
Binární verze lze pro Linux a Windows získat zdarma (ovšem pouze pro akademické účely) na následujících URL:
ftp://ftp-ai.cs.uni-dortmund.de/pub/Users/thorsten/ svm_light/current/svm_light_linux.tar.gz
ftp://ftp-ai.cs.uni-dortmund.de/pub/Users/thorsten/ svm_light/current/svm_light_windows.zip