Chapter 7: Support Vector Machines

A slack variable $\xi_i \geq 0$ relaxes point $i$'s constraint to $y_i(\mathbf{w}^T\mathbf{x}_i + b) \geq 1 - \xi_i$. Its value describes where the point lands. $\xi_i = 0$: on or beyond its own margin plane, no violation. $0 < \xi_i < 1$: inside the margin but still on the correct side of the boundary. $\xi_i = 1$: exactly on the decision boundary. $\xi_i > 1$: on the wrong side, misclassified. At the optimum $\xi_i = \max(0, 1 - y_i f(\mathbf{x}_i))$, so each misclassified point contributes more than 1 and the total slack upper-bounds the number of training errors.

The soft-margin objective adds a penalty to the hard-margin one: $\frac{1}{2}\lVert\mathbf{w}\rVert^2$ rewards a wide margin, and $C\sum_i \xi_i$ charges for every unit of violation. The two terms pull in opposite directions. Shrinking $\mathbf{w}$ widens the margin, which usually puts more points inside it and raises total slack. The problem remains a convex quadratic program, and it is always feasible, since large enough slacks satisfy every constraint. In the dual, the only change from the hard margin is a cap on each weight, $0 \leq \alpha_i \leq C$, so no single point, including an outlier, can dominate the solution.

C sets the exchange rate between margin width and violations, playing the role of an inverse regularization strength, like $1/\lambda$ in ridge regression. Large C makes violations expensive, so the optimizer narrows the margin to classify nearly every training point correctly: low bias, high variance, and as $C \to \infty$ the hard margin returns. Small C tolerates violations for a wide, smooth margin: high bias, low variance, and at very small C the model can collapse to predicting the majority class. Because the scale of C depends on the data size and feature scaling, it must be tuned by cross-validation over a logarithmic grid such as 0.01 to 1,000.

Substituting the optimal slack $\xi_i = \max(0, 1 - y_i f(\mathbf{x}_i))$ turns the constrained problem into an unconstrained one: minimize $\frac{1}{2}\lVert\mathbf{w}\rVert^2 + C\sum_i L(y_i, f(\mathbf{x}_i))$ with the hinge loss above. The loss is zero once a point is correct with functional margin at least 1, and grows linearly as $y f(x)$ falls below 1. It is a convex upper bound on the 0-1 loss. Compared with logistic regression's log loss $\log(1 + e^{-yf})$, which is never exactly zero, hinge loss ignores well-classified points entirely, and that is the source of SVM sparsity. The unconstrained form also allows training with stochastic gradient descent.

A kernel function $K(\mathbf{x}, \mathbf{x}')$ takes two input vectors and returns a number equal to $\phi(\mathbf{x}) \cdot \phi(\mathbf{x}')$, the inner product after mapping both through a feature map $\phi$. The point is that $K$ is computed from the original vectors, often in $O(d)$ time, while $\phi$ might have millions or infinitely many dimensions. Not every function qualifies: Mercer's condition requires that, for any set of points, the Gram matrix of pairwise kernel values be symmetric positive semi-definite. A valid kernel can be read as a similarity measure, large for similar points, and kernels can be combined, since sums and products of valid kernels are valid.

Kernels work because of how the SVM solution is written. In the dual problem the training data enter only as inner products $\mathbf{x}_i \cdot \mathbf{x}_j$, and the decision function is $f(\mathbf{x}) = \sum_i \alpha_i y_i \, \mathbf{x}_i \cdot \mathbf{x} + b$, a weighted sum over support vectors. Replacing each inner product with $K(\mathbf{x}_i, \mathbf{x}_j)$ fits a maximum-margin hyperplane in the feature space while every computation stays in the input space. The cost moves from the feature dimension to the number of samples: training needs kernel values between pairs of points, and prediction needs one kernel value per support vector. That trade is excellent for moderate $n$ and poor for millions of points.

