Support Vector Machines

Support Vector Machines (SVM, Maszyny Wektorów Nośnych) to rodzina metod uczenia maszynowego opracowanych w latach 90. XX wieku, wykorzystywanych głównie do klasyfikacji i regresji. Algorytm opiera się na konstrukcji maksymalnego marginesu pomiędzy dwoma klasami w przestrzeni cech, wykorzystując jednocześnie wektory wsparcia – podzestaw obserwacji, które definiują pozycję granicy decyzyjnej.

Historia

Pierwszą wersję SVM opracowali Vladimir Vapnik i Alexey Chervonenkis w latach 1960‑70, a następnie w 1992 r. opublikowali pracę „Support-Vector Networks”, w której wprowadzili koncepcję kernela (jądro) umożliwiającą pracę w przestrzeni o wysokiej wymiarowości bez konieczności jej explicite wyliczania. Od tego czasu SVM stały się jedną z najważniejszych technik w uczeniu maszynowym i są szeroko stosowane w praktyce.

Zasada działania

Podstawowym problemem SVM jest znalezienie hiperpłaszczyzny (lub jej nieliniowego odpowiednika), która rozdziela dwie klasy z maksymalnym marginesem. Formalnie, w wersji liniowej, rozwiązanie polega na minimalizacji funkcji

        ½‖w‖² + C Σ ξᵢ

przy warunkach

        yᵢ(w·xᵢ + b) ≥ 1 − ξᵢ, ξᵢ ≥ 0,

gdzie w i b definiują hiperpłaszczyznę, C jest parametrem regularyzacji, a ξᵢ to zmienne luzujące (slack variables) pozwalające na pewne naruszenia marginesu w problemach nieidealnie separowalnych.

Metoda Lagrange'a

W celu rozwiązania problemu stosuje się metodę Lagrange'a, przekształcając pierwotny problem konweksyjny w jego dualny (dualny problem optymalizacji). W wersji dualnej funkcja do maksymalizacji przyjmuje postać

        Σ αᵢ − ½ Σ Σ αᵢαⱼ yᵢyⱼ (xᵢ·xⱼ),

gdzie współczynniki αᵢ (zwane multiplikatorami Lagrange'a) są nieujemne i spełniają warunek Σ αᵢ yᵢ = 0. Rozwiązanie tego problemu jest zwykle uzyskiwane przy użyciu algorytmów programowania kwadratowego lub metod sekwencyjnych optymalizacji (SMO – Sequential Minimal Optimization).

Funkcje jądra

Kluczową cechą SVM jest możliwość zastosowania jąder, które pozwalają na pracę w przestrzeni o dużej wymiarowości bez konieczności jej jawnego wyznaczania (tzw. trik jądra). Najczęściej używane funkcje jądra to:

Jądro liniowe – K(x, z) = x·z
Jądro wielomianowe – K(x, z) = (γ x·z + r)ᵈ
Jądro radialne (RBF) – K(x, z) = exp(−γ‖x−z‖²)
Jądro sigmoidalne – K(x, z) = tanh(γ x·z + r)

Dzięki tym funkcjom SVM może tworzyć nieliniowe granice decyzyjne, które w rzeczywistości są liniowe w wyższym wymiarze cech.

Algorytm uczenia

Proces uczenia SVM składa się z następujących kroków:

Wybór odpowiedniej funkcji jądra i parametrów (γ, d, C).
Formułowanie problemu dualnego i jego rozwiązanie metodą optymalizacji (np. SMO lub QP).
Wyodrębnienie wektorów wsparcia – obserwacji, dla których αᵢ > 0.
Obliczenie stałej b na podstawie wektorów wsparcia.
Model gotowy do klasyfikacji nowych przykładów przy użyciu funkcji decyzyjnej f(x) = Σ αᵢ yᵢ K(xᵢ, x) + b.

Zastosowania

SVM znalazły szerokie zastosowanie w wielu dziedzinach, m.in.:

Rozpoznawanie pisma ręcznego i znaków.
Klasyfikacja obrazów w wizji komputerowej.
Detekcja spamu w poczcie elektronicznej.
Analiza sekwencji DNA i klasyfikacja białek w bioinformatyce.
Prognozowanie ryzyka w finansach i ekonomii.

Zalety i wady

Zalety:

Silna teoria matematyczna oparta na optymalizacji konweksyjnej – gwarancja globalnego optimum.
Efektywne w wysokich wymiarach dzięki trikowi jądra.
Możliwość regulacji złożoności modelu poprzez parametr C i wybór jądra.

Wady:

Wymaga starannego doboru parametrów – proces może być kosztowny obliczeniowo.
Słabo skaluje się do bardzo dużych zbiorów danych (powyżej setek tysięcy przykładów) bez dodatkowych technik przyspieszających.
Model jest mniej interpretowalny niż np. drzewa decyzyjne.

Implementacje

W środowiskach programistycznych dostępnych jest wiele implementacji SVM, w tym biblioteki LIBSVM, scikit-learn (Python), TensorFlow oraz R (pakiet e1071).

Literatura

V. N. Vapnik, The Nature of Statistical Learning Theory, Springer, 1995.
C. Cortes, V. Vapnik, „Support-Vector Networks”, Machine Learning, 1995.
J. Platt, „Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines”, 1998.

Maszyny wektorów nośnych pozostają jednym z filarów współczesnego uczenia maszynowego, łącząc solidną teorię matematyczną z praktyczną skutecznością w różnorodnych aplikacjach.