One Score per Class

Logistic regression turns one weighted score into one probability, which is enough for a yes-or-no answer. To choose among $k$ classes, give every class its own weights and its own score, and let the scores compete. This model is softmax regression, also called multinomial logistic regression.

For a row $x = (x_1, \dots, x_d)$ , each class $c = 0, 1, \dots, k-1$ gets a score and then a probability:

z_c = b_c + \sum_{j=1}^{d} W_{c,j}\, x_j \qquad\qquad p_c = \frac{e^{z_c}}{e^{z_0} + e^{z_1} + \dots + e^{z_{k-1}}}

The $p_c$ are positive and add up to 1. Training lowers the cross-entropy cost: the average over all $n$ rows of $-\ln p_{y}$ , where $y$ is the row's true class. Its gradient has a tidy form. For one row, the error of class $c$ is

e_c = p_c - \begin{cases} 1 & \text{if } c = y \\ 0 & \text{otherwise} \end{cases}

The gradient for $W_{c,j}$ is the average of $e_c\, x_j$ over all rows, and the gradient for $b_c$ is the average of $e_c$ .

Task: write train_softmax(X, y, k, lr, steps). Start with every weight and bias at 0, then run steps updates of batch gradient descent, each one moving every weight and bias by lr times its gradient, downhill:

W_{c,j} \leftarrow W_{c,j} - \text{lr} \times \big(\text{gradient for } W_{c,j}\big) \qquad\qquad b_c \leftarrow b_c - \text{lr} \times \big(\text{gradient for } b_c\big)

X is a list of $n$ rows of $d$ numbers. y holds each row's class, an integer from 0 to k - 1. A class may have no rows at all.
Every update uses all the rows, and every gradient in one update is computed from the weights as they were at the start of that update.
Return a tuple (W, b): W is a list of k lists of d weights and b is a list of k biases, all rounded to 4 decimal places.
One test has features in the hundreds, which pushes some scores into the tens of thousands. $e^{z}$ overflows long before that, so compute the probabilities in a way that never raises $e$ to a large positive power.

One Score per Class

Examples

Hints