Building the Street, Row by Row

A factory sorts machine parts into pass ($y = +1$) and fail ($y = -1$) from a few measurements, using a linear support vector machine. For a row $x$ the model computes a score

and predicts $+1$ when $s \ge 0$, and $-1$ otherwise. The dividing line is $s = 0$, and the street around it runs from $s = -1$ to $s = +1$.

Where a row sits. Its margin is $m = y\,s$, its score multiplied by its true label:

• $m \ge 1$: on its own side and outside the street, or exactly on the edge;
• $0 < m < 1$: on the correct side, but inside the street;
• $m \le 0$: on the line, or on the wrong side of it.

What training lowers. For one row, the cost is

The first part, the hinge loss, is zero for a row outside the street on its own side, and grows the deeper a row sits inside the street or past the line. The second part grows with the size of the weights. Small weights mean a wide street (its width is $2 / \lVert w \rVert$), so this part keeps pushing towards the widest street. The number $\lambda$ sets how hard it pushes.

One step of stochastic gradient descent, for one row. Work out the row's margin $m$ using the current $w$ and $b$. Then:

• if $m < 1$ (strictly): every weight becomes $w_j - \text{lr}\,(\lambda\, w_j - y\, x_j)$, and $b$ becomes $b + \text{lr}\; y$;
• otherwise: every weight becomes $w_j - \text{lr}\;\lambda\, w_j$, and $b$ is left alone.

Every step shrinks the weights a little. Only a row inside the street or on the wrong side also pulls the line towards classifying it correctly. The bias is never shrunk.

Task: write train_svm(X, y, lr, lam, epochs, X_new).

• X is a list of rows of numbers, and y gives each row's label, 1 or -1. lr is the learning rate and lam is $\lambda$.
• Start with every weight and the bias at 0.0. One epoch is one pass over the rows in the order given, taking one step per row, and each step uses the weights exactly as the previous step left them. Run epochs epochs; epochs may be 0.
• Then predict each row of X_new with the final weights and bias.

Return a tuple (w, b, predictions): w is the list of weights and b the bias, both rounded to 4 decimal places, and predictions is a list of 1 or -1, one per row of X_new. Predict with the unrounded values.