Kernels and Nonlinear Decision Boundaries

Kernel methods compare examples. The comparison runs through an implicit or explicit feature space. Each of the comparisons below has been built, published and costed by somebody; none of them is a shape that merely could exist.

Many algorithms can be written using pairwise inner products between examples. A valid kernel computes the inner product that would occur in another feature space without constructing every transformed coordinate.

The algorithm still needs a kernel matrix or repeated similarity evaluations. Implicit features do not imply free scaling.

The trick arrived with its costs already tabulated. Boser, Guyon and Vapnik introduced it at COLT 1992, training ten separators on handwritten digits, one per class. The database held 7,300 training and 2,000 test images at 16 × 16 pixels. The kernels were polynomials of order q. Their table lists the dimension N of the corresponding feature space at each order. It is 256 at q = 1, about 3 × 10^4 at q = 2, and 8 × 10^7 at q = 3. At q = 4 it is 4 × 10^9, and at q = 5 it is 1 × 10^12. Across that same range the average number of supporting patterns per separator falls from 97 to 89, 79, 72 and 69. The test error goes 10.5%, 5.8%, 5.2%, 4.9%, 5.2%. A feature space of about 10^12 dimensions is bought without storing a single extra coordinate. What the model keeps is patterns: “The solution is expressed as a linear combination of supporting patterns.”

Hyperparameters determine how local, smooth, or interaction-heavy the boundary becomes. The people who wrote the library these kernels ship in also wrote down which one to start with. They gave reasons in print rather than taste.

The linear kernel is the ordinary dot product, x_i^T x_j. It is equivalent to a linear separator in the supplied features. It is efficient for sparse high-dimensional data, and it offers no nonlinear rescue without engineered features. It is also not a separate country from the RBF kernel. The guide's first reason for making RBF the default is that the linear kernel is a special case of it (Keerthi and Lin 2003). The linear fit remains the baseline you run before anything richer. But it is a corner of the RBF family rather than an alternative to it.

The RBF kernel, exp(-gamma||x_i - x_j||^2), creates local smooth influence. Gamma sets the width of the neighbourhood, and the kernel is sensitive to scaling. The guide's verdict is one sentence: “In general, the RBF kernel is a reasonable first choice.” Part of the reason is arithmetic hygiene. RBF values obey 0 < K_ij <= 1, “in contrast to polynomial kernels of which kernel values may go to infinity (gamma x_i^T x_j + r > 1) or zero (gamma x_i^T x_j + r < 1) while the degree is large”.

That sentence is what “can grow extreme values” means for the polynomial kernel, (gamma x_i^T x_j + r)^d. The degree controls complexity. The scale and the offset matter. The structure it imposes is global interaction rather than local influence. The guide's other objection is cheaper to state: the polynomial kernel has more hyperparameters to search than the RBF kernel does, so it costs more grid to reach the same place.

A domain kernel encodes similarity for strings, graphs, sequences or sets, and can preserve specialized invariances that no generic kernel knows about. Two bills come with it. The first is mathematical validity, and the cautionary case is not exotic. Of the fourth basic kernel in its own list the guide records that “the sigmoid kernel is not valid (i.e. not the inner product of two vectors) under some parameters (Vapnik, 1995)”. That kernel ships with the library. The second bill is expense, and the string-kernel authors measured their own. Their Reuters data set held “approximately 9600 training examples and 3200 test examples with an average length of approximately 2300 characters”. At that size they judged the kernel “is too expensive to apply on large text collections”, which is why their paper introduces an approximation. A domain kernel must match the task evidence. It must also still be affordable at the size the task actually arrives in.

The same training examples can create a broad smooth boundary or a collection of tiny local islands. Which one you get at the extremes is a proved result rather than a plotting impression. Keerthi and Lin proved it in Neural Computation in 2003, writing the kernel as K(x, x') = exp(-||x - x'||^2 / 2 sigma^2).

