definition theorem example

Karwowski, Nielsen & Staton give probabilistic programs a compositional information geometry. A program pulls a metric on its output type back to a metric on its input type, and this assignment is a contravariant lax monoidal functor :

  • , the score part. The Fisher metric of the program’s random choices: how much moving changes the probabilities of its traces.
  • , the velocity part. The metric on , pulled back along the program’s output map and averaged over traces: how much moving changes the values it returns.

For a standard statistical model (finite outputs, so no velocity) is the Fisher metric. For a deterministic program is the ordinary pullback of Riemannian geometry (Theorem 2(7)–(8)). With the Euclidean metric scaled by on the output, is the score-velocity metric (Definition 20).

Sources: Karwowski, Nielsen & Staton arXiv:2610.17886 (notes) §1 (Figure 1), §3 (language ), Definitions 2, 8, 10, 15–20, 33, 56, Remarks 4, 13, Propositions 5, 8, 9, Theorems 1–4, 9, 10, Corollary 2, Example 1, §9.

The construction

  • Programs as traces. The language (§3) is first-order, with real, product and sum types and one source of randomness, a coin flip(x) with log-odds . A program denotes a trace presentation (Definition 2): a space of traces (the random choices made), a density smooth in , and an output map smooth in . Its jet adds the score and the velocity (Definition 10).
  • The category. Finite trace presentations form a Copy-Discard Category (Definition 8, Proposition 5). The semantics of is a strong monoidal functor into its jet version (Theorem 1), and forgetting the traces gives the usual kernel semantics in (Proposition 6). is not a Markov Category (Remark 4): a program can make random choices and discard them, so there are many maps .
  • Two halves of the metric. The Fisher metric of the score (Definition 15) and the expected tangent pullback of the velocity (Definition 16). They are glued by the chain rule which is what makes a functor: .
  • The functor. Its target is : cones of positive semidefinite metrics and positive affine maps (Definitions 17–18). The affine part is the score, the linear part the velocity.

Theorem 2. is a functor, invariant under trace isomorphisms, with , copying adding metrics, discarding giving , the Fisher metric recovered as , the ordinary pullback for deterministic maps, and lax symmetric monoidal.

The geometry is the one of Figure 1. The program gets the metric . Its two specialisations, (a biased coin, pure Fisher geometry) and (a fair coin choosing between and , pure velocity), embed into it as submanifolds that meet transversally. In general the space of programs with a fixed trace space is isometric to a radius-2 hypersurface in a product of cones (Theorem 3), which is why the geometry is locally spherical.

The price: geometry depends on how the program is written

Corollary 2 and Example 1. The score-velocity metric is invariant under trace isomorphisms, but it is not extensional: two presentations of the same kernel can have different metrics. A constant output , written with no randomness, has . Written as “flip a coin with log-odds , ignore it, return ”, it has .

The paper proves that the compositional desiderata (Fisher for models, pullback for deterministic maps, functoriality) force this intensionality (§1). Unused randomness is the same reason fails to be Markov. The extensional geometry of the output distribution is related by a three-level inequality (Theorem 10, from the trace data-processing inequality, Theorem 9):

  • is the Wasserstein–Fisher–Rao metric of the realised measures: it uses only the output distribution.
  • is the score-velocity metric conditioned on the output.
  • is the full metric of the presentation.

On regular finite atomic families the first inequality is an equality (Corollary 8). Information hidden in discarded randomness can only make the presentation metric larger.

Extensions and open ends

  • Weighted programs with observe and score (§6). Normalisation is not a functor (Remark 13).
  • Continuous random variables (§7) use diffeological quasi-Borel spaces (Definition 33; Quasi-Borel Space, Diffeological Space). That category is complete, cocomplete and cartesian closed (Theorem 4), but a probability monad on it is still open (Remark 16).
  • Natural gradient for programs (§8.5): the metric of a program on observations is a sum over copies (Theorem 12), and the natural gradient for a degenerate metric is defined modulo its kernel, in coordinates (Definition 56).
  • Future work (§9): loops, higher-order functions and recursion; a Solomonoff–Jeffreys prior over programs; trans-dimensional Riemannian-manifold Hamiltonian Monte Carlo.

Relation to statistical games and to Lenticulum

  • Two chain rules of the same shape. for the metric and for the free energy of a Statistical Game (Theorem 23). In both, a local term is added to a downstream term transported back along the first stage. Both constructions are lax: here monoidally (Theorem 2(9)), there in the gradient assignment (AutoBayes Remark 30). Whether one is an instance of the other is not settled here.
  • Score and velocity in Lenticulum. For a Lenticulum.jl factor with Gaussian noise, the Fisher metric in the parameters is , the velocity part with (Fisher Information Metric). A factor that also samples discrete choices would add a score part. The vector energy of Scalar and Multivariate Energy §6 keeps the Jacobian for exactly this purpose. That §8 lists its scalarisation choices as forks of the theory matches the intensionality found here: geometry depends on presentation.

Docs: Julia manual: comprehensions — a program is its list of traces (q(x, ω), o(x, ω)).

