Implement SMO for the SVM dual

CodingGraduate⏱ 1 dayClassical MLsvmsmoimplementationkktquadratic programming

Theory: Support Vector Machines — Complete Derivation →

Problem

Implement sequential minimal optimisation for the soft-margin dual and verify it against a general-purpose QP solver.

Derive the closed-form solution of the two-variable subproblem with clipping.
Implement the working-set selection by maximal KKT violation.
Verify the support-vector classification (the three KKT regimes) on a synthetic problem.
Compare the decision boundary with a kernel of your choice against a linear one.

Implement it, then check the implementation against something you can verify independently.

Write it

Solve it here8 tests · Python runs in your browser

import numpy as np

def dual_objective(K, y, alpha):
    """The soft-margin SVM dual objective

sum_i alpha_i - 0.5 * sum_ij alpha_i alpha_j y_i y_j K_ij

for a precomputed kernel matrix K, labels y in {-1, +1} and multipliers
    alpha. Return a float.
    """
    raise NotImplementedError

def smo(K, y, C, tol=1e-3, max_passes=100):
    """Maximise that dual subject to 0 <= alpha_i <= C and sum_i alpha_i y_i = 0.

Return (alpha, b) with alpha an array of length n and b the intercept of

f(x) = sum_i alpha_i y_i K(x_i, x) + b.

The equality constraint means you can only move two multipliers at a
    time, which is what makes the two-variable subproblem solvable in closed
    form: alpha_j is confined to a segment [L, H] cut out by the box, so the
    unconstrained optimum along the line is clipped to it.

Choose the working set by KKT violation, and stop when no pair violates
    the conditions by more than `tol`. At the optimum, for every i:

alpha_i = 0       =>  y_i f(x_i) >= 1
        0 < alpha_i < C   =>  y_i f(x_i)  = 1
        alpha_i = C       =>  y_i f(x_i) <= 1
    """
    raise NotImplementedError

def decision_function(K_test_train, alpha, y, b):
    """f evaluated on new points, given the kernel between them and the
    training set: an array of shape (m,) from a (m, n) kernel block."""
    raise NotImplementedError

⌘/Ctrl + ↵ to run · limit 90s · draft saved in this browser

8 tests will run against your code. The first run downloads the Python runtime — several megabytes, once per browser.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
The geometric margin	Classical ML	Proof	Foundation	15 min
Solve a two-point SVM by hand	Classical ML	Numerical	Beginner	30 min
Complementary slackness and active constraints	Advanced Optimization	Proof	Intermediate	30 min
Implement backpropagation from scratch run	Deep Learning	Coding	Intermediate	3 hours
Implement kernel ridge regression run	Classical ML	Coding	Intermediate	1 hour

Problem

Write it

Solution

Related problems