Full search page →

PR 04 · Neighbors, Kernels and Nonlinear Classifiers

Pattern RecognitionIntermediate28 minUpdated Nov 5, 2026

Needs: PR 03 · Linear Models for Regression and Classification

Navigate: this page and this track: Navigate: this page and this track
Explore this chapter 1 interactive experiment

Run leave-one-out k-nearest-neighbour classification on the real iris measurements, then change the unit of one feature: no flower moves, yet the neighbours and the accuracy do.

What you’ll learn

  • How nearest-neighbor rules produce nonlinear decision regions without fitting any parameters, and why the distance metric matters as much as kk.
  • What the kernel trick is, what makes a function a valid (Mercer) kernel, and how to check it on a finite Gram matrix.
  • The soft-margin support vector machine: its primal and dual problems, support vectors, and how the hyperparameters CC and γ\gamma shape the boundary.
  • How Gaussian processes and relevance vector machines reuse kernels with a probabilistic interpretation.
  • Three other routes to nonlinearity: radial basis function (RBF) networks, decision trees grown with impurity measures (CART), and multilayer perceptrons.
  • How to compare these families fairly, and where they stand in 2026.

The big picture

PR 03 built classifiers whose decision boundary is a straight line, a plane or a hyperplane. Many real problems are not like that. Points inside a ring cannot be separated from points outside it by any straight line. Handwritten “1”s and “7”s overlap in pixel space along curved, twisted regions. We need boundaries that bend.

There are only a few basic ways to make them bend:

  1. Compare with stored examples. Label a new point by looking at the most similar training points (nearest neighbors).
  2. Change the representation, then stay linear. Map each input xx to new features ϕ(x)\phi(x) in which a hyperplane does work. Kernels do this implicitly; RBF networks and multilayer perceptrons do it explicitly, with learned or fixed basis functions.
  3. Cut the space into pieces. A decision tree asks a sequence of yes/no questions, and each answer path ends in a small box with its own label.

One warning applies to every method in this chapter. A nonlinear classifier can only use information that the measurements contain. If two classes look identical in the features you recorded, no amount of boundary-bending will separate them. Feature design is the subject of PR 05. The textbook background for this chapter is Theodoridis and Koutroumbas, Chapters 2 and 4 [1], and Bishop, Sections 2.5.2, 5.1–5.3, 6.1–6.4, 7.1–7.2 and 14.4 [2].

Nearest-neighbor classification

In plain words. To classify a new point, find the kk training points closest to it and let them vote. Nothing is “learned” beyond storing the data, yet the resulting boundary can follow any shape the data have.

The rule and its guarantee

Given training pairs (xn,yn)(x_n, y_n), n=1,…,Nn = 1, \dots, N, and a query xx, let Nk(x)\mathcal{N}_k(x) be the indices of the kk training points nearest to xx under some distance dd. The kk-nearest-neighbor (kk-NN) rule predicts

y^(x)=arg⁡max⁡c∑n∈Nk(x)wn 1[yn=c],\hat y(x) = \arg\max_{c} \sum_{n \in \mathcal{N}_k(x)} w_n \, \mathbf{1}[y_n = c],

where cc runs over the classes, 1[⋅]\mathbf{1}[\cdot] is 1 when its argument is true and 0 otherwise, and wnw_n is a vote weight: wn=1w_n = 1 for plain majority voting, or a decreasing function of d(x,xn)d(x, x_n) for distance-weighted voting.

The vote fractions are a crude estimate of the class posteriors P(c∣x)P(c \mid x): kk-NN is a nonparametric density method in disguise (PR 02), with the neighborhood size set by kk rather than by a fixed bandwidth [2]. Cover and Hart proved the classic result for the 1-NN rule: as the number of training samples grows without bound, its error rate is at most twice the Bayes error rate [3]. This is an asymptotic statement. With finite data, especially in high dimension, kk-NN can be far from that bound.

The metric is a modeling decision

Euclidean distance treats a one-unit difference in every coordinate as equally important. If one feature is measured in millimeters and another in kilometers, the first will dominate every neighborhood. Standardizing features, learning a Mahalanobis metric d(x,z)2=(x−z)⊤M(x−z)d(x,z)^2 = (x-z)^\top M (x-z) with a positive semidefinite matrix MM, or comparing normalized embeddings by cosine similarity all change who counts as a neighbor.

For vectors uu and vv normalized to unit length,

∥u−v∥2=∥u∥2+∥v∥2−2u⊤v=2−2u⊤v.\|u-v\|^2 = \|u\|^2 + \|v\|^2 - 2u^\top v = 2 - 2u^\top v .

So the nearest neighbor by Euclidean distance is exactly the neighbor with the largest cosine similarity: the two criteria rank candidates in reverse order of each other and pick the same neighbors. This is why nearest-neighbor search over normalized deep features (ML 06) can use either.

Choosing kk, and the cost of prediction

A small kk (such as 1) gives a jagged boundary that follows every noisy training point: low bias, high variance. A large kk averages over a wide region and smooths the boundary, but it can wash out a small class entirely. Choose kk, the metric and the scaling by cross-validation on training data only.

kk-NN shifts all the cost to prediction time. A naive query compares xx with all NN training points, which costs O(ND)O(ND) for DD-dimensional inputs. Tree-based indices and approximate nearest-neighbor search reduce this in practice. In high dimension, a further problem appears: when many coordinates carry irrelevant variation, distances between random points concentrate around a common value, and “nearest” stops meaning “most similar.” The right panel of Figure 3 later in this chapter shows a 7-NN boundary on a two-dimensional toy problem, where none of these problems arise.

Kernels: the kernel trick and Mercer’s condition

In plain words. Many linear algorithms only ever use inputs through inner products x⊤zx^\top z. If we replace every inner product by a “similarity function” k(x,z)k(x, z) that equals an inner product in some richer feature space, we get a nonlinear algorithm for the price of a linear one, without ever computing the rich features.

Lifting the data

Take the ring data on the left of Figure 1. No line separates the inner disc from the outer ring. Add a third feature, the squared radius r2=x12+x22r^2 = x_1^2 + x_2^2. In the new three-dimensional space the inner points sit low and the outer points sit high, and a flat plane separates them perfectly. A linear classifier in the lifted space is a circle in the original space.

Left: two concentric rings of points in the plane that no line can separate. Right: the same points lifted to three dimensions by adding the squared radius, where a horizontal plane separates them.
Figure 1 — Lifting to a feature space. Adding the feature r² = x₁² + x₂² turns a circular boundary into a flat plane.

Explicit lifting gets expensive quickly. All monomials of degree up to mm in DD variables number (D+mm)\binom{D+m}{m}; for a 16×1616 \times 16 image (D=256D = 256) and m=3m = 3 that is about 2.9 million features. Kernels avoid building them.

