Support vector machines

Support vector machines (zkratka: SVM) je metoda strojového učení s učitelem, sloužící zejména pro klasifikaci a také pro regresní analýzu. Na jejím vynalezení se podílel zejména Vladimir Vapnik.

Základem metody SVM je lineární klasifikátor do dvou tříd. Cílem úlohy je nalézt nadrovinu, která prostor příznaků optimálně rozděluje tak, že trénovací data náležející odlišným třídám leží v opačných poloprostorech. Optimální nadrovina je taková, že hodnota minima vzdáleností bodů od roviny je co největší. Jinými slovy, okolo nadroviny je na obě strany co nejširší pruh bez bodů (maximální odstup, angl. maximal margin). Na popis nadroviny stačí pouze nejbližší body, kterých je obvykle málo - tyto body se nazývají podpůrné vektory (angl. support vectors) a odtud název metody.

Důležitou součástí techniky Support vector machines je jádrová transformace (angl. kernel transformation) prostoru příznaků dat do prostoru transformovaných příznaků typicky vyšší dimenze. Tato jádrová transformace umožňuje převést původně lineárně neseparovatelnou úlohu na úlohu lineárně separovatelnou, na kterou lze dále aplikovat optimalizační algoritmus pro nalezení rozdělující nadroviny. Trik je v tom, že nadrovina je popsána a při výpočtech je použitý pouze skalární součin, a skalární součin transformovaných dat <f(x), f(x1)> ve vysokorozměrném prostoru se nepočítá explicitně, ale počítá se K(x, x1), tj. hodnota jádrové funkce K na datech v původním prostoru parametrů.

Používají se různé kernelové transformace. Intuitivně, vyjadřují podobnost dat, tj. svých dvou vstupních argumentů.

Výhodou této metody (a jiných metod založených na jádrové transformaci) je, že transformace se dá definovat pro různé typy objektů, nejen body v Rⁿ. Např. pro grafy, stromy, posloupnosti DNA ...

Použití pro jiné úlohy

Základní úloha řešená pomocí SVM je binární klasifikace. Ale myšlenky vycházející z SVM (málo podpůrných vektorů, maximální odstup a jádrové transformace) byly použity i pro návrh algoritmů pro další úlohy strojového učení, např. úlohy binární klasifikace na zašuměných datech (tzv. soft margin), diskrétní klasifikace (do více tříd), regrese, jádrová analýza hlavních komponent (PCA), ranking, strukturované učení, učení z jedné třídy (one class support vector, single class data description).

Literatura

• Bernhard Schölkopf, Alex Smola: Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond (Adaptive Computation and Machine Learning), MIT Press, Cambridge, MA, 2002, ISBN 0-262-19475-9.
• Ingo Steinwart, Andreas Christmann: Support Vector Machines, Springer, New York, 2008. ISBN 978-0-387-77241-7. 602 pp.
• Nello Cristianini, John Shawe-Taylor: Kernel Methods for Pattern Analysis, Cambridge University Press, Cambridge, 2004, ISBN 0-521-81397-2
• Christopher J. C. Burges: A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, 2(2):121-167, 1998.
• Vladimir Vapnik: Statistical Learning Theory, Wiley, Chichester, GB, 1998.
• Vladimir Vapnik: The Nature of Statistical Learning Theory, Springer Verlag, New York, NY, USA, 1995.