2026-07-22T22:30:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18393 2024-03-06T11:01:47Z ddc:004 open_access

Semantic Foundations of Higher-Order Probabilistic Programs in Isabelle/HOL Hirata, Michikazu Minamide, Yasuhiko Sato, Tetsuya Higher-order probabilistic program s-finite kernel Quasi-Borel spaces Isabelle/HOL Higher-order probabilistic programs are used to describe statistical models and machine-learning mechanisms. The programming languages for them are equipped with three features: higher-order functions, sampling, and conditioning. In this paper, we propose an Isabelle/HOL library for probabilistic programs supporting all of those three features. We extend our previous quasi-Borel theory library in Isabelle/HOL. As a basis of the theory, we formalize s-finite kernels, which is considered as a theoretical foundation of first-order probabilistic programs and a key to support conditioning of probabilistic programs. We also formalize the Borel isomorphism theorem which plays an important role in the quasi-Borel theory. Using them, we develop the s-finite measure monad on quasi-Borel spaces. Our extension enables us to describe higher-order probabilistic programs with conditioning directly as an Isabelle/HOL term whose type is that of morphisms between quasi-Borel spaces. We also implement the qbs prover for checking well-typedness of an Isabelle/HOL term as a morphism between quasi-Borel spaces. We demonstrate several verification examples of higher-order probabilistic programs with conditioning. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michikazu Hirata and Yasuhiko Minamide and Tetsuya Sato 2023 Is Part Of LIPIcs, Volume 268, 14th International Conference on Interactive Theorem Proving (ITP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITP.2023.18 urn:nbn:de:0030-drops-183933 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2023.18 eng https://creativecommons.org/licenses/by/4.0/legalcode