Support Vector Machines: A Sparse Kernel Machine Guide

Build an SVM from scratch with scikit-learn and a cvxopt dual QP. Max-margin geometry, the kernel trick, hinge vs cross-entropy.

Cover Image for Support Vector Machines: A Sparse Kernel Machine Guide

Your data contains two classes shaped like interleaving crescent moons, so a straight boundary leaves many points on the wrong side. You want a model that can follow the curved separation without treating every training point as equally decisive. A support vector machine gives you a boundary determined by a subset of training examples. Those support vectors make the model's solution easier to inspect.

Only some observations constrain that separation. The moons boundary uses 40 support vectors from 200 training points. We fit linear and kernel SVMs, compare their boundaries with logistic regression, and inspect the retained points to see how the optimisation chooses them.

Quick Win: Linear and Kernel SVM in One Page

Open In Colab

Two scikit-learn calls. The first fits a linear SVM to a separable 2D blob; the second fits an RBF SVM to the moons.

import numpy as np
from sklearn.datasets import make_blobs, make_moons
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

# Linearly separable blobs
X_lin, y_lin = make_blobs(n_samples=40, centers=2, cluster_std=0.9,
                          center_box=(-2.5, 2.5), random_state=1)
y_lin = np.where(y_lin == 0, -1, 1)
linear = SVC(kernel='linear', C=10.0).fit(X_lin, y_lin)
print(f'linear SVM: {len(linear.support_vectors_)} support vectors '
      f'out of {len(y_lin)} training points')

# Non-linear moons
X_m, y_m = make_moons(n_samples=200, noise=0.22, random_state=3)
X_m = StandardScaler().fit_transform(X_m)
y_m = np.where(y_m == 0, -1, 1)
rbf = SVC(kernel='rbf', C=4.0, gamma=1.5).fit(X_m, y_m)
print(f'RBF SVM:   {len(rbf.support_vectors_)} support vectors '
      f'out of {len(y_m)} training points')

Output:

linear SVM: 4 support vectors out of 40 training points
RBF SVM:   40 support vectors out of 200 training points

The linear SVM uses 10% of the training data; the RBF SVM uses 20%. Everything else is irrelevant once training is done. That is what sparse kernel machine means.

Linear SVM on a separable 2D blob: the solid line is the maximum-margin hyperplane, the dashed lines mark the margin boundaries, and the green circles indicate the four support vectors that touch them.

This is the classic max-margin picture on real data. Now the kernel version on a problem no straight line can solve:

RBF SVM on the moons dataset: the boundary curves around the upper crescent, with 40 support vectors (green circles) clustered along the boundary region.

This is the classic kernel-SVM picture. The curved boundary in the original 2D space comes from a linear hyperplane in a higher-dimensional feature space that the RBF kernel implicitly defines. The next section unpacks how.

What Just Happened: Margin, Lagrangian, Sparsity

Act 1: The maximum margin hyperplane

For a two-class problem with labels tn∈{−1,+1}t_n \in \{-1, +1\}, a linear classifier has the form

y(x)=w⊤ϕ(x)+b,y(\mathbf{x}) = \mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}) + b,

where ϕ\boldsymbol{\phi} is some feature map (identity for the moment). When the classes are linearly separable, infinitely many (w,b)(\mathbf{w}, b) work. The perceptron picks one based on initialisation and data order. The SVM picks the unique solution that maximises the margin, the perpendicular distance from the boundary to the nearest training point.

After rescaling (w,b)(\mathbf{w}, b) so the closest points satisfy tny(xn)=1t_n y(\mathbf{x}_n) = 1, the margin equals 1/∥w∥1 / \|\mathbf{w}\| and the optimisation becomes:

arg⁡min⁡w,b 12∥w∥2subject totn(w⊤ϕ(xn)+b)≥1, ∀n.\arg\min_{\mathbf{w}, b}\ \tfrac{1}{2}\|\mathbf{w}\|^2 \quad \text{subject to}\quad t_n(\mathbf{w}^\top \boldsymbol{\phi}(\mathbf{x}_n) + b) \geq 1, \ \forall n.

A convex quadratic objective with linear inequality constraints. One global minimum, no local optima to worry about.

Act 2: The Lagrangian dual and where sparsity comes from

Introducing Lagrange multipliers an≥0a_n \geq 0 for the NN margin constraints gives the Lagrangian, then eliminating w\mathbf{w} and bb produces the dual problem:

L~(a)=∑n=1Nan−12∑n=1N∑m=1Nanamtntmk(xn,xm),\widetilde{L}(\mathbf{a}) = \sum_{n=1}^{N} a_n - \tfrac{1}{2} \sum_{n=1}^{N} \sum_{m=1}^{N} a_n a_m t_n t_m k(\mathbf{x}_n, \mathbf{x}_m),

