张德祥 (2022-10-11 09:40):
#paper DOI: https://doi.org/10.1145/3428208 Scaling Exact Inference for Discrete Probabilistic Programs 概率推理的计算挑战是应用概率编程的主要障碍,如何解决?如何利用程序的结构来分解推理,如何解耦分不的结构和参数?如何证明编译的语义正确? dice 语言使用weighted model counting (WMC)推理,使用weighted Boolean formulas (WBF) 将代码编译为 binary decision diagrams (BDDs) to represent these formulas; experiments in Section 5 show Dice performing exact inference on a real-world probabilistic program that is 1.9MB large. 由于避免了指数爆炸,dice 编译的大小是线性的,计算是有保证的,编译方法是有数学证明理论的保证。 dice跟之前概率编程很大的不同是,同时支持常规编程语言的结构 if else for等。 一个关键挑战是dice支持任意观察,dice编译程序到两种BDD,一个支持程序的任意执行忽略观察,另一个表示满足观察的所有执行。 dice 开源。 The key insight is to separate the logical representation of the state space of the program from the probabilities 一旦程序被编译成 BDD,Dice 通过 WMC 对原始概率程序进行推理。至关重要的是,它这样做并没有穷尽列举所有的路径或模型。(高效) 通过条件独立进行抽象降低计算复杂度。(独立性,条件独立,局部结构) 补充参考: https://mp.weixin.qq.com/s/Rks2VGLz8G9XS3IGR7xegw
Scaling exact inference for discrete probabilistic programs
翻译
Abstract:
Probabilistic programming languages (PPLs) are an expressive means of representing and reasoning about probabilistic models. The computational challenge of probabilistic inference remains the primary roadblock for applying PPLs in practice. Inference is fundamentally hard, so there is no one-size-fits all solution. In this work, we target scalable inference for an important class of probabilistic programs: those whose probability distributions are discrete . Discrete distributions are common in many fields, including text analysis, network verification, artificial intelligence, and graph analysis, but they prove to be challenging for existing PPLs. We develop a domain-specific probabilistic programming language called Dice that features a new approach to exact discrete probabilistic program inference. Dice exploits program structure in order to factorize inference, enabling us to perform exact inference on probabilistic programs with hundreds of thousands of random variables. Our key technical contribution is a new reduction from discrete probabilistic programs to weighted model counting (WMC). This reduction separates the structure of the distribution from its parameters, enabling logical reasoning tools to exploit that structure for probabilistic inference. We (1) show how to compositionally reduce Dice inference to WMC, (2) prove this compilation correct with respect to a denotational semantics, (3) empirically demonstrate the performance benefits over prior approaches, and (4) analyze the types of structure that allow Dice to scale to large probabilistic programs.
翻译
回到顶部