L’astuce du noyau : noyaux RBF, polynomial et sigmoïde

Many real-world classification problems are not linearly separable — no straight line (or hyperplane) can correctly separate the classes. For example, data arranged in concentric rings cannot be separated by any linear boundary. One approach is to manually create new features (e.g., x², x×y) that make the classes linearly separable in the augmented space. The kernel trick does this automatically and implicitly, without ever computing the coordinates in the high-dimensional space.

A feature map φ(x) transforms an input vector into a higher-dimensional representation. For example, φ([x₁, x₂]) = [x₁², √2·x₁x₂, x₂²] maps 2D data to 3D. After this mapping, classes that overlapped in 2D may become linearly separable in 3D. The SVM then finds a maximum-margin hyperplane in the transformed space. The corresponding decision boundary in the original 2D space is a curve, giving the SVM non-linear classification ability.

Computing φ(x) explicitly is expensive or even impossible (some feature maps produce infinite-dimensional vectors). The key insight is that the SVM dual formulation only needs dot products φ(xᵢ)·φ(xⱼ), not the individual feature vectors. A kernel function K(xᵢ, xⱼ) computes this dot product directly from the original inputs without ever constructing φ(xᵢ). This is the kernel trick: expensive high-dimensional dot products computed cheaply in input space.

The polynomial kernel is defined as K(xᵢ, xⱼ) = (γ · xᵢ·xⱼ + r)^d, where d is the polynomial degree, γ is a scaling factor, and r is the coef0 parameter. A degree-2 polynomial kernel implicitly creates all pairwise interactions (x₁x₂) and squared terms (x₁²). Higher degrees create more complex boundaries but risk overfitting. In scikit-learn, use SVC(kernel='poly', degree=3).

The Radial Basis Function (RBF) kernel, also called the Gaussian kernel, is defined as K(xᵢ, xⱼ) = exp(-γ · ||xᵢ - xⱼ||²). It measures similarity based on distance: nearby points have kernel value close to 1, distant points close to 0. The RBF kernel corresponds to an infinite-dimensional feature map, giving the SVM unlimited expressive power. It is the default kernel in scikit-learn's SVC and works well on most datasets with proper tuning of C and γ.

The gamma parameter controls how far the influence of a single training example reaches. A small gamma makes each point's influence extend far — the decision boundary is smooth and the model underfits (high bias). A large gamma makes influence drop off steeply — the boundary wraps tightly around individual training points (high variance, overfitting). scikit-learn defaults: gamma='scale' (uses 1/(n_features × X.var())) or gamma='auto' (uses 1/n_features). Always tune C and gamma together.

The sigmoid kernel is K(xᵢ, xⱼ) = tanh(γ · xᵢ·xⱼ + r), which resembles the activation function of a two-layer neural network. It is not always a valid (positive semi-definite) kernel for all parameter values, meaning the SVM optimisation may not converge to a global minimum. The sigmoid kernel is rarely the best choice in practice — RBF almost always outperforms it — but it can be useful when interpretability of the neural-network analogy is valued.

A practical guide for kernel selection: use linear when you have many features (text, genomics) or when the data is already high-dimensional — adding more dimensions via kernels is unnecessary; use RBF as the default for low-to-medium dimensional tabular data — it is the most flexible and often best; use polynomial when you have explicit reason to believe polynomial feature interactions matter; avoid sigmoid unless experimenting. Always compare kernels with cross-validation on your specific dataset.

The main weakness of kernel SVMs is scalability. Training requires solving a quadratic programming problem that scales as O(n²) to O(n³) in the number of training examples. For 100,000 examples, an RBF SVM can take hours or run out of memory. Solutions: (1) use LinearSVC for linear kernels, which scales to millions of examples; (2) use approximate kernel methods like Nystroem or RBFSampler that create explicit low-dimensional feature maps; (3) switch to gradient boosting or neural networks for truly large datasets.

The correct way to select a kernel is to compare them all with cross-validation on your dataset. Different datasets favour different kernels. A linearly separable problem gets no benefit from RBF. A problem with complex local structure may need high gamma RBF. Always start with the linear kernel as a baseline, then try RBF with a grid search over C and gamma. If neither outperforms the other significantly, choose linear for interpretability and speed.

Not every function can be used as a kernel. A valid kernel must satisfy Mercer's condition: it must be symmetric (K(x,y) = K(y,x)) and produce a positive semi-definite Gram matrix for any set of inputs. This guarantees that the kernel corresponds to a valid dot product in some feature space, making the SVM optimisation problem convex (one global minimum). Custom kernels for DNA sequences, graphs, or text can be defined and passed to SVC(kernel='precomputed') as long as they satisfy Mercer's theorem.

Test your understanding of the Kernel Trick from this lesson.

In this lesson you learned: kernel functions implicitly compute dot products in high-dimensional feature spaces, the RBF kernel is the most versatile default with gamma controlling the influence radius, and kernel SVMs do not scale to large datasets so consider linear kernels or approximate methods first. Next up we explore tuning C and gamma simultaneously with a grid search.