Standard kernels like RBF and Matérn operate on Euclidean vector spaces—each input is a fixed-length vector of real numbers. However, many real-world data types don't naturally fit this representation:

• Strings and sequences (DNA, proteins, text)
• Graphs and networks (molecules, social networks)
• Sets and bags (documents as word collections)
• Trees and hierarchical structures (parse trees, ontologies)
• Probability distributions (histograms, density estimates)

Domain-specific kernels enable kernel methods to operate directly on these structured data types, without requiring hand-crafted feature engineering.

String kernels measure similarity between sequences of symbols. They are fundamental in computational biology (DNA/protein analysis), natural language processing (text classification), and cybersecurity (malware detection from code patterns).

The Key Insight:

Strings can be mapped to feature vectors by counting occurrences of substrings, characters, or patterns. The kernel computes the inner product in this (potentially infinite-dimensional) feature space without explicit construction.

Spectrum Kernel (Leslie et al., 2002):

The k-spectrum kernel represents a string by the frequency of all contiguous substrings of length $k$:

$$k(s, t) = \langle \Phi_k(s), \Phi_k(t) \rangle = \sum_{u \in \Sigma^k} #_u(s) \cdot #_u(t)$$

where $\Sigma$ is the alphabet, $\Sigma^k$ is the set of all $k$-mers, and $#_u(s)$ counts occurrences of substring $u$ in string $s$.

Example: For $k=3$ and strings $s=\text{"GATTACA"}$, $t=\text{"ATTGAT"}$:

• 3-mers in $s$: GAT, ATT, TTA, TAC, ACA
• 3-mers in $t$: ATT, TTG, TGA, GAT
• Shared: GAT (1×1=1), ATT (1×1=1)
• $k(s,t) = 2$

Subsequence Kernel (Lodhi et al., 2002):

Unlike the spectrum kernel which requires contiguous matches, the subsequence kernel allows gaps, weighted by a decay factor:

$$k(s, t) = \sum_{u \in \Sigma^k} \sum_{\mathbf{i}: s[\mathbf{i}]=u} \sum_{\mathbf{j}: t[\mathbf{j}]=u} \lambda^{l(\mathbf{i}) + l(\mathbf{j})}$$

where $\mathbf{i}$ is a tuple of indices, $s[\mathbf{i}]$ extracts the subsequence at those positions, and $l(\mathbf{i})$ is the "spread" of the indices (last - first + 1). The decay $\lambda \in (0,1)$ penalizes non-contiguous matches.

Intuition: Two strings are similar if they share common subsequences, with contiguous matches worth more than scattered ones.

Mismatch Kernel:

The mismatch kernel extends spectrum kernels to allow up to $m$ mismatches:

$$k(s, t) = \sum_{u \in \Sigma^k} \sum_{v \in N_m(u)} \mathbf{1}[u \sqsubset s] \cdot \mathbf{1}[v \sqsubset t]$$

where $N_m(u)$ is the neighborhood of $u$ (all strings within Hamming distance $m$).

Graph kernels measure similarity between graphs, enabling kernel methods for molecular property prediction, social network analysis, and program analysis. The key challenge is that graphs have variable size and no canonical node ordering.

The Graph Isomorphism Challenge:

Determining whether two graphs are identical (isomorphic) is computationally hard (GI-complete). Practical graph kernels compute approximate similarity based on structural features that are efficient to compute.

Random Walk Kernel (Gärtner et al., 2003):

The random walk kernel counts matching walks between two graphs:

$$k(G, G') = \sum_{l=0}^{\infty} \mu_l \sum_{p \in \text{walks}l(G)} \sum{p' \in \text{walks}l(G')} k{\text{walk}}(p, p')$$

where $\text{walks}l(G)$ is the set of walks of length $l$ in $G$, and $k{\text{walk}}$ compares node/edge labels along walks.

Efficient Computation: Using the direct product graph $G \times G'$ (vertices are pairs of vertices, edges connect pairs if both components are connected), the kernel reduces to counting walks in $G \times G'$:

$$k(G, G') = \mathbf{1}^\top (I - \lambda A_{\times})^{-1} \mathbf{1}$$

where $A_{\times}$ is the adjacency matrix of the product graph and $\lambda < 1/\rho(A_{\times})$ for convergence.

Weisfeiler-Lehman (WL) Subtree Kernel (Shervashidze et al., 2011):

The WL kernel uses iterative neighborhood aggregation to create node labels:

1. Initialize: Each node gets its original label (or degree)
2. Iterate: Update each node's label by hashing: $\ell^{(h+1)}(v) = \text{hash}(\ell^{(h)}(v), {!{\ell^{(h)}(u) : u \in N(v)}!})$
3. Count: After $H$ iterations, count occurrences of each label
4. Compare: Kernel is inner product of label count vectors

$$k(G, G') = \sum_{h=0}^{H} k_{\text{base}}(G^{(h)}, G'^{(h)})$$

where $G^{(h)}$ is graph $G$ with labels from iteration $h$, and $k_{\text{base}}$ is typically a label histogram comparison.

Complexity: $O(Hm)$ per graph where $m$ is the number of edges. Linear in graph size—highly scalable.

Many real-world objects are naturally represented as sets (unordered collections) or probability distributions. Examples include:

• Documents as sets/bags of words
• Images as sets of local descriptors (SIFT, etc.)
• Point clouds from 3D scanning
• Empirical distributions from samples

Set kernels must be permutation-invariant: the kernel value should not depend on the order of elements.

Set Kernels:

Sum Kernel (naive): $$k(X, Y) = \sum_{x \in X} \sum_{y \in Y} k_{\text{base}}(x, y)$$

This counts total similarity across all pairs but ignores set structure.

Mean Kernel: $$k(X, Y) = \frac{1}{|X||Y|} \sum_{x \in X} \sum_{y \in Y} k_{\text{base}}(x, y)$$

Equivalent to kernel between mean embeddings in the RKHS.

Match Kernel: $$k(X, Y) = \sum_{x \in X} \max_{y \in Y} k_{\text{base}}(x, y)$$

Each element in $X$ matches to its best counterpart in $Y$. Note: not symmetric as written.

Maximum Mean Discrepancy (MMD):

The MMD measures the distance between two distributions in RKHS:

$$\text{MMD}^2(P, Q) = |\mu_P - \mu_Q|_{\mathcal{H}}^2$$

Expanding: $$\text{MMD}^2 = \mathbb{E}{x,x' \sim P}[k(x,x')] - 2\mathbb{E}{x \sim P, y \sim Q}[k(x,y)] + \mathbb{E}_{y,y' \sim Q}[k(y,y')]$$

Given samples ${x_i}{i=1}^n \sim P$ and ${y_j}{j=1}^m \sim Q$, the unbiased estimator is:

$$\widehat{\text{MMD}}^2 = \frac{1}{n(n-1)} \sum_{i eq j} k(x_i, x_j) - \frac{2}{nm} \sum_{i,j} k(x_i, y_j) + \frac{1}{m(m-1)} \sum_{i eq j} k(y_i, y_j)$$

Applications:

• Two-sample hypothesis testing
• Domain adaptation
• GAN training (MMD-GAN)
• Distributional regression

Before deep learning dominated computer vision, kernel-based methods with specialized image kernels achieved state-of-the-art results. Understanding these kernels remains valuable for interpretability, small-data regimes, and hybrid approaches.

Challenges in Image Comparison:

1. Translation/rotation variance: Objects can appear anywhere in the image
2. Scale variance: Same object at different sizes
3. Illumination variance: Lighting changes
4. Partial occlusion: Objects partially hidden
5. Intra-class variation: Different instances look different

Spatial Pyramid Match Kernel (Lazebnik et al., 2006):