The kernel trick

A kernel is a function k(x,z)k(x,z) for which there exists a feature map ϕ\phi into some inner-product space with

k(x,z)=ϕ(x)⊤ϕ(z).k(x,z) = \phi(x)^\top \phi(z).

Here xx and zz are inputs, ϕ(x)\phi(x) is the (possibly very long, even infinite) feature vector of xx, and the right-hand side is their inner product. For example, in two dimensions, with x=(a,b)x = (a, b),

(x⊤z+1)2=ϕ(x)⊤ϕ(z),ϕ(x)=(1, 2a, 2b, a2, b2, 2ab).(x^\top z + 1)^2 = \phi(x)^\top\phi(z), \qquad \phi(x) = \big(1,\ \sqrt2 a,\ \sqrt2 b,\ a^2,\ b^2,\ \sqrt2 ab\big).

Evaluating the left side costs one inner product and one square. The right side needs six features per point. For degree mm in DD dimensions, the left side still costs O(D)O(D).

The kernel trick is the observation that any algorithm written entirely in terms of inner products between data points can be “kernelized” by replacing xi⊤xjx_i^\top x_j with k(xi,xj)k(x_i, x_j) [7]. The SVM dual, kernel ridge regression, kernel PCA (PR 05) and Gaussian processes are all of this kind. The result is collected in the Gram matrix K∈RN×NK \in \mathbb{R}^{N\times N}, Kij=k(xi,xj)K_{ij} = k(x_i, x_j).

The code below checks the identity numerically, and then shows a popular “similarity” that is not a valid kernel.

Code · Python · 18 lines
import numpy as np

rng = np.random.default_rng(0)
x, z = rng.normal(size=2), rng.normal(size=2)

def phi(v):  # explicit feature map of (v.w + 1)^2 in 2-D
    a, b = v
    s = np.sqrt(2)
    return np.array([1, s * a, s * b, a * a, b * b, s * a * b])

lhs = (x @ z + 1) ** 2
rhs = phi(x) @ phi(z)
print("kernel:", round(lhs, 6), " explicit:", round(rhs, 6))
assert np.isclose(lhs, rhs)

X = rng.normal(size=(40, 2))
K_sig = np.tanh(2.0 * X @ X.T - 1.0)        # "sigmoid kernel"
print("sigmoid Gram min eigenvalue:", np.linalg.eigvalsh(K_sig).min().round(3))

The two numbers agree. The tanh⁡\tanh “sigmoid kernel” Gram matrix has a clearly negative eigenvalue (about −15-15 here), so for these parameters no feature map ϕ\phi can reproduce it.

Which functions are kernels? Mercer’s condition

A function kk is a valid kernel exactly when it is symmetric, k(x,z)=k(z,x)k(x,z) = k(z,x), and positive semidefinite: for every finite set of points x1,…,xNx_1, \dots, x_N and every real vector a∈RNa \in \mathbb{R}^N,

a⊤Ka=∑i=1N∑j=1Naiaj k(xi,xj)  ≥  0.a^\top K a = \sum_{i=1}^N\sum_{j=1}^N a_i a_j\, k(x_i, x_j) \;\ge\; 0 .

Equivalently, every Gram matrix has nonnegative eigenvalues. Symmetry alone is not enough, as the sigmoid example shows.

Mercer’s theorem [4] gives the continuous version. For a continuous symmetric kk on a compact domain X\mathcal{X}, positive semidefiniteness in the integral sense,

∫X∫Xg(x) k(x,z) g(z) dx dz≥0for all square-integrable g,\int_{\mathcal X}\int_{\mathcal X} g(x)\, k(x,z)\, g(z)\, dx\, dz \ge 0 \quad \text{for all square-integrable } g,

guarantees an expansion k(x,z)=∑i=1∞λi ei(x) ei(z)k(x,z) = \sum_{i=1}^{\infty} \lambda_i\, e_i(x)\, e_i(z) with eigenvalues λi≥0\lambda_i \ge 0 and orthonormal eigenfunctions eie_i. The feature map is then ϕ(x)=(λ1e1(x),λ2e2(x),… )\phi(x) = (\sqrt{\lambda_1}e_1(x), \sqrt{\lambda_2}e_2(x), \dots). In modern terms, every positive semidefinite kernel defines a reproducing kernel Hilbert space (RKHS) of functions, and the representer theorem says that regularized fits in that space are finite combinations f(x)=∑nαnk(xn,x)f(x) = \sum_n \alpha_n k(x_n, x) [7].

Valid kernels can be built from valid kernels. If k1k_1 and k2k_2 are kernels, so are k1+k2k_1 + k_2, c k1c\,k_1 for c>0c > 0, k1k2k_1 k_2, exp⁡(k1)\exp(k_1), and f(x)k1(x,z)f(z)f(x)k_1(x,z)f(z) for any function ff [2]. The common kernels follow:

KernelFormulaParametersNotes
Linearx⊤zx^\top znoneRecovers the linear model
Polynomial(γx⊤z+r)m(\gamma x^\top z + r)^mγ>0\gamma > 0, r>0r > 0, integer m≥1m \ge 1All monomials up to degree mm (r=0r = 0: degree mm only)
Gaussian RBFexp⁡(−γ∥x−z∥2)\exp(-\gamma \lVert x-z\rVert^2)γ>0\gamma > 0Infinite-dimensional feature space; local similarity
Laplacianexp⁡(−γ∥x−z∥1)\exp(-\gamma \lVert x-z\rVert_1)γ>0\gamma > 0Rougher functions than the Gaussian
Sigmoidtanh⁡(γx⊤z+r)\tanh(\gamma x^\top z + r)γ,r\gamma, rNot positive semidefinite in general

The Gaussian RBF kernel is the default nonlinear choice. Its parameter γ\gamma (sometimes written 1/(2σ2)1/(2\sigma^2) with a bandwidth σ\sigma) sets how far similarity reaches. A large γ\gamma makes each training point influence only a tiny neighborhood; a small γ\gamma makes the kernel nearly constant over the data, so the model approaches a very smooth, almost linear function. Because γ\gamma multiplies squared distances, it is tied to the scale of the features: scaling is part of the model. Standardization is a useful default for mixed units, but features already sharing meaningful units may work better without it, as the PR 10 capstone illustrates. Compare these choices inside validation, and fit any scaler only on each training fold [27].

Kernel ridge regression: the trick in one line

Ridge regression with features ϕ\phi minimizes ∑n(tn−w⊤ϕ(xn))2+λ∥w∥2\sum_n (t_n - w^\top\phi(x_n))^2 + \lambda \lVert w\rVert^2. Its solution can be written as w=∑nαnϕ(xn)w = \sum_n \alpha_n \phi(x_n), which leads to

