Deep learning: Backpropagation through time

Train the weights of a recurrent network by unrolling it in time.

What to build

A program that computes the gradients of a linear recurrent network's loss with respect to its two shared weights.

Requirements

  • The network is hₜ = w hₜ₋₁ + u xₜ, with h₀ = 0 and no activation; the loss is (h_T − y)² on the last state only.
  • Print h: and the hidden states, then loss L, dw D and du U, all with four decimal places.

Input

Line 1: w, u and y. Line 2: the inputs x₁ … x_T.

Output

Four lines.

Constraints

T ≤ 100.

Example

Input:

0.5 1 0
1 1

Output:

h: 1.0000 1.5000
loss 2.2500
dw 3.0000
du 4.5000

Why it works

Unrolled, the network is a deep chain that uses w and u at every step, so each weight's gradient is the sum of its contributions at every step, found by passing δ back through the chain.

Examples

Example 1 · Input
0.5 1 0
1 1
Expected output
h: 1.0000 1.5000
loss 2.2500
dw 3.0000
du 4.5000
Example 2 · Input
2 1 0
1 0 0
Expected output
h: 1.0000 2.0000 4.0000
loss 16.0000
dw 32.0000
du 32.0000

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

Hints

Hint 1

Forward: hₜ = w × hₜ₋₁ + u × xₜ with h₀ = 0; keep every h. The loss is (h_T − y)².

Hint 2

Backward: δ = 2(h_T − y); for t from T down to 1, add δ × hₜ₋₁ to dw and δ × xₜ to du, then δ ← δ × w.

Solution

Show one correct solution (try it yourself first)
w, u, y = map(float, input().split())
xs = list(map(float, input().split()))
hs = [0.0]
for x in xs:
    hs.append(w * hs[-1] + u * x)
delta = 2 * (hs[-1] - y)
dw = du = 0.0
for t in range(len(xs), 0, -1):
    dw += delta * hs[t - 1]
    du += delta * xs[t - 1]
    delta *= w
print("h: " + " ".join(f"{h + 0.0:.4f}" for h in hs[1:]))
print(f"loss {(hs[-1] - y) ** 2:.4f}")
print(f"dw {dw + 0.0:.4f}")
print(f"du {du + 0.0:.4f}")

Lesson: Recurrent networks and LSTMs →