maximised subject to an≥0a_n \geq 0 and ∑nantn=0\sum_n a_n t_n = 0. The kernel k(x,x′)=ϕ(x)⊤ϕ(x′)k(\mathbf{x}, \mathbf{x}') = \boldsymbol{\phi}(\mathbf{x})^\top \boldsymbol{\phi}(\mathbf{x}') is the only place the feature map enters. We never compute ϕ\boldsymbol{\phi} explicitly.

The Karush-Kuhn-Tucker (KKT) conditions for this constrained optimisation force, for every training point, either

an=0ortny(xn)=1.a_n = 0 \quad \text{or} \quad t_n y(\mathbf{x}_n) = 1.

Points with an=0a_n = 0 drop out of the prediction y(x)=∑nantnk(x,xn)+by(\mathbf{x}) = \sum_n a_n t_n k(\mathbf{x}, \mathbf{x}_n) + b. The remaining points, the support vectors, sit exactly on the margin boundaries. Sparsity is not added as a regulariser; it falls out of the geometry.

You can solve the dual with cvxopt in twenty lines and verify it matches scikit-learn:

import numpy as np
from cvxopt import matrix, solvers
solvers.options['show_progress'] = False

K = X_lin @ X_lin.T  # linear kernel
N = len(y_lin)
P = matrix((y_lin[:, None] * y_lin[None, :]) * K)
q = matrix(-np.ones(N))
G = matrix(-np.eye(N))
h = matrix(np.zeros(N))
A = matrix(y_lin.astype(float).reshape(1, -1))
b = matrix(0.0)

sol = solvers.qp(P, q, G, h, A, b)
a = np.ravel(sol['x'])
sv_mask = a > 1e-5

w = ((a * y_lin) @ X_lin)
b_int = np.mean(y_lin[sv_mask] - X_lin[sv_mask] @ w)
print(f'cvxopt:  {sv_mask.sum()} SVs, w = {w.round(3)}, b = {b_int:.3f}')
print(f'sklearn: {linear.n_support_.sum()} SVs, '
      f'w = {linear.coef_.ravel().round(3)}, b = {linear.intercept_[0]:.3f}')

Output:

cvxopt:  3 SVs, w = [-4.627 -1.843], b = -5.153
sklearn: 4 SVs, w = [-4.626 -1.843], b = -5.151

Same w\mathbf{w} and bb to four decimal places. The one-SV difference is scikit-learn keeping a borderline point that the hard-margin cvxopt dual zeros out at the chosen tolerance. The dual quadratic program is the SVM, and scikit-learn is just a faster implementation of it (sequential minimal optimisation, Platt 1999) packaged in a friendly API.

Act 3: The kernel trick

