Support Vector Machines & The Kernel Trick

Support Vector Machines (SVMs) represent one of the most mathematically rigorous algorithms in statistical learning theory. Grounded in Vapnik-Chervonenkis (VC) Dimension bounds, SVMs seek the unique decision boundary that maximizes the geometric margin separating two classes, minimizing structural risk rather than empirical risk alone.

1. Geometric Margin and Primal Formulation#

Consider a linearly separable binary dataset $(x_1, y_1), \dots, (x_N, y_N)$ with feature vectors $x_i \in \mathbb{R}^d$ and binary polar labels $y_i \in \{-1, +1\}$.

A separating affine hyperplane is defined by:

Derivation of the Margin Width#

Let $x_0$ be any point in space. The signed Euclidean distance $\gamma$ from $x_0$ to the hyperplane is computed by orthogonal projection along unit normal vector $\frac{w}{\|w\|_2}$:

For classified samples with labels $y_i \in \{-1, +1\}$, the geometric margin is:

2. Soft-Margin SVM & Slack Variables#

Real-world datasets contain label noise and overlapping distributions where no linear hyperplane can achieve 100% clean separation.

To tolerate controlled margin violations, Cortes and Vapnik introduced non-negative slack variables $\xi_i \ge 0$:

• If $\xi_i = 0$: The point is correctly classified outside or on the margin.
• If $0 < \xi_i \le 1$: The point violates the margin but remains on the correct side of the decision boundary.
• If $\xi_i > 1$: The point is misclassified.
• Hyperparameter $C$: Controls the penalty for margin violations. Large $C$ enforces hard margins (high variance), while small $C$ tolerates errors to widen the margin (high bias).

3. The Dual Problem and KKT Optimality Conditions#

To solve this constrained optimization problem, we construct the Lagrangian function with dual multipliers $\alpha_i \ge 0$ and $\beta_i \ge 0$:

First-Order Karush-Kuhn-Tucker (KKT) Stationarity#

Setting partial derivatives with respect to primal variables to zero:

1. With respect to $w$:

1. With respect to $b$:

1. With respect to $\xi_i$:

Substituting into the Lagrangian (The Wolfe Dual)#

Substituting these stationarity relations back into $\mathcal{L}$ eliminates primal variables $w$, $b$, and $\xi$:

4. The Kernel Trick: Infinite Dimensional Feature Spaces#

Observe that the dual objective and inference decision rule depend solely on the inner product between feature vectors:

If data is non-linear in input space $\mathbb{R}^d$, we map it via non-linear feature expansion $\phi(x) \in \mathcal{H}$ into a higher-dimensional Hilbert space where linear separation is achievable.

By Mercer's Theorem, any symmetric positive semi-definite function $K(x, z)$ computes this inner product directly without ever explicitly materializing high-dimensional vector $\phi(x)$:

Mathematical Proof: RBF Kernel as Infinite Dimensions#

The Radial Basis Function (Gaussian) kernel is:

Applying the Taylor series expansion of $e^u = \sum_{k=0}^\infty \frac{u^k}{k!}$:

Because $(x^T z)^k$ is the polynomial kernel generating all polynomial terms up to degree $k$, the infinite series summation proves that the RBF kernel maps inputs into an infinite-dimensional reproducing kernel Hilbert space (RKHS).

5. From-Scratch Implementation: Zero Dependencies#

The following implementations solve Linear SVM using subgradient descent on the regularized Hinge Loss:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from typing import List

class LinearSVMFromScratch:
    def __init__(self, learning_rate: float = 0.001, lambda_param: float = 0.01, num_epochs: int = 1000):
        self.learning_rate = learning_rate
        self.lambda_param = lambda_param
        self.num_epochs = num_epochs
        self.weights: List[float] = []
        self.bias: float = 0.0

    def fit(self, X: List[List[float]], y: List[int]) -> None:
        # Expect labels in {-1, +1}
        num_samples = len(X)
        num_features = len(X[0])
        self.weights = [0.0] * num_features
        self.bias = 0.0

        for _ in range(self.num_epochs):
            for i in range(num_samples):
                # Functional margin: y_i * (w^T x_i + b)
                linear_output = sum(self.weights[j] * X[i][j] for j in range(num_features)) + self.bias
                condition = y[i] * linear_output >= 1.0

                if condition:
                    # Only regularization gradient
                    for j in range(num_features):
                        self.weights[j] -= self.learning_rate * (self.lambda_param * self.weights[j])
                else:
                    # Regularization + Hinge loss subgradient
                    for j in range(num_features):
                        self.weights[j] -= self.learning_rate * (
                            self.lambda_param * self.weights[j] - y[i] * X[i][j]
                        )
                    self.bias += self.learning_rate * y[i]

    def predict(self, X: List[List[float]]) -> List[int]:
        num_features = len(self.weights)
        predictions = []
        for row in X:
            score = sum(self.weights[j] * row[j] for j in range(num_features)) + self.bias
            predictions.append(1 if score >= 0.0 else -1)
        return predictions

if __name__ == "__main__":
    X_train = [[1.0, 2.0], [2.0, 3.0], [2.0, 1.0], [6.0, 7.0], [7.0, 8.0], [8.0, 6.0]]
    y_train = [-1, -1, -1, 1, 1, 1]

    svm = LinearSVMFromScratch(learning_rate=0.01, lambda_param=0.01, num_epochs=500)
    svm.fit(X_train, y_train)
    preds = svm.predict(X_train)
    print(f"Learned weights: {svm.weights}")
    print(f"Learned bias: {svm.bias:.4f}")
    print(f"Predictions: {preds}")

6. Active Knowledge Checks#