Skip to main content

Kernels: dot products without the map

The dot product of two lifted points can often be computed in the original space, at a fraction of the cost. Derive it for the quadratic map, meet the polynomial and RBF kernels and their Gram matrices, and learn the test that tells a true kernel from an impostor.
ML02.8.2L2 Intermediate25 min
In review

The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.

Before this lesson: ML02.8.1 Lifting data until a line works M03.4 Positive definite matrices and quadratic forms

What you will be able to do
  • Derive that the quadratic map satisfies phi(x) . phi(z) = (x . z)^2 and check it with numbers.
  • Define a kernel and its Gram matrix, and compute Gram matrices for the polynomial and RBF kernels by hand.
  • Explain the RBF kernel as a similarity with a length scale, and write out its infinite feature map for one feature.
  • Test a candidate kernel by the eigenvalues of its Gram matrices, and prove that a sum of kernels is a kernel.

The question

The last lesson lifted the data to make a straight cut work, and found the bill: 5,456 columns for a cubic lift of 30 features, 324,632 for degree 5. Yet the SVM’s dual (ML02.7.2) never looks at a single feature. It only asks for dot products between pairs of points. Could we hand it the dot products of the lifted points without ever building the lifted points?

From the last lesson

1. To what heights does the lift \({z = x_1^2 + x_2^2}\) send the rings, and which plane splits them?

Show answer

The inner points go to height 1 and the outer points to 8 or 9, so a level plane between them, such as \(z = 4.5\), splits them. Back in the plane it is the circle of radius 2.12.

2. How many columns does a polynomial lift of degree \(p\) on \(d\) features have?

Show answer

\({\binom{d + p}{p}}\): 5,456 for \(d = 30\) and \(p = 3\).

Intuition

Take two points, \({\vect{x} = (1, 2)}\) and \({\vect{z} = (3, 1)}\), and the quadratic map \({\varphi(\vect{x}) = (x_1^2, \sqrt{2}\,x_1 x_2, x_2^2)}\) of the last lesson. There are two ways to get the dot product of the lifted points.

A diagram of two routes from a blue box holding x equals (1, 2) and z equals (3, 1). The upper route, titled Long route: lift both points, then take the dot product, leads through two vermillion boxes, phi of x equals (1, 2 root 2, 4) and phi of z equals (9, 3 root 2, 1), into a yellow box 9 plus 12 plus 4 equals 25. The lower route, titled Short route: dot product in the plane, then square, leads through a blue box x dot z equals 3 plus 2 equals 5 and a green arrow labelled square into a yellow box 5 squared equals 25. A note between the two yellow boxes reads same number.
ML02.8.2-F1

Two routes to one number. The long route builds both lifted points and multiplies them coordinate by coordinate. The short route takes the dot product in the plane and squares it.

The long route needs the lifted points. The short route never leaves the plane, and it gives exactly the same answer. A function that hands back the dot product in a lifted space, while working only in the original one, is called a kernel. Using one in place of the lift is the kernel trick.

Build it up

Step 1. The long route. Lift each point: \({\varphi(1, 2) = (1,\; 2\sqrt{2},\; 4)}\) and \({\varphi(3, 1) = (9,\; 3\sqrt{2},\; 1)}\). Multiply coordinate by coordinate and add: \({1 \times 9 = 9}\), \({2\sqrt{2} \times 3\sqrt{2} = 12}\) and \({4 \times 1 = 4}\), so the dot product is \(25\).

Step 2. The short route. \({\vect{x} \cdot \vect{z} = 1 \times 3 + 2 \times 1 = 5}\), and \({5^2 = 25}\).

Step 3. Why the \(\sqrt{2}\) is there. Square \({(x_1 z_1 + x_2 z_2)}\) and the cross term comes out twice: \({2\,x_1 x_2 z_1 z_2}\). The lifted dot product has the middle term \({(\sqrt{2}\,x_1 x_2)(\sqrt{2}\,z_1 z_2)}\), which is the same thing. Without the \(\sqrt{2}\) the two routes would disagree.