Replacing the linear kernel k(x,x′)=x⊤x′k(\mathbf{x}, \mathbf{x}') = \mathbf{x}^\top \mathbf{x}' with any positive-definite kernel buys non-linear boundaries without ever materialising the feature map. The classic example is the polynomial kernel k(x,z)=(1+x⊤z)2k(\mathbf{x}, \mathbf{z}) = (1 + \mathbf{x}^\top\mathbf{z})^2, which expands as an inner product in a 6-dimensional feature space. The RBF kernel k(x,x′)=exp⁡(−γ∥x−x′∥2)k(\mathbf{x}, \mathbf{x}') = \exp(-\gamma\|\mathbf{x} - \mathbf{x}'\|^2) corresponds to an infinite-dimensional feature space, and we still pay only O(N2)O(N^2) to evaluate it.

Left: data with one class (red x) clustered inside a ring of the other class (blue o), where no straight line separates them. Right: the same points lifted via phi(x, y) = (x, y, x^2 + y^2) into 3D, where a flat plane at z = 1.5 cleanly divides the two classes.

The lift ϕ(x1,x2)=(x1,x2,x12+x22)\phi(x_1, x_2) = (x_1, x_2, x_1^2 + x_2^2) makes the rings linearly separable in 3D. A linear hyperplane there projects back to the original 2D space as a circle: a non-linear boundary, found by a linear algorithm in feature space. The kernel trick is the realisation that we never need ϕ\phi itself, only the inner products ϕ(x)⊤ϕ(x′)\phi(\mathbf{x})^\top \phi(\mathbf{x}'), which the kernel computes directly from the inputs. Connect this to Gaussian process regression, another method where the kernel matrix Kij=k(xi,xj)K_{ij} = k(\mathbf{x}_i, \mathbf{x}_j) does the heavy lifting.

Going Deeper: Soft Margins, C, and Gamma

Real datasets rarely separate cleanly. The hard-margin formulation has no solution when classes overlap, so we introduce slack variables ξn≥0\xi_n \geq 0, one per point, and reformulate the objective:

min⁡w,b,ξ C∑n=1Nξn+12∥w∥2s.t.tny(xn)≥1−ξn, ξn≥0.\min_{\mathbf{w}, b, \boldsymbol{\xi}}\ C \sum_{n=1}^{N} \xi_n + \tfrac{1}{2}\|\mathbf{w}\|^2 \quad \text{s.t.}\quad t_n y(\mathbf{x}_n) \geq 1 - \xi_n,\ \xi_n \geq 0.

CC controls the trade-off. Small CC tolerates slack; large CC punishes it. In the limit C→∞C \to \infty we recover the hard-margin SVM. The dual changes only by adding upper bounds: 0≤an≤C0 \leq a_n \leq C. Geometrically, CC controls how wide the margin is allowed to be.

Three panels showing linear SVMs trained with C = 0.01, C = 1, and C = 100 on the same overlapping dataset. C = 0.01 produces a wide margin with all 120 points as support vectors. C = 1 narrows the margin and reduces support vectors to 101. C = 100 looks identical to C = 1, the regime in which slack is fully suppressed.

The animated version below sweeps CC from 0.005 to 200 across twelve frames so you can watch the margin shrink and the support set evolve in real time.

Animated C sweep: as C increases from 0.005 to 200, the margin (dashed lines) narrows and the count of support vectors stabilises around the points lying near or beyond the margin boundary.

The RBF kernel adds a second knob: γ\gamma, the inverse length-scale. Small γ\gamma produces broad influence regions (smooth boundaries, underfitting); large γ\gamma makes each support vector influence only its immediate neighbourhood (wiggly boundaries, overfitting):

Three panels showing RBF SVMs on the moons dataset with gamma = 0.3 (49 SVs, smooth boundary), gamma = 1.5 (40 SVs, clean separation), and gamma = 12 (119 SVs, memorised pockets around individual points).

Tuning CC and γ\gamma together is a 2D grid-search problem. Use GridSearchCV with stratified folds, log-spaced grids (10−3,10−2,…,10310^{-3}, 10^{-2}, \ldots, 10^{3} for both), and the overfitting explorer to build intuition for what overfitting looks like before you start. Always scale your features before fitting an RBF SVM; the kernel is distance-based and a feature with a wider range will dominate ∥x−x′∥\|\mathbf{x} - \mathbf{x}'\|.

Hinge vs Cross-Entropy: SVM vs Logistic Regression

The soft-margin SVM can be reformulated as a regularised loss-minimisation problem:

∑n=1NESV(yntn)+λ∥w∥2,\sum_{n=1}^{N} E_{\text{SV}}(y_n t_n) + \lambda \|\mathbf{w}\|^2,

with the hinge loss ESV(yt)=[1−yt]+E_{\text{SV}}(y t) = [1 - y t]_+. Maximum-likelihood logistic regression under target labels t∈{−1,+1}t \in \{-1, +1\} minimises an analogous expression with ELR(yt)=ln⁡(1+exp⁡(−yt))E_{\text{LR}}(y t) = \ln(1 + \exp(-y t)):

Hinge loss (blue) vs rescaled cross-entropy (red), with 0/1 misclassification (black dashed) and squared error (green dotted). Both hinge and cross-entropy upper-bound 0/1; squared error penalises confident-correct predictions, so it is a poor classification loss.

The two losses are similar in shape, but the hinge has a flat region for yt>1y t > 1. Confidently correct points contribute zero gradient and zero penalty. Cross-entropy never goes flat, so every point in the dataset pulls the boundary by some non-zero amount. The flat region is the algebraic source of sparsity: the KKT conditions assign an=0a_n = 0 to every confidently-correct point, which is exactly the set on which the hinge loss is flat.

When does the choice matter? Side-by-side on overlapping data:

Side-by-side: linear SVM (left) marks 101 of 120 points as support vectors and draws a maximum-margin boundary; logistic regression (right) draws a similar boundary but uses every point in fitting it. The decision lines themselves are nearly identical.

Practical implications:

  • Probability outputs. Logistic regression produces calibrated p(t=1∣x)p(t = 1 \mid \mathbf{x}) directly. The SVM does not; you have to fit a sigmoid to the decision function as a post-hoc step (Platt 1999), and Tipping (2001) shows the result is poorly calibrated. If you need a probability, reach for logistic regression or a Bayesian neural network instead.
  • Sparsity. The SVM tells you which points define the boundary. Strip out the others and prediction is O(NS)O(N_S) instead of O(N)O(N), where NSN_S is the number of support vectors. On large datasets this matters at inference time.
  • Outliers. Both losses upper-bound the 0/1 loss; the squared error from {−1,+1}\{-1, +1\} targets does not, and over-penalises confidently-correct points. Avoid squared loss for classification regardless of the algorithm.

Where Sparse Kernel Machines Came From

The SVM has a clean three-paper lineage. Boser, Guyon and Vapnik (1992) introduced the optimal margin classifier with kernels at COLT, building on Vapnik's earlier statistical learning theory work in the USSR (Vapnik & Chervonenkis, 1971). Cortes and Vapnik (1995) added the soft-margin slack variables that made it usable on overlapping data. Platt (1999) gave us sequential minimal optimisation, the algorithm that decomposes the dual QP into pairs of ana_n updates and made SVMs tractable on tens of thousands of points; it is still the engine inside libsvm and therefore inside scikit-learn's SVC.

The deeper motivation is structural risk minimisation: among all classifiers that fit the training data, prefer the one with the smallest Vapnik-Chervonenkis dimension. Maximising the margin reduces the VC dimension of the hyperplane class, which bounds the generalisation gap. The geometry (widest gap) and the statistics (tightest generalisation bound) point to the same solution.

The standard textbook references are Vapnik's The Nature of Statistical Learning Theory (1995, Springer), Cristianini and Shawe-Taylor's An Introduction to Support Vector Machines (Cambridge, 2000), and Schölkopf and Smola's Learning with Kernels (MIT, 2002). Burges (1998), "A Tutorial on Support Vector Machines for Pattern Recognition" (Data Mining and Knowledge Discovery, 2(2): 121-167), is the classic 60-page introduction and is freely available online.

A useful contrast with Bayesian model comparison: the SVM picks CC and γ\gamma by cross-validation, with no marginal-likelihood machinery to weight competing kernel choices automatically. The relevance vector machine (Tipping, 2001) plugs that gap by re-deriving sparsity from a Bayesian prior, recovering posterior probabilities, and typically using fewer basis functions than the SVM.

Limitations and the Bridge to Relevance Vector Machines

Sparse kernel machines are precise and well-grounded, and they have known weak points:

  • No native posterior probabilities. The SVM is a decision machine. Platt scaling fits a sigmoid σ(Ay(x)+B)\sigma(A y(\mathbf{x}) + B) to the decision function as a post-hoc patch, but the calibration is poor, especially in the tails (Tipping, 2001).
  • Two-class by construction. Multi-class SVMs are built by combining binary classifiers, either one-versus-rest (KK classifiers, with the inconsistency that the underlying yk(x)y_k(\mathbf{x}) values are not on the same scale) or one-versus-one (K(K−1)/2K(K-1)/2 classifiers, voted among). Weston and Watkins (1999) propose a single joint objective, but it costs O(K2N2)O(K^2 N^2) to train.
  • Quadratic-to-cubic training cost. The dual QP has NN variables and full SMO scaling sits between O(N2)O(N^2) and O(N3)O(N^3). SVMs do not scale to the millions-of-rows regime where stochastic gradient logistic regression or neural networks shine.
  • Hyperparameter sensitivity. CC and γ\gamma (or polynomial degree) interact in non-obvious ways and require careful tuning. There is no marginal-likelihood criterion to lean on, just cross-validation.
  • Kernel choice is ad hoc. Linear, RBF, polynomial, sigmoid, and string kernels are the standard menu; choosing among them is largely empirical. Kernel composition (k1+k2k_1 + k_2, k1⋅k2k_1 \cdot k_2) extends the menu but does not solve the choice problem.

Use SVMs when: you have moderate-sized data (a few thousand to a few hundred thousand rows), two classes, smooth decision boundaries, no need for calibrated probabilities, and a reason to want a sparse, interpretable support set. Reach for logistic regression when probabilities matter, for tree ensembles when interactions and tabular features dominate, and for relevance vector machines when you need both sparsity and a Bayesian posterior. Use the classification metrics calculator to pick the right operating point on the resulting decision function.

Interactive Tools

  • Classification Metrics Calculator: Convert SVM decision-function thresholds into precision, recall, F1, and ROC curves on your own confusion matrix.
  • Overfitting Explorer: Build intuition for the bias-variance trade-off that CC and γ\gamma are quietly arbitrating.
  • GP Regression Playground: Adjust the same RBF length-scale γ\gamma in a regression setting to see how kernel width controls smoothness.

Stay in the loop

Get notified when new tutorials and deep-dives are published. No spam, unsubscribe anytime.

Related Posts

Frequently Asked Questions