Pegasos Kernel SVM Implementation

#21 · Machine Learning · Hard

Problem

Implement the Pegasos algorithm for kernel SVM classification. Pegasos is a stochastic sub-gradient descent method for solving the SVM optimization problem.

Solution

import numpy as np

def pegasos_kernel_svm(data: list[list[float]], labels: list[int],
                        kernel: str, T: int, lambda_param: float) -> list[float]:
    X = np.array(data, dtype=float)
    y = np.array(labels, dtype=float)
    n = len(y)

    # Kernel function
    def rbf_kernel(x1, x2, gamma=0.5):
        return np.exp(-gamma * np.sum((x1 - x2) ** 2))

    def linear_kernel(x1, x2):
        return np.dot(x1, x2)

    kern = rbf_kernel if kernel == 'rbf' else linear_kernel

    # Alpha coefficients (dual form)
    alphas = np.zeros(n)

    for t in range(1, T + 1):
        eta = 1.0 / (lambda_param * t)
        i = t % n  # Cycle through examples
        # Compute prediction
        decision = sum(alphas[j] * y[j] * kern(X[j], X[i]) for j in range(n))
        if y[i] * decision < 1:
            alphas[i] += 1

    # Compute support vector weights
    sv_indices = np.where(alphas > 0)[0]
    return alphas.tolist()

Explanation

Pegasos works in the dual space, maintaining alpha coefficients for each training example.
At each iteration t, pick a training example and compute the margin condition.
If the example is misclassified or within the margin (y_i * decision < 1), increment its alpha.
The kernel function allows non-linear decision boundaries (RBF) or linear ones.
The final alphas identify the support vectors and their weights.

Complexity

Time: O(T * n) for T iterations with n kernel evaluations each
Space: O(n) for the alpha coefficients

← #20 #22 →