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 Bwith 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
a=2 b=-3 c=10 3 e = a * b d = e + c f = d * d
a: -24.0000 b: 16.0000 c: 8.0000 e: 8.0000 d: 8.0000 f: 1.0000
x=3 1 y = x * x
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}")