# Finite trace presentations ℝ → ℝ: x ↦ [(q(x, ω), o(x, ω)) for each trace ω] (Definition 2)
σ(t) = 1 / (1 + exp(-t))
dx(f, x; ε = 1e-5) = (f(x + ε) - f(x - ε)) / 2ε
# 𝒜_F(h)(x) = g^F(x) + F♯h(x) = E_ω[ S(x, ω)² + h(o(x, ω)) V(x, ω)² ]   (Definitions 15, 16, 19)
function A(F, h, x)
    sum(1:length(F(x))) do ω
        q(t) = F(t)[ω][1]; o(t) = F(t)[ω][2]
        q(x) * (dx(t -> log(q(t)), x)^2 + h(o(x)) * dx(o, x)^2)
    end
end
compose(G, F) = x -> [(qF * qG, oG) for (qF, oF) in F(x) for (qG, oG) in G(oF)]  # let y ← F in G
 
κ = 1.0; euclid(y) = κ
F(x) = [(σ(x), x + 1.0), (1 - σ(x), x)]               # b ← flip(x); return x + b
G(y) = [(σ(y), 2y), (1 - σ(y), y)]                    # c ← flip(y); return c ? 2y : y
# Theorem 2(3): 𝒜 is a contravariant functor, 𝒜_{G∘F} = 𝒜_F ∘ 𝒜_G
x = 0.4
isapprox(A(compose(G, F), euclid, x), A(F, y -> A(G, euclid, y), x); rtol = 1e-6)   # true
 
# Theorem 2(7)-(8): Fisher metric for a model, ordinary pullback for a deterministic map
coin(x) = [(σ(x), 1.0), (1 - σ(x), 0.0)]               # outputs constant: velocity 0
isapprox(A(coin, euclid, x), σ(x) * (1 - σ(x)); rtol = 1e-6)                       # true
square(x) = [(1.0, x^2)]                               # deterministic
isapprox(A(square, euclid, x), κ * (2x)^2; rtol = 1e-6)                            # true
 
# Example 1: the same constant kernel, two presentations, two metrics
plain(x) = [(1.0, 0.0)]
wasteful(x) = [(σ(x), 0.0), (1 - σ(x), 0.0)]          # flip a coin and ignore it
(A(plain, euclid, 0.0), A(wasteful, euclid, 0.0))      # (0.0, 0.25): not extensional
import Mathlib
 
/-- A finite trace presentation `ℝ → ℝ` with `n` traces (Definition 2, one-dimensional). -/
structure FinTrace (n : ℕ) where
  q : ℝ → Fin n → ℝ          -- trace density
  o : ℝ → Fin n → ℝ          -- output map
 
namespace FinTrace
 
/-- Definition 15: the Fisher metric of the score. -/
noncomputable def fisher {n : ℕ} (F : FinTrace n) (x : ℝ) : ℝ :=
  ∑ ω, F.q x ω * (deriv (fun t => Real.log (F.q t ω)) x) ^ 2
 
/-- Definition 16: the expected tangent pullback of a metric `h` on the output. -/
noncomputable def pullback {n : ℕ} (F : FinTrace n) (h : ℝ → ℝ) (x : ℝ) : ℝ :=
  ∑ ω, F.q x ω * h (F.o x ω) * (deriv (fun t => F.o t ω) x) ^ 2
 
/-- Definition 19: `𝒜_F(h) = g^F + F♯ h`. -/
noncomputable def A {n : ℕ} (F : FinTrace n) (h : ℝ → ℝ) (x : ℝ) : ℝ :=
  F.fisher x + F.pullback h x
 
/-- A deterministic program (one trace of mass 1). -/
def det (f : ℝ → ℝ) : FinTrace 1 := ⟨fun _ _ => 1, fun x _ => f x⟩
 
/-- Theorem 2(8): on a deterministic program, `𝒜` is the ordinary pullback `f^* h`. -/
theorem A_det (f : ℝ → ℝ) (h : ℝ → ℝ) (x : ℝ) :
    (det f).A h x = h (f x) * (deriv f x) ^ 2 := by
  simp [A, fisher, pullback, det]
 
end FinTrace
-- The functor 𝒜 on finite trace presentations ℝ → ℝ, checked numerically
type Prog = Double -> [(Double, Double)]               -- x ↦ [(q(x, ω), o(x, ω))]
 
sigma :: Double -> Double
sigma t = 1 / (1 + exp (negate t))
 
dx :: (Double -> Double) -> Double -> Double
dx f x = (f (x + e) - f (x - e)) / (2 * e) where e = 1e-5
 
bigA :: Prog -> (Double -> Double) -> Double -> Double  -- g^F + F♯ h
bigA f h x = sum [ q x * (dx (log . q) x ^ 2 + h (o x) * dx o x ^ 2)
                 | w <- [0 .. length (f x) - 1]
                 , let q t = fst (f t !! w)
                 , let o t = snd (f t !! w) ]
 
compose :: Prog -> Prog -> Prog                         -- let y ← f in g
compose g f x = [ (qf * qg, og) | (qf, of') <- f x, (qg, og) <- g of' ]
 
progF, progG :: Prog
progF x = [(sigma x, x + 1), (1 - sigma x, x)]
progG y = [(sigma y, 2 * y), (1 - sigma y, y)]
 
main :: IO ()
main = do
  let euclid = const 1
  print (bigA (compose progG progF) euclid 0.4, bigA progF (bigA progG euclid) 0.4)  -- equal
  print (bigA (\_ -> [(1, 0)]) euclid 0, bigA (\x -> [(sigma x, 0), (1 - sigma x, 0)]) euclid 0)