← All Cracked ML projects
PL-I01NOT STARTEDINTERMEDIATEMLPYTHONIMPACT ★★☆☆☆

Kernel SVM with your own SMO solver, plus random Fourier features, vs LIBSVM

Also known as: SMO kernel SVM + random Fourier features vs LIBSVM

Match LIBSVM's accuracy with your own SMO, then get 10× faster by turning the kernel into random features.

EST.12 h
REWARD+300 XP
AFTERPlatt + 2

ML-ARENA BENCHMARKS

PROOF: BENCH
METRICINDUSTRYMINE
a9a test accuracy and training wall-clock at fixed (C, γ), where C is the regularisation strength and γ the RBF kernel width
GOAL · SMO within 0.3 pts of LIBSVM's accuracy at ≤ 3× its time; RFF (D ≤ 4000) reaches ≥ 99% of the kernel SVM's accuracy while being ≥ 10× faster
scikit-learn SVC (which wraps LIBSVM) · measured locally—
no results yet
YOUR RESULTS

Your recorded results appear here.

Brief

In NumPy, implement SMO for the RBF-kernel SVM dual. SMO (sequential minimal optimisation) solves the SVM's dual problem, the form where each training point has one weight, by repeatedly updating just two of those weights at a time. Add second-order working-set selection (choose which pair to update using curvature information, so each step makes more progress), shrinking (temporarily ignore training points that are clearly settled) and an LRU kernel-row cache (keep the most recently used rows of the kernel matrix in memory and evict the oldest). Then build random Fourier features (an explicit random feature map whose dot products approximate the RBF kernel), train a Pegasos linear SVM on them (a simple stochastic sub-gradient solver), and plot accuracy vs feature count D. Dataset: a9a (32,561 train / 16,281 test, 123 features).

Approach

Work with the dual in the form LIBSVM uses. With Qst=ysytK(xs,xt)Q_{st} = y_s y_t K(x_s, x_t),

min⁡α 12 α⊤Q α−1⊤αs.t.0≤αt≤C,y⊤α=0.\min_{\alpha}\ \tfrac12\,\alpha^\top Q\,\alpha - \mathbf 1^\top \alpha \quad \text{s.t.}\quad 0 \le \alpha_t \le C,\quad y^\top \alpha = 0.

Keep the gradient G=Qα−1G = Q\alpha - \mathbf 1 for every point. After a pair (i,j)(i, j) moves, update it with G+=Q:,i Δαi+Q:,j ΔαjG \mathrel{+}= Q_{:,i}\,\Delta\alpha_i + Q_{:,j}\,\Delta\alpha_j. That needs two full kernel rows per iteration, and computing kernel rows is where nearly all the time goes. This is why the cache matters more than any clever maths.

Pick the pair the way LIBSVM does (Fan, Chen and Lin, JMLR 2005). Let IupI_{up} be the points that can still move up along the constraint and IlowI_{low} those that can move down. Take i=arg⁡max⁡t∈Iup−ytGti = \arg\max_{t \in I_{up}} -y_t G_t. Then, among t∈Ilowt \in I_{low} with −ytGt<−yiGi-y_t G_t < -y_i G_i, take the jj that minimises −bit2/ait-b_{it}^2 / a_{it}, where ait=Kii+Ktt−2Kita_{it} = K_{ii} + K_{tt} - 2K_{it} and bit=−yiGi+ytGtb_{it} = -y_i G_i + y_t G_t. Half of bit2/aitb_{it}^2 / a_{it} is how much the objective would drop if you solved that pair exactly without the box, so the rule is a one-step look-ahead. Stop when max⁡Iup(−ytGt)−min⁡Ilow(−ytGt)≤10−3\max_{I_{up}} (-y_t G_t) - \min_{I_{low}} (-y_t G_t) \le 10^{-3}. The bias comes out at the end as the average of ytGty_t G_t over the free points.

For the fast half, Bochner's theorem says the RBF kernel is an expectation over random frequencies:

