Pegasos kernel SVM

Background

The Support Vector Machine finds the maximum-margin decision boundary between two classes. Pegasos ("Primal Estimated sub-GrAdient SOlver") trains it by stochastic sub-gradient descent on the hinge-loss + L2 objective, and the kernelised version replaces dot products with a kernel $K$ so the boundary can be non-linear (e.g. an RBF kernel). The trained model is stored as one coefficient $\alpha_i$ per training point plus a bias $b$.

Problem statement

Implement pegasos_kernel_svm(data, labels, kernel, lambda_val, iterations, sigma) that trains a kernel SVM with the Pegasos update and returns $(\alpha, b)$. Initialise $\alpha = 0$, $b = 0$. For each step $t = 1 \dots T$ and each sample $i$, with rate $\eta_t = 1/(\lambda t)$, compute the decision value and update only when the point is inside the margin:

$$f(x_i) = \sum_{j} \alpha_j\, y_j\, K(x_j, x_i) + b$$ $$\text{if } y_i\, f(x_i) < 1: \quad \alpha_i \leftarrow \alpha_i + \eta_t\big(y_i - \lambda\,\alpha_i\big), \quad b \leftarrow b + \eta_t\, y_i$$

Kernels: 'linear' with $K(x,y) = x\cdot y$, and 'rbf' with $K(x,y) = e^{-\lVert x - y\rVert^2 / (2\sigma^2)}$.

Input

• data — np.ndarray of shape (n_samples, n_features).
• labels — np.ndarray of shape (n_samples,): labels in $\{-1, +1\}$.
• kernel — str: 'linear' or 'rbf'.
• lambda_val — float: regularisation strength $\lambda$.
• iterations — int: number of passes $T$.
• sigma — float: RBF bandwidth (ignored for the linear kernel).

Output

Returns a tuple (alphas, b): alphas is a list[float] of length n_samples (rounded to 4 dp) and b is a float (rounded to 4 dp).

Examples

Example 1

Input:  data = [[1,2],[2,3],[3,1],[4,1]], labels = [1,1,-1,-1]
        kernel = 'rbf', lambda_val = 0.01, iterations = 100, sigma = 1.0
Output: alphas = [100.0, 99.0, -100.0, -100.0], b = -150.0

Explanation: under the RBF kernel each pass nudges the coefficients of the samples that violate the margin ($y_i f(x_i) < 1$); after 100 passes the $\alpha$ and $b$ define a non-linear boundary separating the two classes.

Constraints

• The learning rate decays as $\eta_t = 1/(\lambda t)$ with $t$ starting at $1$.
• Update $\alpha_i$ and $b$ only when $y_i f(x_i) < 1$.
• Compute $f(x_i)$ from the current $\alpha$ and $b$ (full kernel sum over all samples).
• Round alphas and b to 4 decimals.

Notes

• This is the kernelised Pegasos: rather than a weight vector $w$, the model keeps one coefficient $\alpha_i$ per training point, so it works even in the infinite-dimensional feature space of the RBF kernel.
• The shrinkage term $-\lambda\alpha_i$ in the update is what maximises the margin instead of merely fitting the data.