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í

  1. (Nejlépe doma) Prostudujte rozšíření lineárního SVM na nelineární v textu [5] v kapitole 4.

  2. 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.

  3. Vyzkoušejte několik různých datových sad.

  4. 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>.

  5. 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