Support Vector Machines

Decision trees divide the world into a series of yes-or-no questions. Random Forests average many trees to reduce variance. Gradient Boosting adds trees sequentially to correct previous mistakes.

Those methods are powerful, but they can produce irregular decision boundaries. Sometimes the data is simpler than that.

Imagine predicting whether Jessie orders a burger using only two features: hours since last meal and burger price. The burger examples sit mostly above the no-burger examples. A straight line separates them almost perfectly.

Burger      o  o  o  o
              o  o  o
----------------------------
No Burger   x  x  x  x
              x  x

Do we need an entire forest of trees? Probably not. We can ask for the best possible separating line. That is the motivation behind Support Vector Machines.

Suppose several different lines classify every training example correctly. At first, they seem equally good. SVMs argue they are not.

Instead of asking which line separates the training data, an SVM asks which line leaves the largest safety margin.

The margin is the empty buffer zone around the decision boundary. If Jessie is close to the boundary, a tiny change in hunger or price could flip the prediction. If the boundary is far away from the closest examples, small changes are less likely to matter.

Most training examples do not determine the final classifier. Move a point far away from the boundary and nothing changes. Move one of the closest points and the optimal boundary changes immediately. Those closest points are the support vectors.

The SVM chapter has one job: understand the best linear decision boundary. Kernels come next, after the linear idea is clear.

The Decision Boundary

A linear classifier uses a boundary:

Everything on one side is predicted as class $+1$. Everything on the other side is predicted as class $-1$. Unlike logistic regression, a standard SVM does not output a probability. Only the sign matters.

Defining The Margin

Suppose a training example is $(x_i,y_i)$, where $y_i\in\{-1,+1\}$. For a hard-margin SVM, every point must be on the correct side of the boundary with enough clearance:

The closest points satisfy equality:

Those equality points are the support vectors. They lie on the two margin lines that run parallel to the decision boundary.

Maximizing The Margin

The margin width is:

Maximizing that margin is equivalent to minimizing $\|w\|$. The standard hard-margin optimization is written as:

This is a constrained optimization problem. Among all boundaries that classify the training data correctly, it chooses the one with the widest margin.

Why It Works

A larger margin creates a more robust classifier. If a boundary passes extremely close to the data, a small change in a feature can flip the prediction. If the boundary leaves a wide empty gap, small perturbations are less likely to matter.

This is why SVMs are not satisfied with any separating line. They prefer the line that separates the classes while staying as far as possible from the nearest training examples.

Soft Margin

Real datasets are rarely perfectly separable. Jessie might sometimes buy a burger while dieting. If the classes overlap, no line can classify every example correctly.

A soft-margin SVM introduces slack variables $\xi_i$ that allow some examples to violate the margin or even be misclassified:

The parameter $C$ controls the trade-off. Large $C$ prioritizes fitting the training data. Small $C$ allows a wider margin even if some examples violate it.

Trees Versus SVMs

Complexity

Traditional SVM training solves a quadratic optimization problem, so it can become expensive on very large datasets. Prediction can be efficient because only the support vectors determine the final decision in the usual formulation.

This implementation trains a linear soft-margin SVM with hinge loss and gradient descent. Labels must be encoded as $-1$ and $+1$.

import numpy as np

class LinearSVM:
    def __init__(self, learning_rate=0.001, C=1.0, epochs=1000):
        self.learning_rate = learning_rate
        self.C = C
        self.epochs = epochs
        self.w = None
        self.b = 0.0

    def fit(self, X, y):
        n_samples, n_features = X.shape
        self.w = np.zeros(n_features)
        self.b = 0.0

        for _ in range(self.epochs):
            for x_i, y_i in zip(X, y):
                margin = y_i * (np.dot(self.w, x_i) + self.b)

                if margin >= 1:
                    grad_w = self.w
                    grad_b = 0
                else:
                    grad_w = self.w - self.C * y_i * x_i
                    grad_b = -self.C * y_i

                self.w -= self.learning_rate * grad_w
                self.b -= self.learning_rate * grad_b

        return self

    def decision_function(self, X):
        return X @ self.w + self.b

    def predict(self, X):
        return np.where(self.decision_function(X) >= 0, 1, -1)

In practice, scale features before training an SVM. Distances and margins are central to the model, so a feature measured in thousands can dominate a feature measured between zero and one.