Support Vector Machines

Goal: finding the optimal hyperplane that maximally separates the datapoints of different classes.

• For linearly separable data, this means finding the hyperplane that maximizes the margin between two classes.
• The margin is the distance between the hyperplane and the closest data points from each class.

Hyperplane:

• in an $n$-dimensional space, a hyperplane is defined as:

• $w^{T}x+b=0$

• The decision rule becomes $sign(w^{T}x+b)$

• The support vectors are the datapoints closest to the decision boundary.

• They define the margin, and the optimal hyperplane is fully determined by these points.

• Removing non-support vectors has no effect on the decision boundary.

Margin is: $Margin=\frac{2}{||w||}$We want to maximize the margin, which is equivalent to minimizing $||w|{|}^2$

The Primal

With labels $y_i\in \{-1,+1\}$, the hard-margin SVM is the constrained quadratic program:

$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2\text{s.t.}{y}_i(w^{\top }{x}_i+b)\ge 1\forall i.$$

Soft Margin C

Real data is rarely separable, so we allow violations via slack variables ${\xi }_i\ge 0$:

$$\underset{w,b,\xi }{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _i{\xi }_i\text{s.t.}{y}_i(w^{\top }{x}_i+b)\ge 1-{\xi }_i.$$

The penalty $C$ trades margin width against training errors:

$C$	Effect
Large $C$	few violations, narrow margin, risk of overfitting
Small $C$	wider margin, more violations, more regularized

Hinge Loss

Eliminating the slacks turns the soft-margin problem into unconstrained regularized empirical risk minimization with the hinge loss:

$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _i\max (0,1-y_i(w^{\top }{x}_i+b)).$$

The hinge is zero once a point is correctly classified with margin at least 1, so only margin-violating points contribute gradient.

The Dual and Kernels

The Lagrangian dual depends on the data only through inner products $x_i^{\top }{x}_j$:

$$\underset{\alpha }{\max }\sum _i{\alpha }_i-\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^{\top }{x}_j,0\le {\alpha }_i\le C,\sum _i{\alpha }_i{y}_i=0.$$

Only support vectors have ${\alpha }_i>0$. Because only inner products appear, we can replace $x_i^{\top }{x}_j$ with a kernel $k(x_i,x_j)$ to fit nonlinear boundaries without ever forming the high-dimensional features. See Kernel Methods. Common choices: RBF $k(x,x^{\prime })=\exp (-\gamma \Vert x-x^{\prime }{\Vert }^2)$ and polynomial kernels.

sklearn

from sklearn.svm import SVC
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
 
clf = make_pipeline(
    StandardScaler(),
    SVC(kernel="rbf", C=1.0, gamma="scale"),
)
clf.fit(X_train, y_train)
print(clf.score(X_test, y_test))

Hinge Loss in torch

import torch
 
def hinge_loss(scores, y, w, C=1.0):     # y in {-1, +1}
    margins = torch.clamp(1 - y * scores, min=0)
    return 0.5 * (w @ w) + C * margins.mean()

Pitfalls

• SVMs are scale-sensitive; always standardize features (the RBF kernel especially).
• Classic SVM solvers scale poorly past ~100k samples; consider linear SVM with SGD (hinge loss) for large data.
• gamma and C interact strongly; tune them jointly by cross-validation.

Related

• Kernel Methods generalize the kernel trick beyond SVMs.