Support Vector Machines

Support Vector Machines (skr. SVM) je algoritmus vykonávajúci najmä klasifikáciu, ale aj regresnú analýzu. Je to jeden z najlepších a najpopulárnejších algoritmov strojového učenia.

Princíp

Princípom SVM je rozdelenie tréningových dát zakreslených v bodovom diagrame (angl. Scatter plot) na dve protiľahlé oblasti náležiace jednotlivým triedam dát. SVM priestor rozdeľuje tzv. nadrovinou (angl. Hyperplane). Nadrovina tiež môže byť označená ako tzv. rozhodovacia hranica (angl. Decision boundary), ktorá oddeľuje na bodovom diagrame dve triedy a určuje, ktoré body patria do ktorej triedy (obr. 1).

Pre optimálnu nadrovinu platí, že musí byť umiestnená v čo najväčšom odstupe (angl. Maximal margin) od krajných bodov, nazývaných podporné vektory (angl. Support vectors). Inými slovami, nadrovina musí vytvárať okolo seba čo najväčšie pásmo bez bodov a musí byť v strede tohto pásma tak, aby okrajové body oboch rozdelených oblastí boli rovnako vzdialené. SVM sa delí na lineárnu a nelineárnu, a to podľa schopnosti rozdeliť priestor.

Varianty

Lineárna SVM je variant tohto algoritmu, ktorý sa používa, keď sú dáta lineárne oddeliteľné, čiže oddeliteľné lineárnou nadrovinou. Pri lineárnej SVM algoritmus pracuje v pôvodnej dvojrozmernej rovine dát.

Nelineárna SVM sa používa, keď rovinu dát nie je možné rozdeliť lineárne. Tu sa uplatňuje funkcia zvaná jadrová transformácia (angl. Kernel transformation) alebo jadrový trik (angl. Kernel trick). Táto funkcia funguje tak, že lineárne nerozdeliteľnú dvojrozmernú množinu dát rozšíri o ďalšiu dimenziu, čím vzniká trojrozmerná rovina. Osi dvojrozmernej roviny $x$ a $y$ sú vlastnosti objektu, teda features a os $z$ pri trojrozmernej rovine je výsledkom rovnice $z=x^2+y^2$. Táto trojrozmerná rovina je už potom lineárne rozdeliteľná.

Parametre

Pri programovaní SVM klasifikátora sa používajú rôzne parametre. Medzi najdôležitejšie patria jadro, gamma a C.

Jadro alebo kernel je funkcia, ktorá je základom SVM a vykonáva jeho výpočty. Pre lineárnu SVM existuje len jedno lineárne jadro. Pre nelineárnu SVM je k dispozícii viacero jadier a prístupov k riešeniu. Medzi najpoužívanejšie patria RBF (Radial basis function) a polynomiálne jadro (obr. 2).

Gamma (obr. 3) určuje ako ďaleko od nadroviny budú mať body vplyv na túto hranicu. Keď je gamma vysoká, nadrovinu ovplyvňujú len body, ktoré sú pri nej blízko a vzdialené body ignoruje. Pri vysokej hodnote sa môže začať nadrovina zakrikovať a kľukatiť okolo jednotlivých dátových bodov. Ak je gamma nízka, nadrovinu ovplyvňujú aj vzdialené body. Tento parameter využíva len jadro RBF.

Parameter C určuje kompromis medzi rovnosťou nadroviny a počtom správne klasifikovaných tréningových bodov. Pri vyšších hodnotách C sa bude nadrovina zakrivovať a kľukatiť okolo jednotlivých dátových bodov, aby všetky zaradila do správnej oblasti. Týmto však klasifikátor stráca schopnosť zovšeobecňovať. Naopak pri nižších hodnotách bude nadrovina rovná, ale za cenu zopár nesprávne klasifikovaných dátových bodov.