Source
Fong, Spivak & Tuyéras (2017; LICS 2019), “Backprop as Functor: A compositional perspective on supervised learning”, LIT-827, read in full in NOTE-625 from arXiv v3 with its appendices.
What was actually shown
The obstruction (Section I, Remark II.2). Two learners A → B and B → C, each a parametrised function with an update rule, do not compose: the upstream learner needs a training pair in A × B, and nothing supplies the b.
Learn (Prop. II.4). A learner A → B is (P, I, U, r): a parameter set P, an implementation I : P × A → B, an update U : P × A × B → P, and a request r : P × A × B → A, the input the learner would rather have had. Composites pass the downstream request upstream as the training target. Learners, identified up to bijection of parameter sets, form a symmetric monoidal category; associativity holds only up to that identification.
The functor (Thm III.2, Thm A.1). Fix ε > 0 and a differentiable error e(x, y) with ∂e/∂x(x₀, −) invertible for every x₀. Sending a differentiable parametrised function (P, I) to (P, I, p − ε∇ₚE_I, f_a(∇ₐE_I)), with E_I the summed error and f_a the componentwise inverse of ∂e/∂x(a_i, −), is a faithful, injective-on-objects, strong symmetric monoidal functor Para → Learn. The proof is the chain rule: the upstream gradient evaluated at the downstream request equals the gradient of the composite’s error. So gradient descent on a composite is the composite of local updates exchanging requests, which is backpropagation.
Quadratic error (Ex. III.4, Remark III.5). The request is a − ∇ₐE_I, with no ε. Its likeness to a gradient step is an artifact of that error.
Networks (Props IV.2, V.1). An activation gives a functor from neural network shapes to Para. Under quadratic error every network learner is generated by scalar multiplication, bias, activation, and the split and merge maps, whose bimonoid structure depends on the error function.
What could have come out otherwise. Gradient descent on a composite could have differed from any composite of local rules. With the request defined by inverting ∂e/∂x, it does not.
What this does not say
- That composition is impossible without requests. Section I argues it; other ways to manufacture an upstream target are not ruled out (NOTE-625, C2).
- That learners learn. Learn places no convergence requirement on U; the authors say so.
- Anything about cross-entropy in general. Its derivative is not invertible at 0 and 1, and §VII-A handles it only by assuming the data and initial parameters stay away from them.
- Anything about minibatches, momentum, adaptive optimisers or stochastic updates. The setting is deterministic, single-datum gradient descent with a fixed step.
- That the backward message is a gradient step. It is a requested input.
- An instruction for practice. The theorem says how training algorithms
compose. NOTE-625 filed no THEORY on the ground that a claim about
backpropagation’s structure belongs to the anthology; the LIT carries
anthology-candidate, and the anthology does not hold the paper. What is kept here is the compositional point.
Connections
- THEORY-686, from the same authors’ book (LIT-803), is the order-level version of the theme. Here a functor from syntax to semantics exists only after the semantics is enriched with a backward channel.