Is any symmetric similarity a kernel of the kind described here?

No. Every finite Gram matrix must also be positive semidefinite.

Must the feature map be constructed explicitly?

No. Avoiding that construction is a central benefit when an algorithm only needs the inner products.

Can a valid kernel return a negative number?

Yes. A linear kernel on oppositely directed vectors provides a simple example.

AI Glossary / Mathematics and optimization / Intermediate

Kernel (kernel method)

Definition

A kernel, in kernel-based machine learning, is a function that evaluates an inner product between representations of two inputs in a feature space. For a real-valued positive-semidefinite kernel, every finite Gram matrix is symmetric and positive semidefinite. This lets suitable algorithms work with transformed-feature inner products without necessarily constructing the transformed features explicitly.

What it means

A kernel often behaves like a similarity measure, but that description is incomplete. Not every intuitive similarity function is a valid positive-semidefinite kernel. The mathematical property matters because learning methods rely on the geometry and optimization structure it provides.
The same word has other meanings, including an operating-system kernel, a convolution filter, and the nullspace of a linear map. This entry concerns the function used in kernel methods. Its feature space can be finite-dimensional or infinite-dimensional, and the feature representation is not necessarily unique.

How it works

Given inputs x and z, write k(x,z)=<phi(x),phi(z)> for an associated feature map phi. For examples x_1 through x_n, construct the Gram matrix K with entries K_ij=k(x_i,x_j). Positive semidefiniteness requires c-transpose K c≥0 for every real coefficient vector c and every finite input selection.
Examples include the linear kernel x-transpose z and suitable polynomial and Gaussian radial-basis kernels. Their parameters affect the resulting geometry. A learning algorithm can use kernel values in place of explicit feature inner products where its formulation permits that substitution. A valid kernel alone does not specify the model, loss, regularization, or evaluation procedure.

Three practical examples

A support-vector classifier can use a kernel to represent nonlinear boundaries in the original input coordinates.
Kernel ridge regression can model a nonlinear relationship through similarities to training examples.
A structured-data model can use a carefully designed kernel for objects such as strings or graphs when ordinary coordinate features are inconvenient.

Think of it this way

Think of comparing two objects through a shared measuring system without writing down every coordinate used by that system. The analogy is limited because a kernel is not an arbitrary shortcut or black-box resemblance score: it must supply the required inner-product structure for the method being used.

Worked example

Consider an original scalar-input polynomial kernel k(x,z)=(1+xz)^2. Expanding gives 1+2xz+x²z². Define phi(x)=(1,sqrt(2)x,x²). Then the ordinary dot product phi(x) dot phi(z) equals the kernel exactly.
For x=1 and z=2, direct kernel evaluation gives (1+2)^2=9. The transformed vectors are (1,sqrt(2),1) and (1,2sqrt(2),4). Their dot product is 1+4+4=9, confirming the feature-map interpretation.
For the two inputs 0 and 1, the Gram matrix has rows (1,1) and (1,4). Its diagonal entries are positive and its determinant is 3, so this particular two-by-two matrix is positive definite. More generally, the explicit feature map establishes positive semidefiniteness for every finite input set: c-transpose K c is the squared norm of the sum of c_i phi(x_i), which cannot be negative.
Now consider a proposed similarity table on two objects with rows (1,2) and (2,1). All entries are positive and the table is symmetric. Nevertheless, using c=(1,−1) gives c-transpose K c=−2. This table fails the positive-semidefinite requirement, demonstrating that positive entries and symmetry are insufficient.
Kernel values also need not lie between zero and one. Our valid polynomial example gives 9. A linear kernel can even be negative between two inputs: k(1,−1)=−1, while its Gram matrices remain positive semidefinite. Positivity refers to quadratic forms of Gram matrices, not to every individual pairwise value.

Illustrative case study

In a fictional example, Cedar Labels designs a custom similarity score for short product descriptions. The score seems intuitively reasonable, so the team plans to insert it into a kernel-based model without further analysis.
An analyst checks small Gram matrices and finds a negative quadratic form. The team investigates a feature-based construction whose kernel validity can be justified, then compares predictive results on held-out examples. This invented case illustrates the difference between a plausible similarity and a valid kernel. Passing a few finite checks alone would still not prove validity over every possible input.

Common misconceptions and mistakes

A kernel is not automatically a distance. Distances and inner products have different defining properties, even though a kernel can induce a feature-space distance through k(x,x)+k(z,z)−2k(x,z).
Do not confuse positive-semidefinite with strictly positive-definite. Duplicate inputs or finite-dimensional feature maps can produce singular Gram matrices while the kernel remains valid. Regularization may be needed for a particular numerical solve.
The kernel trick does not eliminate every computational cost. A dense Gram matrix for n examples has n² entries, which can become expensive. Choosing a more elaborate kernel also does not guarantee better generalization; it changes model assumptions that require evaluation.

Business use

Kernel choice is a modeling decision about what relationships between inputs the learner can exploit. For a business problem, compare candidate kernels and their parameter settings using a validation plan aligned with the intended task. Scaling input variables matters because it can change the kernel geometry substantially.
Document whether the chosen function has a known valid construction, how missing or unusual inputs are handled, and what training and prediction costs are expected. Avoid explaining every latent feature as a real-world property. The useful business evidence is performance and reliability on relevant cases, supported by a mathematically appropriate formulation.

Check your understanding

A two-item similarity matrix has positive entries but c-transpose K c is negative for one vector c. Is it a valid Gram matrix for a real positive-semidefinite kernel?

Answer: No. One negative quadratic form is enough to violate the required property.

Related terms

Learn next

Derive an explicit feature map for the homogeneous scalar kernel (xz)^2 and compare it with the worked kernel's three features. Then test the invalid two-object matrix using both its quadratic form and eigenvalues. Explain why one valid small matrix cannot prove a proposed function valid everywhere.

Feature map

Sources

Primary terminology source: Alexander Jung and collaborators, The Aalto Dictionary of Machine Learning, kernel in kernel methods: https://aaltodictionaryofml.github.io/ADictML_Main.pdf . Symmetry and finite Gram-matrix positive semidefiniteness were checked against the source. All polynomial, matrix, and fictional examples above are original.

Previous: Kernel function Next: Kernel method