Calculus on Computational Graphs: Backpropagation

Abstraction: Backpropagation as reverse-mode differentiation on computational graphs

Key points:

• Backpropagation can make gradient descent training up to 10 million times faster than naive derivative computation; invented dozens of times independently across fields
• Computational graphs represent expressions as DAGs; derivatives on edges follow the chain rule; summing over all paths gives multivariate chain rule
• Naive path-summing causes combinatorial explosion; forward- and reverse-mode differentiation factor paths and touch each edge exactly once
• Reverse-mode (backpropagation) computes derivatives of one output w.r.t. all inputs in a single pass — ideal for neural nets with millions of parameters and one loss
• Forward-mode is preferable when a function has many outputs and few inputs; both use linearization + dynamic programming
• Vanishing gradients in RNNs are naturally understood through the lens of how derivatives flow through the computation graph

Connections: Christopher Olah · Backpropagation · Computational Graphs · Automatic Differentiation · Neural Networks

Source: http://colah.github.io/posts/2015-08-Backprop/index.html