Which functions are kernels?
Section of Support vector machines, part of Statistical learning
Which functions are kernels?
| Type | Section |
| Taught in | Support vector machines |
| Part | Statistical learning |
A proposed similarity is not automatically an inner product. The necessary and sufficient condition is symmetry and positive semidefiniteness of every finite Gram matrix. This yields a representation in a Hilbert feature space. Mercer’s spectral theorem adds regularity and domain assumptions. The finite-Gram criterion is the condition needed for the convex dual:
\sum_{i=1}^{n}\sum_{j=1}^{n} c_i c_j K(x_i,x_j)\ge 0
for every finite choice of input points and every real vector c. Equivalently, the Gram matrix K_S=(K(x_i,x_j))_{ij} must be positive semidefinite. Checking one training Gram matrix checks that particular optimisation problem, not validity of the function on every possible data set.
If K_1 and K_2 are kernels in this sense, so are \alpha K_1+\beta K_2 for \alpha,\beta\ge 0, the product K_1 K_2, and the powers K^d for d\in\mathbb{N}. The product statement is the Schur product theorem for entrywise products of positive semi-definite matrices. These closure properties let new kernels be built from old ones.
Used in
See also
Signed distance · Vapnik’s radius–margin bound · Hard-margin primal · Hard-margin dual · Soft-margin primal · Kernel · Linear separators and the margin · Distance to a hyperplane