Weighted Automata for Exact Inference in Discrete Probabilistic Programs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911285893922816 |
|---|---|
| author | Geißler, Dominik Winkler, Tobias |
| author_facet | Geißler, Dominik Winkler, Tobias |
| contents | 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 $\mathbb{N}^k$ as weighted automata over a commutative alphabet with $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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_15074 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Weighted Automata for Exact Inference in Discrete Probabilistic Programs Geißler, Dominik Winkler, Tobias Formal Languages and Automata Theory Programming Languages 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 $\mathbb{N}^k$ as weighted automata over a commutative alphabet with $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. |
| title | Weighted Automata for Exact Inference in Discrete Probabilistic Programs |
| topic | Formal Languages and Automata Theory Programming Languages |
| url | https://arxiv.org/abs/2509.15074 |