SVM (Support Vector Machine) — maszyna wektorów nośnych

Support Vector Machine (SVM), po polsku maszyna wektorów nośnych, to jeden z najpotężniejszych klasycznych algorytmów uczenia maszynowego. SVM znajduje optymalną hiperpłaszczyznę rozdzielającą dane na klasy — taką, która maksymalizuje margines między klasami. Przez ponad dekadę (lata 2000-2012) SVM był dominującym algorytmem klasyfikacji, zanim głębokie sieci neuronowe przejęły pałeczkę.

Intuicja SVM

Wyobraź sobie punkty dwóch klas na płaszczyźnie — niebieskie i czerwone. Istnieje nieskończenie wiele prostych, które je rozdzielą. Która jest najlepsza?

SVM wybiera prostą (w ogólności: hiperpłaszczyznę), która maksymalizuje margines — odległość od najbliższych punktów obu klas. Intuicja: im większy margines, tym bardziej „pewna" jest klasyfikacja i tym lepiej model generalizuje na nowe dane.

Wektory nośne

Wektory nośne (support vectors) to punkty danych najbliższe hiperpłaszczyźnie rozdzielającej. To one „podpierają" (support) granicę decyzyjną — gdyby je usunąć, granica by się zmieniła. Wszystkie inne punkty (dalsze od granicy) nie wpływają na położenie hiperpłaszczyzny. Dlatego SVM jest odporny na outlier-y odległe od granicy.

Matematyka SVM

Liniowy SVM

Dla danych treningowych (xᵢ, yᵢ), gdzie yᵢ ∈ {-1, +1}:

Hiperpłaszczyzna: w · x + b = 0

Margines: 2 / ||w||

Problem optymalizacji:

min (1/2) ||w||²

pod warunkiem: yᵢ(w · xᵢ + b) ≥ 1 dla wszystkich i

To problem optymalizacji wypukłej z ograniczeniami — rozwiązywany przez multiplikatory Lagrange'a i programowanie kwadratowe.

Soft Margin SVM

Realne dane rzadko są idealnie liniowo separowalne. Soft margin SVM (C-SVM) wprowadza zmienne slack ξᵢ pozwalające na naruszenia marginesu:

min (1/2) ||w||² + C · Σ ξᵢ

pod warunkiem: yᵢ(w · xᵢ + b) ≥ 1 - ξᵢ, ξᵢ ≥ 0

Hiperparametr C kontroluje kompromis:

• Duże C → mniej naruszeń (hard margin), ryzyko overfittingu
• Małe C → więcej naruszeń, szerszy margines, lepsza generalizacja

Formulacja dualna

Problem SVM rozwiązuje się zwykle w formulacji dualnej (dual formulation), która operuje na mnożnikach Lagrange'a αᵢ zamiast bezpośrednio na w:

max Σ αᵢ - (1/2) Σᵢ Σⱼ αᵢ αⱼ yᵢ yⱼ (xᵢ · xⱼ)

Kluczowa obserwacja: formulacja dualna zależy od iloczynów skalarnych xᵢ · xⱼ, nie od samych wektorów. To otwiera drogę do kernel trick.

Kernel Trick — nieliniowy SVM

Wiele problemów nie jest liniowo separowalnych. Kernel trick rozwiązuje to bez jawnego transformowania danych do wyższego wymiaru.

Idea

1. Mapuj dane do przestrzeni o wyższym wymiarze φ(x), gdzie stają się liniowo separowalne
2. W wyższym wymiarze zastosuj liniowy SVM
3. Kernel trick: zamiast obliczać φ(xᵢ) · φ(xⱼ) (kosztowne), oblicz K(xᵢ, xⱼ) — funkcję jądra dającą ten sam wynik bez jawnej transformacji

Popularne kernele

