Problem 415660 · hard · Level 04 Non-Linear Data Structures

Three Species, One Model

softmax regression · multiclass classification · cross-entropy · gradient descent · numerical stability

A seed bank sorts seeds of k plant species from a few measurements. Logistic regression handles two classes; here each class c gets its own weight vector W[c] and bias b[c], its score is z_c = W[c]·x + b[c], and the model's probabilities are

p_c = e^(z_c) / (e^(z_0) + e^(z_1) + ... + e^(z_(k-1)))

The loss is the average over the training examples of -log p_y, the negative log of the probability the model gives to the true class y.

Write softmax_regression(X, y, k, lr, steps, queries):

  1. Start with every entry of W (a list of k lists of d weights) and of b (a list of k biases) equal to 0.0.
  2. Run steps steps of batch gradient descent on the loss with learning rate lr: compute the partial derivatives with respect to every W[c][j] and b[c] on all examples at the current parameters, then update everything.
  3. Return (W, b, loss, predictions): the final parameters, the loss at them, and for every row of queries the class with the highest probability (the smallest class number if several are equally high).

The helper seed_sizes(n, seed) returns (X, y) for n seeds of 3 species.

Examples

Input:  X = [[0, 0], [1, 0], [0, 1]], y = [0, 1, 2], k = 3, lr = 1.0, steps = 1, queries = [[1, 0]]
Output: ([[-0.1111111111111111, -0.1111111111111111], [0.22222222222222224, -0.1111111111111111],
          [-0.1111111111111111, 0.22222222222222224]], [0.0, 0.0, 0.0], 0.9589712973654582, [1])
Explanation: at the start every probability is 1/3. The example of class 1 at [1, 0] raises W[1][0]
and lowers W[0][0] and W[2][0]. The biases stay (almost exactly) 0 because each class has one example.

Input:  X = [[1, 2]], y = [1], k = 3, lr = 0.5, steps = 0, queries = [[1, 2]]
Output: ([[0.0, 0.0], [0.0, 0.0], [0.0, 0.0]], [0.0, 0.0, 0.0], 1.0986122886681098, [0])
Explanation: untrained, all three classes are equally likely (loss log 3), and the tie goes to class 0.

Constraints

  • 1 <= n <= 300, 1 <= d <= 4, 2 <= k <= 5, labels in 0 .. k-1 (a class may have no examples)
  • 0 <= steps <= 300, 0 < lr <= 2; scores can reach a few hundred, so compute the probabilities without overflow
  • floats are compared with a tolerance of 1e-6; the queries avoid exact ties except when all weights are 0

Goals

  • Extend logistic regression from two classes to k classes with the softmax
  • Derive the gradient of the multiclass log loss for every weight of every class
  • Train by batch gradient descent and predict with a stated tie-break
Starting Python…