paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A Cartesian Closed Category for Random Variables

随机变量的笛卡尔闭范畴
LICS Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science2024匹配度 3/10 · 论文属于概率编程的形式语义与范畴论研究,与用户关注的贝叶斯程序分析仅有间接关联;不涉及静态分析、LLM/Agent、浮点程序分析或工业工具落地,且偏纯理论构造。引用 4 inbox
Pietro Di Gianantonio, Abbas Edalat
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:在 Scott 域框架下构造随机变量域,建立概率编程语义的笛卡尔闭范畴与四个强交换单子。

本文在传统 Scott 域框架内给出概率编程语义的一个新构造,解决该领域长期未决问题。作者考虑从固定概率空间(单位区间或 Cantor 空间)到任意 Scott 域的随机变量所构成的 Scott 域,证明将随机变量映到其概率分布的映射是到概率幂域上的 Scott 连续满射,并保持典范基元;当基域可有效给出时该映射可计算。随后通过用偏等价关系丰富 Scott 域范畴,得到笛卡尔闭范畴,以刻画随机变量在这些域上的等价。该范畴上的随机变量域构造子与两种标准概率空间结合,产生四个基本强交换单子,可用于定义概率编程语义。

问题
概率编程缺乏在传统 Scott 域框架下令人满意的语义模型,尤其是随机变量域与概率幂域的关系长期未决。
方法
从固定概率空间(单位区间或 Cantor 空间)到 Scott 域的随机变量构造 Scott 域,并用偏等价关系丰富 Scott 域范畴以刻画随机变量等价。
评估
证明随机变量到概率分布的映射是保持基元的 Scott 连续满射且在有效可给定时可计算,并由此得到笛卡尔闭范畴及四个强交换单子。
原文摘要(Abstract)

We present a novel, yet rather simple construction within the traditional framework of Scott domains to provide semantics to probabilistic programming, thus obtaining a solution to a long-standing open problem in this area. We work with the Scott domain of random variables from a standard and fixed probability space---the unit interval or the Cantor space---to any given Scott domain. The map taking any such random variable to its corresponding probability distribution provides a Scott continuous surjection onto the probabilistic power domain of the underlying Scott domain, which preserving canonical basis elements, establishing a new basic result in classical domain theory. If the underlying Scott domain is effectively given, then this map is also computable. We obtain a Cartesian closed category by enriching the category of Scott domains by a partial equivalence relation to capture the equivalence of random variables on these domains. The constructor of the domain of random variables on this category, with the two standard probability spaces, leads to four basic strong commutative monads, suitable for defining the semantics of probabilistic programming.

链接与引用

DOI 原文 · arXiv · PDF(开放获取) · DBLP

BibTeX
@inproceedings{abs-2402-11727,
  title = {A Cartesian Closed Category for Random Variables},
  author = {Pietro Di Gianantonio and Abbas Edalat},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662126}
}