Silva, A;
Dahlqvist, F;
Danos, V;
Garnier, I;
(2018)
Borel Kernels and their Approximation, Categorically.
In:
Proceedings of the 34th Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXIV).
(pp. pp. 91-119).
Elsevier: Toronto, Canada.
Preview |
Text
Silva_1-s2.0-S1571066118300860-main.pdf - Published Version Download (427kB) | Preview |
Abstract
This paper introduces a categorical framework to study the exact and approximate semantics of probabilistic programs. We construct a dagger symmetric monoidal category of Borel kernels where the dagger-structure is given by Bayesian inversion. We show functorial bridges between this category and categories of Banach lattices which formalize the move from kernel-based semantics to predicate transformer (backward) or state transformer (forward) semantics. These bridges are related by natural transformations, and we show in particular that the Radon-Nikodym and Riesz representation theorems - two pillars of probability theory - define natural transformations. With the mathematical infrastructure in place, we present a generic and endogenous approach to approximating kernels on standard Borel spaces which exploits the involutive structure of our category of kernels. The approximation can be formulated in several equivalent ways by using the functorial bridges and natural transformations described above. Finally, we show that for sensible discretization schemes, every Borel kernel can be approximated by kernels on finite spaces, and that these approximations converge for a natural choice of topology. We illustrate the theory by showing that our approximation scheme can be used in practice as an approximate Bayesian inference algorithm and as an approximation scheme for programs in the probabilistic network specification language ProbNetKAT.
| Type: | Proceedings paper |
|---|---|
| Title: | Borel Kernels and their Approximation, Categorically |
| Event: | Mathematical Foundations of Programming Semantics (MFPS XXXIV), 3-7 June 2018, Halifax, Canada |
| Location: | Canada |
| Dates: | 03 June 2018 - 07 June 2018 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.entcs.2018.11.006 |
| Publisher version: | https://doi.org/10.1016/j.entcs.2018.11.006 |
| Language: | English |
| Additional information: | Copyright © 2018 The Author(s). Published by Elsevier B.V. www.elsevier.com/locate/entcs https://doi.org/10.1016/j.entcs.2018.11.006 This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/). |
| Keywords: | Probabilistic programming, probabilistic semantics, Markov process, Bayesian inference, approximation |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10064296 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