Step 4. The saving grows with \(d\). With \(d\) features the quadratic map has one coordinate for each square and one for each pair, \({d + d(d - 1)/2 = d(d + 1)/2}\) in all: 465 for \(d = 30\). The short route still costs \(d\) multiplications and one squaring.

Step 5. A kernel is a similarity. The dot product is large when two lifted points point the same way. That suggests designing the similarity directly. The most used choice scores two points by their distance, high when they are close and near zero when they are far apart.

Two panels. The left panel plots the RBF kernel value against the distance between two points, from 0 to 3.2, for three values of gamma: a wide sky-blue curve for gamma equals 0.25, a blue curve for gamma equals 1 and a narrow vermillion curve for gamma equals 4. All start at 1 at distance 0 and fall towards 0. The right panel, titled Gram matrix, gamma equals 0.5, is a twelve by twelve grid of squares for the rings, shaded from pale to dark vermillion, with rows grouped and labelled inner, outer axis and outer diagonal. The diagonal squares are darkest, the four inner points are fairly alike, and most squares between distant points are almost white. A note reads darker equals more alike.
ML02.8.2-F2

Left: the RBF kernel falls from 1 as two points move apart; a larger \(\gamma\) makes it fall faster. Right: the kernel of every pair of ring points, a table of similarities called the Gram matrix.

The formal statement

NoteDefinition: kernel and Gram matrix

A kernel is a function \({k(\vect{x}, \vect{z})}\) for which some feature map \(\varphi\) gives

\[ k(\vect{x}, \vect{z}) = \varphi(\vect{x}) \cdot \varphi(\vect{z}) \]

for all \(\vect{x}\) and \(\vect{z}\). For points \({\vect{x}_1, \dots, \vect{x}_n}\), the Gram matrix (or kernel matrix) \(\mat{K}\) is the \(n \times n\) matrix with entries \({K_{ij} = k(\vect{x}_i, \vect{x}_j)}\).

The quadratic kernel. For \(\vect{x}\) and \(\vect{z}\) in \(\R^d\), expand the square of a sum as a double sum:

\[ \begin{aligned} (\vect{x} \cdot \vect{z})^2 &= \Big(\sum_{i} x_i z_i\Big)\Big(\sum_{j} x_j z_j\Big) \\ &= \sum_{i} \sum_{j} x_i x_j\, z_i z_j . \end{aligned} \]

The terms with \({i = j}\) give \({\sum_i x_i^2 z_i^2}\). Each pair \({i < j}\) appears twice, once as \((i, j)\) and once as \((j, i)\), so

\[ \begin{aligned} (\vect{x} \cdot \vect{z})^2 &= \sum_{i} x_i^2\, z_i^2 \\ &\quad + \sum_{i < j} \big(\sqrt{2}\,x_i x_j\big)\big(\sqrt{2}\,z_i z_j\big) . \end{aligned} \]

That is \({\varphi(\vect{x}) \cdot \varphi(\vect{z})}\) for the map that lists every square \(x_i^2\) and every product \({\sqrt{2}\,x_i x_j}\). For \(d = 2\) it is the map of the last lesson.

Polynomial kernels. Adding a constant \({c \ge 0}\) and raising to a power \(p\) gives the polynomial kernel

\[ k(\vect{x}, \vect{z}) = (\vect{x} \cdot \vect{z} + c)^p . \]

For \({c > 0}\) its feature map holds every monomial of degree up to \(p\), each with a fixed positive weight: the \({\binom{d + p}{p}}\) columns of the last lesson, for the price of one dot product. For \({c = 0}\) only the monomials of degree exactly \(p\) remain, as in the quadratic kernel.

The RBF kernel. The radial basis function (or Gaussian) kernel is

\[ k(\vect{x}, \vect{z}) = e^{-\gamma\, \norm{\vect{x} - \vect{z}}^2}, \qquad \gamma > 0 . \]