α=(K+λI)−1t,f(x)=kx⊤α,\alpha = (K + \lambda I)^{-1} t, \qquad f(x) = k_x^\top \alpha,

where t=(t1,…,tN)⊤t = (t_1,\dots,t_N)^\top are the targets, λ>0\lambda > 0 is the regularization strength, II is the N×NN \times N identity, and kx=(k(x1,x),…,k(xN,x))⊤k_x = (k(x_1,x), \dots, k(x_N,x))^\top holds the similarities of a query xx to the training points. The DD-dimensional feature-space solve has become an N×NN \times N sample-space solve: attractive when features are many and samples few, expensive (O(N3)O(N^3) time, O(N2)O(N^2) memory) when NN is large.

Code · Python · 16 lines
import numpy as np
from sklearn.kernel_ridge import KernelRidge
from sklearn.metrics.pairwise import rbf_kernel

rng = np.random.default_rng(1)
X = rng.uniform(-3, 3, size=(60, 1))
t = np.sin(X[:, 0]) + 0.1 * rng.normal(size=60)
lam, gamma = 0.1, 0.5

K = rbf_kernel(X, X, gamma=gamma)
alpha = np.linalg.solve(K + lam * np.eye(len(X)), t)
Xq = np.linspace(-3, 3, 5)[:, None]
f_ours = rbf_kernel(Xq, X, gamma=gamma) @ alpha
f_skl = KernelRidge(alpha=lam, kernel="rbf", gamma=gamma).fit(X, t).predict(Xq)
print(np.round(f_ours, 4))
assert np.allclose(f_ours, f_skl)

The hand-written solve and scikit-learn’s KernelRidge agree, and the predictions follow sin⁡x\sin x at the five query points.

Support vector machines

In plain words. Among all boundaries that separate the classes, pick the one with the widest empty “street” between them. Only the points on the edges of the street, or inside it, matter; they are the support vectors. Allowing a few points into the street, at a price CC, makes the method work on overlapping data. Replacing inner products by a kernel makes the street curve.

Hard and soft margins

Use labels yn∈{−1,+1}y_n \in \{-1,+1\} and a score f(x)=w⊤ϕ(x)+bf(x) = w^\top\phi(x) + b, with weight vector ww and bias bb; predict the sign of ff. If the data are separable, scale ww and bb so that the closest points satisfy ynf(xn)=1y_n f(x_n) = 1. The distance between the two lines f=±1f = \pm 1, the margin, is then 2/∥w∥2/\lVert w\rVert. Maximizing it means minimizing 12∥w∥2\tfrac12\lVert w\rVert^2 subject to ynf(xn)≥1y_n f(x_n) \ge 1 for all nn: the hard-margin SVM of Boser, Guyon and Vapnik [5].

Real data overlap, so Cortes and Vapnik introduced slack variables ξn≥0\xi_n \ge 0 that measure how far each point violates the margin [6]. The soft-margin SVM solves

min⁡w,b,ξ 12∥w∥2+C∑n=1Nξnsubject toynf(xn)≥1−ξn,  ξn≥0.\min_{w,b,\xi}\ \frac12\lVert w\rVert^2 + C\sum_{n=1}^N \xi_n \quad\text{subject to}\quad y_n f(x_n) \ge 1 - \xi_n,\ \ \xi_n \ge 0 .

A point with ξn=0\xi_n = 0 is on the correct side with margin at least one. At an optimum, 0<ξn<10 \lt \xi_n \lt 1 means a point is inside the street but correctly classified; ξn=1\xi_n=1 lies on the decision boundary, and ξn>1\xi_n \gt 1 is misclassified. The constant C>0C > 0 sets the price of violations. Eliminating ξ\xi gives the equivalent unconstrained form

min⁡w,b 12∥w∥2+C∑nmax⁡(0, 1−ynf(xn)),\min_{w,b}\ \frac12\lVert w\rVert^2 + C \sum_{n} \max\big(0,\ 1 - y_n f(x_n)\big),

regularized hinge loss. A point with ynf(xn)≥1y_n f(x_n) \ge 1 contributes no loss at all; this is the source of the SVM’s sparsity. (Some texts average the losses and put the constant on the regularizer instead, writing λ2∥w∥2+1N∑nhinge\tfrac{\lambda}{2}\lVert w\rVert^2 + \tfrac1N\sum_n \text{hinge}. The two forms match when C=1/(λN)C = 1/(\lambda N).)

The dual problem and support vectors

Introducing a Lagrange multiplier αn≥0\alpha_n \ge 0 for each margin constraint and eliminating ww, bb and ξ\xi gives the dual problem [2], [6]:

max⁡α ∑n=1Nαn−12∑n=1N∑m=1Nαnαmynym k(xn,xm)subject to0≤αn≤C,  ∑n=1Nαnyn=0.\max_{\alpha}\ \sum_{n=1}^N \alpha_n - \frac12\sum_{n=1}^N\sum_{m=1}^N \alpha_n\alpha_m y_n y_m\, k(x_n, x_m) \quad\text{subject to}\quad 0 \le \alpha_n \le C,\ \ \sum_{n=1}^N \alpha_n y_n = 0 .

It is a convex quadratic program in the NN multipliers αn\alpha_n, and the data appear only through kernel values k(xn,xm)k(x_n, x_m). That is where the kernel trick enters. The optimal weight vector is w=∑nαnynϕ(xn)w = \sum_n \alpha_n y_n \phi(x_n), so predictions need only kernels too:

f(x)=∑n=1Nαnyn k(xn,x)+b.f(x) = \sum_{n=1}^N \alpha_n y_n\, k(x_n, x) + b .

The Karush–Kuhn–Tucker (KKT) optimality conditions sort the training points into three groups:

  • αn=0\alpha_n = 0: the point is outside the street (ynf(xn)≥1y_n f(x_n) \ge 1) and has no influence on ff;
  • 0<αn<C0 \lt \alpha_n \lt C: the point lies exactly on the margin (ynf(xn)=1y_n f(x_n) = 1); these points determine bb;
  • αn=C\alpha_n = C: the point is inside the street or misclassified (ynf(xn)≤1y_n f(x_n) \le 1).

Points with αn>0\alpha_n > 0 are the support vectors. Deleting any other point and retraining gives the same classifier. How many there are depends on the data: on a heavily overlapping problem, a large fraction of the training set can end up as support vectors, and prediction becomes as expensive as nearest-neighbor search.

How CC and γ\gamma shape an RBF-SVM

With the Gaussian kernel, two numbers control everything. CC sets how much the training errors cost relative to a wide margin; γ\gamma sets how local the kernel is. Figure 2 sweeps both on the same noisy data.

