Machine Learning from First Principles

Project 8 · Part VII: Projects

Support Vector Machines from Scratch

Implement the SMO algorithm that trains kernel SVMs, check it against the KKT conditions, and show that it reproduces scikit-learn’s LIBSVM solution to four decimals.

After this project you will be able to

  • Implement linear, polynomial, and RBF kernels and a soft-margin SVM solver based on SMO.
  • Maintain an error cache and use Platt’s heuristics to choose working pairs.
  • Verify a solution with the KKT conditions and the dual objective.
  • Compare a from-scratch solver with a library implementation on accuracy, support vectors, and the optimal objective value.

Code: projects/p8_svm/ (svm_smo.py, svm_sklearn.py, tests/). Background: Chapter 9.

P8.1The Problem

Train soft-margin support vector machines by solving the dual quadratic program of Sections 9.4 and 9.6,

$$\max_{\bm\alpha}\ \sum_i\alpha_i-\frac12\sum_{i,j}\alpha_i\alpha_jy^{(i)}y^{(j)}K_{ij}\quad\text{s.t.}\quad 0\le\alpha_i\le C,\ \ \sum_i\alpha_iy^{(i)}=0,$$

with our own implementation of sequential minimal optimization (SMO) (Platt 1998), and demonstrate that it finds the same optimum as a production solver. “Same” is checked three ways: the KKT conditions hold within the tolerance, the dual objective matches, and the predictions agree.

P8.2The Data

Three data sets of increasing realism, each split 70/30 with stratification and standardized with statistics of the training part only:

  • Two moons (400 points, noise 0.25): two interleaved half circles, not linearly separable.
  • Circles (400 points): one class inside the other, separable only with a nonlinear kernel.
  • Breast cancer (569 tumors, 30 features from images of cell nuclei; scikit-learn’s load_breast_cancer): a real diagnostic task, nearly linearly separable.

P8.3Building It from Scratch

Kernels and the Gram matrix. For training sets of a few thousand points it is fastest to compute the whole Gram matrix $K_{ij}=K(\vx^{(i)},\vx^{(j)})$ once. The RBF kernel uses $\norm{\va-\vb}^2=\norm\va^2-2\va\T\vb+\norm\vb^2$ to vectorize all pairwise distances, clipping tiny negative values caused by rounding.

The error cache. SMO needs the errors $E_k=f(\vx^{(k)})-y^{(k)}$ of all points to choose pairs and to update $b$. Recomputing them costs $O(n^2)$ per step; instead, after changing $\alpha_i$, $\alpha_j$, and $b$, every error changes by a known amount, an $O(n)$ update:

$$E_k\gets E_k+y^{(i)}\Delta\alpha_iK_{ik}+y^{(j)}\Delta\alpha_jK_{jk}+\Delta b .$$

One SMO step. The core of the solver optimizes a pair $(i,j)$ in closed form (Section 9.7): compute the segment $[L,H]$ on which $\alpha_j$ can move while both multipliers stay in $[0,C]$ and the equality constraint holds, take the unconstrained Newton step along the segment, clip it, update $\alpha_i$ to compensate, and recompute $b$ so that the KKT conditions hold for whichever of the two points ends strictly inside $(0,C)$:

import numpy as np

def smo_pair_update(i, j, alpha, y, K, E, b, C, eps=1e-8):
    """Optimize alpha_i, alpha_j jointly; returns the new (alpha, E, b) or None if no progress."""
    a_i, a_j, s = alpha[i], alpha[j], y[i] * y[j]
    L, H = ((max(0, a_j - a_i), min(C, C + a_j - a_i)) if s < 0
            else (max(0, a_i + a_j - C), min(C, a_i + a_j)))
    kappa = K[i, i] + K[j, j] - 2 * K[i, j]
    if H - L < eps or kappa <= 1e-12:
        return None                                   # (the full solver also handles kappa <= 0)
    a_j_new = np.clip(a_j + y[j] * (E[i] - E[j]) / kappa, L, H)
    if abs(a_j_new - a_j) < eps:
        return None
    a_i_new = a_i + s * (a_j - a_j_new)
    b_i = b - E[i] - y[i] * (a_i_new - a_i) * K[i, i] - y[j] * (a_j_new - a_j) * K[i, j]
    b_j = b - E[j] - y[i] * (a_i_new - a_i) * K[i, j] - y[j] * (a_j_new - a_j) * K[j, j]
    b_new = b_i if 0 < a_i_new < C else b_j if 0 < a_j_new < C else (b_i + b_j) / 2
    E = E + y[i] * (a_i_new - a_i) * K[i] + y[j] * (a_j_new - a_j) * K[j] + (b_new - b)
    alpha = alpha.copy(); alpha[i], alpha[j] = a_i_new, a_j_new
    return alpha, E, b_new

