Support Vector Machines, the game

The widest street

A support vector machine (SVM) separates two classes with a hyperplane (a line in 2-D) and chooses the one with the widest margin: the empty “street” between the classes. The points touching or inside the street are the support vectors; they alone decide where the boundary goes.

Turn the C dial

Real data rarely separates perfectly, so SVMs use a soft margin. The parameter C sets how much to punish points on the wrong side: small C → wide, tolerant margin with many support vectors; large C → narrow margin that tries hard to classify every training point.

Real iris data: versicolor vs virginica by petal length and width, which overlap slightly. Linear SVM fitted at five values of C.

The kernel trick

When the classes can’t be split by a straight line, an SVM can map the data into a higher-dimensional space where they can. The kernel trick computes similarities in that space without ever building it.

Code it in Python

The article trains a linear SVM from scratch with sub-gradient descent on five 2-D points. Here is that idea, compact, followed by scikit-learn.

import numpy as np

X = np.array([[-2, 4, -1], [4, 1, -1], [1, 6, -1], [2, 4, -1], [6, 2, -1]])  # last column = bias term
y = np.array([-1, -1, 1, 1, 1])

w, eta, epochs = np.zeros(3), 1, 100000
for epoch in range(1, epochs):
    for i, x in enumerate(X):
        if y[i] * (x @ w) < 1:                       # inside the margin or misclassified
            w += eta * (y[i] * x - 2 * (1 / epoch) * w)
        else:
            w += eta * (-2 * (1 / epoch) * w)        # only the regularization pull
print(w)

from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

X, y = datasets.load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
scaler = StandardScaler().fit(X_train)
svm = SVC(kernel="rbf", C=1.0, gamma="scale").fit(scaler.transform(X_train), y_train)
print(svm.score(scaler.transform(X_test), y_test), "support vectors:", svm.n_support_)

Defeat the Margin Boss 🐲

Six questions, three hearts.

Keep levelling up

You learned what a separating hyperplane and margin are, which points are support vectors, how C trades margin width for training errors, how kernels handle non-linear data, and how to train an SVM.