Support vector machines

Problem

Two classes of points can often be split by many different lines. Logistic regression picks the one that maximises the likelihood, which keeps moving every point a little further from the line. A different question is which line will make the fewest mistakes on new points that land near the boundary. A line that grazes a training point leaves no room for error, while one that sits in the middle of the gap tolerates noise on both sides.

Real data adds two complications. Some points sit on the wrong side of any line, so the method must allow violations at a cost. And many classes are not separated by a line at all: points inside a ring belong to one class and points outside to the other. Support vector machines handle the margin and both complications with a single convex optimisation problem, which has one global optimum and a solution that depends only on a few training points.

Intuition

A linear classifier predicts sign(w·x + b). The value y(w·x + b) is the functional margin of a point: positive when the point is on its correct side, larger the further it is. Scaling w and b does not move the line, so fix the scale by asking the closest points to have functional margin exactly 1. The two lines w·x + b = ±1 then bound an empty strip of width 2/‖w‖, and making the strip as wide as possible means making ‖w‖ as small as possible.

When the strip cannot be empty, each point pays a hinge loss max(0, 1 − y(w·x + b)): nothing once it is outside the strip on its correct side, and a cost growing linearly as it moves into the strip or across the line. C sets the exchange rate between a wider strip and those payments. Points that end up exactly on the strip's edge, inside it, or on the wrong side are the support vectors; every other point could be deleted without changing the answer.

Mechanics

The soft-margin primal

minimise over w, b:   ½‖w‖² + C Σᵢ max(0, 1 − yᵢ(w·xᵢ + b))    with yᵢ ∈ {−1, +1}

The first term widens the margin, the second charges each violation. With slack variables ξᵢ this is the quadratic program: minimise ½‖w‖² + C Σ ξᵢ subject to yᵢ(w·xᵢ + b) ≥ 1 − ξᵢ and ξᵢ ≥ 0. As C → ∞ every ξᵢ is forced to 0 when that is possible, giving the hard-margin SVM. Divide by C and the objective is the average hinge loss plus an L2 penalty of strength 1/(2C): the same shape as regularised logistic regression with the log loss swapped for the hinge, which is why scikit-learn's SGDClassifier(loss="hinge") trains a linear SVM.

The dual and the support vectors

maximise over α:   Σᵢ αᵢ − ½ Σᵢ Σⱼ αᵢ αⱼ yᵢ yⱼ K(xᵢ, xⱼ)    subject to 0 ≤ αᵢ ≤ C,   Σᵢ αᵢ yᵢ = 0
w = Σᵢ αᵢ yᵢ xᵢ    f(x) = Σᵢ αᵢ yᵢ K(xᵢ, x) + b

The Lagrange dual has one variable per training point and touches the data only through dot products, written K(xᵢ, xⱼ) = xᵢ·xⱼ for the linear SVM. The optimality (KKT) conditions sort the points into three groups:

• αᵢ = 0: margin yᵢf(xᵢ) ≥ 1, outside the strip. The point has no influence on the solution.
• 0 < αᵢ < C: margin exactly 1, on the edge of the strip. These free support vectors fix b: b = yᵢ − Σⱼ αⱼ yⱼ K(xⱼ, xᵢ) for any of them.
• αᵢ = C: margin ≤ 1, inside the strip or misclassified. Bounded support vectors pay hinge loss; no single point can pull harder than C.

At the optimum the primal and dual objectives are equal (strong duality holds because the problem is convex with linear constraints), so the duality gap is a stopping test.

Kernels

Because the dual and the decision function need only K(xᵢ, xⱼ), any function that is an inner product φ(x)·φ(x′) in some feature space can replace the dot product. The SVM then finds a maximum-margin hyperplane in that space, which is a curved boundary in the original one, without ever computing φ. Mercer's condition (K is symmetric and every Gram matrix is positive semidefinite) is what guarantees such a φ exists and keeps the dual concave. The kernels libsvm implements:

linear: x·x′    polynomial: (γ x·x′ + coef0)^degree    RBF: exp(−γ ‖x − x′‖²)    sigmoid: tanh(γ x·x′ + coef0)

The polynomial kernel with degree 2 and coef0 = 1 in one dimension is (x x′ + 1)² = x²x′² + 2xx′ + 1 = φ(x)·φ(x′) with φ(x) = (x², √2 x, 1): a line in that space is a parabola in x. The RBF kernel corresponds to an infinite-dimensional φ. Its γ is an inverse squared length scale: a point influences the decision only within roughly 1/√γ of itself. The sigmoid kernel is not positive semidefinite for all parameters, so it is rarely the right choice.

Solving the dual: SMO