Small gamma is large sigma^2, and similarity decays slowly, creating broad influence and smoother boundaries. Pushed far enough it stops being smooth and starts being empty. Sigma^2 tending to infinity with C fixed is one of the three routes they identify to severe underfitting, in which the entire data space is assigned to the majority class. The other two are sigma^2 fixed with C tending to 0, and sigma^2 tending to 0 with C fixed small. Scikit-learn 1.9.0 states the same limit in engineering terms: with very small gamma “The resulting model will behave similarly to a linear model”.

Moderate gamma is the region where local structure appears while neighbouring cases still interact, and it is the region a search exists to find. The published grids show how wide the hunt has to be. The scikit-learn example searches C over np.logspace(-2, 10, 13) and gamma over np.logspace(-9, 3, 13).

Large gamma is sigma^2 tending to 0. Similarity decays quickly, and with C fixed sufficiently large this is severe overfitting in the paper's precise sense: small regions around the minority-class training examples are classified as that class, and the rest of the space as the majority class. The library says the same thing to its users. “If gamma is too large, the radius of the area of influence of the support vectors only includes the support vector itself and no amount of regularization with C will be able to prevent overfitting.” The islands are not a rendering artifact. They are the model.

The violation penalty and the kernel width are therefore not two independent dials, and Keerthi and Lin tie them together exactly. When sigma^2 tends to infinity with C = C_tilde * sigma^2, the classifier converges to the linear SVM with penalty C_tilde. Along that one path through the pair, the nonlinear model is the linear model. That is why C and gamma have to be searched together rather than one after the other.

A kernel used in standard SVM or kernel-ridge theory should generate a positive semidefinite Gram matrix under the required conditions, and an intuitive similarity can violate that property and break the geometry or optimizer assumptions.

Use established kernels. Otherwise verify the mathematical conditions of a custom design.

The condition is old enough to have a citation. It is current enough to have a shipping counterexample. It descends from a paper on functions of positive and negative type that James Mercer published through the Royal Society in 1909. The counterexample is installed on most machines that run an SVM. LIBSVM's kernel type 3 is the sigmoid, tanh(gamma*u'*v + coef0). Scikit-learn exposes the same function as the “sigmoid” kernel, with r specified by coef0. Hsuan-Tien Lin and Chih-Jen Lin studied it at National Taiwan University. With the sigmoid, they record, “the kernel matrix may not be positive semi-definite (PSD)”. It is only “conditionally positive definite (CPD) in certain parameters and thus are valid kernels there”. And “existing software may have difficulties such as endless loops when using non-PSD kernels”. A similarity function can be popular, implemented, and still outside the theory that justifies the solver.

This is the same kernel the practical guide flags while listing its four basic choices. That is worth noticing about the amber card in the comparison above. The validity requirement on a domain kernel is not a formality invented for exotic designs. It is a condition the fourth stock kernel in the standard library already fails under some parameters.

Kernel hyperparameters interact strongly with preprocessing and regularization. The sequence below is not a preference. It is close to the procedure the LIBSVM guide recommends — scale the data, use the RBF kernel, grid-search C and gamma by cross-validation — and the guide publishes what each step is worth on one data set.

That data set is astroparticle physics: 3,089 training instances, 4,000 testing instances, 4 features, 2 classes. LIBSVM's default parameters on the raw data give 66.925% test accuracy. Linearly scaling each attribute to [-1, +1], changing nothing else, gives 96.15%. Scaling plus the grid search, which selects C = 2 and gamma = 2 at a five-fold cross-validation rate of 96.8922%, gives 96.875%. Table 1 records the same task at 75.2% accuracy “by users” against 96.9% “by our procedure”. The gap between a competent user and the written procedure on identical data is that table.

1. Fit a linear baseline, to determine whether the supplied features already separate the task.

2. Scale inside folds. The 66.925%-to-96.15% jump is this step and only this step. Doing it inside the folds is what keeps distance-based kernel parameters comparable without letting the held-out rows inform the scaling.

3. Search C and kernel settings jointly, on logarithmic ranges, under valid nested evaluation. “We found that trying exponentially growing sequences of C and γ is a practical method to identify good parameters”, the guide reports. Its example sequences are C = 2^-5, 2^-3, ..., 2^15 and gamma = 2^-15, 2^-13, ..., 2^3, with a coarse grid first and a finer grid on the better region.