A three-by-three grid of RBF-SVM decision boundaries on noisy two-moons data. Rows increase C from 0.1 to 100, columns increase gamma from 0.1 to 10; support vectors are circled.
Figure 2 — RBF-SVM on noisy two-moons data (standardized). Small γ gives almost linear boundaries; large γ gives islands around individual points. Small C tolerates many margin violations (many support vectors); large C fits the training points harder. Generated by scripts/figures/pr_04_kernels_nonlinear_classifiers_extra.py.

Read the grid like this. Moving down (larger CC) makes the boundary chase individual training points, and the number of support vectors drops because fewer points are allowed inside the margin. Moving right (larger γ\gamma) shrinks each point’s sphere of influence; at γ=10\gamma = 10 the classifier draws little islands, which is overfitting. The good region is a diagonal band: when γ\gamma grows, a smaller CC is usually needed. In practice one searches CC and γ\gamma on a logarithmic grid with cross-validation.

Code · Python · 30 lines
import numpy as np
from sklearn.datasets import make_moons
from sklearn.model_selection import GridSearchCV, train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

X, y = make_moons(n_samples=500, noise=0.18, random_state=2)
Xtr, Xte, ytr, yte = train_test_split(
    X, y, test_size=0.3, stratify=y, random_state=2)
models = {
    "linear SVM": SVC(kernel="linear", C=1),
    "RBF SVM": SVC(kernel="rbf", C=3, gamma=0.7),
    "7-neighbor": KNeighborsClassifier(n_neighbors=7),
}
for name, estimator in models.items():
    model = make_pipeline(StandardScaler(), estimator).fit(Xtr, ytr)
    print(name, "test accuracy:", round(model.score(Xte, yte), 4))

search = GridSearchCV(
    make_pipeline(StandardScaler(), SVC(kernel="rbf")),
    {"svc__C": [0.1, 1, 10, 100], "svc__gamma": [0.01, 0.1, 1, 10]},
    cv=5)
search.fit(Xtr, ytr)
best = search.best_estimator_
print("best:", search.best_params_,
      "CV acc:", round(search.best_score_, 4),
      "test acc:", round(best.score(Xte, yte), 4),
      "support vectors:", best[-1].n_support_.sum(), "of", len(Xtr))

On this split the linear SVM reaches 0.827 test accuracy, the hand-picked RBF-SVM and the 7-NN rule both 0.96. The grid search chooses C=1C = 1, γ=1\gamma = 1 (cross-validated accuracy 0.971) with 59 of 350 training points as support vectors, and scores 0.953 on the test set. The tuned model is not “worse” than the hand-picked one in any meaningful sense: with 150 test points, one test point is 0.0067 of accuracy, and the two differ by one point. Treat single-split differences of this size as noise (PR 09). The scaler lives inside the pipeline so that it is refitted on each training fold.

Linear SVM, RBF SVM and seven-neighbor boundaries on synthetic moons; dots are held-out samples.
Figure 3 — Linear SVM, RBF-SVM and 7-NN on the same split as the code above. Scalers are fitted on training data only; dots and scores use the held-out partition. A synthetic example, not a general benchmark.

Scores are not probabilities

The SVM output f(x)f(x) is a signed distance-like score, not P(y=+1∣x)P(y = +1 \mid x). Its training objective never asks it to be calibrated. If probabilities are needed (for a reject option, PR 01, or for combining models), fit a separate monotone mapping from scores to probabilities on held-out data, and check it with a reliability diagram (PR 09). Multiclass SVMs are usually built from binary ones, either one-versus-rest or one-versus-one (scikit-learn’s SVC uses one-versus-one).

Gaussian processes and relevance vectors

In plain words. A Gaussian process uses the same kernels, but instead of returning one best function it returns a whole distribution of plausible functions, so each prediction comes with an error bar.

A Gaussian process (GP) is a prior over functions ff such that any finite set of values (f(x1),…,f(xN))(f(x_1), \dots, f(x_N)) is jointly Gaussian with mean zero (typically) and covariance Kij=k(xi,xj)K_{ij} = k(x_i, x_j) [8]. The kernel must therefore be a valid covariance, that is, positive semidefinite. For regression with Gaussian observation noise of variance σ2\sigma^2, the posterior at a query xx is Gaussian with

μ(x)=kx⊤(K+σ2I)−1t,s2(x)=k(x,x)−kx⊤(K+σ2I)−1kx,\mu(x) = k_x^\top (K + \sigma^2 I)^{-1} t, \qquad s^2(x) = k(x,x) - k_x^\top (K + \sigma^2 I)^{-1} k_x ,

where μ(x)\mu(x) is the predictive mean and s2(x)s^2(x) the variance of the latent function. The mean is exactly kernel ridge regression with λ=σ2\lambda = \sigma^2. The variance is new: it is small near training inputs and grows back to the prior variance k(x,x)k(x,x) far from them. Kernel hyperparameters (such as γ\gamma and σ2\sigma^2) can be chosen by maximizing the marginal likelihood instead of cross-validation [2], [8].

Two cautions. The uncertainty is conditional on the chosen kernel; a confident GP with the wrong kernel can be confidently wrong. And GP classification is harder: a Bernoulli likelihood on top of a Gaussian latent function makes the posterior non-Gaussian, so Laplace, expectation propagation or variational approximations are needed (PR 08).

The relevance vector machine (RVM), introduced by Tipping [9] and presented in Bishop, Section 7.2 [2], uses the same functional form as the SVM, f(x)=∑nwnk(xn,x)+bf(x) = \sum_n w_n k(x_n, x) + b, but places a separate zero-mean Gaussian prior on each weight wnw_n with its own precision hyperparameter. Maximizing the marginal likelihood drives many precisions to infinity, which switches the corresponding basis functions off. The surviving training points, the “relevance vectors,” are typically far fewer than an SVM’s support vectors, the outputs are probabilistic, and the basis functions do not need to satisfy Mercer’s condition. The price is a non-convex training problem. “Sparse” thus has different meanings: few stored basis functions (SVM, RVM), few nonzero input weights (lasso), or sparse input data. Say which one you mean.

Radial basis function networks

In plain words. Put a few Gaussian “bumps” at representative places in the input space, measure how strongly a new point activates each bump, and feed those activations to a linear classifier. It is the lifting idea of Figure 1, but with a small, explicit set of features.

An RBF network computes

f(x)=∑j=1Mwj exp⁡ ⁣(−γ∥x−μj∥2)+w0,f(x) = \sum_{j=1}^{M} w_j\, \exp\!\big(-\gamma \lVert x - \mu_j \rVert^2\big) + w_0 ,