Liniowy: K(x, x') = x · x' Brak transformacji. Szybki, dobry dla danych wysokowymiarowych (tekst, genomika).

Wielomianowy: K(x, x') = (γ · x · x' + r)^d Parametr d kontroluje stopień wielomianu. Granice decyzyjne w kształcie krzywych wielomianowych.

RBF (Radial Basis Function / Gaussian): K(x, x') = exp(-γ ||x - x'||²) Najpopularniejszy kernel. Mapuje do nieskończenie wymiarowej przestrzeni. Parametr γ kontroluje „zasięg" wpływu każdego punktu — mały γ = gładka granica, duży γ = złożona granica.

Sigmoid: K(x, x') = tanh(γ · x · x' + r) Podobny do sieci neuronowej z jedną warstwą ukrytą.

Dobór kernela

• Dane liniowo separowalne → kernel liniowy
• Dane nieliniowe, mało cech → RBF (domyślny wybór)
• Dane wysokowymiarowe (tekst: tysiące cech) → kernel liniowy (szybszy, często wystarczający)

Hiperparametry SVM

C (regularization parameter)

Kontroluje kompromis margines vs błędy. Dobierany przez walidację krzyżową.

γ (gamma) — dla RBF

Kontroluje zasięg wpływu punktu. Mały γ → gładka granica (underfitting). Duży γ → złożona granica (overfitting). Domyślnie: 1 / (n_features × variance).

Grid Search

Typowo C i γ dobierane przez grid search z walidacją krzyżową:

• C ∈ {0,01; 0,1; 1; 10; 100; 1000}
• γ ∈ {0,0001; 0,001; 0,01; 0,1; 1}

SVM do regresji (SVR)

Support Vector Regression (SVR) adaptuje ideę SVM do regresji. Zamiast maksymalizować margines między klasami, SVR dopasowuje rurę ε-insensitive — toleruje błędy mniejsze niż ε bez kary:

min (1/2) ||w||² + C · Σ (ξᵢ + ξᵢ*)

Punkty wewnątrz rury nie generują straty — tylko punkty poza rurą.

SVM wieloklasowy

Oryginalny SVM jest binarny (dwie klasy). Strategie wieloklasowe:

• One-vs-One (OvO): k(k-1)/2 klasyfikatorów, głosowanie. Domyślne w scikit-learn
• One-vs-Rest (OvR): k klasyfikatorów (klasa vs reszta)

Zalety i wady SVM

Zalety

• Skuteczny w wysokich wymiarach — działa dobrze gdy n_features > n_samples
• Odporny na overfitting — margines zapewnia dobrą generalizację
• Elastyczny — kernel trick obsługuje nieliniowe granice
• Mocne gwarancje teoretyczne — teoria VC, PAC learning
• Nie wymaga dużych danych — działa dobrze na małych-średnich zbiorach

Wady

• Skalowanie — O(n²) do O(n³) złożoność treningowa. Nie nadaje się do milionów próbek
• Wybór kernela i hiperparametrów — wymaga eksperymentowania
• Brak prawdopodobieństw — domyślnie daje etykietę, nie prawdopodobieństwo (Platt scaling dodaje tę zdolność)
• Wrażliwy na skalę cech — wymaga standaryzacji danych
• Trudna interpretowalność — kernel RBF tworzy złożone granice

SVM vs inne algorytmy

SVM w praktyce (scikit-learn)

from sklearn.svm import SVC
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import GridSearchCV

# Standaryzacja jest kluczowa dla SVM
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)

# Grid search po C i gamma
param_grid = {'C': [0.1, 1, 10, 100], 'gamma': ['scale', 0.01, 0.1]}
svm = GridSearchCV(SVC(kernel='rbf'), param_grid, cv=5)
svm.fit(X_train_scaled, y_train)

Zastosowania SVM

• Klasyfikacja tekstu — kategoryzacja dokumentów, spam detection (SVM z kernelem liniowym na TF-IDF)
• Bioinformatyka — klasyfikacja genów, predykcja struktury białek
• Rozpoznawanie pisma — jeden z pierwszych skutecznych algorytmów OCR
• Diagnostyka medyczna — klasyfikacja obrazów medycznych na małych zbiorach
• Wykrywanie anomalii — One-Class SVM do detekcji outlierów

Podsumowanie

SVM to elegancki algorytm łączący solidne podstawy teoretyczne z praktyczną skutecznością. Maksymalizacja marginesu, kernel trick i odporność na overfitting czynią go doskonałym wyborem dla małych-średnich zbiorów danych i wysokowymiarowych przestrzeni cech. Choć głębokie uczenie zdominowało wiele zastosowań, SVM pozostaje wartościowym narzędziem w arsenale uczenia maszynowego.