The linear kernel $K(\mathbf{x}, \mathbf{x}') = \mathbf{x}^T\mathbf{x}'$ uses the identity feature map, so it gives exactly the linear SVM of the previous topics. Its advantages are speed and simplicity: the model collapses to a single weight vector, prediction costs $O(d)$, and specialized solvers such as LIBLINEAR train on millions of sparse examples. It is the right choice when the number of features is large relative to the number of samples, as in text classification with bag-of-words features. In that regime the data are usually close to linearly separable already, so a nonlinear kernel adds cost and hyperparameters without adding accuracy. It cannot fit curved boundaries in low-dimensional data.

The polynomial kernel $K(\mathbf{x}, \mathbf{x}') = (\gamma\mathbf{x}^T\mathbf{x}' + r)^d$ corresponds to a feature space containing all monomials of the inputs up to degree $d$. The degree $d$ sets the flexibility: 2 gives quadratic boundaries such as ellipses, 3 gives cubic ones. The constant $r$ (coef0 in scikit-learn) weights lower-degree terms against the top-degree ones; with $r = 0$ only degree-$d$ products remain. The feature count grows as $\binom{p+d}{d}$ for $p$ inputs, which explains the kernel's value. In practice high degrees are numerically unstable, since values far from 1 explode or vanish when raised to a high power, so degrees above 3 or 4 are rare.

The radial basis function (RBF) kernel $K(\mathbf{x}, \mathbf{x}') = \exp(-\gamma\lVert\mathbf{x} - \mathbf{x}'\rVert^2)$ measures similarity by distance: 1 for identical points, decaying toward 0 as they move apart, with $\gamma > 0$ setting how fast. Its feature space is infinite-dimensional, as a Taylor expansion of the exponential shows, and it can approximate any smooth boundary. The decision function becomes a weighted sum of Gaussian bumps centered on the support vectors, so the model behaves like a smart nearest-neighbor method. It is the usual default for nonlinear SVMs. It needs scaled features, since distances drive everything, and it extrapolates poorly: far from all support vectors, every kernel value is near zero.

Gamma sets the reach of each support vector's influence, roughly $1/\sqrt{\gamma}$ in distance units. Large gamma makes each Gaussian bump narrow, so the boundary can wrap around individual points: low bias, high variance, and eventually memorization, with nearly every point a support vector. Small gamma makes the bumps wide, and the boundary becomes smooth, approaching a linear one: high bias, low variance. scikit-learn's default gamma='scale' uses $1/(p \cdot \mathrm{Var}(X))$, which adapts to the feature scale. Gamma interacts with C, so the two must be tuned together on a logarithmic grid, typically $10^{-3}$ to $10^{3}$, with cross-validation.

The sigmoid kernel $K(\mathbf{x}, \mathbf{x}') = \tanh(\gamma\mathbf{x}^T\mathbf{x}' + r)$ was inspired by neural networks: an SVM with this kernel resembles a two-layer network with tanh hidden units. Its weakness is that it is not a valid Mercer kernel for most settings of $\gamma$ and $r$: the Gram matrix can have negative eigenvalues, so the optimization is no longer convex, and solvers may converge to poor or unstable solutions. Lin and Lin found that it behaves acceptably only in a restricted region, with $\gamma > 0$ and $r < 0$, where it acts much like the RBF kernel. In practice it rarely beats RBF, and modern neural networks have replaced its motivation.

SVMs are distance-based: the RBF kernel uses $\lVert\mathbf{x} - \mathbf{x}'\rVert^2 = \sum_j (x_j - x'_j)^2$, and even the linear margin is measured in feature units. A feature measured in large units, such as income in dollars, contributes squared differences millions of times larger than one measured in small units, such as age in years, and the kernel effectively ignores the small one. Standardizing each feature to zero mean and unit variance, or min-max scaling, puts features on equal footing. Fit the scaler on the training data only, ideally inside a Pipeline so cross-validation does not leak test statistics. Tree models from earlier chapters do not need this; SVMs do.

C and gamma both control complexity, and they interact. Gamma sets how wiggly the boundary can be; C sets how hard the optimizer fits every point. High C with high gamma gives a boundary that wraps tightly around individual points, severe overfitting. Low C with low gamma gives a nearly linear, heavily regularized boundary, underfitting. Good settings often lie along a diagonal ridge in the plane of log C against log gamma: a smaller gamma can be offset by a larger C. Tuning one at a time can miss the best pair, so search them jointly.

Because good C and gamma values can lie anywhere across several orders of magnitude, search on a logarithmic scale. A practical recipe from the LIBSVM authors is coarse to fine. First evaluate a coarse grid such as C in 0.1, 1, 10, 100 and gamma in 0.001, 0.01, 0.1, 1 with k-fold cross-validation. Then search a finer grid centered on the best cell. If the winner sits on the edge of the grid, extend the grid in that direction before refining. Each grid point costs k fits. Randomized search or Bayesian optimization, covered in Model Evaluation, are alternatives when there are more hyperparameters.

SVMs shine on small to medium datasets, up to tens of thousands of samples, where a clear margin exists and features are informative. They are especially strong in high-dimensional sparse settings such as text, where a linear SVM is a classic baseline that is hard to beat, and in domains with good similarity measures that can be written as custom kernels. They are weaker when samples number in the millions, where kernel training cost explodes, when calibrated probabilities are central, and on heterogeneous tabular data with mixed types and missing values, where gradient-boosted trees usually win with less preprocessing. Neural networks dominate raw images, audio, and text at scale.