where μ1,…,μM\mu_1, \dots, \mu_M are MM centers, γ\gamma sets the width of each bump, wjw_j are output weights and w0w_0 is a bias. Moody and Darken proposed the classic two-stage training [10]: first place the centers without labels, for example by kk-means clustering (PR 07); then, with centers fixed, the output weights solve an ordinary linear least-squares or logistic regression problem. Park and Sandberg showed that RBF networks are universal approximators: with enough centers they can approximate any continuous function on a compact set arbitrarily well [11].

Compare this with the kernel machines above. A kernel SVM effectively places one bump on every support vector, chosen by the margin criterion. An RBF network uses M≪NM \ll N bumps whose positions come from clustering (or from gradient descent if all parameters are trained jointly), which makes prediction cheap. Its weakness is that unsupervised center placement ignores the labels, so centers may be wasted where the classes do not meet.

Code · Python · 24 lines
import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler

X, y = make_moons(n_samples=500, noise=0.18, random_state=2)
Xtr, Xte, ytr, yte = train_test_split(
    X, y, test_size=0.3, stratify=y, random_state=2)
scaler = StandardScaler().fit(Xtr)
Xtr, Xte = scaler.transform(Xtr), scaler.transform(Xte)

M, gamma, lam = 12, 1.0, 1e-3
centers = KMeans(M, n_init=10, random_state=0).fit(Xtr).cluster_centers_

def design(X):  # N x (M+1): Gaussian bumps plus a bias column
    d2 = ((X[:, None, :] - centers[None, :, :]) ** 2).sum(-1)
    return np.c_[np.exp(-gamma * d2), np.ones(len(X))]

Phi = design(Xtr)
t = 2.0 * ytr - 1.0                      # targets in {-1, +1}
w = np.linalg.solve(Phi.T @ Phi + lam * np.eye(M + 1), Phi.T @ t)
pred = (design(Xte) @ w > 0).astype(int)
print("RBF network test accuracy:", round((pred == yte).mean(), 4))

Twelve bumps and a least-squares output layer give 0.953 test accuracy on the moons split, on par with the RBF-SVM that keeps dozens of support vectors. Figure 5 (left) shows the same network with a logistic output layer.

Decision trees

In plain words. A decision tree plays twenty questions with the data. Each question looks at one feature and asks “is it at most this threshold?” Each answer sends the point left or right, until it reaches a leaf that holds a label. The tree is grown greedily: at every step, pick the question that makes the two resulting groups as “pure” as possible.

Impurity measures

Let a node contain training points with class proportions p1,…,pCp_1, \dots, p_C (fraction of the node’s points in each class cc). An impurity function is zero when one class has all the points and largest when the classes are evenly mixed. The three standard choices are

Gini:G=1−∑c=1Cpc2=∑cpc(1−pc),Entropy:H=−∑c=1Cpclog⁡2pc,Misclassification:E=1−max⁡cpc.\begin{aligned} \text{Gini:}\quad & G = 1 - \sum_{c=1}^C p_c^2 = \sum_{c} p_c (1-p_c), \\ \text{Entropy:}\quad & H = -\sum_{c=1}^C p_c \log_2 p_c, \\ \text{Misclassification:}\quad & E = 1 - \max_c p_c . \end{aligned}

The Gini index is the probability that two points drawn at random (with replacement) from the node have different labels. Entropy is the information-theoretic uncertainty of the label, in bits. Misclassification error is the error rate if the node predicted its majority class. Figure 4 (left) plots the three for two classes.

Left: Gini, half-entropy and misclassification impurity as functions of the class-1 fraction p, all zero at p equals 0 and 1 and maximal at 0.5. Middle and right: axis-aligned decision regions of a depth-3 tree with 6 leaves and an unlimited-depth tree with 29 leaves on noisy moons.
Figure 4 — Left: two-class impurity measures (entropy scaled by ½ to share the axis). Middle: a depth-3 CART tree gives a coarse, axis-aligned staircase. Right: an unlimited tree carves tiny boxes around noisy points, overfitting the training data.

Gini and entropy are strictly concave, so splitting a node never increases their weighted average. Misclassification error is piecewise linear and often fails to reward a split that makes the children purer without changing either child’s majority label. That is why trees are grown with Gini or entropy and evaluated with error rate.

Growing a tree: the CART algorithm

The CART procedure of Breiman, Friedman, Olshen and Stone [12] grows a binary tree top-down. At a node with point set SS, it considers every feature jj and every threshold τ\tau between consecutive observed values, splitting SS into SL={x∈S:xj≤τ}S_L = \{x \in S: x_j \le \tau\} and SR=S∖SLS_R = S \setminus S_L. It chooses the split with the largest impurity decrease

Δi(j,τ)=i(S)−∣SL∣∣S∣ i(SL)−∣SR∣∣S∣ i(SR),\Delta i(j, \tau) = i(S) - \frac{|S_L|}{|S|}\, i(S_L) - \frac{|S_R|}{|S|}\, i(S_R),

where i(⋅)i(\cdot) is the chosen impurity and ∣S∣|S| counts the points in a set. It then recurses on both children until a stopping rule fires (pure node, minimum node size, maximum depth). Quinlan’s ID3 [13] is a close relative that uses entropy, calls Δi\Delta i the information gain, and makes multiway splits on categorical features.

The code finds the best root split by brute force and checks it against scikit-learn, whose DecisionTreeClassifier implements an optimized version of CART.

Code · Python · 26 lines
import numpy as np
from sklearn.datasets import make_moons
from sklearn.tree import DecisionTreeClassifier

def gini(labels):
    p = np.bincount(labels, minlength=2) / len(labels)
    return 1.0 - (p ** 2).sum()

def best_split(X, y):
    best = (np.inf, None, None)
    for j in range(X.shape[1]):
        values = np.unique(X[:, j])
        for thr in (values[:-1] + values[1:]) / 2:
            left = X[:, j] <= thr
            n_l, n_r = left.sum(), (~left).sum()
            score = (n_l * gini(y[left]) + n_r * gini(y[~left])) / len(y)
            if score < best[0]:
                best = (score, j, thr)
    return best

X, y = make_moons(n_samples=300, noise=0.25, random_state=1)
score, j, thr = best_split(X, y)
root = DecisionTreeClassifier(max_depth=1).fit(X, y).tree_
print(f"ours: feature {j}, threshold {thr:.4f}, weighted Gini {score:.4f}")
print(f"sklearn: feature {root.feature[0]}, threshold {root.threshold[0]:.4f}")
assert j == root.feature[0] and np.isclose(thr, root.threshold[0])

Both choose feature 1 with threshold 0.0547, reducing the impurity from 0.5 at the root to a weighted 0.287.

Pruning and the character of trees

A tree grown until every leaf is pure memorizes the training set (Figure 4, right). CART’s answer is cost-complexity pruning [12]: grow a large tree T0T_0, then for each subtree TT obtained by collapsing internal nodes, measure

