Implement RBF (Gaussian) Kernel Function

Problem

Implement the RBF (Radial Basis Function / Gaussian) Kernel. Given two vectors, compute the kernel value: K(x, y) = exp(-gamma * ||x - y||^2). Also support computing the full kernel matrix for a set of data points.

Solution

Compute the squared Euclidean distance between the vectors and apply the Gaussian exponential. For the kernel matrix, compute pairwise.

import math

def rbf_kernel(
    x: list[float],
    y: list[float],
    gamma: float | None = None,
) -> float:
    dim = len(x)
    if gamma is None:
        gamma = 1.0 / dim

    sq_dist = sum((x[d] - y[d]) ** 2 for d in range(dim))
    return round(math.exp(-gamma * sq_dist), 6)


def rbf_kernel_matrix(
    X: list[list[float]],
    gamma: float | None = None,
) -> list[list[float]]:
    n = len(X)
    dim = len(X[0])
    if gamma is None:
        gamma = 1.0 / dim

    matrix = []
    for i in range(n):
        row = []
        for j in range(n):
            sq_dist = sum((X[i][d] - X[j][d]) ** 2 for d in range(dim))
            row.append(round(math.exp(-gamma * sq_dist), 6))
        matrix.append(row)

    return matrix

Explanation

1. The RBF kernel measures similarity between two vectors based on their Euclidean distance.
2. Compute ||x - y||^2 = sum((x_d - y_d)^2).
3. Apply the Gaussian: K(x, y) = exp(-gamma * ||x - y||^2).
4. When gamma is not specified, default to 1 / n_features (scikit-learn convention).
5. K(x, y) = 1 when x = y (identical points) and approaches 0 as points diverge.
6. The RBF kernel implicitly maps data into an infinite-dimensional feature space, enabling SVMs to find nonlinear decision boundaries.
7. The kernel matrix is symmetric and positive semi-definite: K[i][j] = K(X[i], X[j]).

Complexity

• Time: O(d) for a single kernel evaluation; O(n^2 * d) for the full kernel matrix
• Space: O(1) for a single evaluation; O(n^2) for the kernel matrix