It is 1 when the points coincide and falls towards 0 as they move apart. Writing \({\gamma = 1/(2\ell^2)}\) shows it as a bell curve in the distance with width \(\ell\), the length scale: a large \(\gamma\) is a short length scale, and only close neighbours count as similar.

Go deeper: the RBF kernel's feature map has infinitely many coordinates

Take one feature. Expand the square in the exponent, \({(x - z)^2 = x^2 - 2xz + z^2}\), and split the exponential:

\[ e^{-\gamma (x - z)^2} = e^{-\gamma x^2}\; e^{-\gamma z^2}\; e^{2\gamma x z} . \]

The Taylor series \({e^u = \sum_{k \ge 0} u^k / k!}\) with \({u = 2\gamma x z}\) gives

\[ \begin{aligned} e^{-\gamma (x - z)^2} &= \sum_{k=0}^{\infty} \frac{(2\gamma)^k}{k!}\, x^k z^k \\ &\qquad \times e^{-\gamma x^2} e^{-\gamma z^2} \\ &= \sum_{k=0}^{\infty} \varphi_k(x)\, \varphi_k(z), \end{aligned} \]

with

\[ \varphi_k(x) = e^{-\gamma x^2} \sqrt{\frac{(2\gamma)^k}{k!}}\; x^k . \]

So the RBF kernel is a dot product, but in a space with one coordinate for every power of \(x\): infinitely many. No computer could build that lift; the kernel computes its dot products with one subtraction, one square and one exponential.

A bar and line chart for x equals 1, z equals 2 and gamma equals 0.5. Orange bars show the size of each term of the series, for 1 to 10 terms kept: about 0.08, 0.16, 0.16, 0.11, 0.05, then shrinking towards zero. A vermillion line with dots shows the running sum, rising from 0.08 to 0.25, 0.41, 0.52, 0.57 and levelling off on a dashed line at 0.6065, labelled k(1, 2) equals e to the minus 0.5 equals 0.6065.
ML02.8.2-F3

The series of the deeper block for \({x = 1}\), \({z = 2}\), \({\gamma = 0.5}\). Eight terms already give 0.6059 of the exact 0.6065.

NoteResult: every Gram matrix of a kernel is positive semidefinite

If \({k(\vect{x}, \vect{z}) = \varphi(\vect{x}) \cdot \varphi(\vect{z})}\), then for any points and any numbers \({c_1, \dots, c_n}\), \({\vect{c}\T \mat{K} \vect{c} \ge 0}\).

Proof. Write the quadratic form as a double sum and use the feature map:

\[ \begin{aligned} \vect{c}\T \mat{K} \vect{c} &= \sum_{i} \sum_{j} c_i c_j \\ &\qquad \times \varphi(\vect{x}_i) \cdot \varphi(\vect{x}_j) \\ &= \Big(\sum_i c_i \varphi(\vect{x}_i)\Big) \\ &\qquad \cdot \Big(\sum_j c_j \varphi(\vect{x}_j)\Big) \\ &= \Big\|\sum_i c_i \varphi(\vect{x}_i)\Big\|^2 \;\ge\; 0 . \end{aligned} \]

The second line pulls the sums apart, which the dot product allows because it is linear in each side. A symmetric matrix with this property is positive semidefinite, and (M03.4) that is the same as having no negative eigenvalue.

The converse also holds. Mercer’s theorem, in the form the CS229 notes give it: a symmetric function \(k\) is a kernel exactly when, for every finite set of points, its Gram matrix is positive semidefinite. So a candidate can be checked without finding its feature map: build Gram matrices and look at their eigenvalues. One negative eigenvalue, on one set of points, rules it out.

Building new kernels. If \(k_1\) and \(k_2\) are kernels, so is \({k_1 + k_2}\).

Proof. Let \({\varphi_1}\) and \({\varphi_2}\) be their maps, and stack them into one longer list, \({\varphi(\vect{x}) = (\varphi_1(\vect{x}), \varphi_2(\vect{x}))}\). A dot product of stacked lists is the sum of the dot products of the parts:

\[ \varphi(\vect{x}) \cdot \varphi(\vect{z}) = k_1(\vect{x}, \vect{z}) + k_2(\vect{x}, \vect{z}) . \]

The same works through the Gram matrices: \({\vect{c}\T(\mat{K}_1 + \mat{K}_2)\vect{c}}\) is a sum of two numbers that are each at least 0. A positive multiple \({a\,k_1}\) with \({a > 0}\) is a kernel with the map \({\sqrt{a}\,\varphi_1}\), and a product \({k_1 k_2}\) is a kernel too (exercise 3). These rules build \({(\vect{x} \cdot \vect{z} + c)^p}\) from the plain dot product and a constant.

Worked example

The Gram matrices of three ring points, \((1, 0)\), \((0, 1)\) and \((2, 2)\).

Quadratic kernel. The dot products are \({(1, 0) \cdot (0, 1) = 0}\), \({(1, 0) \cdot (2, 2) = 2}\), \({(0, 1) \cdot (2, 2) = 2}\) and \({(2, 2) \cdot (2, 2) = 8}\), with 1 for each of the first two points with itself. Squaring each:

\[ \mat{K} = \begin{pmatrix} 1 & 0 & 4 \\ 0 & 1 & 4 \\ 4 & 4 & 64 \end{pmatrix} . \]

Two checks by hand. The trace is \({1 + 1 + 64 = 66}\), the sum of the eigenvalues. The determinant, expanded along the first row, is

\[ \begin{aligned} &1\,(64 - 16) - 0 + 4\,(0 - 4) \\ &\quad = 48 - 16 = 32, \end{aligned} \]

the product of the eigenvalues. NumPy gives 0.496, 1 and 64.504, which add to 66, multiply to 32, and are all positive.

RBF kernel with \({\gamma = 0.5}\). The squared distances are 2 between the first two points and \({1 + 4 = 5}\) from each of them to \((2, 2)\). So the entries off the diagonal are \({e^{-1} \approx 0.368}\) and \({e^{-2.5} \approx 0.082}\), with 1 on the diagonal. One eigenvector can be read off: the matrix sends \({(1, -1, 0)}\) to (the two entries \(0.082\) in its last row cancel)

\[ \begin{aligned} &(1 - 0.368,\; 0.368 - 1,\; 0) \\ &\quad = 0.632\,(1, -1, 0), \end{aligned} \]

so 0.632 is an eigenvalue. The other two are 0.966 and 1.401; all three are positive.

Two three by three grids of numbers with rows and columns labelled (1, 0), (0, 1) and (2, 2), each cell shaded vermillion by its size. The left grid, titled Quadratic: (x dot z) squared, holds 1, 0, 4 in the first row, 0, 1, 4 in the second and 4, 4, 64 in the third, with the 64 darkest. Below it: eigenvalues 0.50, 1, 64.50: all at least 0. The right grid, titled RBF: e to the minus 0.5 times the squared distance, holds 1, 0.368, 0.082; 0.368, 1, 0.082; 0.082, 0.082, 1, with the diagonal darkest. Below it: eigenvalues 0.63, 0.97, 1.40: all at least 0.
ML02.8.2-F4

The two Gram matrices entry by entry. Every eigenvalue is positive, as the theorem promises.

Code

The two routes, then Gram matrices and the eigenvalue test.

import math
import numpy as np

def quad_map(x):
    return np.array([x[0] ** 2, math.sqrt(2) * x[0] * x[1], x[1] ** 2])

x, z = np.array([1.0, 2.0]), np.array([3.0, 1.0])
print("long route: ", quad_map(x) @ quad_map(z))
print("short route:", (x @ z) ** 2)

def gram(kernel, X):
    return np.array([[kernel(a, b) for b in X] for a in X])