Rα(T)=R(T)+α ∣T~∣,R_\alpha(T) = R(T) + \alpha\, |\widetilde T| ,

where R(T)R(T) is the training misclassification rate, ∣T~∣|\widetilde T| is the number of leaves and α≥0\alpha \ge 0 is a complexity price. Increasing α\alpha traces a nested sequence of smaller and smaller trees; choose α\alpha by cross-validation (ccp_alpha in scikit-learn).

Trees have a distinctive profile. They need no feature scaling, handle mixed numeric and categorical inputs, ignore irrelevant features if they never help a split, and produce rules a person can read. Their boundaries are axis-aligned staircases, so a diagonal boundary costs many splits. And they are unstable: a small change in the data can change the root split and hence the whole tree. Averaging many randomized trees (bagging, random forests) or adding them sequentially (boosting) fixes the instability, and that is the topic of PR 09.

Multilayer perceptrons as nonlinear classifiers

In plain words. A multilayer perceptron (MLP) is an RBF network whose bumps are replaced by learned “ramps,” and whose ramps are themselves learned from the labels. Each hidden unit draws one line; the next layer combines the lines into curved regions.

A one-hidden-layer MLP for CC classes computes

h=σ(W1x+b1),P(y=c∣x)=softmax⁡(W2h+b2)c,h = \sigma(W_1 x + b_1), \qquad P(y = c \mid x) = \operatorname{softmax}(W_2 h + b_2)_c ,

where W1,b1W_1, b_1 map the DD inputs to HH hidden units, σ\sigma is an elementwise nonlinearity (ReLU max⁡(0,⋅)\max(0,\cdot), logistic or tanh⁡\tanh), and W2,b2W_2, b_2 map hidden units to class scores. All weights are trained jointly by minimizing cross-entropy with gradient descent, the gradients being computed by backpropagation [14]. Unlike every method above, both the features (hh) and the classifier are learned from the labels. The universal approximation theorems of Cybenko [15] and Hornik [16] guarantee that one hidden layer with enough units can approximate any continuous function on a compact set; they say nothing about how many units are needed or whether gradient descent will find them. The full story, from neurons and activations to backpropagation and training tricks, is in ML 02; the image-classification version is in IP 13.

Geometrically, with ReLU units each hidden unit splits the input space with a hyperplane, and the network output is piecewise linear on the resulting cells, which is why the MLP boundary in Figure 5 is made of straight segments.

Code · Python · 16 lines
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.neural_network import MLPClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

X, y = make_moons(n_samples=500, noise=0.18, random_state=2)
Xtr, Xte, ytr, yte = train_test_split(
    X, y, test_size=0.3, stratify=y, random_state=2)
for hidden in [(2,), (16,), (16, 16)]:
    mlp = make_pipeline(
        StandardScaler(),
        MLPClassifier(hidden_layer_sizes=hidden, alpha=1e-3,
                      max_iter=3000, random_state=0))
    mlp.fit(Xtr, ytr)
    print(hidden, "test accuracy:", round(mlp.score(Xte, yte), 4))

With two hidden units the network can only bend the boundary once and reaches 0.833. Sixteen units reach 0.947, and a second layer of 16 does not help on this easy two-dimensional problem. Depth pays off on high-dimensional inputs such as images, where it lets the network build features hierarchically (ML 03).

Left: an RBF network's smooth curved boundary on held-out moons data with its 12 k-means centers marked. Right: an MLP's piecewise-linear boundary on the same data.
Figure 5 — Two explicit feature maps. Left: an RBF network with 12 k-means centers and a logistic output layer gives smooth, local curves. Right: an MLP with ReLU units gives a piecewise-linear boundary. Held-out points from the same split as the code.

Choosing among nonlinear classifiers

MethodBoundary shapeTraining costPrediction costKey hyperparametersTypical strengths
kk-NNAny; follows dataNone (store data)O(ND)O(ND) per querykk, metric, scalingSimple baseline; good with good embeddings
Kernel SVMSmooth (RBF)Roughly O(N2)O(N^2)–O(N3)O(N^3)O(NsvD)O(N_{\text{sv}} D)CC, kernel, γ\gammaSmall/medium data, strong theory
Gaussian processSmooth, with uncertaintyO(N3)O(N^3) exactO(N)O(N) mean, O(N2)O(N^2) varianceKernel; set by marginal likelihoodCalibrated uncertainty (regression)
RBF networkSmooth, localClustering + linear solveO(MD)O(MD)MM, γ\gammaCheap prediction
Decision treeAxis-aligned boxesO(DNlog⁡N)O(DN\log N) per levelO(depth)O(\text{depth})Depth, leaf size, α\alphaInterpretable; mixed feature types
MLPPiecewise linear (ReLU)Iterative SGDO(weights)O(\text{weights})Width, depth, decay, learning rateScales to large data; learns features

Here NsvN_{\text{sv}} is the number of support vectors and MM the number of RBF centers. The complexity entries are orders of magnitude, not exact counts. No row wins everywhere. Compare candidates under one validation protocol, and remember the lesson of the grid-search example: differences of a fraction of a percent on one split are rarely real.

Modern view

Kernel methods dominated pattern recognition from the late 1990s until deep networks took over large-scale perception around 2012. They did not disappear; they changed roles. Six strands summarize the current picture.

Surveys of the classical field. Hofmann, Schölkopf and Smola’s review in the Annals of Statistics [7] is the standard map of kernel methods: positive definite kernels and their RKHS, the representer theorem, kernel construction for structured data such as strings and graphs, and the statistical learning theory behind large margins. Cervantes et al. [19] survey SVM classification from the application side: variants developed where the basic SVM struggles (very large data sets, many classes, imbalanced classes), combinations with evolutionary parameter search, a long catalogue of applications, and the method’s limitations. For trees, Costa and Pedreira [20] review recent decision-tree research around the three goals of any predictive learner: fitting the training data, generalizing beyond it, and staying interpretable.

Scaling kernels. The O(N2)O(N^2) memory of a Gram matrix was the main barrier. Rahimi and Recht’s random features [17] approximate a shift-invariant kernel such as the RBF by an explicit random map z(x)∈RRz(x) \in \mathbb{R}^R with z(x)⊤z(x′)≈k(x,x′)z(x)^\top z(x') \approx k(x,x'), so that a linear model on RR random features stands in for the kernel machine. Liu et al.’s survey [18] organizes a decade of follow-ups: sampling schemes for the random features, theory on how many features are needed for a given accuracy, and connections to deep networks. Combining such approximations with GPU linear algebra, the FALKON line of work trains kernel ridge regression on billions of points [23], and GPyTorch [24] makes exact and approximate Gaussian process inference practical on GPUs with iterative matrix–matrix solvers.

