RBF Kernel Matrix

hardFREESupport Vector MachinesMachine Learning 1

Compute the Radial Basis Function (RBF/Gaussian) kernel matrix.

The RBF kernel is: $K(x, y) = \exp\left(-\frac{\|x - y\|^2}{2\sigma^2}\right)$

Given a set of vectors $X$ (n points) and parameter $\sigma$ , compute the $n \times n$ kernel matrix.

Return the matrix with values rounded to 4 decimal places. The diagonal should be all 1.0 (each point compared to itself).

Example

Input

X = [[0, 0], [1, 0], [0, 1]]
sigma = 1.0

Output

[[1.0, 0.6065, 0.6065], [0.6065, 1.0, 0.3679], [0.6065, 0.3679, 1.0]]

Reasoning

Inputs: X holds $n = 3$ points in the plane, $p_0 = (0, 0)$ , $p_1 = (1, 0)$ , $p_2 = (0, 1)$ , and sigma $= 1.0$ sets how quickly similarity fades with distance. With $\sigma = 1$ the denominator is $2\sigma^2 = 2$ .
Squared distances: $\|p_0 - p_1\|^2 = 1^2 + 0^2 = 1$ , $\|p_0 - p_2\|^2 = 0^2 + 1^2 = 1$ , and $\|p_1 - p_2\|^2 = 1^2 + (-1)^2 = 2$ .
Kernel values: the two unit-distance pairs give $e^{-1/2} \approx 0.6065$ ; the pair at squared distance 2 gives $e^{-2/2} = e^{-1} \approx 0.3679$ . Each point against itself has distance 0, so $e^{0} = 1.0$ on the diagonal.
Output: a $3 \times 3$ matrix where entry (row $i$ , column $j$ ) is $K(p_i, p_j)$ , rounded to 4 decimal places: [[1.0, 0.6065, 0.6065], [0.6065, 1.0, 0.3679], [0.6065, 0.3679, 1.0]].
Notice: the matrix is symmetric because $\|p_i - p_j\| = \|p_j - p_i\|$ , and every value lies in $(0, 1]$ . A smaller $\sigma$ shrinks the off-diagonal entries towards 0; a larger one pushes them towards 1.

Constraints

X: 2D list (n x features)
sigma: positive float
Return n x n symmetric kernel matrix
Round each value to 4 decimal places

Learn this in

Support Vector MachinesML Study Plan

More from Machine Learning 1

Polynomial Kernelmedium Hinge Losseasy Linear Decision Boundaryeasy Gradient Boosting Residual Stephard Random Feature Subspacemedium

Concept primer

Background Knowledge

The Radial Basis Function (RBF) kernel, also known as the Gaussian kernel, is a widely used kernel in Support Vector Machines (SVMs). It measures the similarity between two points in a high-dimensional space by calculating the Euclidean distance between them. The RBF kernel is defined as $K(x, y) = \exp\left(-\frac{\|x - y\|^2}{2\sigma^2}\right)$ , where $\|x - y\|$ is the Euclidean distance between $x$ and $y$ , and $\sigma$ is a parameter that controls the spread of the kernel.

In the context of SVMs, the kernel matrix is a square matrix where the entry at row $i$ and column $j$ represents the similarity between the $i^{th}$ and $j^{th}$ data points. The kernel matrix is used to transform the original data into a higher-dimensional space, allowing for non-linear separation of classes. The RBF kernel matrix is a specific type of kernel matrix that uses the RBF kernel to compute the similarities between data points.

The RBF kernel has several important properties, including positive semi-definiteness, which ensures that the kernel matrix is always positive semi-definite. This property is crucial for the convergence of SVM algorithms. Additionally, the RBF kernel is stationary, meaning that it only depends on the distance between the two points, and not on their absolute positions. These properties make the RBF kernel a popular choice for many machine learning applications.

Algorithm/Approach

The general approach to computing the RBF kernel matrix involves iterating over each pair of data points, calculating the Euclidean distance between them, and then applying the RBF kernel formula to obtain the similarity value. This process is typically repeated for all pairs of points, resulting in a square matrix where the entry at row $i$ and column $j$ represents the similarity between the $i^{th}$ and $j^{th}$ points.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize an $n \times n$ matrix to store the kernel values, where $n$ is the number of data points.
Iterate over each pair of data points $(x_i, x_j)$ , where $i$ and $j$ range from $1$ to $n$ .
For each pair, calculate the Euclidean distance $\|x_i - x_j\|$ between the two points.
Apply the RBF kernel formula to obtain the similarity value $K(x_i, x_j) = \exp\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)$ .
Store the similarity value in the corresponding entry of the kernel matrix.
Repeat the process for all pairs of points.
Round the kernel values to 4 decimal places.

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Forgetting to initialize the diagonal elements of the kernel matrix to 1.0, since each point is identical to itself.
Using an incorrect formula for the Euclidean distance or the RBF kernel.
Failing to handle edge cases, such as when the input data points are not vectors or when the parameter $\sigma$ is not a positive value.

Time & Space Complexity

The time complexity of computing the RBF kernel matrix is $O(n^2 d)$ , where $n$ is the number of data points and $d$ is the dimensionality of the data. This is because we need to iterate over all pairs of points and calculate the Euclidean distance between them. The space complexity is $O(n^2)$ , since we need to store the kernel matrix. Note that these complexities assume that the Euclidean distance calculation has a time complexity of $O(d)$ .

solution.py

Python 3.13

Test results