Kernel SVM training, typically with the SMO algorithm used by LIBSVM and scikit-learn's SVC, scales between about $O(n^2)$ and $O(n^3)$ in the number of samples $n$, depending on the data, C, and cache size. The kernel matrix alone has $n^2$ entries: 0.8 GB in float64 for 10,000 samples and 80 GB for 100,000. Prediction costs one kernel evaluation per support vector, which can also be slow when there are many. Beyond roughly 10,000 to 100,000 samples, switch to linear solvers (LinearSVC, or SGDClassifier with hinge loss), which scale about linearly, or approximate the kernel with Nystroem or random Fourier features and train a linear model on top.

An SVM outputs a score $f(\mathbf{x})$, a signed distance from the boundary, not a probability. Platt scaling converts scores to probabilities by fitting a sigmoid $P(y = 1 \mid f) = 1/(1 + \exp(Af + B))$ on held-out data, with $A$ and $B$ chosen to minimize log loss. In scikit-learn, probability=True does this with an internal 5-fold cross-validation, which makes training noticeably slower, and predict_proba can occasionally disagree with predict near the boundary. CalibratedClassifierCV gives explicit control and offers isotonic regression for larger datasets. If you only need a ranking, such as for ROC AUC, the raw decision_function scores are enough.

SVMs are binary classifiers, so $K$ classes need a combination scheme. One-vs-rest (OvR) trains $K$ classifiers, each separating one class from all others, and predicts the class with the highest score; the subproblems are imbalanced and use all $n$ samples. One-vs-one (OvO) trains $K(K-1)/2$ classifiers, one per pair of classes, each on only about $2n/K$ samples, and predicts by voting. Because kernel training is superlinear in $n$, many small OvO problems are often cheaper than a few large OvR ones. scikit-learn's SVC uses OvO internally; LinearSVC uses OvR. Accuracy is usually similar, as Hsu and Lin found.

The epsilon-insensitive loss $L_\epsilon = \max(0, \lvert y - f(x)\rvert - \epsilon)$ is zero whenever the prediction is within $\epsilon$ of the target and grows linearly beyond that. It combines two ideas. The dead zone of width $2\epsilon$ means small errors, often just noise, are ignored, which is what makes SVR sparse: points inside the tube do not affect the model. The linear growth outside, like absolute error, means large residuals and outliers have bounded influence on the gradient, unlike squared error, where a single residual of 10 counts 100 times as much as a residual of 1. It is the regression analog of the hinge loss.

SVR minimizes $\frac{1}{2}\lVert\mathbf{w}\rVert^2 + C\sum_i(\xi_i + \xi_i^*)$ subject to $y_i - f(\mathbf{x}_i) \leq \epsilon + \xi_i$ and $f(\mathbf{x}_i) - y_i \leq \epsilon + \xi_i^*$, with all slacks nonnegative. $\xi_i$ measures how far a target lies above the tube and $\xi_i^*$ how far below; at most one is positive for any point. The norm term prefers flat functions, a form of regularization, and C prices points that escape the tube. The dual solution is $f(\mathbf{x}) = \sum_i (\alpha_i - \alpha_i^*) K(\mathbf{x}_i, \mathbf{x}) + b$, where only points on or outside the tube have nonzero coefficients. These are SVR's support vectors.

Epsilon sets the half-width of the tube and therefore the size of residual the model treats as noise. A larger epsilon puts more points inside the tube, giving fewer support vectors, a sparser and faster model, and a flatter fit; too large and the tube swallows real signal and the model underfits. A smaller epsilon makes nearly every point a support vector and fits more closely, including noise. Epsilon is in the same units as the target, so a natural starting point is a fraction of the noise standard deviation, or the error tolerance that matters for the application. Cherkassky and Ma proposed $3\sigma\sqrt{\ln n / n}$ for noise level $\sigma$.

Kernels work in SVR exactly as in classification: replace inner products with $K(\mathbf{x}_i, \mathbf{x}_j)$, and the prediction becomes a weighted sum of kernel values at the support vectors. A linear kernel fits a hyperplane, a polynomial kernel fits polynomial trends, and the RBF kernel fits smooth arbitrary curves as a sum of Gaussian bumps. The kernel's inductive bias matters most outside the training range. A linear model extrapolates its trend, while an RBF prediction decays toward the intercept far from all support vectors, because every kernel value there is near zero. Choose the kernel to match the expected shape, and tune C, epsilon, and gamma jointly.