Kernels as a lens on deep learning. Jacot, Gabriel and Hongler showed that, in an infinite-width limit with suitable scaling, training a neural network by gradient descent is equivalent to kernel regression with a fixed neural tangent kernel [21]. Belkin, Ma and Mandal argued that phenomena puzzling in deep learning, such as fitting the training data exactly yet still generalizing, already appear in kernel machines, so understanding kernels is a prerequisite for understanding deep networks [22]. Real networks of finite width do learn their features, which a fixed kernel cannot, so this analogy is a theoretical tool, not a replacement.

Trees still rule tabular data. For data in tables (rows of heterogeneous measurements rather than pixels or words), Grinsztajn, Oyallon and Varoquaux benchmarked tree ensembles against deep architectures on 45 medium-sized datasets and found the tree-based models still ahead, attributing the gap to neural networks’ sensitivity to uninformative features, their rotation invariance, and their bias toward smooth functions [25]. The newest challenger is a tabular foundation model: TabPFN, a transformer trained across millions of synthetic datasets, predicts on a new small dataset in a single forward pass. Its authors report that it outperforms previous methods, including tuned gradient-boosted tree ensembles, on datasets with up to 10,000 samples, with far less training time [26].

Neighbors on learned features. The nearest-neighbor rule has had a revival as a classifier on top of large pretrained embeddings. Once features are good, a kk-NN or cosine-similarity classifier is often the simplest strong baseline, and it can add new classes without retraining. IP 13 and ML 06 discuss this pattern.

Open problems. Exact kernel methods and GPs still scale poorly in NN; approximation quality versus speed remains an active trade-off [18]. Choosing kernels for structured data is still largely manual. Single trees remain unstable, and globally optimal trees are expensive to compute [20]. And for tabular data, whether foundation-style models will displace tuned tree ensembles beyond small datasets is an open question as of 2026.

Key takeaways

  • Nonlinear boundaries come from three ideas: comparing with stored examples (kk-NN), lifting to a feature space where a linear rule works (kernels, RBF networks, MLPs), or partitioning the space (trees).
  • kk-NN’s behavior is set by the metric and scaling as much as by kk; for unit vectors, Euclidean and cosine neighbors coincide.
  • A kernel is valid exactly when every Gram matrix is symmetric positive semidefinite (Mercer’s condition). The kernel trick replaces inner products by kernel values in any algorithm written in inner products.
  • The soft-margin SVM minimizes 12∥w∥2\tfrac12\lVert w\rVert^2 plus CC times hinge loss. Its dual depends on the data only through the kernel, and only support vectors (αn>0\alpha_n > 0) affect predictions. Tune CC and γ\gamma jointly, on standardized features, by cross-validation.
  • GPs give kernel predictions with uncertainty; the RVM (Tipping) gives sparse probabilistic kernel models. SVM scores are not probabilities.
  • RBF networks use a few explicit Gaussian bumps; trees grow greedily by impurity decrease (Gini or entropy) and need pruning; MLPs learn their own features and are covered in depth in ML 02.
  • No family wins everywhere: kernels for small/medium smooth problems, trees and their ensembles for tabular data, deep networks for raw perceptual data, neighbors on top of good embeddings.

Exercises

  1. Distance and cosine. Derive ∥u−v∥2=2−2u⊤v\lVert u-v\rVert^2 = 2 - 2u^\top v for unit vectors, and show that the 1-NN under Euclidean distance equals the 1-NN under cosine similarity. Does this still hold if the vectors are not normalized?
Hint

Expand ∥u−v∥2=u⊤u−2u⊤v+v⊤v\lVert u-v\rVert^2 = u^\top u - 2u^\top v + v^\top v. With unit norms, distance is a decreasing function of u⊤vu^\top v, so the minimizer of one is the maximizer of the other. Without normalization the norms enter: a long vector pointing in a slightly different direction can be closer in Euclidean distance than a short, perfectly aligned one.

  1. Building a kernel. Show that k(x,z)=(x⊤z)2k(x,z) = (x^\top z)^2 is a valid kernel in R2\mathbb{R}^2 by writing down its feature map. Then use the closure rules to argue that the Gaussian kernel exp⁡(−γ∥x−z∥2)\exp(-\gamma\lVert x-z\rVert^2) is valid.
Hint

ϕ(x)=(x12,x22,2x1x2)\phi(x) = (x_1^2, x_2^2, \sqrt2 x_1 x_2). For the Gaussian, write exp⁡(−γ∥x−z∥2)=exp⁡(−γ∥x∥2) exp⁡(2γx⊤z) exp⁡(−γ∥z∥2)\exp(-\gamma\lVert x-z\rVert^2) = \exp(-\gamma\lVert x\rVert^2)\,\exp(2\gamma x^\top z)\,\exp(-\gamma\lVert z\rVert^2). The middle factor is exp⁡\exp of a valid (scaled linear) kernel, and the outer factors have the form f(x) k(x,z) f(z)f(x)\,k(x,z)\,f(z).

  1. The limits of γ\gamma. For a fixed finite data set, what does the RBF Gram matrix tend to as γ→0\gamma \to 0 and as γ→∞\gamma \to \infty? Relate each limit to the leftmost and rightmost columns of Figure 2.
Hint

As γ→0\gamma \to 0 every entry tends to 1 (the all-ones matrix): all points look alike and the boundary becomes nearly linear or constant. As γ→∞\gamma \to \infty the off-diagonal entries tend to 0 and K→IK \to I: each point is only similar to itself, so the SVM can memorize every training label, which is the “islands” regime.

  1. Support vectors and cost. An RBF-SVM trained on 100,000 images keeps 90% of them as support vectors. What does this imply about the data and about prediction time? Name two things you could try.
Hint

Many points sit inside the margin or are misclassified: the classes overlap heavily in this feature space, or CC is small or γ\gamma is badly chosen. Each prediction needs about 90,000 kernel evaluations. Try re-tuning CC and γ\gamma, better features, random features with a linear SVM, or a different model family.

  1. Impurity by hand. A node has 40 points of class A and 40 of class B. Split 1 gives children (30 A, 10 B) and (10 A, 30 B). Split 2 gives (40 A, 20 B) and (0 A, 20 B). Compute the misclassification-error decrease and the Gini decrease for both splits. Which split does each measure prefer?
Hint

