Support Vector Machines: Duality and Kernels

Module: Machine Learning | Difficulty: Advanced

Primal Problem

Dual Problem

Kernel Trick

| Kernel | Formula | Feature Space | |--------|---------|---------------| | Linear | | | | Polynomial | | | | RBF | | |

Support Vectors

Points where are support vectors. Decision function depends only on SVs.

import numpy as np
from cvxopt import matrix, solvers

class SVM:
    def __init__(self, C=1.0, kernel='rbf', gamma=1.0):
        self.C = C; self.kernel = kernel; self.gamma = gamma
    def _kernel_matrix(self, X1, X2):
        if self.kernel == 'rbf':
            sq = np.sum(X1**2,1).reshape(-1,1) + np.sum(X2**2,1) - 2*X1@X2.T
            return np.exp(-self.gamma * sq)
        return X1 @ X2.T
    def fit(self, X, y):
        n = len(y)
        K = self._kernel_matrix(X, X)
        P = matrix(np.outer(y,y) * K)
        q = matrix(-np.ones(n))
        G = matrix(np.vstack([-np.eye(n), np.eye(n)]))
        h = matrix(np.hstack([np.zeros(n), np.full(n, self.C)]))
        A = matrix(y.astype(float).reshape(1,-1))
        b = matrix(0.0)
        sol = solvers.qp(P, q, G, h, A, b)
        self.alpha = np.array(sol['x']).flatten()
        self.sv = self.alpha > 1e-5
        self.w = (self.alpha[self.sv] * y[self.sv]) @ X[self.sv]
        self.b = y[self.sv][0] - self.w @ X[self.sv][0]
    def predict(self, X):
        return np.sign(self._kernel_matrix(X, X[self.sv]) @ (self.alpha[self.sv]*y[self.sv]) + self.b)

Research Insight: The kernel trick implicitly maps data to infinite-dimensional spaces without computing the mapping. The RBF kernel's implicit feature space is a Hilbert space, and the representer theorem guarantees that the solution lies in the span of kernel evaluations.