On S-Finite Measures and Kernels

Matthijs Vákár, C.-h. Luke OngarXiv 2018 · DOI · arXiv

Abstract: In this note, we develop some of the basic theory of s-finite (measures and) kernels, a little-studied class of kernels which Staton has recently convincingly argued is precisely the semantic counterpart of (first-order) probabilistic programs. We discuss their Carathéodory extension and extend Staton's analysis of their product measures. We give various characterisations of such kernels and discuss their relationship to the more commonly studied classes of $\sigma$-finite, subprobability and probability kernels. We use these characterisations to establish suitable Radon-Nikodým, Lebesgue decomoposition and disintegration theorems for s-finite kernels. We discuss s-finite analogues of the classical randomisation lemma for probability kernels. Throughout, we give some examples to explain the connection with (first-order) probabilistic programming. Finally, we briefly explore how some of these results extend to quasi-Borel spaces, hence how they apply to higher-order probabilistic programming.

Introduction

In probabilistic programming (PPL), programs are often viewed as kernels—functions that take an input and return a measure (a distribution) over possible outputs. While standard measure theory often focuses on $\sigma$-finite measures (like the Lebesgue measure), these fail a critical requirement for programming: compositionality. $\sigma$-finite kernels are not closed under composition; piping the output of one $\sigma$-finite program into another may result in a non-$\sigma$-finite measure.

This paper addresses this gap by developing a complete theory for s-finite kernels (countable sums of finite kernels). As argued by Sam Staton, s-finite kernels are the "correct" semantic counterpart for probabilistic programs because they are closed under composition and can represent improper priors and counting measures.

Characterizing S-Finite Kernels

The authors provide several characterizations of s-finite kernels. They prove that these kernels are exactly those that can be expressed as the pushforward of a $\sigma$-finite kernel, or as a subprobability kernel scaled by a measurable function.

Commutative diagram illustrating the relationship between a measure $\mu$ and its associated integral operator.

Central to this theory is the relationship between a measure and its integral operator, as shown in the diagram above. The integral provides the mapping from measurable functions to values in $[0, \infty]$, effectively lifting the measure to a functional. In the s-finite context, the authors introduce the concept of 0-$\infty$-sets (sets where every subset has measure either 0 or $\infty$) to handle the "badly infinite" parts of measures that do not exist in standard $\sigma$-finite theory.

Extending Fundamental Theorems

A major contribution of this work is the systematic extension of the "Big Three" theorems of measure theory to the s-finite case:

  1. Radon-Nikodým Theorem: Establishes conditions under which one s-finite kernel has a density with respect to another, providing the mathematical foundation for importance sampling.
  2. Lebesgue Decomposition: Allows for the separation of kernels into singular and absolutely continuous parts.
  3. Disintegration Theorem: Proves that s-finite kernels can be "disintegrated," which is the theoretical requirement for performing Bayesian inference (calculating a posterior from a prior and a likelihood).

Furthermore, the authors establish a Randomization Lemma, showing that any s-finite kernel can be constructed from three simple building blocks: a deterministic function, the Lebesgue measure on $[0, 1]$, and a counting measure on the integers. This justifies why PPL languages only need a few basic primitives (like sample and score) to represent complex models.

Higher-Order Semantics and Quasi-Borel Spaces

To support higher-order probabilistic programming—where functions can be passed as arguments—the authors extend their results to Quasi-Borel Spaces (QBS). They successfully extend Radon-Nikodým and Lebesgue decomposition to this setting, demonstrating that these semantic tools remain robust even in complex, higher-order environments.

Conclusion and Future Work

While this paper provides the mathematical "heavy lifting" for PPL semantics, challenges remain. Specifically, establishing a general disintegration theorem for Quasi-Borel Spaces is not yet clear and remains a significant open challenge. Additionally, as a theoretical work, the transition from these existence proofs to efficient symbolic disintegration algorithms in PPL compilers is an ongoing area of research.

Summary updated

Abstract

In this note, we develop some of the basic theory of s-finite (measures and) kernels, a little-studied class of kernels which Staton has recently convincingly argued is precisely the semantic counterpart of (first-order) probabilistic programs. We discuss their Carathéodory extension and extend Staton's analysis of their product measures. We give various characterisations of such kernels and discuss their relationship to the more commonly studied classes of $σ$-finite, subprobability and probability kernels. We use these characterisations to establish suitable Radon-Nikodým, Lebesgue decomoposition and disintegration theorems for s-finite kernels. We discuss s-finite analogues of the classical randomisation lemma for probability kernels. Throughout, we give some examples to explain the connection with (first-order) probabilistic programming. Finally, we briefly explore how some of these results extend to quasi-Borel spaces, hence how they apply to higher-order probabilistic programming.
BibTeX
@misc{vakar2018s,
  author = {Matthijs Vákár and C.-H. Luke Ong},
  title = {{On S-Finite Measures and Kernels}},
  year = {2018},
  eprint = {1810.01837},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.01837},
}

Loading related content...

Figure