Root Gini =0.5= 0.5, root error =0.5= 0.5. Split 1: both children have error 0.250.25 and Gini 2⋅0.75⋅0.25=0.3752\cdot0.75\cdot0.25 = 0.375; weighted error 0.250.25, weighted Gini 0.3750.375. Split 2: left child error 1/31/3, Gini 2⋅23⋅13=4/92\cdot\tfrac23\cdot\tfrac13 = 4/9; right child pure. Weighted error 6080⋅13=0.25\tfrac{60}{80}\cdot\tfrac13 = 0.25, weighted Gini 6080⋅49=1/3\tfrac{60}{80}\cdot\tfrac49 = 1/3. Error cannot tell them apart (both 0.25); Gini prefers split 2, which creates a pure node.

  1. RBF network design. In the RBF-network code, vary M∈{2,4,12,50}M \in \{2, 4, 12, 50\} and γ∈{0.1,1,10}\gamma \in \{0.1, 1, 10\}. Which combinations underfit and which overfit? Why does a small MM with a large γ\gamma behave badly?
Hint

With few centers and a large γ\gamma, the bumps are narrow and most points activate none of them strongly, so the design matrix is nearly zero away from the centers and the classifier falls back to the bias. Many centers with a large γ\gamma start to behave like a kernel machine with too little regularization.

References

  1. S. Theodoridis and K. Koutroumbas, Pattern Recognition, 4th ed., Academic Press, 2009, Chapters 2 and 4. publisher page

  2. C. M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006, Sections 2.5.2, 5.1–5.3, 6.1–6.4, 7.1–7.2 and 14.4. official book page and PDF

  3. T. Cover and P. Hart, “Nearest Neighbor Pattern Classification,” IEEE Transactions on Information Theory, vol. 13, no. 1, pp. 21–27, 1967. doi:10.1109/TIT.1967.1053964

  4. J. Mercer, “Functions of Positive and Negative Type, and Their Connection with the Theory of Integral Equations,” Philosophical Transactions of the Royal Society of London, Series A, vol. 209, pp. 415–446, 1909. doi:10.1098/rsta.1909.0016

  5. B. E. Boser, I. M. Guyon, and V. N. Vapnik, “A Training Algorithm for Optimal Margin Classifiers,” Proceedings of the Fifth Annual Workshop on Computational Learning Theory (COLT), pp. 144–152, 1992. doi:10.1145/130385.130401

  6. C. Cortes and V. Vapnik, “Support-Vector Networks,” Machine Learning, vol. 20, pp. 273–297, 1995. doi:10.1007/BF00994018

  7. T. Hofmann, B. Schölkopf, and A. J. Smola, “Kernel Methods in Machine Learning,” The Annals of Statistics, vol. 36, no. 3, 2008. doi:10.1214/009053607000000677

  8. C. E. Rasmussen and C. K. I. Williams, Gaussian Processes for Machine Learning, MIT Press, 2006. book page

  9. M. E. Tipping, “Sparse Bayesian Learning and the Relevance Vector Machine,” Journal of Machine Learning Research, vol. 1, pp. 211–244, 2001. JMLR

  10. J. Moody and C. J. Darken, “Fast Learning in Networks of Locally-Tuned Processing Units,” Neural Computation, vol. 1, no. 2, pp. 281–294, 1989. doi:10.1162/neco.1989.1.2.281

  11. J. Park and I. W. Sandberg, “Universal Approximation Using Radial-Basis-Function Networks,” Neural Computation, vol. 3, no. 2, pp. 246–257, 1991. doi:10.1162/neco.1991.3.2.246

  12. L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone, Classification and Regression Trees, Chapman and Hall/CRC, 2017 edition. doi:10.1201/9781315139470

  13. J. R. Quinlan, “Induction of Decision Trees,” Machine Learning, vol. 1, pp. 81–106, 1986. doi:10.1007/BF00116251

  14. D. E. Rumelhart, G. E. Hinton, and R. J. Williams, “Learning Representations by Back-Propagating Errors,” Nature, vol. 323, pp. 533–536, 1986. doi:10.1038/323533a0

  15. G. Cybenko, “Approximation by Superpositions of a Sigmoidal Function,” Mathematics of Control, Signals, and Systems, vol. 2, pp. 303–314, 1989. doi:10.1007/BF02551274

  16. K. Hornik, “Approximation Capabilities of Multilayer Feedforward Networks,” Neural Networks, vol. 4, no. 2, pp. 251–257, 1991. doi:10.1016/0893-6080(91)90009-T

  17. A. Rahimi and B. Recht, “Random Features for Large-Scale Kernel Machines,” Advances in Neural Information Processing Systems 20 (NIPS), 2007. paper

  18. F. Liu, X. Huang, Y. Chen, and J. A. K. Suykens, “Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 44, no. 10, pp. 7128–7148, 2022. doi:10.1109/TPAMI.2021.3097011

  19. J. Cervantes, F. Garcia-Lamont, L. Rodríguez-Mazahua, and A. Lopez, “A Comprehensive Survey on Support Vector Machine Classification: Applications, Challenges and Trends,” Neurocomputing, vol. 408, pp. 189–215, 2020. doi:10.1016/j.neucom.2019.10.118

  20. V. G. Costa and C. E. Pedreira, “Recent Advances in Decision Trees: An Updated Survey,” Artificial Intelligence Review, vol. 56, pp. 4765–4800, 2023. doi:10.1007/s10462-022-10275-5

  21. A. Jacot, F. Gabriel, and C. Hongler, “Neural Tangent Kernel: Convergence and Generalization in Neural Networks,” NeurIPS, 2018. arXiv:1806.07572

  22. M. Belkin, S. Ma, and S. Mandal, “To Understand Deep Learning We Need to Understand Kernel Learning,” arXiv:1802.01396, 2018. arXiv

  23. G. Meanti, L. Carratino, L. Rosasco, and A. Rudi, “Kernel Methods Through the Roof: Handling Billions of Points Efficiently,” Advances in Neural Information Processing Systems 33 (NeurIPS), 2020. paper

  24. J. R. Gardner, G. Pleiss, D. Bindel, K. Q. Weinberger, and A. G. Wilson, “GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration,” NeurIPS, 2018. arXiv:1809.11165

  25. L. Grinsztajn, E. Oyallon, and G. Varoquaux, “Why Do Tree-Based Models Still Outperform Deep Learning on Typical Tabular Data?,” Advances in Neural Information Processing Systems 35 (NeurIPS), Datasets and Benchmarks Track, 2022. paper

  26. N. Hollmann, S. Müller, L. Purucker, A. Krishnakumar, et al., “Accurate Predictions on Small Data with a Tabular Foundation Model,” Nature, vol. 637, pp. 319–326, 2025. doi:10.1038/s41586-024-08328-6

  27. scikit-learn developers, “Support Vector Machines,” user guide, accessed 2026-11-05. documentation

Check your understanding

This tutorial has 6 exercises. Can you solve them without opening the hints?

Go to the exercises ↑

Next PR 05 · Feature Selection, Transforms and Dimensionality · 25 min