quad = lambda a, b: (a @ b) ** 2
rbf = lambda a, b, gamma=0.5: math.exp(-gamma * np.sum((a - b) ** 2))
P = np.array([(1.0, 0.0), (0.0, 1.0), (2.0, 2.0)])
for name, kernel in [("quadratic", quad), ("RBF", rbf)]:
    K = gram(kernel, P)
    print(name, "Gram matrix:\n", np.round(K, 3), "\n eigenvalues:", np.round(np.linalg.eigvalsh(K), 3))
long route:  25.0
short route: 25.0
quadratic Gram matrix:
 [[ 1.  0.  4.]
 [ 0.  1.  4.]
 [ 4.  4. 64.]] 
 eigenvalues: [ 0.496  1.    64.504]
RBF Gram matrix:
 [[1.    0.368 0.082]
 [0.368 1.    0.082]
 [0.082 0.082 1.   ]] 
 eigenvalues: [0.632 0.966 1.401]

Now the twelve ring points under four candidates: the quadratic kernel, the polynomial kernel with \({c = 1}\), the RBF kernel and, as an impostor, the squared distance \({\norm{\vect{x} - \vect{z}}^2}\). scikit-learn’s pairwise module computes the first three.

from sklearn.metrics.pairwise import polynomial_kernel, rbf_kernel

R = np.array([(1, 0), (-1, 0), (0, 1), (0, -1), (3, 0), (-3, 0), (0, 3), (0, -3),
              (2, 2), (2, -2), (-2, 2), (-2, -2)], dtype=float)
D2 = ((R[:, None, :] - R[None, :, :]) ** 2).sum(axis=-1)
candidates = {
    "(x.z)^2": polynomial_kernel(R, degree=2, gamma=1, coef0=0),
    "(x.z + 1)^2": polynomial_kernel(R, degree=2, gamma=1, coef0=1),
    "RBF, gamma 0.5": rbf_kernel(R, gamma=0.5),
    "squared distance": D2,
}
for name, K in candidates.items():
    ev = np.linalg.eigvalsh(K)
    smallest = round(ev.min(), 3) + 0.0        # + 0.0 prints a rounding error of -1e-15 as 0.000
    print(f"{name:17s} smallest eigenvalue {smallest:8.3f}   rank {np.sum(np.abs(ev) > 1e-9)}")

terms = [math.exp(-0.5 * 1 - 0.5 * 4) * 1.0 ** k / math.factorial(k) * 2.0 ** k for k in range(8)]
print("eight terms of the RBF series:", round(sum(terms), 4), " exact:", round(math.exp(-0.5), 4))
(x.z)^2           smallest eigenvalue    0.000   rank 3
(x.z + 1)^2       smallest eigenvalue    0.000   rank 6
RBF, gamma 0.5    smallest eigenvalue    0.376   rank 12
squared distance  smallest eigenvalue  -72.000   rank 4
eight terms of the RBF series: 0.6059  exact: 0.6065

The ranks tell a story. The quadratic kernel’s Gram matrix has rank 3, because its lifted points live in three dimensions. With \({c = 1}\) there are six monomials, and rank 6. The RBF kernel’s matrix has full rank 12: its lifted space has room for every point to point its own way. The squared distance has a smallest eigenvalue of \(-72\), so it is no kernel at all.

Explore

This module’s interactive, the kernel lift, lives in lesson 3. Its second half puts an RBF kernel to work: slide \(\gamma\) and watch the boundary follow the length scale.

Pitfalls

Two bar charts of the twelve eigenvalues of a Gram matrix on the rings, smallest first. The left chart, marked with a cross and titled squared distance, has three vermillion bars below zero, two of them at minus 72, then eight bars at zero and one green bar at about 156; a note reads three below zero, the lowest minus 72. The right chart, marked with a tick and titled e to the minus 0.5 times the squared distance, has twelve green bars, all above zero, from 0.38 up to about 1.9; a note reads all twelve above zero, the lowest 0.38.
ML02.8.2-F5

Wrong beside right. Left: the squared distance looks like a sensible score, but its Gram matrix has negative eigenvalues. Right: the RBF kernel, built from the same distance, passes.

