Support Vector Machines (SVM)

V této úloze budeme navrhovat klasifikátor, který maximalizuje vzdálenost oddělující nadplochy od trénovacích dat, zvaný Support Vector Machines (SVM). Dnes implementujeme lineární verzi SVM, kterou v příštím cvičení rozšíříme na nelineární a vyzkoušíme na reálných datech.

Zadání

Příprava na cvičení (doma a na přednášce):
  1. Nastudujte formulaci optimalizační úlohy, kterou řeší SVM algoritmus (rovnice (1) a (2) pro lineárně separabilní, (4) a (5) pro neseparabilní data, viz [2]). O jaký typ optimalizační úlohy jde? Porovnejte s perceptronem.
  2. Ujasněte si geometrický význam jednotlivých proměných jak v primární, tak v duální úloze. Vaše porozumnění by mělo být takové, že až budete na cvičení dotázáni (budete), budete schopni geometrický význam jednotlivých proměnných krátce vysvětlit.
Úlohy k vypracování na cvičení:
  1. Imlementujte SVM algoritmus pro lineárně separabilní i neseparabilní data. Použijte duální formu optimalizační úlohy. K vlastnímu řešení úlohy kvadratického programování použijte funkci gsmo.
    Poznámky k používání funkce gsmo:
  2. Ukažte na vhodně zvolené trénovací sadě (viz např. obrázek níže), jak volba konstanty C ovlivňuje pozici oddělující nadplochy. K vytvoření dat a vizualizaci použijte funkce createdata, ppatterns a pline.

    C = Inf C = 1
  3. 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)

Doporučená literatura

[1] Christopher J. C. Burges. A Tutorial On Support Vector Machines for Pattern Recognition

[2] Text cvičení z minulých let

[3] Archív zápisů z přednášek rozpoznávání (33RPZ)

[4] Quadratic programming
   
Created by Karel Zimmerman, 16.11.2006. Last update 26.11.2008