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 gradient
G_i = Σ_j Q_ij·α_j + p_iis 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 gap
m(α) − 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. |