The spatial pyramid match (SPM) kernel extends bag-of-words to capture spatial layout:

1. Extract local features: SIFT, HOG, or learned descriptors
2. Quantize to visual words: K-means clustering creates a codebook
3. Build spatial pyramid: Divide image into $2^l \times 2^l$ cells at level $l$
4. Histogram per cell: Count visual words in each cell
5. Weighted matching: Match histograms across levels

$$k(I, I') = \sum_{l=0}^{L} \frac{1}{2^{L-l}} \left[ \mathcal{I}^l(I, I') - \mathcal{I}^{l-1}(I, I') \right]$$

where $\mathcal{I}^l$ is the histogram intersection at level $l$. Finer matches (higher $l$) are weighted more than coarse matches.

Pyramid Match Kernel (Grauman & Darrell, 2005):

The pyramid match kernel (PMK) handles sets of features by multi-resolution histogram matching:

1. Build histograms: At resolution $i$, bin features into $D \cdot 2^i$ bins (where $D$ is feature dimension)
2. Compute intersections: $\mathcal{I}^i = \sum_j \min(H^i_I(j), H^i_{I'}(j))$
3. Weight by level: Matches at finer levels (larger $i$) contribute more

$$k(I, I') = \sum_{i=0}^{L} w_i \left( \mathcal{I}^i - \mathcal{I}^{i+1} \right)$$

Convolution Kernels for Images:

Direct pixel-based kernels rarely work due to sensitivity to translation. The convolution kernel addresses this:

$$k(I, I') = \sum_{\tau} k_{\text{base}}(I_{\text{patch}}(\tau), I'_{\text{patch}}(\tau))$$

summing base kernel evaluations over all spatial positions $\tau$.

Time series data presents unique challenges for kernel design: variable length, temporal dependencies, and phase shifts (similar patterns occurring at different times).

Dynamic Time Warping (DTW) Kernel:

DTW finds the optimal alignment between two time series by warping the time axis. While DTW distance is not a valid kernel (violates positive definiteness), several kernelized versions exist:

$$k_{\text{DTW}}(\mathbf{x}, \mathbf{y}) = \exp\left(-\gamma \cdot \text{DTW}(\mathbf{x}, \mathbf{y})\right)$$

Warning: This is NOT guaranteed positive definite. In practice, it often works, but theoretically it's a pseudo-kernel.

Global Alignment Kernel (Cuturi, 2007):

A proper positive-definite DTW-like kernel:

$$k_{\text{GA}}(\mathbf{x}, \mathbf{y}) = \sum_{\pi \in \mathcal{A}(|\mathbf{x}|, |\mathbf{y}|)} \prod_{(i,j) \in \pi} k_{\text{local}}(x_i, y_j)$$

summing over all valid alignments $\pi$ in the alignment space $\mathcal{A}$.

Signature Kernels (Kiraly & Oberhauser, 2019):

The path signature is a mathematical object that uniquely characterizes continuous paths (modulo tree-like equivalence). The signature kernel measures similarity between paths via their signatures:

$$k(\mathbf{x}, \mathbf{y}) = \langle S(\mathbf{x}), S(\mathbf{y}) \rangle$$

where $S(\mathbf{x})$ is the truncated signature (a collection of iterated integrals).

Properties:

• Naturally handles variable-length sequences
• Captures complex dependencies through iterated integrals
• Provably universal for continuous paths
• Efficient computation via kernel trick (PDE solving)

Fourier/Spectral Kernels for Time Series:

Compare time series via their frequency content:

$$k(\mathbf{x}, \mathbf{y}) = k_{\text{base}}\left(|\mathcal{F}(\mathbf{x})|, |\mathcal{F}(\mathbf{y})|\right)$$

where $\mathcal{F}$ is the discrete Fourier transform. This is phase-invariant but loses temporal localization.

Designing domain-specific kernels follows a principled approach: encode the invariances and similarities that matter for your domain while maintaining positive definiteness.