Support Vector Machines and Kernel Methods

Among the many hyperplanes that might separate two linearly separable classes, Corinna Cortes and Vladimir Vapnik's 1995 paper "Support-Vector Networks" argues that one particular choice is principled: the hyperplane with maximal margin, defined as "the linear decision function with maximal margin between the vectors of the two classes." Concretely, the optimal hyperplane "separates the training data with a maximal margin: it determines the direction w/|w| where the distance between the projections of the training vectors of two different classes is maximal." Stanford CS229's lecture notes formalize this margin concept in two related but distinct ways: the functional margin of a training example (x⁽ⁱ⁾, y⁽ⁱ⁾) is defined as γ̂⁽ⁱ⁾ = y⁽ⁱ⁾(wᵀx⁽ⁱ⁾ + b), while the geometric margin, γ⁽ⁱ⁾ = y⁽ⁱ⁾((w/‖w‖)ᵀx⁽ⁱ⁾ + b/‖w‖), rescales this by the norm of w so that it corresponds to an actual, rescaling-invariant Euclidean distance from the point to the decision boundary; because the functional margin can be made arbitrarily large simply by scaling w and b up, it is the geometric margin that captures what maximal margin really means. CS229's notes show that maximizing this geometric margin over a linearly separable dataset reduces to the optimization problem min_{w,b} (1/2)‖w‖² subject to y⁽ⁱ⁾(wᵀx⁽ⁱ⁾ + b) ≥ 1 for every training example, a quadratic objective with linear constraints, which Cortes and Vapnik's original paper describes as a "quadratic programming problem."

Because this optimization problem's constraints are only tight, meaning satisfied with equality, for the training points closest to the boundary, the solution w depends only on a small subset of the training data: the points lying exactly on the margin, which give the support vector method its name. Every other training point, safely on the correct side of its margin, could in principle be removed from the dataset entirely without changing the fitted hyperplane at all, a sharp contrast to methods like linear regression's normal equations, where every single training point contributes to the final solution. Cortes and Vapnik's paper further shows that this quadratic program can be reformulated into an equivalent dual problem in which the objective depends on the training data only through pairwise dot products between input vectors, never through the vectors' individual coordinates; CS229's notes make this dual explicit as maximizing W(α) = Σᵢαᵢ − (1/2)Σᵢ,ⱼ y⁽ⁱ⁾y⁽ʲ⁾αᵢαⱼ⟨x⁽ⁱ⁾, x⁽ʲ⁾⟩ over the dual variables α, with the fitted classifier's prediction for a new point x likewise expressible using only inner products, wᵀx + b = Σᵢαᵢy⁽ⁱ⁾⟨x⁽ⁱ⁾, x⟩ + b. This dependence on inner products alone, rather than on the raw feature vectors themselves, is what makes the kernel trick possible, since any expression built entirely out of inner products can be computed in a different, implicit feature space simply by substituting a different function for the inner product.

Because the SVM optimization problem and its final prediction rule depend on the training data only through inner products ⟨x⁽ⁱ⁾, x⁽ʲ⁾⟩, Stanford CS229's lecture notes describe a substitution that lets support vector machines draw nonlinear decision boundaries without ever leaving the linear-classifier machinery already derived: replace every inner product with a kernel function K(x, z), defined so that K(x, z) = ⟨φ(x), φ(z)⟩ for some feature mapping φ that sends the original input into a new, often much higher-dimensional, feature space. Wherever the algorithm previously computed ⟨x, z⟩ directly, it now computes K(x, z) instead, which implicitly performs the entire computation as if the inputs had first been mapped through φ into the higher-dimensional space, without ever actually constructing φ(x) or φ(z) as explicit vectors. CS229's notes work through the Gaussian, or radial basis function, kernel as a concrete example, K(x, z) = exp(−‖x − z‖²/(2σ²)), describing it as "a reasonable measure of x and z's similarity" that in fact "corresponds to an infinite dimensional feature mapping φ," meaning the implicit feature space this kernel corresponds to has infinitely many dimensions, a space no algorithm could ever construct explicitly but which the kernel trick makes fully usable anyway, since only K(x, z) itself, never φ(x), ever needs to be computed.

Not every function of two inputs qualifies as a valid kernel, since the substitution only makes mathematical sense if K(x, z) really does correspond to an inner product in some feature space. CS229's notes state the precise condition, attributed to Mercer's theorem: for K to be a valid kernel, it is necessary and sufficient that, for any finite set of points {x⁽¹⁾, ..., x⁽ⁿ⁾}, the corresponding n-by-n kernel matrix, whose (i, j) entry is K(x⁽ⁱ⁾, x⁽ʲ⁾), is symmetric and positive semi-definite. Cortes and Vapnik's original 1995 paper anticipates exactly this generalization, noting that the classification function "only depends on the dot-products" in feature space and that substituting "any symmetric function K(u, v)" satisfying this same Mercer condition for the ordinary inner product lets the support vector method construct "arbitrary types of decision surfaces," not just straight hyperplanes, entirely by choosing a different kernel rather than by redesigning the optimization algorithm itself. This is the sense in which the kernel trick separates the geometry of the problem, whatever curved or twisted decision surface the data actually requires, from the algorithm, which continues to solve the exact same quadratic program regardless of which kernel is plugged in.

The maximum-margin idea underlying support vector classification can be adapted to regression as well, producing what Alex Smola and Bernhard Scholkopf's 2004 tutorial on the subject calls Support Vector Regression, or SVR. Rather than trying to make every prediction match its target as closely as possible, the way ordinary least-squares regression does, SVR's stated goal is different: "to find a function f(x) that has at most ε deviation from the actually obtained targets yi for all the training data, and at the same time is as flat as possible," where ε is a small tolerance chosen in advance. This is formalized using the ε-insensitive loss function, defined so that a deviation ξ incurs zero loss when |ξ| ≤ ε and a loss of |ξ| − ε otherwise, meaning any prediction that falls within ε of its true target incurs exactly zero loss, no matter how close or far from perfect it is within that tolerance, while predictions that miss by more than ε are penalized only for the excess beyond ε, and that excess is penalized linearly rather than quadratically. Because not every training point can necessarily be fit within an ε-wide tube around the true function while also keeping the function as flat as possible, the tutorial introduces slack variables ξᵢ, ξᵢ* "to cope with otherwise infeasible constraints," allowing some points to fall outside the tube at a controlled cost.

This framing produces an optimization problem with the same overall shape as the classification SVM: minimize (1/2)‖w‖², the same flatness-maximizing objective used to find the maximum-margin hyperplane, subject now to constraints that keep predictions within the ε-tube wherever possible and penalize the slack variables when they cannot be. The tutorial is explicit that "only the points outside the shaded region contribute to the cost," which mirrors the classification case's dependence on only the support vectors, points near or violating the margin, rather than on every single training example; in SVR, the analogous support vectors are precisely the training points that lie on or outside the boundary of the ε-tube, while points comfortably inside it contribute nothing at all to the fitted function. Because this optimization problem, like the classification SVM's, can be expressed entirely in terms of inner products between training inputs, the same kernel substitution used for nonlinear classification carries over directly to SVR: replacing each inner product with a kernel function such as the Gaussian RBF kernel lets support vector regression fit a curved, nonlinear function through the ε-tube rather than only a flat line or hyperplane, while still solving the same fundamentally convex, sparsely-supported optimization problem underneath.