Deep learning: One step of softmax regression

Do one full training step of a multi-class classifier.

What to build

A program that performs one gradient-descent step of softmax regression from zero weights on a batch of examples.

Requirements

  • The model computes logits z = W x + b for K classes; W (K × d) and b start at zero. The loss is the mean cross-entropy over the N examples. Update every parameter by −rate × its gradient.
  • Print loss L (before the update), then W: with each class's row separated by |, then b:, all with four decimal places.

Input

Line 1: K, d, N and the learning rate. Then N lines: d features and the class.

Output

Three lines.

Constraints

K, d ≤ 10; N ≤ 100.

Example

Input:

2 1 2 1
1 0
-1 1

Output:

loss 0.6931
W: 0.5000 | -0.5000
b: 0.0000 0.0000

Why it works

The gradient p − one-hot, multiplied by each example's features and averaged, raises the weights that point towards each example's true class and lowers the others.

Examples

Example 1 · Input
2 1 2 1
1 0
-1 1
Expected output
loss 0.6931
W: 0.5000 | -0.5000
b: 0.0000 0.0000
Example 2 · Input
3 2 1 0.3
1 2 2
Expected output
loss 1.0986
W: -0.1000 -0.2000 | -0.1000 -0.2000 | 0.2000 0.4000
b: -0.1000 -0.1000 0.2000

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

With W and b all zero, every class has probability 1/K for every example, and the loss is log K.

Hint 2

dW[k][j] = (1/N) Σᵢ (pᵢₖ − yᵢₖ) xᵢⱼ and db[k] = (1/N) Σᵢ (pᵢₖ − yᵢₖ), where yᵢₖ is 1 for the true class.

Solution

Show one correct solution (try it yourself first)
import math

K, d, N, rate = input().split()
K, d, N, rate = int(K), int(d), int(N), float(rate)
data = []
for _ in range(N):
    *x, label = input().split()
    data.append(([float(v) for v in x], int(label)))
W = [[0.0] * d for _ in range(K)]
b = [0.0] * K
dW = [[0.0] * d for _ in range(K)]
db = [0.0] * K
loss = 0.0
for x, label in data:
    z = [sum(w * xi for w, xi in zip(W[k], x)) + b[k] for k in range(K)]
    top = max(z)
    e = [math.exp(v - top) for v in z]
    p = [v / sum(e) for v in e]
    loss -= math.log(p[label]) / N
    for k in range(K):
        g = (p[k] - (1 if k == label else 0)) / N
        db[k] += g
        for j in range(d):
            dW[k][j] += g * x[j]
W = [[w - rate * g for w, g in zip(row, grow)] for row, grow in zip(W, dW)]
b = [v - rate * g for v, g in zip(b, db)]


def fmt(values):
    return " ".join(f"{v + 0.0:.4f}" for v in values)


print(f"loss {loss:.4f}")
print("W: " + " | ".join(fmt(row) for row in W))
print("b: " + fmt(b))

Lesson: Softmax and multi-class classification →