Choosing pairs. The outer loop alternates between a pass over all points and passes over the non-bound points ($0<\alpha<C$), which are the ones most likely to change. A point $j$ is examined if it violates the KKT conditions by more than the tolerance (for example $y^{(j)}f(\vx^{(j)})<1-\text{tol}$ while $\alpha_j<C$). Its partner $i$ is chosen to maximize $|E_i-E_j|$, which approximately maximizes the step size; if that pair makes no progress, the solver tries the other non-bound points and finally all points, starting at random positions. The algorithm stops when a full pass changes nothing. The file svm_smo.py also handles the degenerate case $\kappa\le0$ (two identical points) by evaluating the objective at both ends of the segment, as in Platt’s paper.

Checking the answer. The KKT conditions of Section 9.6 give a certificate of optimality that does not depend on any other solver: points with $\alpha_i=0$ must have $y^{(i)}f(\vx^{(i)})\ge1$, points with $\alpha_i=C$ must have $y^{(i)}f(\vx^{(i)})\le1$, and points in between must lie exactly on the margin. The method kkt_violation returns the largest violation, which must be below the tolerance $10^{-3}$.

P8.4Using Libraries

scikit-learn’s SVC wraps LIBSVM, which uses an SMO-type decomposition method with second-order working-set selection and caching of kernel rows. Its dual_coef_ attribute stores $y^{(i)}\alpha_i$ for the support vectors, from which svm_sklearn.py recomputes LIBSVM’s dual objective on the same Gram matrix:

import numpy as np

def sklearn_dual(svc, K, y):
    """Dual objective of a fitted sklearn SVC, given the training Gram matrix K and labels y in {-1, +1}."""
    alpha = np.zeros(len(y))
    alpha[svc.support_] = np.abs(svc.dual_coef_[0])          # dual_coef_ stores y_i * alpha_i
    ay = alpha * y
    return alpha.sum() - 0.5 * ay @ K @ ay

Note that scikit-learn’s RBF kernel is parameterized as $\exp(-\gamma\norm{\vx-\vz}^2)$, as ours is, and that the default gamma="scale" would choose a different $\gamma$; pass it explicitly when comparing.

P8.5Results and Discussion

With $C=1$ and the kernels shown, running python svm_sklearn.py gives:

Data, kernelAccuracy (ours / SVC)SVs (ours / SVC)Dual (ours / SVC)Agree
Moons, RBF $\gamma=1$0.908 / 0.90878 / 7855.9219 / 55.9219100%
Circles, RBF $\gamma=2$1.000 / 1.00045 / 4518.6970 / 18.6971100%
Cancer, linear0.953 / 0.95327 / 2714.1975 / 14.1975100%
Cancer, RBF $\gamma=0.05$0.953 / 0.953112 / 11242.6410 / 42.6410100%

The two solvers find the same optimum: the dual objectives agree to four or more significant digits, the support vectors coincide, and the classifiers agree on every test point. Since the dual is concave, any two correct solvers must agree on the objective value, so this is a strong check of the implementation; the multipliers themselves can differ slightly when the problem is degenerate, but the decision function is the same. Each fit takes well under a second; LIBSVM is faster by a constant factor thanks to compiled code and better working-set selection, and it also avoids storing the full Gram matrix, which our implementation needs.

Two observations connect back to Chapter 9. On the cancer data, the linear SVM uses only 27 of 398 training points as support vectors, a sparse solution produced by the hinge loss; the RBF kernel with the same $C$ uses 112, because a more flexible boundary passes close to more points. On the circles, a linear SVM would be at chance level, while the RBF kernel separates the classes perfectly, as the lifting picture of Section 9.5 predicts.

P8.6Extensions

  1. Plot the dual objective and the KKT violation after every outer pass. How does convergence depend on $C$?
  2. Implement LIBSVM’s second-order working-set selection, which picks $i$ to maximize the predicted increase of the objective, and compare the number of steps.
  3. Replace the precomputed Gram matrix by a cache of recently used kernel rows, and train on 20,000 points of a larger data set.
  4. Implement one-vs-rest multiclass classification on top of the binary solver and test it on load_digits.
Machine Learning from First Principles · Edition 2.0 · Companion site to the PDF book.