让程序在运行中验证复杂时间行为,给出概率保证。
Quantitative Verification of Omega-regular Properties in Probabilistic Programming
- 将时序逻辑融入概率编程,分析程序轨迹满足特定性质的概率。
- 通过分解接受条件并构造随机屏障证书,严格计算满足概率的上下界。
- 适合研究概率模型时序验证或需要形式化保障的开发者。
概率编程为指定统计模型提供高层框架,将随机性和条件化嵌入可执行程序。然而,现有推断技术通常只计算固定时间点(尤其是程序终止时)的状态后验分布,无法捕捉概率行为的时序演化。本文提出时序后验推断(TPI),通过计算满足omega正则规范的执行轨迹的后验分布,并基于可能的时间观测进行条件化,实现概率编程与时序逻辑的统一。为获得严格的定量保证,我们开发了一种新方法,用于计算omega正则性质的满足概率上下界。该方法将Rabin接受条件分解为持久性与重现性两部分,构建随机屏障证书以有声地约束每个分量。我们在原型工具TPInfer中实现了该方法,并在一组基准测试上评估,展示了在复杂时序属性下高效且有效的推断能力。
原文摘要 · Abstract (English)
Probabilistic programming provides a high-level framework for specifying statistical models as executable programs with built-in randomness and conditioning. Existing inference techniques, however, typically compute posterior distributions over program states at fixed time points, most often at termination, thereby failing to capture the temporal evolution of probabilistic behaviors. We introduce temporal posterior inference (TPI), a new framework that unifies probabilistic programming with temporal logic by computing posterior distributions over execution traces that satisfy omega-regular specifications, conditioned on possibly temporal observations. To obtain rigorous quantitative guarantees, we develop a new method for computing upper and lower bounds on the satisfaction probabilities of omega-regular properties. Our approach decomposes Rabin acceptance conditions into persistence and recurrence components and constructs stochastic barrier certificates that soundly bound each component. We implement our approach in a prototype tool, TPInfer, and evaluate it on a suite of benchmarks, demonstrating effective and efficient inference over rich temporal properties in probabilistic models.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。