Polynomial Kernel

mediumFREESupport Vector MachinesMachine Learning 1

Compute the polynomial kernel matrix between two sets of vectors.

The polynomial kernel is: $K(x, y) = (x \cdot y + c)^d$

Given two sets of vectors $A$ (m points) and $B$ (n points), compute the $m \times n$ kernel matrix where entry $(i,j) = K(A_i, B_j)$ .

Return the matrix with values rounded to 4 decimal places.

Example

Input

A = [[1, 2], [3, 4]]
B = [[5, 6], [7, 8]]
c = 1, d = 2

Output

[[324, 576], [1600, 2916]]

Reasoning

Inputs: $A$ holds $m = 2$ points and $B$ holds $n = 2$ points, each 2-dimensional; $c = 1$ is the shift and $d = 2$ the degree. The result is a $2 \times 2$ grid: row $i$ for $A_i$ , column $j$ for $B_j$ .
Dot products: $A_1 \cdot B_1 = 1 \cdot 5 + 2 \cdot 6 = 17$ , $A_1 \cdot B_2 = 1 \cdot 7 + 2 \cdot 8 = 23$ , $A_2 \cdot B_1 = 3 \cdot 5 + 4 \cdot 6 = 39$ , $A_2 \cdot B_2 = 3 \cdot 7 + 4 \cdot 8 = 53$ .
Shift and raise: $(17 + 1)^2 = 324$ , $(23 + 1)^2 = 576$ , $(39 + 1)^2 = 1600$ , $(53 + 1)^2 = 2916$ .
Output: [[324, 576], [1600, 2916]]. All inputs are integers, so rounding to 4 decimal places changes nothing here.
Notice that $K$ is not symmetric here because $A \neq B$ . Squaring stretches gaps: dot products 17 and 53 differ by about $3\times$ , kernel values by $9\times$ , so a higher $d$ emphasises strong similarities.

Constraints

A: 2D list (m x features), B: 2D list (n x features)
c: constant term (float), d: degree (integer)
Return 2D list (m x n) kernel matrix
Round each value to 4 decimal places

Learn this in

Linear RegressionML Study Plan Support Vector MachinesML Study Plan

More from Machine Learning 1

RBF Kernel Matrixhard Hinge Losseasy Linear Decision Boundaryeasy Gradient Boosting Residual Stephard Random Feature Subspacemedium

Concept primer

Background Knowledge

The polynomial kernel is a type of kernel function used in Support Vector Machines (SVMs) to transform the original feature space into a higher-dimensional space, allowing for more complex and non-linear relationships between the data points. The polynomial kernel is defined as $K(x, y) = (x \cdot y + c)^d$ , where $x$ and $y$ are the input vectors, $c$ is a constant term, and $d$ is the degree of the polynomial. This kernel function enables the SVM to operate in the higher-dimensional space without explicitly computing the transformation, which can be computationally expensive.

In the context of SVMs, the kernel matrix plays a crucial role in the training process. The kernel matrix is a square matrix where the entry at position $(i, j)$ represents the similarity between the $i^{th}$ and $j^{th}$ data points, computed using the kernel function. In this problem, we are tasked with computing the kernel matrix between two sets of vectors, $A$ and $B$ , where $A$ has $m$ points and $B$ has $n$ points. The resulting kernel matrix will have dimensions $m \times n$ , with each entry $(i, j)$ representing the similarity between the $i^{th}$ point in $A$ and the $j^{th}$ point in $B$ .

The dot product ( $x \cdot y$ ) is a fundamental operation in computing the polynomial kernel. It measures the similarity between two vectors by summing the products of their corresponding components. In the context of the polynomial kernel, the dot product is used to compute the similarity between the input vectors, which is then raised to the power of $d$ and added to the constant term $c$ . Understanding the dot product and its role in the polynomial kernel is essential for implementing the solution.

Algorithm/Approach

The general approach to solving this problem involves iterating over each pair of vectors from the two sets, computing the dot product, and then applying the polynomial kernel formula to obtain the kernel value. This process can be parallelized or vectorized to improve efficiency, especially for large datasets. The algorithm pattern involves nested loops to iterate over the vectors, followed by the computation of the dot product and the application of the kernel function.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize an $m \times n$ matrix to store the kernel values.
Iterate over each vector $A_i$ in set $A$ and each vector $B_j$ in set $B$ .
For each pair of vectors $(A_i, B_j)$ , compute the dot product $A_i \cdot B_j$ .
Apply the polynomial kernel formula: $K(A_i, B_j) = (A_i \cdot B_j + c)^d$ .
Store the computed kernel value in the corresponding entry $(i, j)$ of the kernel matrix.
Round the kernel values to 4 decimal places.

Common Pitfalls

When implementing the solution, watch out for the following:

Incorrect computation of the dot product, which can lead to incorrect kernel values.
Failure to handle edge cases, such as zero or negative values of $c$ or $d$ .
Inefficient iteration over the vectors, which can result in slow performance for large datasets.
Incorrect rounding of the kernel values, which can affect the accuracy of the results.

Time & Space Complexity

The time complexity of the solution is $O(m \cdot n \cdot p)$ , where $m$ is the number of vectors in set $A$ , $n$ is the number of vectors in set $B$ , and $p$ is the dimensionality of the vectors. This is because we need to iterate over each pair of vectors and compute the dot product, which involves iterating over the components of the vectors. The space complexity is $O(m \cdot n)$ , as we need to store the kernel matrix, which has dimensions $m \times n$ .

solution.py

Python 3.13

Test results