The dual is a quadratic program with n variables and an n × n kernel matrix, too big to hand to a generic QP solver for large n. Sequential minimal optimisation (Platt, 1998) updates two αs at a time, the smallest set that can move while keeping Σ αᵢyᵢ = 0, and the two-variable problem has a closed-form solution clipped to the box [0, C]. It keeps the gradient of the dual, picks the pair that most violates the optimality conditions, updates, and stops when the largest violation is below the tolerance (scikit-learn's tol, default 1e-3).

This page's helper uses the first-order rule: the maximal violating pair. libsvm, which scikit-learn's SVC wraps, picks the second index with second-order information (Fan, Chen and Lin, 2005), shrinks variables that are stuck at a bound, and caches kernel rows (cache_size, in MB). Both reach the same optimum; the second-order rule needs fewer iterations. Each step costs a kernel row, so training is between O(n²) and O(n³) and the scikit-learn documentation advises other estimators beyond a few tens of thousands of samples.

Worked example

Implementation

from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC, LinearSVC
from sklearn.linear_model import SGDClassifier
from sklearn.model_selection import GridSearchCV

X = [[1, 1], [2, 1], [1, 2.5], [2.5, 2], [3.5, 3], [4.5, 3], [3, 4.5], [4, 4.5]]
y = [-1, -1, -1, -1, 1, 1, 1, 1]

hard = SVC(kernel="linear", C=100).fit(X, y)
hard.coef_, hard.intercept_      # [[1, 1]], [-5.5]
hard.support_                    # [3, 4]: P4 and P5
hard.dual_coef_                  # [[-1, 1]]: alpha_i * y_i

# Kernel SVMs need scaled inputs; search C and gamma together on a log grid.
model = make_pipeline(StandardScaler(), SVC(kernel="rbf"))
search = GridSearchCV(model, {"svc__C": [0.1, 1, 10, 100],
                              "svc__gamma": ["scale", 0.01, 0.1, 1]}, cv=5)

# Many samples, linear boundary: liblinear or SGD on the primal.
linear = make_pipeline(StandardScaler(), LinearSVC(C=1.0))
sgd = make_pipeline(StandardScaler(), SGDClassifier(loss="hinge", alpha=1e-4))

SVC outputs scores, not probabilities. For calibrated probabilities wrap it in CalibratedClassifierCV; the old probability=True flag is deprecated in 1.9.1. For regression the same machinery with an ε-insensitive loss is SVR.

Tradeoffs

• Scale. Kernel SVM training needs the kernel matrix, in pieces, so time grows between n² and n³ and memory with the cache. Beyond tens of thousands of samples use LinearSVC, SGDClassifier, or an approximate feature map (Nystroem, RBFSampler) followed by a linear model.
• Prediction cost. Each prediction evaluates the kernel against every support vector. Small C and large γ make many support vectors and slow predictions.
• C and γ. Both control flexibility and they interact, so tune them together on a logarithmic grid with cross-validation.
• Preprocessing. The kernel compares raw distances, so unscaled features silently drop out, as the scaling example shows.
• Scores, not probabilities. The decision value is a distance-like score. Calibrate it if you need probabilities, and use class_weight for imbalanced classes.
• Against other models. On small to medium tabular data, gradient-boosted trees usually need less preprocessing and tuning. On images, text and audio, learned features from neural networks replaced hand-picked kernels. SVMs remain strong for small, high-dimensional problems such as text with many sparse features, and the margin and kernel ideas reappear across the field.

Connections

The hinge loss sits beside the log loss on the loss functions page, and the primal is regularised empirical risk as in regularization. The dual comes from Lagrange multipliers, the constrained version of the stationarity condition on derivatives and gradients. Scoring by similarity to stored examples returns in attention, where the similarity is a dot product of learned features, and gradient boosting is the usual alternative on tabular data.

References

• Cortes and Vapnik. Support-Vector Networks. Machine Learning 20, 273–297, 1995. doi:10.1007/BF00994018
• Boser, Guyon and Vapnik. A Training Algorithm for Optimal Margin Classifiers. COLT, 144–152, 1992. doi:10.1145/130385.130401
• Platt. Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. Microsoft Research MSR-TR-98-14, 1998. microsoft.com/research
• Fan, Chen and Lin. Working Set Selection Using Second Order Information for Training Support Vector Machines. Journal of Machine Learning Research 6, 1889–1918, 2005. jmlr.org/papers/v6/fan05a
• Chang and Lin. LIBSVM: A Library for Support Vector Machines. ACM Transactions on Intelligent Systems and Technology 2(3), 27:1–27:27, 2011. doi:10.1145/1961189.1961199
• scikit-learn 1.9.1: sklearn/svm/_classes.py, sklearn/svm/_base.py, sklearn/svm/src/libsvm/svm.cpp.