SequentialMinimalOptimizationSolver<T>

Models & Types · AiDotNet.Solvers.QuadraticProgramming

Solves the support-vector-machine dual with Sequential Minimal Optimization.

For Beginners

Training a support-vector machine means choosing one number per training example, subject to a rule tying them together — so you cannot adjust one alone without breaking the rule. Two is the smallest number you can move while keeping it satisfied, and moving exactly two has a formula. The method repeatedly picks the pair that is furthest from being correct, fixes that pair exactly, and repeats until nothing is meaningfully wrong.

How It Works

Solves the quadratic program every support-vector formulation reduces to:

with Q_ij = y_i·y_j·K(x_i, x_j). Classification, ν-classification, ε-regression and one-class detection all differ only in what p, y, C and the starting point are — the solver itself is the same, which is why this is written once here rather than separately inside each model.

A general-purpose quadratic-programming solver is the wrong tool for this particular QP. Q is dense and n × n in the number of training points, so an active-set or interior-point method factorizes an n × n system per iteration — cubic in dataset size, and it must hold the whole kernel matrix in memory. SMO (Platt, 1998) avoids both: it optimizes exactly two multipliers at a time, the smallest number the equality constraint permits, and each such subproblem has a closed-form answer.

This implements the modern formulation used by LIBSVM (Chang and Lin, 2011; Fan, Chen and Lin, 2005) rather than the original error-cache presentation:

  • the gradientG_i = Σ_j Q_ij·α_j + p_i is maintained incrementally, which

generalizes the classification-only “prediction error” to every formulation above;

  • maximal-violating-pair selection chooses the two multipliers whose KKT violation is

largest, which is provably convergent and is the step that makes the most progress;

  • the stopping test is the duality gapm(α) − M(α) ≤ tolerance, a real measure

of distance from optimality rather than a count of unchanged sweeps.

The simplified variant taught in course notes picks the partner multiplier at random and stops after a fixed number of quiet passes; it converges far more slowly and can stall.

Constructors

Constructor Summary
SequentialMinimalOptimizationSolver(SequentialMinimalOptimizationOptions options) Creates an SMO solver.

Methods

Method Summary
ValueTuple<Vector<T>, T, int> Solve(Func<int, int, T> kernel, Vector<T> labels, Vector<T> linear, Vector<T> upperBounds, Vector<T> initialAlphas, Func<int, int> kernelIndex) Solves the dual, returning the multipliers and the bias term.