Module 9: Coends and the Integration Calculus
Coends are the categorical generalization of integration and trace. This module develops the coend calculus — including the Fubini theorem for coends and the Ninja Yoneda Lemma — and identifies coends in the ML operations you already know: tensor contraction, variable marginalization, belief propagation, and the partition function. The central payoff is a precise diagnosis of when Z is tractable: it is a question about which category you integrate over, not about probability theory per se.
Learning Objectives
- Define ends and coends via the wedge and cowedge conditions.
- Compute simple coends explicitly in Set and Vect.
- State and apply the Fubini theorem for coends: iterated coends commute.
- Identify tensor contraction as a coend over an index category.
- Identify probabilistic marginalization as a coend over the marginalized variable.
- Explain why the partition function Z is a coend and characterize when it is tractable.
Materials
Key Concepts
- Wedge: A family of morphisms w_c: W → F(c, c) satisfying a naturality condition for all morphisms in C; the data of an end.
- End: ∫_c F(c, c) — the terminal wedge for a bifunctor F: C^op × C → E; the categorical analogue of an invariant or fixed-point construction.
- Coend: ∫^c F(c, c) — the initial cowedge; the categorical trace of a bifunctor; generalizes tensor contraction, marginalization, and summation over shared indices.
- Fubini Theorem for Coends: ∫^c ∫^d F(c,d) ≅ ∫^d ∫^c F(c,d); the order of coend integration is irrelevant — the categorical statement of variable elimination order-independence.
- Ninja Yoneda Lemma: F(c) ≅ ∫^{c'} C(c', c) · F(c'); any functor can be reconstructed from its hom-sets via a coend; the coend formulation of the Yoneda lemma.
- Partition Function as Coend: Z = ∫^x exp(−βE(x)) dμ(x); intractable over all of configuration space, tractable when the integration is restricted to the correct subcategory (the data manifold).
Central Concepts from Prerequisites
- Modules 2–8: categories, functors, natural transformations, Kan extensions
- Probability: marginalization, factor graphs, belief propagation
- Linear algebra: tensor products, index contraction
- Statistical mechanics: partition function (previewed here; formalized in Module 12)