z(x)=2/D cos⁡(Wx+b),Wkj∼N(0, 2γ),bk∼U[0,2π],E[z(x)⊤z(x′)]=e−γ∥x−x′∥2.z(x) = \sqrt{2/D}\,\cos(Wx + b),\qquad W_{kj} \sim \mathcal N(0,\,2\gamma),\quad b_k \sim U[0, 2\pi],\qquad \mathbb E\big[z(x)^\top z(x')\big] = e^{-\gamma\|x - x'\|^2}.

The error of each kernel entry shrinks like 1/D1/\sqrt D, so accuracy climbs fast and then flattens. Train Pegasos on z(x)z(x) with step 1/(λt)1/(\lambda t) and λ=1/(nC)\lambda = 1/(nC), which is the same objective as the SVM with that CC. Append a constant feature for the bias.

Build in this order: plain SMO on a small subset checked against SVC, then second-order selection, then the cache, then shrinking, then the full data. Measure iterations and kernel-row computations first, not seconds.

VISUALFig. 1
yᵢ = yⱼ: αᵢ + αⱼ STAYS FIXED unclipped optimum clipped to H old pair LH 0C αᵢαⱼ yᵢ ≠ yⱼ: αⱼ − αᵢ STAYS FIXED optimum inside: keep it old pair LH 0C αᵢαⱼ Σ yₜαₜ = 0 pins the pair to a line. The box 0 ≤ α ≤ C cuts that line to the segment [L, H]. αⱼ ← clip(αⱼ + yⱼ(Eᵢ − Eⱼ)/η, L, H), η = Kᵢᵢ + Kⱼⱼ − 2Kᵢⱼ αᵢ ← αᵢ + yᵢyⱼ(αⱼ,old − αⱼ,new), Eₜ = f(xₜ) − yₜ
One SMO step. The equality constraint keeps the pair on a line, and the box [0, C]² cuts that line to the segment [L, H]. The best point on the line is found in closed form, then clipped. Why it's here: Every SMO bug is a mistake in L, H or the clip. See both label cases before you code them.

Where people get stuck

  • Two different gammas. scikit-learn's default gamma="scale" is not LIBSVM's default of 1 / number of features. Pass the same explicit γ to both, or you are racing different models.
  • Feature count. If you load a9a and a9a.t separately, pass n_features=123 to both so the matrices always have the same width.
  • Shrinking without unshrinking. Shrunk points keep a stale gradient. If you test the stopping rule or compute the bias without rebuilding it, you stop early with a wrong model.
  • Zero curvature. Duplicate points give ait=0a_{it} = 0. LIBSVM replaces it with a tiny positive number (1e-12); without that you divide by zero.
  • Slow kernel rows. Compute a row as exp(-γ·(sq[i] + sq - 2·X @ X[i])) with precomputed squared norms, in float64. Anything with a Python loop over points will lose the time race by itself.
HINT · OBJECTIVE 3
Stuck? Hints stay hidden until you ask.
HINT · OBJECTIVE 5
Stuck? Hints stay hidden until you ask.

Objectives

0 / 8 CLEARED

Read-only. Log in to update progress.

VICTORY CONDITIONS

  1. SMO within 0.3 points of LIBSVM's (scikit-learn SVC's) a9a test accuracy at ≤ 3× its training time, and RFF with D ≤ 4000 reaching ≥ 99% of the kernel SVM's accuracy while ≥ 10× faster, at the same fixed (C, γ). Record with `python tools/mlarena.py record PL-I01 "<value>"`.
  2. Your solver stops with a KKT gap ≤ 1e-3 over all points (after unshrinking), and its dual objective matches SVC's to 1e-3 relative.
  3. The accuracy-and-time vs D plot is published next to the kernel SVM baseline.

Side quests

Swap random Fourier features for Nyström features (kernel columns at sampled landmark points) at the same D, and compare accuracy per feature.
Replace Pegasos with dual coordinate descent, the method behind LIBLINEAR, on the same random features, and compare time to the same accuracy.

Terms in plain words

SVM dual
A rewrite of the SVM problem where you learn one weight per training point instead of one weight per feature, which lets you use kernels.
SMO
A solver for the SVM dual that improves two point-weights at a time, because a pair can be solved exactly in closed form.
RBF kernel
A similarity score exp(−γ·distance²) between two points that lets an SVM draw curved decision boundaries.
Random Fourier features (RFF)
Random cosine features whose dot products approximate the RBF kernel, so a fast linear model can stand in for a kernel SVM.
Pegasos
A stochastic sub-gradient method for training a linear SVM one mini-batch at a time.
Working-set selection
The rule SMO uses to pick which pair of point-weights to update next; LIBSVM's version uses curvature to pick the pair that gains most.
KKT gap
The largest remaining violation of the optimality conditions; SMO stops when it falls below a tolerance such as 1e-3.

Why it rates ★★☆☆☆

SMO is a true optimisation algorithm, and RFF links kernel methods to deep nets. But SVMs are out of fashion.