Support Vector Machines (SVM)
V tomto cvičení rozšíříme lineární SVM klasifikátor z minulého cvičení
na nelineární. Dále si vyzkoušíme použít algoritmus nelineárního SVM na
reálných
datech.
Formulace úlohy
Rozšíření lineárního SVM na nelineární lze provést mnoha způsoby volbou
různé jádrové funkce. Vždy
se ale využívá toho, že data se vyskytují v duální úloze (ne tak v
primární, což je také jeden z důvodů, proč řešit úlohu v jejím duálním
vyjádření!) ve formě skalárních součinů. Samotný princip rozšíření je
velmi podobný rozšíření lineárního Perceptronového algoritmu na
nelineární a je velmi dobře popsán ve 4. kapitole [5].
V našem případě použijeme RBF jádrovou funkci K(xi,
xj) = exp(-||xi - xj||2/2σ2).
Tato jádrová funkce odpovídá mapování původních dat do nekonečně
dimenzionálního prostoru. Nemůžeme tedy jako ve cvičení na Perceptron
jednoduše vyřešit úlohu ve vícedimenzionálním prostoru (ani bychom tam
nedokázali vyjádřit namapovaná data), ale musíme důsledně využívat
kernelové funkce všude tam, kde bychom jinak použili skalární součin.
Zadání
- (Nejlépe doma)
Prostudujte rozšíření lineárního SVM na nelineární v textu
[5] v
kapitole 4.
- Rozšiřte lineární SVM klasifikátor z minulého cvičení na
nelineární pomocí RBF jádra.
Demonstrujte funkčnost na jednoduchém příkladě (vygenerujte si ho
pomocí
createdata).
Nápověda 1:
Pro vykreslení výsledku použijte funkci pboundary
stejně jako jsme ji použili ve cvičení na Perceptron. Místo
funkce classif_quadrat_perc
napište funkci classif_rbf_svm,
se stejnými parametry a patřičně
upraveným modelem.
Nápověda 2: Funkce
classif_rbf_svm funguje podobně jako její perceptronový
protějšek. Vstupem jsou testovací data (ty dodá funkce
pboundary automaticky) a struktura
model, která může obsahovat libovolné
položky, které potřebujete, abyste mohli data klasifikovat (tj. přinejmenším
všechny potřebné parametry SVM klasifikátoru). Výstupem je vektor stejné
délky jako testovací data obsahující +1 nebo -1 podle
toho, jak byla data naším klasifikátorem klasifikována.
- Vyzkoušejte několik různých datových sad.
- Navržený klasifikátor použijte ke klasifikaci znaků data_33rpz_cv08.mat
pomocí dvou příznaků
x = (součet hodnot
pixelů v levé
polovině obrázku) - (součet
hodnot pixelů v pravé
polovině obrázku)
y =
(součet hodnot
pixelů v horní
polovině obrázku) - (součet
hodnot pixelů v dolní
polovině obrázku)
Nápověda:
Kvůli numerické stabilitě normalizujte rozsah hodnot do intervalu <-1,+1>.
- Experimentujte s nastavenim parametrů C a σ.
Bonusová úloha
Pro úlohu klasifikace
znaků najděte optimální hodnotu parametru σ RBF jádra
pomocí krosvalidace (viz cvičení na Parzenova
okna).
Doporučená literatura
[1] SVM
[2] Archív
zápisů z přednášek rozpoznávání (33RPZ)
[3]
Quadratic
programming
[4] Nelineární perceptron
[5] Christopher J. C.
Burges. A Tutorial On
Support Vector Machines for
Pattern Recognition.
Created
by Jan Šochman, 2.12.2007. Last update 26.5.2009