📘

RBF Kernel Matrix

HardSupport Vector Machines 📚 Machine 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:

The RBF kernel matrix is computed by calculating $K(x, y) = \exp\left(-\frac{\|x - y\|^2}{2\sigma^2}\right)$ for each pair of points $x$ and $y$ in the input set $X$ .
For the given input $X = [[0, 0], [1, 0], [0, 1]]$ and $\sigma = 1.0$ , we calculate the pairwise distances and apply the RBF kernel formula to obtain the kernel matrix values.
The diagonal elements are all $1.0$ since $\|x - x\|^2 = 0$ , resulting in $K(x, x) = \exp(0) = 1.0$ for each point $x$ .
The off-diagonal elements are calculated using the RBF kernel formula, e.g., $K([0, 0], [1, 0]) = \exp\left(-\frac{\|(0-1)^2 + (0-0)^2\|}{2 \cdot 1.0^2}\right) = \exp\left(-\frac{1}{2}\right) \approx 0.6065$ .

Constraints:

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

More from Machine Learning 1

Polynomial KernelMedium Hinge LossEasy Linear Decision BoundaryEasy Gradient Boosting Residual StepHard Random Feature SubspaceMedium

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

0/0

Run code to see test results.