Building Kernel Functions

The Problem: Non-Linear Data

Imagine your data looks like this:

How can we solve this? The core idea behind kernel methods is to project the data into a higher-dimensional space where it does become linearly separable.

For a fantastic and intuitive explanation of this core concept, I recommend watching this segment from StatQuest.

The Kernel Trick: A Clever Shortcut

Explicitly transforming your data into a higher dimension can be computationally very expensive, especially if the new dimension is very large (or even infinite!). This is where the kernel trick comes in.

A kernel is a function that takes two data points, ${\mathbf{x}}_i$ and ${\mathbf{x}}_j$, and returns a value that is equivalent to the dot product of these points in a higher-dimensional space, without ever actually creating the higher-dimensional vectors.

In other words, if $\Phi (\mathbf{x})$ is the function that maps $\mathbf{x}$ to a higher dimension, a kernel $K$ satisfies:
$K({\mathbf{x}}_i,{\mathbf{x}}_j)=\Phi ({\mathbf{x}}_i)\cdot \Phi ({\mathbf{x}}_j)$

Our SVM optimization and prediction only ever use dot products between data points. By replacing these dot products with a kernel function, we can make our SVM operate in a high-dimensional space for "free". This is the essence of the kernel trick.

Let's look at the two most common kernels you'll be implementing.

1. The Polynomial Kernel

The polynomial kernel is a great way to capture interactions between features. For example, it can learn decision boundaries that are quadratic, cubic, and so on.

The formula for the polynomial kernel is:
$K({\mathbf{x}}_i,{\mathbf{x}}_j)=({\mathbf{x}}_i^T{\mathbf{x}}_j+c{)}^d$

Here:

• ${\mathbf{x}}_i^T{\mathbf{x}}_j$ is the dot product of the input vectors.
• d is the degree of the polynomial, a hyperparameter that controls the complexity of the decision boundary.
• c is a coefficient hyperparameter (often called coef0 in libraries like Scikit-learn).

This article provides a simple, from-scratch implementation of this function that we can adapt.

Your Implementation

Now, let's write a Python function for the polynomial kernel. Your function should take two NumPy arrays, X1 and X2, and compute the kernel matrix. Given your background in Python and NumPy, you can implement this efficiently using vectorized operations. The dot product between two matrices X1 (shape m x k) and X2 (shape n x k) can be computed as X1 @ X2.T, resulting in the m x n matrix of all pairwise dot products.

import numpy as np

def polynomial_kernel(X1, X2, degree=3, coef=1):
    """
    Computes the polynomial kernel between two sets of vectors.
    
    Args:
        X1 (np.ndarray): A matrix of shape (m, k) where m is the number of samples.
        X2 (np.ndarray): A matrix of shape (n, k) where n is the number of samples.
        degree (int): The degree of the polynomial.
        coef (float): The coefficient term.
        
    Returns:
        np.ndarray: The kernel matrix of shape (m, n).
    """
    # The @ operator in NumPy performs matrix multiplication.
    # X1 @ X2.T computes the dot product for all pairs of vectors in X1 and X2.
    return (X1 @ X2.T + coef) ** degree

# --- Example Usage ---
# Let's create two small matrices
A = np.array([[1, 2], [3, 4]])
B = np.array([[5, 6], [7, 8], [9, 10]])

# Compute the polynomial kernel matrix
# The result should be a 2x3 matrix
kernel_matrix = polynomial_kernel(A, B, degree=2, coef=1)
print("Polynomial Kernel Matrix:\n", kernel_matrix)

2. The RBF (Radial Basis Function) Kernel

The RBF kernel is the most popular choice for SVMs. It is a general-purpose kernel that can learn very complex regions. It works by considering the Euclidean distance between points; its value is high for points that are close together and low for points that are far apart.

The formula for the RBF kernel is:
$K({\mathbf{x}}_i,{\mathbf{x}}_j)=\exp (-\gamma ||{\mathbf{x}}_i-{\mathbf{x}}_j|{|}^2)$

Here:

• $||{\mathbf{x}}_i-{\mathbf{x}}_j|{|}^2$ is the squared Euclidean distance between the two vectors.
• $\gamma$ (gamma) is a hyperparameter that defines how much influence a single training example has. A small $\gamma$ means a larger similarity radius, leading to a smoother decision boundary. A large $\gamma$ means the influence is local, which can lead to a more complex, "wiggly" boundary.

To implement this efficiently, we can use scipy.spatial.distance.cdist, which is designed to compute distances between all pairs of vectors in two collections.

The following resource shows this exact implementation within an SVM class structure.

Your Implementation

Let's write the RBF kernel function. Make sure you have SciPy installed (pip install scipy).

from scipy.spatial.distance import cdist

def rbf_kernel(X1, X2, gamma=0.1):
    """
    Computes the RBF kernel between two sets of vectors.
    
    Args:
        X1 (np.ndarray): A matrix of shape (m, k).
        X2 (np.ndarray): A matrix of shape (n, k).
        gamma (float): The kernel coefficient.
        
    Returns:
        np.ndarray: The kernel matrix of shape (m, n).
    """
    # cdist computes the pairwise squared Euclidean distance between vectors in X1 and X2
    sq_dist = cdist(X1, X2, 'sqeuclidean')
    return np.exp(-gamma * sq_dist)

# --- Example Usage ---
# Using the same matrices A and B from before
# The result should be a 2x3 matrix
rbf_kernel_matrix = rbf_kernel(A, B, gamma=0.1)
print("\nRBF Kernel Matrix:\n", rbf_kernel_matrix)

Visualizing the Power of Kernels

So what do these functions enable in practice? By swapping the simple dot product in an SVM with one of these kernel functions, we can produce radically different decision boundaries capable of fitting complex data.

Conclusion

In this lesson, you've taken a critical step towards building a powerful, general-purpose SVM. You moved beyond the limitations of linear models by understanding and implementing kernel functions.

Key Takeaways:

• The Problem: Linear classifiers fail when data is not linearly separable.
• The Idea: Project data into a higher dimension where it becomes linearly separable.
• The Kernel Trick: A computationally efficient method to achieve this by replacing dot products with a kernel function, which calculates the dot product in the higher-dimensional space without explicit transformation.
• Implementation: You wrote Python functions from scratch for the polynomial kernel and the RBF kernel, the two most widely used kernels for SVMs.

Preview of the Next Lesson:

You now have the building blocks: a linear SVM implementation and standalone kernel functions. In the next lesson, we will put them together. You will modify the SVM you built previously to accept a kernel function, allowing it to solve non-linear classification problems. This will involve updating your fit and predict methods to use the kernel matrix instead of a simple dot product.