Deep learning: Backpropagate by hand

Do backpropagation on a small calculation, step by step.

What to build

A program that computes the gradient of the last variable of a calculation with respect to every variable.

Requirements

  • Each line is NAME = A op B with op +, - or * and A, B earlier variables. A variable can be used several times; its gradient is the sum over its uses.
  • Print NAME: G (four decimal places) for every variable: the inputs in the order given, then the computed variables in order.

Input

Line 1: the inputs as name=value items. Line 2: k. Then k lines.

Output

One line per variable.

Constraints

k ≤ 50.

Example

Input:

a=2 b=-3 c=10
3
e = a * b
d = e + c
f = d * d

Output:

a: -24.0000
b: 16.0000
c: 8.0000
e: 8.0000
d: 8.0000
f: 1.0000

Why it works

Going backwards, each line passes its output's gradient to its operands multiplied by its local derivative, and adding these contributions applies the chain rule along every path.

Examples

Example 1 · Input
a=2 b=-3 c=10
3
e = a * b
d = e + c
f = d * d
Expected output
a: -24.0000
b: 16.0000
c: 8.0000
e: 8.0000
d: 8.0000
f: 1.0000
Example 2 · Input
x=3
1
y = x * x
Expected output
x: 6.0000
y: 1.0000

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

Hints

Hint 1

Run the lines forward to get every value, then set the gradient of the last variable to 1 and go through the lines in reverse.

Hint 2

For `z = a * b`, add grad(z) × b to grad(a) and grad(z) × a to grad(b); for + and −, pass grad(z) on (negated for the second operand of −).

Solution

Show one correct solution (try it yourself first)
inputs = [item.split("=") for item in input().split()]
values = {name: float(v) for name, v in inputs}
order = [name for name, _ in inputs]
steps = []
for _ in range(int(input())):
    name, _, a, op, b = input().split()
    values[name] = {"+": values[a] + values[b], "-": values[a] - values[b], "*": values[a] * values[b]}[op]
    steps.append((name, a, op, b))
    order.append(name)
grad = {name: 0.0 for name in order}
grad[order[-1]] = 1.0
for name, a, op, b in reversed(steps):
    g = grad[name]
    if op == "+":
        grad[a] += g
        grad[b] += g
    elif op == "-":
        grad[a] += g
        grad[b] -= g
    else:
        grad[a] += g * values[b]
        grad[b] += g * values[a]
for name in order:
    print(f"{name}: {grad[name]:.4f}")

Lesson: Backpropagation →