Definition D1
For a function F of several variables, differentiating with respect to xᵢ while holding the remaining variables fixed is written ∂F/∂xᵢ. That is, lim (h→0) [F(…, xᵢ+h, …) − F(…, xᵢ, …)]/h.
Proof.
(1)With the remaining variables fixed, F is a function of xᵢ alone. The partial derivative is the derivative of that function.convention
(2)This limit is defined by ε-δ. It has the same meaning as the one-variable derivative; it is not a different rule.A2
∎
Definition D2
Set u₀ = x and, for k = 1, …, n, set uₖ = fₖ(uₖ₋₁, wₖ). The final value L = uₙ is called the output.
Proof.
(1)Layer k receives the previous layer's value uₖ₋₁ and its own value wₖ, and produces uₖ.convention
(2)Write aₖ = ∂uₖ/∂uₖ₋₁ and bₖ = ∂uₖ/∂wₖ. Both are obtained by looking at one layer alone.(1), D1
(3)The output L is a single number, and what is sought are the n quantities ∂L/∂w₁, …, ∂L/∂wₙ.(1), D1
∎
Definition D3
Computational cost is counted by the number of multiplications. The aₖ and bₖ are treated as already given.
Proof.
(1)Multiplying m numbers takes m − 1 multiplications.convention
∎
Lemma L1
If y = f₃(f₂(f₁(x))) with u₁ = f₁(x), u₂ = f₂(u₁), then y′ = f₃′(u₂)·f₂′(u₁)·f₁′(x)
Proof.
(1)Setting g = f₃∘f₂ gives y = g(f₁(x)).convention
(2)By the chain rule, y′ = g′(u₁)·f₁′(x)(1), A1
(3)By the chain rule again, g′(u₁) = f₃′(f₂(u₁))·f₂′(u₁) = f₃′(u₂)·f₂′(u₁)(1), A1
(4)Therefore y′ = (f₃′(u₂)·f₂′(u₁))·f₁′(x) = f₃′(u₂)·f₂′(u₁)·f₁′(x)(2), (3), A3, E
(5)Three layers use the chain rule twice. More layers only repeat the same step.(2), (3)
∎
Theorem T1
If n ≥ 2 and y = fₙ(⋯f₁(x)⋯), then y′ = fₙ′(uₙ₋₁)·fₙ₋₁′(uₙ₋₂)⋯f₁′(x).
Proof.
(1)n = 2 is the chain rule itself.A1
(2)Suppose it holds at n and call that composition F. F′(x) = fₙ′(uₙ₋₁)⋯f₁′(x)assumption
(3)The (n+1)-layer composition is fₙ₊₁∘F, so (fₙ₊₁∘F)′(x) = fₙ₊₁′(uₙ)·F′(x)(2), A1
(4)Substituting (2) into (3) and removing parentheses gives a product of n+1 factors.(2), (3), A3
(5)By induction the statement holds for all n ≥ 2.(1), (4), A6
∎
Theorem T2
Setting δₖ = ∂L/∂uₖ gives δₙ = 1, δₖ₋₁ = δₖ·aₖ, ∂L/∂wₖ = δₖ·bₖ.
Proof.
(1)Since L = uₙ, δₙ = ∂uₙ/∂uₙ = 1D2, D1
(2)A change in uₖ₋₁ changes uₖ, and a change in uₖ changes L. There is no other path between them.D2
(3)By the chain rule, ∂L/∂uₖ₋₁ = (∂L/∂uₖ)·(∂uₖ/∂uₖ₋₁) = δₖ·aₖ(2), A1, D1, D2
(4)For the same reason, ∂L/∂wₖ = (∂L/∂uₖ)·(∂uₖ/∂wₖ) = δₖ·bₖ(2), A1, D1, D2
(5)Therefore δ is determined one by one from back to front, starting at δₙ.(1), (3)
∎
Corollary C
For every k with 1 ≤ k ≤ n, δₖ = aₖ₊₁·aₖ₊₂⋯aₙ. For k = n the right side is an empty product, whose value is taken to be 1.
Proof.
(1)Set j = n − k and argue by induction on j.convention
(2)If j = 0 then k = n. By T2, δₙ = 1, and the right side is also 1, so the claim holds.T2, (1), convention
(3)Suppose the claim holds at j, that is, δₖ = aₖ₊₁⋯aₙ for k = n − j.assumption, (1)
(4)By T2, δₖ₋₁ = δₖ·aₖ = (aₖ₊₁⋯aₙ)·aₖ = aₖ·aₖ₊₁⋯aₙ, which is the claim at j+1.(3), T2, A3, A4, A5
(5)By induction, δₖ = aₖ₊₁⋯aₙ for every k with 1 ≤ k ≤ n.(2), (4), A6
(6)Determining δ one step at a time from back to front and computing each δₖ directly as a product give the same value.(5), T2
∎
Theorem T3
Obtaining all of δ₁, …, δₙ₋₁ takes n − 1 multiplications from the back, and (n−1)(n−2)/2 multiplications computing each separately.
Proof.
(1)From the back: start at δₙ = 1 and apply δₖ₋₁ = δₖaₖ for k = n down to 2. The multiplications total n − 1.T2, D3, N
(2)Separately: δₖ = aₖ₊₁⋯aₙ has n − k factors, hence takes n − k − 1 multiplications.C, D3
(3)Summing for k = 1 to n−1 gives (n−2) + (n−3) + ⋯ + 1 + 0(2), N
(4)That sum is (n−2)(n−1)/2(3), A7
(5)The difference between the two counts is (n−1)(n−2)/2 − (n−1) = (n−1)(n−4)/2(1), (4), A8, A9, A3, A4, N
(6)For n = 4 the two counts are equal at 3; for n ≥ 5, (n−1)(n−4)/2 > 0, so the backward pass takes fewer.(5), A10, A11, N
(7)For n = 100 the counts are 99 and 4851. The former is proportional to n, the latter to n².(1), (4), N
(8)The root of the difference is that the output is a single number. The value that starts from the back is the single δₙ = 1, and carrying it forward finishes every layer in one pass. Working from the front rebuilds the same product from scratch at every layer.(1), (2), T2
∎