import numpy as np
import matplotlib.pyplot as plt
from sklearn.svm import SVC
rng = np.random.default_rng(10)
a = rng.normal([1.0, 1.0], 0.45, (30, 2))
b = rng.normal([3.0, 3.0], 0.45, (30, 2))
X = np.vstack([a, b])
y = np.array([0] * 30 + [1] * 30)Support vector machines
Examples
If two classes can be separated by a hyperplane, there are usually infinitely many hyperplanes that do it. Which one should we take.
The maximal margin classifier
The margin is the distance from the hyperplane to the nearest training point. The maximal margin classifier takes the hyperplane with the largest margin.
Only the points on the edge of the margin matter. These are the support vectors. Moving any other point does not change the solution at all, which is a very different behaviour from linear regression.
- A large
Cmeans we allow almost no violations of the margin, which is the maximal margin classifier.
Soft margins
Real data is rarely separable, and even when it is, the maximal margin classifier is very sensitive to single points near the boundary.
A support vector machine allows some points to be inside the margin, or on the wrong side. The hyper-parameter \(C\) controls how much. A small \(C\) allows many violations, which gives a wide margin and a rigid classifier. A large \(C\) allows few, which gives a narrow margin and a flexible classifier.
\(C\) is a regularization parameter, and it is chosen by cross-validation.
Kernels
A hyperplane is a rigid assumption. If the boundary is a circle, no hyperplane will do.
The trick is to map the input into a higher dimensional space where the classes are separable, and put a hyperplane there. A hyperplane in that space is a curved boundary in the original space.
The useful part is that we never have to build the mapping. The solution only depends on inner products between points, so it is enough to have a function that gives the inner product in the new space. That function is the kernel.
The common choice is the radial basis function,
\[ K(x, x') = \exp\left(-\gamma\|x - x'\|^2\right). \]
Practical notes
A support vector machine needs standardized inputs, because the kernel uses distances.
It scales badly with \(n\). Fitting is roughly quadratic in the number of points, so it is not the right choice for a million rows. It is a good choice when \(p\) is large and \(n\) is a few thousand.
SVC gives no probabilities by default. With probability=True it fits an extra calibration step, which is slow and not always well calibrated. If probabilities matter, logistic regression or a tree ensemble is usually a better choice.