“Any sensible similarity score can be used as a kernel.”

Only one whose Gram matrices are all positive semidefinite. The squared distance fails on the rings, and on even less: for two points at distance \(r\) its Gram matrix is

\[ \begin{pmatrix} 0 & r^2 \\ r^2 & 0 \end{pmatrix}, \]

whose eigenvalues are \(r^2\) and \({-r^2}\). An SVM given such a function is no longer solving a convex problem, and its solver can fail or return nonsense.

“A negative entry in the Gram matrix means the function is not a kernel.”

Entries may be negative: the plain dot product of \((1, 0)\) and \((-1, 0)\) is \(-1\). The test is about the eigenvalues of the whole matrix, not the signs of its entries.

“A bigger \(\gamma\) makes the RBF kernel wider.”

It is the other way round. \(\gamma\) multiplies the squared distance, so a bigger \(\gamma\) makes the kernel fall faster: \({\gamma = 1/(2\ell^2)}\) is an inverse squared length scale. In scikit-learn, gamma sets this same number.

Check yourself

Recall

1. For the quadratic map, what is \({\varphi(\vect{x}) \cdot \varphi(\vect{z})}\) in terms of \(\vect{x}\) and \(\vect{z}\)?

Show answer

\({(\vect{x} \cdot \vect{z})^2}\). The \(\sqrt{2}\) on the cross term supplies the factor 2 that squaring a sum produces.

2. What is a Gram matrix?

Show answer

For points \({\vect{x}_1, \dots, \vect{x}_n}\), the \(n \times n\) matrix of kernel values \({K_{ij} = k(\vect{x}_i, \vect{x}_j)}\): the dot products of all pairs of lifted points.

3. What is the RBF kernel of a point with itself, what happens far away, and what does a larger \(\gamma\) do?

Show answer

It is 1 for a point with itself and falls towards 0 as points move apart. A larger \(\gamma\) makes it fall faster: a shorter length scale.

4. How can you test whether a function is a kernel without finding its feature map?

Show answer

Build its Gram matrix on sets of points and look at the eigenvalues. If one set gives a negative eigenvalue, it is not a kernel. Mercer’s theorem says that if every Gram matrix is positive semidefinite, it is.

5. Why is the sum of two kernels a kernel?

Show answer

Stack the two feature maps into one list; the dot product of stacked lists is the sum of the two dot products. Equivalently, \({\vect{c}\T(\mat{K}_1 + \mat{K}_2)\vect{c}}\) is a sum of two numbers that are each at least 0.

Exercises

1. ★ Compute \({(\vect{x} \cdot \vect{z} + 1)^2}\) for \({\vect{x} = (1, 2)}\) and \({\vect{z} = (3, 1)}\). Then check it with the feature map

\[ \begin{aligned} \varphi(\vect{x}) = \big(&1,\; \sqrt{2}\,x_1,\; \sqrt{2}\,x_2, \\ &x_1^2,\; \sqrt{2}\,x_1 x_2,\; x_2^2\big) . \end{aligned} \]

Show solution

\({\vect{x} \cdot \vect{z} = 5}\), so the kernel is \({6^2 = 36}\). The lifted points are \({\varphi(\vect{x}) = (1, \sqrt{2}, 2\sqrt{2}, 1, 2\sqrt{2}, 4)}\) and \({\varphi(\vect{z}) = (1, 3\sqrt{2}, \sqrt{2}, 9, 3\sqrt{2}, 1)}\). The products of matching coordinates are 1, 6, 4, 9, 12 and 4, which add up to 36.

2. ★★ Show that \({k(\vect{x}, \vect{z}) = \vect{x} \cdot \vect{z} - 1}\) is not a kernel.

Show solution

Take the single point \({\vect{x}_1 = \vect{0}}\). Its Gram matrix is the \(1 \times 1\) matrix \({(k(\vect{0}, \vect{0})) = (-1)}\), whose only eigenvalue is \(-1\). With \({c_1 = 1}\), \({\vect{c}\T \mat{K} \vect{c} = -1 < 0}\). A true kernel would give \({\norm{\varphi(\vect{0})}^2 \ge 0}\) there, so no feature map exists.

