Linear SVM with Hinge Loss

Train a linear support vector machine by subgradient descent.

Labels are -1 and +1, not 0 and 1. The objective is the hinge loss plus an L2 penalty:

loss = (1/n) * sum_i max(0, 1 - y_i * (x_i . w + b)) + lam * ||w||^2

The hinge is not differentiable at the kink, so use a subgradient. Only the points that violate the margin, meaning y_i * (x_i . w + b) < 1, contribute:

dw = -(1/n) * sum over violators of y_i * x_i   +   2 * lam * w
db = -(1/n) * sum over violators of y_i

Start from w = zeros(d) and b = 0.0 and run exactly epochs full batch updates. Return (w, b).

The margin condition is < 1, not < 0. That is what separates an SVM from a perceptron: points that are correctly classified but sit too close to the boundary still push it away. Points comfortably beyond the margin contribute nothing at all, which is why the solution depends only on the support vectors.

The penalty applies to w only, never to b.

Function signature

def fit_svm(X, y, lr, lam, epochs):

Example

Input

X = np.array([[-2.0], [-1.0], [1.0], [2.0]])
y = np.array([-1, -1, 1, 1])
fit_svm(X, y, lr=0.1, lam=0.01, epochs=500)

Output

(array([1.03786938]), 0.0)

Reasoning

The classes sit on each side of 0 in mirror image, so b stays at 0. w grows until the inner points at -1 and 1 reach the margin, where y * x * w = 1. Subgradient steps keep pushing it each time a point dips inside the margin, so w settles a little above 1.

Constraints and notes

• Labels are -1 and +1.
• A point counts as a violator when y * (x . w + b) < 1.
• The penalty applies to w only, not to b.