4. Map support: inspect distances, support vectors and sparse regions.

5. Stress extrapolation: test points beyond observed feature support and under shift.

6. Measure computation: record Gram-matrix memory, training time and prediction support-vector count. The quantity to write down for the first of those is the standard cost of kernel training, O(m^2) space in the training set size m.

The kernel trick can avoid an enormous explicit feature vector. Standard kernel training often still depends on pairwise relations among samples. Memory and training cost can therefore grow rapidly with the number of rows.

Approximation methods, linearized features, or different model families may be necessary at scale.

That bill was measured early, and the modern library still documents it. In 1998 John Platt published sequential minimal optimization at Microsoft Research, and the abstract states the band. “SMO scales somewhere between linear and quadratic in the training set size for various test problems, while the standard chunking SVM algorithm scales somewhere between linear and cubic in the training set size.” His test case was the UCI adult income task: 32,562 training examples encoded as 123 binary attributes. His log-log fits give SMO ~N^1.9 against chunking ~N^3.1 for a linear SVM. For a Gaussian one they give ~N^2.1 against ~N^2.9. Scikit-learn 1.9.0 puts its own libsvm-based solver in a band that begins where Platt's measurements ended. It “scales between O(n_features × n_samples^2) and O(n_features × n_samples^3) depending on how efficiently the libsvm cache is used in practice”. It also names the size at which exact kernel training stops being practical. “The fit time scales at least quadratically with the number of samples and may be impractical beyond tens of thousands of samples.”

A second, independent group states the exponents and the sizes together. Tsang, Kwok and Cheung, at the Hong Kong University of Science and Technology, open their 2005 core vector machine paper by stating the standard cost of kernel training: O(m^3) time and O(m^2) space in the training set size m. “It is thus computationally infeasible on very large data sets.” Their Table 1 gives the sizes at which that becomes the binding constraint: checkerboard 1,000,000 patterns over 2 attributes; forest cover type 522,911 over 54; extended USPS digits 266,079 over 676; extended MIT face 889,986 over 361; KDDCUP-99 intrusion detection 4,898,431 over 127; UCI adult 32,561 over 123. An O(m^2) object over 4,898,431 rows is not slow, it is absent.

“Approximation methods may be necessary at scale” has a measured price. Rahimi and Recht put one on it in 2007. “Unfortunately, methods that operate on the kernel matrix (Gram matrix) of the data scale poorly with the size of the training dataset.” Their answer was to replace the Gram matrix with a fixed random feature map, and their Table 1 prices it. On the UCI Adult classification task, 32,000 instances over 123 dims — the same task Platt used — random Fourier features with D = 500 give 14.9% test error in 9 seconds, against 15.1% in 7 minutes for the exact SVM (SVMlight). On Forest Cover, 522,000 instances over 54 dims, random binning features with P = 50 give 2.2% in 25 minutes, against 2.2% in 44 hours for the exact SVM (libSVM). The identical error rate, at 44 hours against 25 minutes. The same table lists CPU (6,500 instances, 21 dims), Census (18,000 instances, 119 dims) and KDDCUP99 (4,900,000 instances, 127 dims).

Individual raw-feature coefficients may not exist in an accessible form, so interpretation shifts toward support vectors, sensitivity, local perturbations, and comparison with simpler representations.

Do not infer a universal feature effect from a boundary whose behavior depends on all pairwise similarities.

There is a theorem behind that shift. The generalized representer theorem, published in 2001, extends Wahba's classical result “to a larger class of regularizers and empirical risk terms”. Its authors state the consequence directly. “The result shows that a wide range of problems have optimal solutions that live in the finite dimensional span of the training examples mapped into feature space, thus enabling us to carry out kernel algorithms independent of the (potentially infinite) dimensionality of the feature space.” The same property that makes the computation possible is what removes the per-feature coefficient. The fitted function is an expansion over training examples. So the objects available for inspection are those examples and their weights. Their number is a figure you have already seen fall, from 97 to 69 per separator across nine and a half orders of magnitude of implicit dimension.