3. ★★★ Let \(k_1\) and \(k_2\) be kernels with feature maps \({\varphi_1}\) (with \(D_1\) coordinates) and \({\varphi_2}\) (with \(D_2\)). Show that \({k_1 k_2}\) is a kernel by writing down a feature map for it.

Show solution

Write \(u_a\) for the coordinates of \({\varphi_1}\) and \(v_b\) for those of \({\varphi_2}\). Let \(\varphi\) list all \({D_1 D_2}\) products \({u_a(\vect{x})\,v_b(\vect{x})}\), one for each pair \((a, b)\). Then

\[ \begin{aligned} &\varphi(\vect{x}) \cdot \varphi(\vect{z}) \\ &= \sum_{a} \sum_{b} u_a(\vect{x}) v_b(\vect{x})\, u_a(\vect{z}) v_b(\vect{z}) \\ &= \Big(\sum_a u_a(\vect{x}) u_a(\vect{z})\Big) \\ &\qquad \times \Big(\sum_b v_b(\vect{x}) v_b(\vect{z})\Big) \\ &= k_1(\vect{x}, \vect{z})\; k_2(\vect{x}, \vect{z}) . \end{aligned} \]

The second line groups the factors with index \(a\) and those with index \(b\); a double sum of products that split this way is the product of two single sums.

Summary card

A kernel is the dot product of a lift, computed without the lift.

The anchor figure again: from x equals (1, 2) and z equals (3, 1), the long route through the lifted points gives 9 plus 12 plus 4 equals 25, and the short route gives 5 squared equals 25.
ML02.8.2-F1

Two routes, one number.

  • Kernel. \({k(\vect{x}, \vect{z}) = \varphi(\vect{x}) \cdot \varphi(\vect{z})}\); Gram matrix \({K_{ij} = k(\vect{x}_i, \vect{x}_j)}\).
  • Polynomial. \({(\vect{x} \cdot \vect{z} + c)^p}\), all monomials up to degree \(p\).
  • RBF. \({e^{-\gamma \norm{\vect{x} - \vect{z}}^2}}\), an infinite lift; \({\gamma = 1/(2\ell^2)}\).
  • The test. Every Gram matrix positive semidefinite (Mercer); sums, products and positive multiples of kernels are kernels.

Sources and next steps

Sources. Each was opened and checked against this lesson on 15 November 2026.

  • Tengyu Ma and Andrew Ng, CS229 Lecture Notes, Stanford University, Sections 5.3 and 5.4. Defines the kernel as the inner product of a feature map (equation 5.10), shows that \({(\vect{x}\T\vect{z})^2}\) is the kernel of the map of all products \({x_i x_j}\) and costs \(O(d)\) instead of \(O(d^2)\), treats \({(\vect{x}\T\vect{z} + c)^2}\) and the Gaussian kernel with its infinite-dimensional feature map, proves that a kernel matrix is positive semidefinite, and states Mercer’s theorem in the finite form used here.
  • Kilian Weinberger, Lecture 14: Kernels continued, Cornell CS4780 (Fall 2018). Lists the rules that build well-defined kernels from others, including positive multiples, sums, products and the exponential of a kernel.
  • scikit-learn 1.9 User Guide, Section 1.4.6, Kernel functions. Gives the linear, polynomial \({(\gamma\langle x, x'\rangle + r)^d}\), RBF \({\exp(-\gamma\norm{x - x'}^2)}\) and sigmoid kernels with their parameter names gamma, coef0 and degree.

Next. ML02.8.3 Kernel SVMs swaps the dot product in the SVM’s dual for a kernel and lets the boundary bend.

This lesson unlocks

ML02.8.3 Kernel SVMs

Your progress is saved in this browser only. No account, no tracking.
Back to top