Architektura

Support Vector Machine

Historyczny

Algorytm uczenia nadzorowanego znajdujący hiperpłaszczyznę o maksymalnym marginesie separacji między klasami; dzięki sztuczce jądrowej (kernel trick) potrafi modelować nieliniowe granice decyzyjne.

Kategoria

Architektura

Poziom abstrakcji

Primitive

Poziom operacji

ModelInferencjaTrening

Zastosowania

Klasyfikacja tekstu (kategoryzacja dokumentów, wykrywanie spamu)Klasyfikacja obrazów i rozpoznawanie wzorców (przed-era deep learning)Bioinformatyka — klasyfikacja białek i ekspresji genówWykrywanie anomalii (one-class SVM)Regresja (SVR) dla małych, dobrze opisanych zbiorów danychKlasyfikacja pisma odręcznego i OCR

Jak działa

1. Szukamy hiperpłaszczyzny w·x + b = 0 maksymalizującej margines 2/‖w‖ przy ograniczeniach y_i(w·x_i + b) ≥ 1. 2. Przekształcamy do problemu optymalizacji kwadratowej QP (lub jego dualnej formy Lagrange'a), gdzie wektory nośne (support vectors) — punkty na marginesie — wyznaczają rozwiązanie. 3. Soft-margin (parametr C): dopuszczamy naruszenia marginesu przez zmienne relaksacyjne ξ_i ≥ 0. Duże C → mały margines, mało błędów treningu; małe C → szeroki margines, dopuszcza więcej błędów. 4. Kernel trick: zamiast jawnej transformacji φ(x), zastępujemy iloczyn skalarny funkcją jądra K(x_i, x_j) = φ(x_i)·φ(x_j). Popularne jądra: RBF K = exp(−γ‖x−x'‖²), wielomianowe, sigmoidalne. 5. Predykcja: sign(Σ α_i y_i K(x_i, x) + b), gdzie sumujemy tylko po wektorach nośnych (α_i > 0). 6. Trening: algorytm SMO (Sequential Minimal Optimization) rozkłada QP na podproblemy dwuwymiarowe, rozwiązywane analitycznie.

Rozwiązany problem

Klasyfikatory liniowe znajdują dowolną hiperpłaszczyznę separującą klasy, ale nie gwarantują dobrej generalizacji — istnieje nieskończenie wiele takich płaszczyzn. SVM rozwiązuje ten problem wybierając hiperpłaszczyznę o maksymalnym marginesie (odległości od najbliższych punktów każdej klasy), co minimalizuje ryzyko błędu na nowych danych. Problem nieliniowych granic decyzyjnych rozwiązuje sztuczka jądrowa, mapując dane do wyższego wymiaru bez jawnej transformacji.

Kluczowe mechanizmy

Maksymalizacja marginesu między klasami (max-margin classifier)

Wektory nośne (support vectors) — wyłącznie one definiują granicę decyzyjną

Sztuczka jądrowa (kernel trick) — niejawne mapowanie do przestrzeni wyższego wymiaru

Funkcje jądra: liniowe, RBF (Gaussian), wielomianowe, sigmoidalne

Soft-margin z parametrem C — kompromis między marginesem a błędem klasyfikacji

Optymalizacja kwadratowa z ograniczeniami (QP) lub algorytm SMO

Funkcja straty hinge: max(0, 1 − y·f(x))

Mocne strony i ograniczenia

Mocne strony

✓Skuteczny w przestrzeniach o wysokim wymiarze (np. tekst po wektoryzacji)

✓Dobre właściwości generalizacyjne — solidna teoria VC

✓Sztuczka jądrowa pozwala na nieliniową klasyfikację bez jawnej transformacji

✓Wynik jest deterministyczny — globalne optimum problemu wypukłego

✓Mała wrażliwość na liczbę cech względem liczby przykładów

✓Stabilność — model zależy tylko od wektorów nośnych

Ograniczenia

✗Trening kosztowny obliczeniowo: O(N²)–O(N³) względem liczby przykładów

✗Słabo skaluje się dla bardzo dużych zbiorów (miliony przykładów)

✗Brak natywnie skalibrowanych prawdopodobieństw (wymaga Plat scaling)

✗Wybór jądra i hiperparametrów (C, γ) wymaga kosztownej walidacji krzyżowej

✗Wielokategoryjna klasyfikacja wymaga schematów one-vs-rest lub one-vs-one

✗Interpretowalność niska po zastosowaniu jąder nieliniowych

✗Wrażliwy na skalowanie cech

Implementacja

Pułapki implementacyjne

Złożoność O(n²)–O(n³) uniemożliwia skalowanie na duże zbioryŚrednia

Standardowe solvery SVM (SMO, libsvm) mają złożoność kwadratową lub sześcienną względem liczby próbek — dla n>100k trenowanie jest niepraktyczne. Alternatywy: SGD-SVM, LinearSVC (O(n)).

Dobór kernela i hiperparametrów wymaga CVŚrednia

Wybór kernela (RBF, poly, linear) i parametrów C, γ ma duży wpływ na wynik — brak domyślnych wartości działających we wszystkich przypadkach. Grid search + CV jest kosztowny dla dużych zbiorów.

Ewolucja

Oryginalny paper · 1995 · Machine Learning · Corinna Cortes

Support-Vector Networks

Corinna Cortes, Vladimir Vapnik

1963

Władimir Wapnik i Aleksiej Czerwonienkis publikują algorytm "Generalized Portrait" — prekursora liniowego SVM.

1992

Boser, Guyon i Vapnik wprowadzają sztuczkę jądrową, umożliwiając nieliniową klasyfikację w przestrzeniach o wysokim wymiarze.

1995

Cortes i Vapnik publikują "Support-Vector Networks" — wariant soft-margin staje się fundamentem nowoczesnego SVM.

1998

John Platt opisuje algorytm SMO (Sequential Minimal Optimization), drastycznie przyspieszając trening SVM.

2001

Chih-Chung Chang i Chih-Jen Lin wydają bibliotekę LIBSVM — najpopularniejszą implementację SVM w nauce i przemyśle.

2012

AlexNet wygrywa ImageNet — głębokie sieci wypierają SVM jako dominujący klasyfikator w wizji komputerowej.

Złożoność obliczeniowa

Charakterystyki obliczeniowe

→Złożoność treningu: O(N²)–O(N³) w zależności od implementacji i jądra

→Złożoność predykcji: O(N_sv · d), gdzie N_sv to liczba wektorów nośnych

→Pamięć: O(N²) dla macierzy Grama (możliwe cachowanie częściowe)

→Trening trudny do zrównoleglenia — globalna optymalizacja wypukła

→Predykcja trywialnie zrównoleglalna po przykładach

→Zwykle CPU; GPU rzadko stosowane (mała korzyść względem deep learning)

Uwagi do benchmarku

Przed erą deep learning SVM dominował w klasyfikacji tekstu (20 Newsgroups, Reuters-21578, RCV1) z dokładnością 85–92%, wyraźnie powyżej Naive Bayes. W rozpoznawaniu cyfr MNIST liniowy SVM osiąga ~92%, a SVM z jądrem RBF ~98,6%. W ImageNet 2010–2011 SVM był standardem do momentu wprowadzenia AlexNet (2012). Na małych zbiorach (poniżej 10 tys. próbek) SVM nadal jest konkurencyjny względem sieci neuronowych.