Linear SVM with Hinge Loss

A linear support vector machine finds the separating line with the widest margin. Train it with (sub)gradient descent on the regularised hinge loss, for labels $y \in \{-1, +1\}$ :

\mathcal{L} = \frac{\lambda}{2}\|w\|^2 + \frac{1}{n}\sum_i \max(0,\; 1 - y_i(w \cdot x_i + b))

Subgradient: examples with margin $y_i(w \cdot x_i + b) < 1$ contribute $-y_i x_i$ (and $-y_i$ for $b$ ), averaged over $n$ ; the regulariser contributes $\lambda w$ (not to $b$ ).

Implement hinge_loss(X, y, w, b, lam), train_svm(X, y, lam=0.01, lr=0.1, epochs=500) (full-batch, starting from zeros, returning (w, b)), predict_svm(X, w, b) (±1, with 0 mapping to +1) and support_vectors(X, y, w, b, tol=1e-3): the indices with margin ≤ 1 + tol.