Module 8: Kan Extensions

Kan extensions are the universal way to extend a functor from a small domain to a larger one while preserving as much structure as possible. This module develops both the left and right Kan extension, derives the pointwise colimit formula, and establishes the central claim of the course: that EBM generalization is approximating a left Kan extension, and the categorical version is exact, deterministic, and requires no gradient descent. The module includes a Python implementation of the discrete propagation engine, making the abstract construction directly computational.

Learning Objectives

Define left and right Kan extensions via their universal properties.
Derive the pointwise formula: (Lan_K F)(d) = colim_{(c, Kc→d)} F(c).
Interpret the left Kan extension as a propagation formula over the morphism structure of the category.
Contrast left Kan (initial, optimistic) with right Kan (terminal, conservative) as modeling choices.
Connect EBM gradient descent to the approximation of a Kan extension colimit in a continuous setting.
Implement the discrete Kan extension propagation engine in Python and apply it to an energy function.

Materials

Key Concepts

Kan Extension: Given K: C → D and F: C → E, the left (or right) Kan extension is the universal functor D → E that agrees with F on the image of K and extends optimally to the rest of D.
Left Kan Extension Lan_K F: The initial extension; computed pointwise as a colimit over the comma category (K ↓ d) for each d ∈ D; the most parsimonious consistent extension.
Right Kan Extension Ran_K F: The terminal extension; computed pointwise as a limit over (d ↓ K); the most conservative consistent extension.
Pointwise Formula: (Lan_K F)(d) = colim_{(c, f: Kc→d)} F(c); the energy at an unseen point is the extremum of known energies reachable via morphisms — a propagation, not a sample.
Energy Propagation: The Kan extension interpretation of generalization: known values at training points propagate to unseen points through the morphism structure; no optimization required.
Density Comonad: The comonad arising from Lan_K K when K is dense; encodes how much information is "lost" by not knowing the full category D.

Central Concepts from Prerequisites

Modules 2–7: categories, functors, adjunctions, limits and colimits
Machine learning: energy-based models, gradient descent, generalization
Python: dictionaries, max/min over iterables (for the lab)