Contribution
Before this paper, “backpropagation is the chain rule” was a statement about derivatives of one fixed network. The paper makes learning algorithms themselves the things that compose. It isolates the extra datum composition needs, the request function. It defines the category Learn of learners, and shows that gradient descent with backpropagation is a structure-preserving map into it from differentiable parametrised functions. So training a composite by gradient descent and composing separately trained parts by passing requests give the same algorithm.
Key insight
A learner has to answer two questions about a training pair (a, b): how should my parameter change, and what input should I have received? The second answer is the training target for whatever sits upstream. If the upstream error is measured against that requested input, and the request inverts the error’s derivative, then the upstream gradient equals the gradient of the whole composite’s error. Compositionality of training reduces to the chain rule.
Assumptions
- Learn (Section II). Objects are sets; a learner A → B is (P, I, U, r) with P a set, I : P × A → B, U : P × A × B → P, r : P × A × B → A. Learners are identified up to a bijection f : P → P′ intertwining I, U and r. No convergence or correctness property is required of U.
- Para (Definition III.1). Objects are Euclidean spaces ℝⁿ; morphisms are pairs (P, I) with P = ℝᵖ and I : P × ℝⁿ → ℝᵐ differentiable, identified up to differentiable bijection of parameter spaces.
- Main theorem. A fixed step size ε > 0; a differentiable error e : ℝ × ℝ → ℝ such that ∂e/∂x(x₀, −) : ℝ → ℝ is invertible for every x₀; total error E_I(p, a, b) = Σⱼ e(Iⱼ(p, a), bⱼ) (Appendix B allows a normalising factor α_B, to cover averaged errors).
- The setting is deterministic, single-datum (online) gradient descent; batches and stochasticity are not treated.
Key results
- Proposition II.4. Learn is a symmetric monoidal category. Composite of (P, I, U, r) : A → B and (Q, J, V, s) : B → C is (P × Q, I∗J, U∗V, r∗s) with (I∗J)(p, q, a) = J(q, I(p, a)), (U∗V)(p, q, a, c) = (U(p, a, s(q, I(p, a), c)), V(q, I(p, a), c)), (r∗s)(p, q, a, c) = r(p, a, s(q, I(p, a), c)). Identity (ℝ⁰, id, !, π₂); monoidal product is parallel in every component. Associativity holds only up to the identification of learners, since (P × Q) × N ≅ P × (Q × N) is not an equality.
- Theorem III.2. Under the main assumptions, L_{ε,e}(P, I) = (P, I, U_I, r_I) with U_I(p, a, b) = p − ε∇ₚE_I(p, a, b) and r_I(p, a, b) = f_a(∇ₐE_I(p, a, b)), f_a the componentwise inverse of ∂e/∂x(aᵢ, −), is a faithful, injective-on-objects, strong symmetric monoidal functor Para → Learn. The proof (Theorem A.1) shows ∇ₚE_I(p, a, r_J(q, I(p, a), c)) = ∇ₚE_{I∗J}(p, q, a, c) by the chain rule and the definition of f; the request case is the same computation in a; monoidality uses E_{I‖J} = E_I + E_J.
- Example III.4. Quadratic error e(x, y) = ½(x − y)²: f_{x₀}(y) = x₀ − y, U_I is ordinary gradient descent and r_I(p, a, b) = a − ∇ₐE_I(p, a, b).
- Proposition IV.2. A differentiable activation σ gives a functor I_σ : NNet → Para, sending a layer C ⊆ [m] × [n] to (w, x) ↦ σ(Σᵢ wⱼᵢxᵢ + wⱼ)ⱼ; composing gives NNet → Learn.
- Proposition V.1. Quadratic-error gradient descent gives a symmetric monoidal functor FVect → Learn, so each ℝⁿ in Learn carries a bimonoid (merge by addition with request (a₃ − a₂, a₃ − a₁); copy with request a₂ + a₃ − a₁). Remark V.2: a different error function gives a different bimonoid. Example V.3: every quadratic-error neural network learner is generated by scalar multiplication, bias, activation and these maps.
- Section VI. For a two-layer network the composite update U_A equals U_B ∗ U_C, checked on the coordinate p₁₁.
Claims
| id | claim | strength | support |
|---|---|---|---|
| C1 | Learners with request functions form a symmetric monoidal category | strong (proof) | Proposition II.4, Appendix A |
| C2 | Without a request function there is no composite update rule | moderate | informal argument, Section I and Remark II.2; no impossibility theorem |
| C3 | For invertible ∂e/∂x(x₀, −), gradient descent with backpropagation is a faithful strong symmetric monoidal functor Para → Learn | strong (proof) | Theorem III.2, Theorem A.1 |
| C4 | The request’s resemblance to a gradient step is an artifact of quadratic error | strong for the stated example | Example III.4, Remark III.5 |
| C5 | Neural-network learners under quadratic error are generated by five kinds of basic learner | moderate | Proposition V.1, Example V.3, argued by diagrams |
| C6 | Lens ↪ Learn ↪ Game | weak here | stated in Section VII-D, proofs cited to Fong–Johnson and Hedges |
Concepts
- learner: a tuple (P, I, U, r) of parameter set, implementation, update and request functions; “supervised learning algorithm”.
- request function: r(p, a, b), the input value the learner sends upstream as a training target; the backpropagated message.
- Para: differentiable parametrised functions between Euclidean spaces.
- Learn: the symmetric monoidal category of learners up to bijective reparametrisation.
- gradient descent/backpropagation functor L_{ε,e}: the functor of Theorem III.2.
- 2-morphism of learners (Definition VII.1): a map f : P → Q intertwining I, U and r; equivalence of learners is isomorphism in this bicategory.
Connections
Builds on the use of monoidal categories and string diagrams for networks (Baez, Fong and Pollard on Markov processes; Coecke and Kissinger), graphical linear algebra (Baez and Erbele; Bonchi, Sobociński and Zanasi) for the bimonoids, and the algebra of directed acyclic graphs (Fiore and Devesas Campos) for networks with interfaces. It names asymmetric lenses (Bohannon, Pierce and Vaughan) and open games (Ghani, Hedges, Winschel and Zahn) as the same bidirectional shape, with the request playing the role of put or coplay.
Bearing on the record
- Compositionality. The record holds Fong and Spivak’s book (LIT-803), which presents functorial semantics in general; this paper is a worked instance in which a functor from syntax to semantics exists only after the semantics is enriched with a backward channel. That a compositional translation needed an extra datum to exist is the paper’s structural point, and it is the one worth keeping here.
- No THEORY filed. The main theorem is a correct, self-contained
mathematical statement, but a THEORY about the structure of
backpropagation is a claim about ML systems, which is the anthology’s
side; the LIT carries
anthology-candidate. - No instruction for machine-learning practice.
Limitations
- Fixed step size, a single training datum per update, deterministic updates; minibatches, momentum and adaptive optimisers are not covered.
- Cross-entropy, the commonest classification loss, fails the invertibility hypothesis at 0 and 1; §VII-A handles it only on the region where the derivative is invertible, by assumption on the data and initial parameters.
- Learn requires nothing of a learner’s behaviour; it says how learners compose, not whether they learn. The authors say so.
- C2 (that composition is impossible without requests) is argued, not proved: other ways to manufacture an upstream target are not ruled out.
- The extension of NNet to a symmetric monoidal category (IDAG) is described and cited, not proved here.
Open questions
- A functor for losses whose ∂e/∂x is not invertible everywhere, or for stochastic and batched updates: what replaces the request when it is not determined pointwise?
- Whether lens-style well-behavedness laws on (I, r) characterise learners that converge, which the authors raise in §VII-D.