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 ,
Keep the gradient for every point. After a pair moves, update it with . 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 be the points that can still move up along the constraint and those that can move down. Take . Then, among with , take the that minimises , where and . Half of 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 . The bias comes out at the end as the average of over the free points.
For the fast half, Bochner's theorem says the RBF kernel is an expectation over random frequencies:
The error of each kernel entry shrinks like , so accuracy climbs fast and then flattens. Train Pegasos on with step and , which is the same objective as the SVM with that . 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.
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=123to 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 . 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.
Objectives
Read-only. Log in to update progress.
VICTORY CONDITIONS
- 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>"`.
- 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.
- The accuracy-and-time vs D plot is published next to the kernel SVM baseline.
Side quests
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.