Weighted Automata for Exact Inference in Discrete Probabilistic Programs
Dominik Geißler, Tobias Winkler · 2025
Read Weighted Automata for Exact Inference in Discrete Probabilistic Programs by Dominik Geißler, Tobias Winkler (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-15074.txt.
Introduction
Dominik Geißler and Tobias Winkler work out exact answers for programs with chance in them, in a 2025 paper. Such programs mix code with random draws and checks on what was seen. Inference asks for the odds of each outcome given those checks. Exact answers are the hard, prized case.
Their code turns a distribution over tuples of whole numbers into a weighted automaton, a machine that reads symbols and adds up weights. Each kind of program step becomes a build step on such machines. For a broad class of programs the shift from prior to final odds is fully mechanical. A proof ties the machine's answer to the standard meaning of the program, so the result is exact, not a guess.
Catalog record
| CREATOR | Dominik Geißler, Tobias Winkler |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 109 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-15074
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Weighted Automata for Exact Inference in Discrete Probabilistic Programs Dominik Geißler, Tobias Winkler Abstract In probabilistic programming, the inference problem asks to determine a program’s posterior distribution conditioned on its “observe” instructions. Inference is challenging, especially when exact rather than approximate results are required. Inspired by recent work on probability generating functions (PGFs), we propose encoding distributions on ℕ k \mathbb{N}^{k} as weighted automata over a commutative alphabet with k k symbols. Based on this, we map the semantics of various imperative programming statements to automata-theoretic constructions. For a rich class of programs, this results in an effective translation from prior to posterior distribution, both encoded as automata. We prove that our approach is sound with respect to a standard operational program semantics. 1 Introduction Probabilistic programming languages extend traditional programming languages by capabilities for sampling numbers from pre-defined distributions, and conditioning the current program state on observations [ 11 ] . Probabilistic programs have numerous applications, including machine learning [ 25 ] , cognitive science [ 10 ] , and autonomous systems [ 21 ] . Semantically, probabilistic programs can be seen as transformers of probability distributions : From an initial distribution over inputs, also called prior , to a final distribution over outputs, also called posterior [ 17 , 11 ] . Inference means characterizing the posterior resulting from a given prior. In this paper, we study the imperative language ReDiP [ 5 , 15 ] , short for rectangular discrete probabilistic programming language . This language imposes some syntactical restrictions (see Section 3 for details), while preserving decidability of many (inference) tasks: For instance, for loop-free programs, the moments of the posterior distributions can be computed exactly, and program equivalence is decidable [ 5 ] . We only consider the loop-free fragment of ReDiP in this paper; adding general while loops renders the language Turing-complete. A key challenge related to ReDiP is its support for some infinite-support distributions. Implementing the distribution transformer semantics directly thus requires manipulating such distributions in an effective manner. In [ 14 , 5 , 15 ] , symbolic closed-form expressions of probability generating functions (PGFs) were employed for this purpose. In this paper, we propose an automata-theoretic alternative to the PGF approach. Our main idea is to encode distributions over the \mathbb{N} -valued variables of a ReDiP program by means of weighted automata over a commutative alphabet. This automaton model, which we call probability generating automata (PGA), is a restricted form of a weighted multi-counter system: Intuitively, each time a PGA takes an X -transition, the program variable represented by X is incremented. The probability that X=n in the distribution described by a PGA is thus the sum of the weights of all paths containing exactly n many X -transitions; this extends naturally to joint distributions. // all variables initially 0 \displaystyle\{R\,\texttt{:=}~0\}~\texttt{[}\nicefrac{{9}}{{10}}\texttt{]}~\{R\,\texttt{:=}~1\}\,\fatsemi \displaystyle\mathtt{if}~(R=0)~\{ \displaystyle\qquad X\,\texttt{+=}~\texttt{NegBin}\texttt{(}1\texttt{,}\nicefrac{{1}}{{2}}\texttt{)} \displaystyle\}~\texttt{else}~\{ \displaystyle\qquad X\,\texttt{+=}~\texttt{NegBin}\texttt{(}2\texttt{,}\nicefrac{{1}}{{2}}\texttt{)} \displaystyle\}\,\fatsemi \displaystyle\texttt{observe}~\texttt{(}X\geq 2\texttt{)} \frac{40}{11} \tfrac{1}{2} \tfrac{1}{2} \tfrac{9}{10} \tfrac{1}{2}X \tfrac{1}{2}X \tfrac{1}{10}R \tfrac{1}{2}X \tfrac{1}{2}X \tfrac{1}{2} \tfrac{1}{2} \tfrac{1}{2} \tfrac{1}{2}X \tfrac{1}{2}X \tfrac{1}{2}X \tfrac{1}{2}X \tfrac{1}{2}X Figure 1 : Left: High-risk policyholder model in ReDiP . Right: Illustration of the PGA construction for the posterior distribution (defined in detail in Section 4 ). \tfrac{40}{11} is the normalization factor resulting from the observe -operation as described in Section 4.7 . Motivating Example: Inferring High-Risk Policyholders. Suppose that an insurance company models the number X of claims filed by each individual policyholder as a Poisson-Gamma model \theta\sim\texttt{Gamma}\texttt{(}\alpha\texttt{,}\beta\texttt{)};X\sim\texttt{Poisson}\texttt{(}\theta\texttt{)} , which is equivalent to a negative binomial model X\sim\texttt{NegBin}\texttt{(}\alpha\texttt{,}\frac{\beta}{1+\beta}\texttt{)} [ 26 ] . 1 1 1 Poisson and gamma distributions are not supported directly by our language. For simplicity, we further assume a Bernoulli prior on \alpha ( \alpha=1 with prior probability 0.9 ; \alpha=2 with prior probability 0.1 ) and fix \beta=1 ; these choices imply that low-risk customers ( \alpha=1 ) file one claim on average, whereas high-risk policyholders ( \alpha=2 ) file two claims. Now consider the following scenario: An employee of the insurance notices that she is processing, for the second time, a claim of the same policyholder—hence she knows that this individual has filed at least two claims. A typical inference problem is to determine the probability of the customer being in the high-risk category. This situation can be modeled in ReDiP as shown in Figure 1 , and solved 2 2 2 The posterior probability of being high-risk is exactly \nicefrac{{2}}{{11}}\approx 0.182 . by analyzing the resulting automaton (see Example 3 ). Contributions. In summary, the contributions of this paper are as follows: • We propose encoding joint distributions—possibly with infinite support—over non-negative integer variables as certain weighted automata ( Section 2 ). • We provide an effective translation from programs to automata transformations, enabling posterior inference via common automata-theoretic constructions ( Sections 3 and 4 ). • We prove our approach sound with regards to an existing operational program semantics in terms of Markov chains [ 23 ] ( Section 5 ). 2 Background on Weighted Automata We define \mathbb{R}_{\texttt{+}}=\left\{r\in\mathbb{R}\mid r\geq 0\right\} , {\mathbb{R}_{\texttt{+}}^{\infty}}=\mathbb{R}_{\texttt{+}}\cup\left\{\infty\right\} , and \mathbb{B}=\{0,1\} . Semirings and Formal Power Series. The following definitions closely follow [ 19 ] . A semiring is a 5-tuple (\mathbb{S},+,\cdot,0,1) where (\mathbb{S},+,0) is a commutative monoid, (\mathbb{S},\cdot,1) is a monoid, \cdot distributes over + , and a\cdot 0=0\cdot a=0 for all a\in\mathbb{S} . If the operations and neutral elements are clear from the context, we only use \mathbb{S} to refer to the semiring. We call a semiring \mathbb{S} naturally ordered if the binary relation a\sqsubseteq b\overset{\text{\tiny def}}{\iff}\exists c\in\mathbb{S}\colon a+c=b forms a partial order on \mathbb{S} . A semiring together with a sum operator \sum_{i\in I}a_{i} defined for arbitrary—possibly infinite—families (a_{i})_{i\in I} is called complete if \sum_{i\in I}a_{i} behaves as usual finite sums for finite I , and is commutative as well as distributive (see [ 19 ] for the formal definitions). A naturally ordered, complete semiring \mathbb{S} is called \omega -continuous if the following condition holds for all countable families (a_{i})_{i\in\mathbb{N}} : \forall c\in\mathbb{S}\colon\forall n\in\mathbb{N}\colon\sum_{i\leq n}a_{i}\sqsubseteq c\implies\sum_{i\in\mathbb{N}}a_{i}\sqsubseteq c. Two \omega -continuous semirings of interest are the Boolean semiring (\mathbb{B},\lor,\land,0,1) and the non-negative extended real semiring ({\mathbb{R}_{\texttt{+}}^{\infty}},+,\cdot,0,1) . In the latter, the sum operator is defined via \sum_{i\in I}a_{i}=\sup\left\{\sum_{i\in E}a_{i}\mid E\subseteq I,E\text{ finite}\right\} , which possibly evaluates to the \infty element. Given an \omega -continuous semiring (\mathbb{S},+,\cdot,0,1) and a monoid (\mathbb{M},\circ,e) , we define the set \mathbb{S}\langle\!\langle\mathbb{M}\rangle\!\rangle of formal power series (FPS) as the set of maps \{f\colon\mathbb{M}\to\mathbb{S}\} . As usual, FPS are denoted as “formal infinite sums” f=\sum_{m\in\mathbb{M}}f(m)m . We call f(m) the coefficient of m\in\mathbb{M} and define the support of f as \mathrm{supp}(f)=\{m\in\mathbb{M}\mid f(m)\neq 0\} . \mathbb{S}\langle\!\langle\mathbb{M}\rangle\!\rangle is a semiring with the following operations: For all f_{1},f_{2}\in\mathbb{S}\langle\!\langle\mathbb{M}\rangle\!\rangle and m\in\mathbb{M} , (f_{1}+f_{2})(m)=f_{1}(m)+f_{2}(m) and (f_{1}\cdot f_{2})(m)=\sum_{m=m_{1}\circ m_{2}}f_{1}(m_{1})\cdot f_{2}(m_{2}) . The neutral elements are 0 and 1e=e . If \mathbb{S} is \omega -continuous, then so is \mathbb{S}\langle\!\langle\mathbb{M}\rangle\!\rangle [ 19 ] . Example 1 (Formal Power Series) We illustrate FPS by means of the instances relevant to this paper. The overall idea is that FPS generalize the concept of (weighted) formal languages. Let V be a finite alphabet. • V^{*} is a monoid with concatenation and neutral element \varepsilon , and \mathbb{B}\langle\!\langle V^{*}\rangle\!\rangle is isomorphic to the semiring of formal languages 2^{V^{*}} over V . In this semiring, addition is union and