Support vector machines

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Support vector machines (zkratka: SVM) je metoda strojového učení. V úloze klasifikace SVM hledá nadrovinu, která v prostoru příznaků optimálně rozděluje trénovací data. Optimální nadrovina je taková, že body leží v opačných poloprostorech a 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, algl. 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. Tato metoda je ze své přirozenosti binární, tedy rozděluje data do dvou tříd. Rozdělující nadrovina je lineární funkcí v prostoru příznaků.

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 Rn. Např. pro grafy, stromy, posloupnosti DNA ...

Použití pro jiné úlohy[editovat | editovat zdroj]

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) se použili 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íc 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[editovat | editovat zdroj]

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