Categorithm

Bayesian Learner

A Bayesian learner is a learner, a forward map paired with a backward update, whose backward leg is Bayesian inversion. The general construction realises this by taking a lens category as a grothendieck-construction whose fibrewise backward semantics is inversion, then parametrising it via the Para construction. The familiar functor is the trivial-lens special case, and sequential Bayesian learning is its iterated, online section.

The Grothendieck-lens version

Let be a markov-category and let be its category of states up to almost-sure equivalence. Its objects are states , and its morphisms are channels identified when they agree almost everywhere. This is itself an -actegory, acted on by the deterministic part.

Definition, the inversion fibration

Over take an indexing and set

the grothendieck-construction of , whose backward semantics is Bayesian inversion. The restriction functors transport a state to its posterior rather than to a formal dual. All the probabilistic content, namely that the backward map is a posterior and not an inverse function, is localised in . The surrounding Grothendieck and Para layers are the same as in the deterministic case.

Construction, the Bayesian learner

A section embeds each channel as a lens carrying its own inversion as the backward leg. Applying Para gives

the Bayesian-learning mechanism, a parametrised stochastic map whose parameters are updated along the inversion supplied fibrewise by . This is the stochastic counterpart of the classical .

BayesLearn, the trivial-lens special case

Collapse to a constant fibre and the Grothendieck lens becomes the trivial lens category over the state category of a chosen Markov category. It has a forward slot and a backward slot with no fibrewise transport left to track. Here the section is explicit.

Construction, the diagonal-with-dagger section

Define

with the Bayesian inversion of . Because the backward slot is contravariant, respects composition exactly when and for the forward projection , so is a genuine section. Then sends a parametrised channel to the parametric lens , whose get is the forward channel and whose put is its posterior. A composite learner’s backward pass is , so inference propagates back through the pipeline in reverse.

Remark, the content is the dagger, not the diagonal

The diagonal is formal bookkeeping; the substance is the dagger section , so everything the construction claims rests on inversion being functorial and order-reversing, and holding only up to almost-sure equality. That “Bayesian inversion is a dagger up to a.s.” is stated and worked out in category-of-influences, its canonical home; here it is simply assumed. Where fails to exist or to compose, is only partially defined, and whether is a genuine pseudofunctor, so that inversions compose coherently across the base, is the load-bearing check.

Sequential update as the online section

Online learning is the same channel run again and again, each posterior handed forward as the next prior. Work in with objects pairs . A parametric model at step is a channel , from which the joint is formed, pairing input and prediction.

Definition, the posterior recurrence

Given the datum as a Dirac state , the Bayesian inversion of the joint updates the parameter belief,

and threading the output posterior in as the next prior gives the chain , which is sequential Bayesian learning as the iterated -section of .

Remark, the batch alternative

Instead of threading, collect the data through a collection monad and update once against . Batch and sequential agree only when the update is exchangeable in the data order.

Property, why the thread is delicate

Normalization is not a functor. Dividing by the evidence does not respect composition, so one works with the unnormalized likelihood and normalizes only at read-out. Copy is incompatible with the dagger. The comonoid is not preserved by Bayesian inversion, so a datum may not be freely duplicated across updates. Both are the Markov-categorical shadow of familiar pitfalls in probabilistic programming; the inversion itself is studied in category of statistics.

References

  • T. Fritz, A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics (Advances in Mathematics, 2020)
  • B. Fong, D. Spivak, R. Tuyeras, Backprop as Functor (2019)
  • G. Cruttwell, B. Gavranovic, N. Ghani, P. Wilson, F. Zanasi, Categorical Foundations of Gradient-Based Learning (2021)