Kernels & Support Vector Machines
Maximum margins and the kernel trick.
Among all the lines that separate two classes, pick the one farthest from both. That single geometric choice leads to a convex quadratic program whose solution depends on only a few training points, whose dual sees the data only through inner products, and whose generalization can be bounded without reference to the dimension. Replace the inner products by a kernel and the same machinery learns curved boundaries in infinite-dimensional feature spaces.
What you’ll learn
- Derive the hard-margin SVM's primal and dual problems, use the KKT conditions to characterize support vectors, and prove the leave-one-out bound .
- Formulate the soft-margin SVM as regularized hinge-loss minimization, derive its box-constrained dual, and explain why the hinge loss is classification-calibrated.
- State Mercer's condition and the Moore–Aronszajn construction of a reproducing kernel Hilbert space, and compute the feature map of a polynomial kernel.
- State and sketch a margin-based generalization bound that depends on rather than on the dimension.
The maximum-margin hyperplane
A linear classifier predicts . On a training point, is its functional margin, positive when the point is classified correctly, and dividing by gives its geometric margin, the signed distance to the hyperplane. Rescaling changes neither the classifier nor the geometric margin, so fix the scale by requiring . The margin is then , and maximizing it is a convex quadratic program:
Why maximize the margin? A margin makes every training point robust: no perturbation smaller than can flip it. It also controls learning. The perceptron makes at most mistakes on data in a ball of radius that are separable with margin (Novikoff's theorem, in Perceptron Convergence & Its Limits), and the last step of this lesson turns the same ratio into a generalization bound that ignores the dimension.
Duality, KKT conditions and support vectors
Attach a multiplier to each margin constraint:
Minimize over the primal variables. Setting the gradients to zero expresses through the data and constrains the multipliers:
Substitute back. The data now appear only through inner products :
The primal is a convex QP with affine constraints, so strong duality holds whenever it is feasible, and the KKT conditions of Optimization & Convexity characterize the optimum. Complementary slackness says that only points on the margin can carry weight:
The points with are the support vectors. They alone determine , and any one of them gives . Delete every other point and the solution does not change, which yields a clean bound on generalization.
A hard-margin SVM trained on 1,000 linearly separable points has 25 support vectors. What does the leave-one-out argument guarantee?
- The test error is exactly 2.5%
- The leave-one-out error is at most 2.5%
- The training error is 2.5%
- Nothing, unless a kernel is used
Show the answer
B. The leave-one-out error is at most 2.5%
At most the 25 support vectors can be misclassified when left out, so the leave-one-out error is at most ; in expectation over training sets, that bounds the test error of an SVM trained on 999 points. A sparse solution is evidence of good generalization, whatever the dimension of the feature space.
Soft margins and the hinge loss
Real data are rarely separable. The soft-margin SVM (Cortes & Vapnik, 1995) lets point violate its margin by a slack , at a price per unit of slack:
At the optimum each slack is as small as allowed, with . So the soft-margin SVM is -regularized empirical risk minimization with the hinge loss:
In the Lagrangian, the multipliers of the constraints enter through . The dual is the hard-margin dual with a box:
Complementary slackness sorts the training points into three kinds:
Points beyond the margin carry no weight, points on it are the free support vectors, and points inside it or misclassified sit at the bound . The dual is solved by SMO (Platt, 1998) or, for linear SVMs, by dual coordinate descent (Hsieh et al., 2008).
Is the hinge loss a sensible surrogate for 0–1 loss? It upper-bounds it, , and it is classification-calibrated: the minimizer of the conditional hinge risk is , the Bayes classifier. Quantitatively, for every (Zhang, 2004; Bartlett, Jordan & McAuliffe, 2006), so driving the hinge risk to its minimum drives the classification risk to the Bayes error. The SVM's output is not a probability, though; Platt scaling fits a sigmoid to it afterwards (Platt, 1999).
Kernels: the trick, Mercer and the RKHS
In the dual, and in the classifier , the data appear only through inner products. Replace each by and the SVM becomes a maximum-margin linear classifier in the feature space of , which is a curved boundary in the original space, at the cost of evaluating : the kernel trick.
In two dimensions, expand the square of an inner product:
That is an inner product of three-dimensional features, and a linear boundary in that space is a conic in the plane. On the classifier widget's disk-and-ring data, where a linear SVM manages only 67% test accuracy, the feature alone separates the classes perfectly:
In general with corresponds to all monomials of degree at most , a feature space of dimension , evaluated in time. The Gaussian kernel is infinite-dimensional: factor out the norms and expand the exponential of the inner product:
Necessary. If is an inner product of features, every quadratic form of a Gram matrix is a squared norm:
Sufficient (Moore–Aronszajn). Take the functions as building blocks and define their inner product by the kernel. Positive semidefiniteness makes this a valid inner product on their span:
The reproducing property holds by construction, and Cauchy–Schwarz gives , so a function of norm 0 vanishes everywhere. Completing the span gives , with feature map :
Kernels can be built from kernels: sums, products (by the Schur product theorem), positive multiples, limits, for any function , and the exponential of a kernel are all kernels. Kernels also exist on strings, graphs and sets, which is how SVMs classified text and protein sequences long before deep learning. By the representer theorem of Linear Models & Their Geometry, the optimal classifier is always a finite combination .
Why margins generalize
Replace the 0–1 loss by the ramp loss : 1 below 0, 0 above , and linear in between. It is sandwiched between the two indicators of the bound and is -Lipschitz:
The standard Rademacher-complexity bound for a loss with values in holds uniformly over , with the empirical Rademacher complexity:
Talagrand's contraction lemma strips off the Lipschitz ramp at the price of a factor ; the labels do not change the complexity, because has the same law as :
For the linear class, Cauchy–Schwarz and then Jensen's inequality bound the complexity by the radius of the ball, with no dimension anywhere:
The bound depends on the hypothesis only through , which is scale-free: rescaling changes and together. For the hard-margin SVM, take and : the complexity term is , whatever the dimension of the feature space, even infinite as for the Gaussian kernel. Large margins relative to the data's radius, not few parameters, are what generalize. The bound is stated for a fixed ; making it uniform over adds only a term of order .
Data lie in a ball of radius , the hard-margin SVM finds margin (so at ), and . What is the complexity term ?
Show the answer
0.2
. With the confidence term adds about 0.04, and on separable data the empirical margin error is 0, so the bound guarantees a test error below about 24%. That is loose, as such bounds usually are, but it does not depend on the dimension, and it shrinks like .
Key takeaways
- The hard-margin SVM maximizes the margin by minimizing subject to ; its dual sees the data only through inner products.
- KKT complementary slackness makes the solution sparse: only support vectors have , and the leave-one-out error is at most .
- The soft margin is -regularized hinge-loss minimization, with box constraints in the dual; the hinge loss is classification-calibrated but yields no probabilities.
- A symmetric function is a kernel exactly when all its Gram matrices are positive semidefinite (Mercer, Moore–Aronszajn); polynomial kernels compute monomials in time, and the Gaussian kernel is infinite-dimensional.
- Margin bounds of the form are dimension-free: large margins relative to the data's radius, not few parameters, are what generalize.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
A soft-margin SVM is retrained after deleting a training point that had . What happens to the solution?
- Nothing: the same remains optimal
- The margin widens
- Every remaining changes slightly
- changes but does not
Show the answer
A. Nothing: the same remains optimal
The old solution satisfies the KKT conditions of the reduced problem: the deleted point contributed nothing to or to , and every other condition is unchanged. The widget shows the converse direction: points added far on the correct side leave the boundary untouched.
Why can an SVM use the Gaussian kernel, whose feature space is infinite-dimensional?
- Because the SVM truncates the feature space to its first dimensions
- Because the dual problem and the classifier need only the kernel values , an Gram matrix
- Because the Gaussian kernel's feature vectors are sparse
- Because the margin bound rules out infinite dimensions
Show the answer
B. Because the dual problem and the classifier need only the kernel values , an Gram matrix
Both the dual objective and involve the data only through kernel values, so feature vectors are never formed. The representer theorem guarantees that nothing is lost by working in the span of the functions .
Which of these functions on is not a valid kernel?
- , for
Show the answer
C.
For two points at distance , the Gram matrix of is , with eigenvalues : not positive semidefinite. The others are kernels: a polynomial kernel, the Gaussian kernel, and the covariance function of Brownian motion.
At an input with , which value of minimizes the expected hinge loss ?
- , which is
Show the answer
D.
The conditional hinge risk is . On it equals , which keeps falling, and beyond it rises, so the minimum is at , with risk 0.6. The hinge loss recovers the Bayes classifier's label, , but not the probability, unlike the log loss, whose minimizer is the log-odds, 0.85.
Further reading
- B. E. Boser, I. M. Guyon & V. N. Vapnik, "A training algorithm for optimal margin classifiers," Proceedings of COLT (1992).
- C. Cortes & V. Vapnik, "Support-vector networks," Machine Learning 20, 273–297 (1995).
- B. Schölkopf & A. J. Smola, Learning with Kernels (MIT Press, 2002).
- P. L. Bartlett & S. Mendelson, "Rademacher and Gaussian complexities: risk bounds and structural results," Journal of Machine Learning Research 3, 463–482 (2002).
- M. Mohri, A. Rostamizadeh & A. Talwalkar, Foundations of Machine Learning, 2nd ed. (MIT Press, 2018).