Implement Polynomial Kernel Function

Problem

Implement a polynomial kernel function used in SVMs. Given two input vectors x1 and x2, a degree d, and an optional constant c (default 1), compute K(x1, x2) = (x1 . x2 + c)^d.

Solution

import numpy as np

def polynomial_kernel(x1: np.ndarray, x2: np.ndarray, d: int, c: float = 1.0) -> float:
    dot_product = np.dot(x1, x2)
    return (dot_product + c) ** d

Explanation

1. Compute the dot product of the two input vectors.
2. Add the constant c to the dot product.
3. Raise the result to the power d.

The polynomial kernel maps inputs into a higher-dimensional feature space without explicitly computing the transformation, enabling SVMs to find non-linear decision boundaries.

Complexity

• Time: O(n) where n is the dimensionality of the input vectors
• Space: O(1)