Higher order programming with probabilistic effects: A model of stochastic memo...
summary
Claims a concrete categorical model that makes stochastic memoization respect the crucial dataflow property while keeping higher-order functions by building a topos from finite graphs (Rado graph/automorphism action), interpreting internal probability measures and using a commutative, semicartesian monad to model probability. Shows de Finetti/Aldous–Hoover representation-style reductions, rules out quasi-Borel spaces for memoization, and demonstrates the construction works for Boolean higher-order programs as a restrictive proof-of-concept rather than a full solution for uncountable domains.
AI-written summary · about
chapters (10)
- 0:00Start
- 0:57Deterministic Memoization
- 1:58Stochastic Memoization
- 5:24Memoization equations
- 6:12Memoization law
- 7:32Dataflow property
- 10:41Kolmogorov extension
- 12:56Pólya's Urn and de Finetti
- 15:19Random graphs: memoization for representation theorems
- 18:28Rado topos
related talks
19mProbabilistic programming interfaces for random graphs: Markov categories, graph...
49mSemantic Foundations for Probabilistic Programming
19mIncremental Computation for Efficient Programmable Inference in Probabilistic Programs
18mCompositional imprecise probability: a solution from graded monads and Markov categories
13mTyped Abstractions for Causal Probabilistic Programming
59mA Welcome to Causal Probabilistic Programming
31mProbabilistic Programming: The What, Why and How
16mA Domain-Specific Probabilistic Programming Language for Reasoning about Reasoning(…)