概率编程 Probabilistic Programming

概率编程 Probabilistic Programming

https://www.pure.ed.ac.uk/ws/files/19355513/Gordon_Henzinger_ET_AL_2014_Probabilistic_Programming.pdf

概述本文重点

《概率编程：用于非结构化数据的稳健且高效推断的统一框架》的核心重点在于：

1. 核心问题与目标： 文章旨在解决一个普遍存在的挑战：如何从文本、图像等非结构化数据中，可靠且高效地推断出我们真正关心的结构化变量（例如经济政策不确定性指数、地缘政治风险指数）。现有方法常假设可以直接观测到这些结构化变量的真实值，但在现实应用中，真实值往往只存在于细粒度层面（如单篇文章），而研究者关心的是更高层级的聚合值（如月度均值），这些值无法直接观测。本文的目标是提供一个统一、稳健且高效的框架，让不具备深厚统计学或机器学习背景的程序员也能利用概率建模的力量。

2. 核心解决方案：MAR-S 框架的扩展应用： 文章的核心贡献是系统性地阐述并推广了 MAR-S (Missing at Random - Structural) 框架。该框架的核心思想是：

• 第一步（填补）

  ：使用标注数据训练一个“填补函数”（可以是简单的关键词分类器，也可以是复杂的深度神经网络），来预测缺失的结构化数据。

• 第二步（去偏）

  ：通过 MAR-S 机制对第一步的填补结果进行校正，得到无偏的估计量。

• 第三步（推断）

  ：基于这些无偏的估计量进行后续的统计分析（如回归分析），并通过标准的统计技术（如 delta 方法、处理测量误差的回归方法）来构建有效的置信区间和进行推断。

3. 关键创新与优势：

• 理论严谨性

  ：提供了严格的统计推断方法，能够生成 渐近有效 的置信区间，并明确考虑了因填补和聚合带来的 系统性测量误差 。

• 实用性与普适性

  ：方法概念直观，易于实施，可自然扩展到 聚类数据 和 面板数据 ，并能适应多种实际场景（如结果变量也需填补、测量误差非正态等）。

• 性能提升

  ：通过实证案例证明，使用更精确的填补模型（如深度神经网络）相比传统方法（如关键词分类器）能产生 更窄的置信区间 ，体现了“更准确填补带来更高效率”的回报。

• 揭示偏差

  ：清晰地展示了忽略测量误差会导致严重的 衰减偏差 和 置信区间被低估 ，从而得出错误的统计推断。

4. 实证验证与应用： 文章通过三个详尽的实证案例验证了框架的有效性：

• EPU 指数

  （Baker et al., 2016）：对比了关键词分类器与深度神经网络分类器在估算经济政策不确定性指数时的表现，量化了后者的精度优势。

• GPR 指数

  （Caldara and Iacoviello, 2022）：同样展示了深度学习模型在估算地缘政治风险指数上的优越性，并分析了其在回归分析中的影响。

• 均值估计示例

  ：利用作者自建数据集，深入探讨了 MAR-S 的设计选择。

5. 总结与展望： 本文不仅完善了现有理论，为实证研究者提供了一套可操作的工具，还指出了未来的研究方向，例如如何更好地处理高度类别不平衡的数据、如何将框架应用于更多元化的领域等。总而言之，它为从非结构化数据中提取结构化信息这一关键任务，提供了一个强大、灵活且实用的解决方案。

摘要

概率程序是普通的函数式或命令式程序，增加了两个构造：(1) 从分布中随机抽取值的能力；(2) 通过观测对程序中变量的值进行条件约束的能力。计算机视觉、编码理论、密码协议、生物学和可靠性分析等不同应用领域的模型都可以写成概率程序。

概率推理是指计算由概率程序隐式指定的概率分布的显式表示的问题。根据应用的不同，推断所需的输出可能有所不同——我们可能希望估计某个函数 f 关于该分布的期望值，或分布的众数，或仅仅是从此分布中抽取的一组样本。

在本文中，我们描述了“概率编程”这一研究领域与编程语言及软件工程（包括语言设计、程序的静态与动态分析）之间的联系。我们综述了当前的研究现状，并展望了未来研究的有前景方向。

1. 引言

概率程序是“普通”的程序（用 C、Java、LISP 或 ML 等语言编写），增加了两个构造：(1) 从分布中随机抽取值的能力；(2) 通过 observe 语句对程序中变量的值进行条件约束的能力（这允许将现实世界观测到的数据纳入概率程序）。已有多种概率编程语言和系统被提出 [5, 19, 21, 22, 31, 33, 41, 49]。然而，与旨在执行的“普通”程序不同，概率程序的目的是隐式地指定一个概率分布。概率程序可用于表示概率图模型 [32]，后者使用图来表示随机变量之间的条件依赖关系。概率图模型广泛应用于统计学和机器学习，其应用领域包括信息抽取、语音识别、计算机视觉、编码理论、生物学和可靠性分析。

概率推理是指计算由概率程序隐式指定的概率分布的显式表示的问题。如果概率分布涉及大量变量，则联合概率分布的显式表示可能既难以高效获得，在特定应用场景下也可能没有必要。例如，我们可能希望计算某个函数 f 关于该分布的期望值（这可能无需表示整个联合分布即可更高效地计算）。或者，我们可能希望计算变量最可能的取值，即分布的众数。又或者，我们可能只想从分布中抽取一组样本，以测试其他期望输入符合所建模分布的系统。

概率编程的目标是让拥有足够领域知识但可能缺乏概率论或机器学习专业知识的程序员能够便捷地使用概率建模和机器学习。我们希望将推断的细节隐藏在编译器和运行时系统内部，使程序员能够运用其领域专长来表达模型，从而极大地增加能从概率建模中受益的程序员数量。

本文的目标是为软件工程界提供概率编程的概览。我们假设读者熟悉程序分析和程序语义，但会提供概率推理所需的所有必要背景知识。我们使用一种简单的类 C 语言语法来表示概率程序。我们将概率推理与程序的静态和动态分析联系起来。我们讨论语言设计问题，并指出要实现概率编程真正普及机器学习，仍需解决的若干挑战。

在第 2 节，我们从实例入手介绍概率程序，最后给出其精确的形式语义。 在第 3 节，我们描述概率程序与其他读者可能熟悉的概率模型（如马尔可夫链和贝叶斯网络）之间的关系，以及这些模型如何被编码为概率程序。 在第 4 节，我们描述机器学习、安全和生物学等不同领域的应用如何被编码为概率程序。 在第 5 节，我们讨论概率程序的语言设计问题，以及如何使用 Excel 表格等高级语言来描述概率程序。 在第 6 节，我们描述执行概率推理的技术，并将其与程序的静态和动态分析进行类比。 在第 7 节，我们讨论概率编程领域中几个开放性问题和未来研究的机会。

2 背景

我们从一些例子开始本节，以帮助读者熟悉概率程序，并非正式地解释赋予概率程序语义背后的主要思想。本节最后将给出概率程序语法和语义的精确描述。

简单概率程序示例。我们通过图1中的三个简单概率程序来介绍概率程序的语法和语义。左上角的程序，即示例1(a)，抛掷两枚公平硬币（通过从均值为0.5的伯努利分布中抽样模拟），并将这些硬币投掷的结果分别赋给布尔变量c1和c2，然后返回(c1, c2)。该程序的语义是其返回值的期望值。在此情况下，这等于(1/2, 1/2)。因为我们有Pr(c1=false, c2=false) = Pr(c1=false, c2=true) = Pr(c1=true, c2=false) = Pr(c1=true, c2=true) = 1/4，所以返回值的期望由1/4×(0,0) + 1/4×(0,1) + 1/4×(1,0) + 1/4×(1,1) = (1/2, 1/2)给出（将true视为1，false视为0）。

示例1(b)中的程序与示例1(a)略有不同——它在返回(c1, c2)的值之前执行了observe(c1||c2)语句。observe语句会阻止不满足布尔表达式c1||c2的运行，并且不允许这些运行发生。允许满足c1||c2的运行发生。该程序的语义是条件于允许运行的期望返回值。由于条件化后得到Pr(c1=false, c2=false) = 0，而Pr(c1=false, c2=true) = Pr(c1=true, c2=false) = Pr(c1=true, c2=true) = 1/3，因此我们得出期望返回值为0×(0,0) + 1/3×(0,1) + 1/3×(1,0) + 1/3×(1,1) = (2/3, 2/3)。

此示例的另一个变体如示例2所示。该程序还计算导致值为true的硬币投掷次数，并将此计数存储在变量count中。该程序的语义是条件于允许运行的期望返回值。同样，由于条件化后得到Pr(c1=false, c2=false) = 0，而Pr(c1=false, c2=true) = Pr(c1=true, c2=false) = Pr(c1=true, c2=true) = 1/3，因此我们得出期望返回值为0×0 + 1/3×1 + 1/3×1 + 1/3×2 = 4/3。

我们注意到，语句observe(x)与程序验证文献中使用的语句assume(x) [2,15,42] 密切相关。此外，我们注意到observe(x)等价于while(!x) skip语句，因为概率程序的语义关注的是程序终止运行时输出的归一化分布，而忽略非终止运行。然而，我们使用术语observe(x)，因为它在概率编程系统中被广泛使用 [5,22]。

带循环的概率程序。图2展示了两个带有循环的概率程序。图2左侧的程序，即示例3，等价于示例2中的程序，其中observe语句已通过一个while循环等效编码。示例2第9行的observe语句仅允许满足条件(c1 || c2)的运行。第9-17行的while循环具有与observe语句相同的功能。如果(c1 || c2)成立，则循环退出。否则，它仅重新抽样c1和c2，重新计算count，并再次检查条件(c1 || c2)。

一般来说，observe语句可以使用循环进行编码。然而，反之则难以实现，除非计算循环不变式。为了说明这一点，请考虑图2右侧的示例4。在这个程序中，b的返回值为1当且仅当第3-7行的while循环执行偶数次；若循环执行奇数次，则b的返回值为0。因此，程序返回的b的期望值（即b为1的概率）等于while循环执行偶数次的概率。循环执行0次的概率为0.5，因为这与第3行中c被赋值为1的概率相同。循环执行2次的概率等于第3行中c被赋值为0的概率，且第6行首次执行时c被赋值为0、第二次执行时c被赋值为1的概率，由于三次对c的赋值都是独立的伯努利试验，每次概率为0.5，因此该概率等于0.5³。将所有偶数次执行的情况相加，我们得到几何级数0.5 + 0.5³ + 0.5⁵ + …，其值为2/3。

语法与语义。现在我们已经用简单的例子介绍了概率程序，接下来我们将给出精确的语法和语义。（我们的语义是Kozen [35]提出的经典概率程序语义的一种变体。）我们所考虑的概率编程语言PROB是一种类C的命令式编程语言，增加了两个额外的语句：

3. 与其他模型的关系

在本节中，我们将探讨概率程序与读者可能曾接触过的其他概率模型之间的关系。具体而言，我们考虑（1）贝叶斯网络和（2）离散时间马尔可夫链。我们展示贝叶斯网络可以被编码为无循环的概率程序。我们还表明，虽然马尔可夫链可以被编码为带循环的概率程序，但由于我们的概率程序语义仅考虑终止运行，而马尔可夫链具有非终止运行，因此马尔可夫链的稳态概率分布只能对一类受限的马尔可夫链表示为概率程序的输出（从而可通过概率推断进行计算）。最后，我们简要地将概率程序与概率数据库和马尔可夫逻辑网络联系起来。

3.1 贝叶斯网络

图6左侧的示例5展示了如何将图5中的贝叶斯网络编码为概率程序。注意，该程序仅按拓扑顺序遍历贝叶斯网络，并根据每个节点的CPD进行评估。

一般来说，每个贝叶斯网络都可以编码为一个无环概率程序，并以直接的方式进行，条件可以通过概率程序中的观察语句进行建模。

3.2 离散时间马尔可夫链

图7展示了一个具有13个顶点的示例DTMC。该DTMC实现了Knuth-Yao算法[30]，用于从公平硬币投掷中获得公平的稳态概率 。结果表明，顶点11到16的稳态概率为1/6，其他顶点为0。

每个DTMC都可以编码为概率程序。DTMC图中的循环可以使用概率程序中的while循环进行编码。例如，图8展示了一个等效于图7中DTMC的概率程序。

与我们为概率程序给出的语义不同，DTMC的语义考虑了终止运行（是有限的），DTMC的语义本质上考虑了无限运行。然而，在DTMC的每个终端SCC（强连通分量）是单例顶点的情况下（例如，图7中的DTMC，其中6个终端SCCs都是单例顶点），我们可以在达到终端SCC时终止概率程序的执行，如图8所示。在DTMC的终端SCC包含多个顶点的情况下，如果我们希望概率程序计算顶点的稳态概率，则必须调整第2节中的语义以考虑无限运行。

3.3 扩展

已经广泛研究了离散时间马尔可夫链（DTMC）的几种扩展。我们简要提到其中的两种扩展。第一种扩展是马尔可夫决策过程（MDP），通过在DTMC中添加非确定性来获得。也就是说，除了在每个顶点进行的概率选择外，模型还允许进行非确定性选择。在每个顶点解决非确定性选择可以通过所谓的策略来完成，一旦选择了策略，我们就得到了一个DTMC。已经研究了几种在MDP中计算策略的算法[50]。第二种扩展是连续时间马尔可夫链（CTMC），其中隐含了时间的概念，每个转换都标注了一个速率 γ，并且在每个状态下，系统花费的时间由指数分布决定。在化学（CTMC是分子混合模型，通常是生物分子）和其他科学中，几个应用自然地表示为CTMC。CTMC可以通过显式引入时间作为程序变量，并使用一种称为均匀化[46]的技术来编码为概率程序。我们将在后续章节中回到这些扩展。

3.4 概率数据库

4. 应用

在本节中，我们展示来自机器学习、临床诊断、生态学和安全等不同领域的应用，并说明如何将这些应用建模为概率程序。我们将使用一些语言构造，如函数调用和 switch 语句，这些是对第2节所介绍语法的补充。

在线游戏中的技能评级。微软 Xbox Live 等在线游戏系统会对参与在线游戏的玩家进行相对技能评级，以便将技能水平相近的玩家匹配在一起进行游戏。问题在于，如何根据每位玩家迄今为止所玩游戏的结果来估算其技能水平。已有研究提出了一种针对此问题的贝叶斯模型 [26]。图9展示了如何将这一被称为 TrueSkill 的模型表达为一个概率程序。我们考虑三位玩家 A、B 和 C，他们的技能分别由变量 skillA、skillB 和 skillC 表示，这些变量通过从均值为100、方差为10的高斯分布中抽样进行初始化。基于若干场已玩比赛的结果（本例中为3场比赛），我们对由此生成的技能进行条件约束。第一场比赛在 A 和 B 之间进行，A 赢得了比赛。这通过为两个随机变量 perfA1 和 perfB1（分别表示两位玩家在第一场比赛中的表现）赋值，并使用 observe 语句约束 perfA1 大于 perfB1 来建模。请注意，玩家的表现（例如玩家 A）是其技能的一个函数，但额外引入了高斯噪声，以模拟因模型不完善（例如玩家前一晚的睡眠量）而可能出现的表现波动。第二场比赛在 B 和 C 之间进行，B 赢得了比赛。第三场比赛在 A 和 C 之间进行，A 赢得了比赛。利用此模型，我们希望计算这些随机变量的联合概率分布，并以此估算玩家之间的相对技能水平。请注意，每个 observe 语句都约束了某场比赛中的表现，从而隐式地约束了玩家的技能，因为表现取决于技能。此类评级可用于分配积分，或将技能水平相近的玩家匹配起来，以提升游戏体验。在本例中，通过推断（使用第6节的技术）得到的技能 skillA、skillB 和 skillC 分别为：skillA = 高斯分布(105.7, 0.11)，skillB = 高斯分布(100.0, 0.11)，skillC = 高斯分布(94.3, 0.11)。由于 A 击败了 B 和 C，而 B 击败了 C，最终得出的分布与我们对它们相对技能的直观判断相符。

捕食者-猎物种群模型。Lotka-Volterra 捕食者-猎物模型 [37, 57] 是一种描述捕食者物种和猎物物种种群随时间演变的种群模型。它通过一组所谓的“化学计量”反应来定义，如下所示：

我们考虑一个包含山羊（记为 G）和老虎（记为 T）的生态系统。第一个反应模拟山羊的繁殖。第二个反应模拟老虎对山羊的捕食以及随之而来的老虎数量增加。第三个反应模拟老虎因自然原因死亡。

事实证明，该系统可以等价地建模为一个连续时间马尔可夫链（CTMC），其状态是一个有序对 (G, T)，由山羊数量 G 和老虎数量 T 组成。第一个反应可视为 CTMC 中从状态 (G, T) 到 (G + 1, T) 的一次转移，其发生速率为 c₁·G（其中 c₁ 为某个速率常数），且仅在 G > 0 时被激活。接着，第二个反应可视为 CTMC 中从状态 (G, T) 到 (G - 1, T + 1) 的一次转移，其发生速率为 c₂·G·T（其中 c₂ 为某个速率常数），且仅在 G > 0 且 T > 0 时被激活。最后，最后一个反应可视为 CTMC 中从状态 (G, T) 到 (G, T - 1) 的一次转移，其发生速率为 c₃·T（其中 c₃ 为某个速率常数），且仅在 T > 0 时被激活。

通过一种称为“均匀化”的过程，这样的 CTMC 可以使用嵌入式离散时间马尔可夫链（DTMC）进行建模，并编码为一个概率程序，如图10所示。该程序从山羊和老虎的初始种群数量开始，执行 Lotka-Volterra 模型的转移，直到达到预设的时间限制，然后返回最终的山羊和老虎种群数量。由于执行过程是概率性的，该程序模拟了山羊和老虎种群的输出分布。while 循环的主体被划分为三个条件：(1) 第一个条件模拟山羊和老虎同时存在的情况，此时三种反应均可能发生。(2) 第二个条件模拟仅有山羊存在的情况（这是一个极端情形），此时仅可能发生山羊的繁殖。(3) 第三个条件模拟仅有老虎存在的情况（这是另一个极端情形），此时仅可能发生老虎的死亡。

将该模型编码为概率程序的过程复杂、非模块化且效率低下——在每个状态，程序都必须首先找出哪些反应被激活，然后计算所有激活反应的总速率并执行均匀化。一种更直接的编码方式，在语法和语义上都更为理想，是可取的，我们将在第7节进一步讨论这一点。

肾病估算的敏感性分析。在医学诊断中，医生常常需要根据实验室检测结果和患者的电子病历信息，判断患者是否患有某种特定疾病。然而，检测结果可能存在噪声。此外，假设电子病历中也可能存在转录错误。我们希望评估由于检测噪声和转录错误导致的决策敏感性。

图11展示了一个概率程序，该程序模拟了系统的运行行为，源自文献[52]。我们描述该模型，并遵循[52]中的相关假设。成人肾病的一个常用衡量指标是“估算肾小球滤过率”（eGFR），它基于患者的年龄、性别、种族以及测得的血清肌酐水平计算得出。我们使用一个名为CKD-EPI 1的广泛使用的公式来定义函数estimateLogEGFR。该程序考虑了所有输入变量的噪声——血清肌酐水平（由logScr变量表示）、性别（isFemale变量）和种族（isAA变量，若患者为非裔美国人则为真），并计算由于这些变化导致计算出的eGFR值变动0.1或以上的概率。变量bigChange用于建模当eGFR值因上述变化而变动0.1或以上的情形。程序返回此值，因此可用于估算由于对输入噪声的假设而导致eGFR出现此类误差的概率。

基于知识的安全策略。Mardziel 等人 [39] 探索了基于知识的安全策略，这是一种基于概率编程的访问控制机制。在他们的研究中，基于 Clarkson 等人 [12] 的理论，用户的代理 U 会接收针对用户秘密数据的查询，并通过监控每个查询方 Q 对秘密数据的知识分布（以概率分布形式表示），来决定是否接受该查询。策略由针对秘密数据不同方面的知识阈值给出。

例如，假设秘密数据包含用户 U 的生日和年份，例如1980年9月27日，这些数据存储在整数变量 bday = 270 和 byear = 1980 中。在此情况下，访问控制策略由两个知识阈值配置：第一，查询者猜测出生日期的概率应低于20%；第二，查询者同时猜中出生日期和年份的概率应低于5%。

进一步假设，根据人口统计信息，查询方 Q（一名广告商）的先验知识是，bday 的取值范围在 0 ≤ bday < 365 内，byear 的取值范围在 1956 ≤ byear < 1993 内，且这些值均等可能。我们可以将这种先验信念表示为以下概率程序：

现在，假设查询者希望识别那些生日在未来一周内的用户，以便向他们推送特别优惠。为此，广告商向用户发送以下查询：

访问控制的问题在于是否允许广告商查看输出，而策略规定，只要广告商在执行查询后对秘密数据的知识不超过上述知识阈值，即可允许其访问。

我们通过概率推断来决定访问控制问题。首先，我们推断从先验信念加上查询，再结合两种可能性之一——observe(output == 0) 或 observe(output == 1)——所得到的概率程序的后验分布。其次，在每种情况下，我们检查 bday 的任何可能取值的后验概率是否超过20%，或 (bday, byear) 的任何可能取值组合的概率是否超过5%。若未超过，则符合策略，可将查询结果返回给广告商 Q；否则，该查询将被拒绝。每次从 Q 发出的查询运行后，我们会更新对 Q 知识的表示，以便用于下一次访问控制决策。

请注意，访问控制的决策是通过检查知识阈值是否不会因秘密数据的任何可能取值而被突破来做出的，而非基于实际的秘密数据本身。考虑这样一种情形：广告商希望在连续两天内运行该查询，第一天为 today = 260，第二天为 today = 261。如果我们使用真实的秘密数据 bday = 270 来做决策，那么在这两种情况下，查询输出 output = 0，且均未突破任何知识阈值。但假设实际上秘密数据是 bday = 267，那么运行这两个查询将必然揭示秘密，因为第一个查询会返回 output = 0，第二个查询会返回 output = 1，而这只有在 bday = 267 时才可能发生。因此，我们需要在允许第一个查询后拒绝第二个查询，但这种拒绝行为本身会泄露关于秘密的信息，可能违反知识阈值。为避免这一困境，决策是通过对所有可能的秘密值进行量化来做出的。

文献[39]的作者描述了他们方案的一种实现，该实现利用了一种基于多面体的可靠抽象解释，并对其性能进行了评估。这项工作仍处于早期阶段，但却是未来研究的一个有前景的方向。

5. 语言设计

命令式、函数式与逻辑式范式。正如确定性编程语言一样，概率编程语言也存在命令式、函数式和逻辑式范式。我们的原型语言 PROB 是命令式的，基于 C# 的建模语言 Infer.NET [41] 以及用于推理密码算法和协议的 CertiCrypt [3] 和 EasyCrypt [4] 验证工具所使用的密码学建模语言 PWHILE 也是命令式的。目前最广泛采用的概率编程语言 BUGS [19] 是函数式的。此后出现了许多其他的函数式概率语言，包括 IBAL [49]、STAN [54] 和基于随机λ演算的 Church [21]。概率逻辑语言则包括 BLOG [40]、Alchemy [31] 和 Tuffy [43]。此简短列表远非详尽；更多概率语言的讨论请参见 Wiki probabilistic-programming.org。

避免“阻抗失配”。编程语言类型与数据库模式之间的“阻抗失配”是传统编程中长期存在的问题。例如，访问关系型数据库的程序需要依赖样板代码或库，将外部表连接到传统语言中的数组或集合类等编程语言类型。同样的失配问题也出现在概率编程语言中：聚合数据在程序中被表示为多个数组，而在数据库中则是一组关系表。

Tabular [23] 是一种新的概率编程语言，其最显著的特点是程序以带注释的关系模式编写。传统上，在 SQL 或其他关系表示法中，表的模式描述了表中每一行各项的数据类型。在 Tabular 中，传统的模式通过概率表达式得到增强，这些表达式定义了如何对表的每一行进行采样，从而构成一个数据的概率生成模型。Tabular 的表模式对应于常用于定义图模型的“板式表示法”。

例如，以下是前面讨论过的 TrueSkill 模型的 Tabular 模式。它包含一个玩家表和一个玩家间比赛表。我们可以将 Tabular 模式视为一个函数：给定一个具体的数据库（即我们的实际数据），它会定义一个预测性数据库——一个分布，该分布的表具有与具体数据库相同的列，但增加了隐变量列。在 TrueSkill 的例子中，玩家表有一个隐含的“技能”列，而比赛表则有隐含的“表现”列。

标记为“隐含”的列仅存在于预测性数据库中。输入列和输出列必须存在于具体数据库中。不同之处在于，输出列中可能存在空值（null），但输入列中不允许有缺失值。输出列上的概率表达式用于预测缺失值；在生成过程中，当具体数据库中的值非空时，我们会添加 observe 约束，使预测值等于该具体值。尽管模型可能依赖（因而被条件化）于输入数据，但它无法预测缺失的输入值。

Tabular 通过翻译成一个命令式的概率程序（类似于 PROB 程序）来实现，并运行 Infer.NET 来计算预测性数据库中每个单元格的后验边缘分布。对于对应第4节示例的具体数据库（其中 A 击败 B，B 击败 C，A 击败 C），推断结果如下：

以类似的方式，比赛表（Matches table）的预测形式会填充其隐含的表现值。

对 Tabular 的早期实验评估提供了一些证据，表明其模型比使用 Infer.NET 输入语言编写的等效模型要显著简洁得多，并且在可读性和易理解性方面也更有优势，同时在速度上几乎没有损失的情况下返回相同的结果 [23]。其期望是，Tabular 能够将概率编程的优势带给那些希望用电子表格而非完整编程环境来建模数据的数据爱好者。

6. 推断

计算由概率程序所指定的分布被称为概率推断。推断出的概率分布称为后验概率分布，而程序最初做出的猜测称为先验概率分布。存在多种执行推断的方法。我们简要指出，对于具有无界域的程序，精确推断是不可判定的。即使对于仅包含布尔变量的程序，精确推断也是 -完全问题 [51]。因此，在本节中，我们仅讨论近似推断的技术。

6.1 贝叶斯网络的推断

我们首先概述贝叶斯网络的推断算法。对于贝叶斯网络，高效且近似的推断通常通过消息传递算法（如置信传播 [47]）或采样技术（如马尔可夫链蒙特卡洛 MCMC 算法 [38]）来完成。

消息传递。在第2节中，我们看到贝叶斯网络表示其变量上的联合概率分布。特别地，我们还看到贝叶斯网络的结构代表了联合概率分布的一种特定分解方式（利用依赖关系结构，将其分解为每个节点条件概率分布 CPD 的乘积）。像置信传播 [47] 这样的消息传递算法正是利用这种分解，以高效地计算网络中每个变量的概率分布。

可以证明，重复应用上述步骤将导致样本根据目标分布 P 进行抽取[38]。

6.2 概率程序的推断

多种推断技术已在概率编程系统中得以实现 [5, 19, 21, 27, 31, 33, 41, 49]。这些技术是上述贝叶斯网络推断技术的变体，可大致分为以下两类：

1. 静态推断

   ：该方法是将概率程序编译为一个概率模型（如贝叶斯网络），然后使用置信传播及其变体等算法进行推断 [47]。Infer.NET [41] 就是此类工具的一个例子。

2. 动态推断

   ：另一种方法是通过多次执行程序，利用采样来执行概率语句，在有效运行中观察目标变量的值，并对观测值进行统计计算，从而推断出所需分布的近似结果。Church [21] 和 Stan [27] 等概率编程系统即采用动态推断技术。

在本节余下部分，我们将建立这些方法与程序分析工作的关键联系。我们表明，推断本质上是推广到概率程序的程序分析 [7, 44]，因此探讨了软件工程和程序分析领域的研究者为概率编程领域做出贡献的机会。

静态分析。概率程序的语义可以通过数据流分析来计算。此处的数据流事实是概率分布，它们可通过符号执行每条语句、在汇合点合并数据流事实、并在循环处执行不动点计算来传播。在 [11] 中，我们展示了如何使用代数决策图 (ADDs) 高效地执行此分析。ADD [1] 是一种图形化数据结构，用于紧凑地表示有限函数（在此情况下，是对联合概率分布的符号表示）。

我们在图13中以示例1(b)（来自图1）为例说明此分析。符号执行前两条语句“c1 = Bernoulli(0.5)”和“c2 = Bernoulli(0.5)”会分别得到 c1 和 (c1, c2) 上的均匀分布。这两个分布均可由一个仅含单个叶节点的代数决策图 (ADD) 紧凑表示。接着，在处理语句 observe(c1||c2) 时，分析会计算出由图中所示 ADD 表示的子分布。最后，通过对该子分布进行归一化，即可得到代表 (c1, c2) 后验分布的最终 ADD。更多细节请参阅 [11]。

同样，也可以使用基于抽象解释 [13] 的技术来估算后验概率——事实上，近期已有相关有趣的研究工作 [39, 52]。

静态分析也可用于对概率程序进行切片 [45]，以提高推断效率。考虑图14(a)中所示的程序。这是示例6中程序的一个变体。基于控制依赖和数据依赖的常规静态程序切片技术 [18] 会产生图14(b)中的程序，但此计算是错误的，因为可以证明切片后的程序与原程序并不等价。

observe 语句（第20行）引入了常规程序中不存在的新类型依赖关系。具体而言，对变量 l 值的观测会影响 g 的值，进而间接影响 i，最终影响 s。此外，这种从 i 到 g 的影响流还“打开”了一条路径，使得影响可以从 d 流向 i，最终也流向 s。这种影响流在 [45] 中通过一种称为“观测依赖”的新概念进行解释，并与贝叶斯网络中的“活动路径” [32] 相关。结合传统的控制依赖和数据依赖，“观测依赖”可用于对概率程序进行切片。此外，切片算法可实现为源代码到源代码的程序转换，通过移除无关语句，极大地提高了推断效率，同时能提供可证明等价的答案。在当前例子中，结果表明所有变量 d、i、g、l 和 s 在此程序中都是相关的（若同时考虑观测依赖、控制依赖和数据依赖，则可识别出所有这些依赖关系），而唯一在语义上等价于图14(a)程序的切片就是整个程序本身！

动态分析。动态方法（也称为基于采样的方法）被广泛使用，因为无论用何种编程语言表达程序，运行概率程序都是很自然的。此场景下的主要挑战是，在执行过程中生成的许多样本最终会因不满足观测条件而被拒绝。这类似于标准概率模型中的拒绝采样 [38]。

为了提高效率，理想情况下应尽可能避免生成那些后续会被拒绝的样本。在 [44] 中，我们提出了一种名为 R2 的采样算法，该算法利用程序分析来应对这一挑战。具体而言，R2 包含以下步骤：

1. 反向传播观测：通过使用前像操作 [16] 或 PRE 分析，将观测语句反向传播回程序，使得每个概率赋值语句后立即紧跟着一个 observe 语句。此转换保持了程序语义（如图4所定义），并有助于进行高效的采样（将在下一步定义）。
2. 执行修改后的 Metropolis-Hastings (MH) 采样 [10]：在经过转换的概率程序上执行修改版的 MH 采样。这些修改利用了转换后程序的结构特征——即观测语句紧跟在概率赋值语句之后——并通过从子分布中采样来避免拒绝。

上述两个步骤防止了因执行结果不满足观测条件而导致的样本拒绝，并显著提高了在给定时间预算内接受的 MH 样本数量。相比之下，先前的方法 [21, 48, 58, 59] 并未专门解决因观测失败而导致的拒绝问题。

7. 讨论

在本节中，我们概述了一些未来工作的方向。我们首先讨论概率编程与概率模型检验之间的关系。尽管这两个领域的目标不同，但我们认为，两个社区之间的思想交流是未来研究的一个有趣方向。我们还探讨了与机器学习其他子领域（如优化社区）互动的可能性。我们探索了为当前概率编程语言添加一些尚不具备的新特性——特别是添加非确定性和更原生的连续时间支持。最后，我们讨论了为使概率程序能被机器学习非专家广泛使用所需的一些工具支持方面的进展。

概率模型检验。概率模型检验涉及检查一个概率模型是否满足某个定量规范。虽然这一概念自20世纪80年代就已存在 [34, 56]，但在过去十年中，构建诸如 PRISM [36] 和 MRMC [29] 等模型检验器方面取得了很大进展。PRISM 支持多种概率模型，如离散时间马尔可夫链、连续时间马尔可夫链和马尔可夫决策过程。所有模型都用类似守卫命令的语法表达，属性则用概率时序逻辑（如 PCTL [24]）表达。这些属性通常对概率或期望值设定定量界限。一个说明概率界限的例子是：“安全气囊在碰撞后0.02秒内未能展开的概率小于0.01”。另一个说明期望值界限的例子是：“协议完成传输一个数据包的期望时间小于3毫秒”。

概率模型检验和概率编程系统作为不同的社区发展起来，有着不同的目标，尽管它们所使用的分析技术非常相关。概率程序的目标是表示（并建模）一个概率分布。其观点是贝叶斯式的，通常概率程序会从“先验”分布中为变量赋值，然后通过 observe 语句约束变量间的关系，程序的目标是表示一个通过观测条件化先验分布而得到的“后验”分布。概率推断的目标（如在概率编程系统中实现的那样）是计算该后验分布的适当表示形式，或计算关于该后验分布的函数期望值。相比之下，概率模型检验的目标是进行验证，即对包含概率组件的系统进行建模，并验证那些对系统所有可能行为设定定量界限的属性。

然而，尽管目标不同，这两个社区仍使用相关技术。例如，PRISM 使用多终端决策图 (MTDDs) 对有限状态概率模型进行符号分析 [14]，而代数决策图 (ADDs) 已被概率编程系统用于执行后验推断 [11]，也被贝叶斯网络用于通过变量消元进行推断 [9]。因此，我们相信概率编程和概率模型检验社区可以相互借鉴彼此的经验。

机器学习中的其他方法。当前的概率编程方法深受机器学习中贝叶斯方法的影响。将概率程序视为生成模型，从先验分布开始，并将程序语义定义为经过观测条件化后的后验分布，这种哲学观点是典型的贝叶斯式。探索用语言表示来自机器学习其他子社区（如优化社区）的方法是有趣的，该社区已构建了各种用于大规模机器学习的可扩展工具（例如参见 [28]）。即使在当前概率程序的语义（即贝叶斯式）下，如果我们的目标是找到后验分布的众数（例如用于计算最大似然估计），那么在对概率程序进行适当的平滑变换以确保后验分布连续之后，梯度下降等优化技术可能是适用的。这是一个有前景的方向，因为优化技术比第6节讨论的搜索技术（如MCMC）更具可扩展性。

非确定性。非确定性是一种强大的建模工具，可用于处理未知信息，以及在细节不重要的情况下指定抽象。例如，考虑图17中的两个程序。图17左侧的程序模拟了一个未知值被用作均值的情况，我们仅知道该均值是 {50, 51, 52, 53, 54, 55} 中的某一个值，但不知道具体是哪一个。目前，大多数概率编程系统都无法表示（因而也无法分析）这样的模型。取而代之的是，使用基于概率选择的近似模型，如图17右侧所示。区别在于，在右侧程序中，均值是从集合 {50, 51, 52, 53, 54, 55} 中均匀随机选取的。两个程序的一个重要区别是，左侧程序的含义是一组高斯分布（每个分布有不同的均值），而右侧程序的含义是一个单一的高斯分布，其均值由另一个分布决定。

非确定性的使用在马尔可夫决策过程 (MDP) 中也是基础性的，MDP 在控制理论 [6] 中被广泛用于控制器综合的建模问题。在这种情况下，模型中有多个点需要做出非确定性选择（并表示为 MDP），控制器综合的目标是提出一种所谓的“策略”，该策略将系统的状态映射到控制器应做的非确定性选择上，以最大化某个目标函数（通常指定为系统运行过程中获得奖励的某种聚合）。此类控制器综合算法（如策略迭代或价值迭代）在 MDP 文献中广为人知，并已在控制器综合工具 [6] 以及概率模型检验器（如 PRISM [36]）中实现。然而，将非确定性作为一种建模工具来表示概率程序中的未知量并不常见。提供这样的功能可以在许多情况下表达更自然的模型。然而，表示和推断一组分布比处理单个分布要复杂得多，因此在概率程序中添加非确定性并仍能提供可扩展的推断，面临着诸多技术挑战。

连续时间建模。连续时间模型（如 CTMC）是化学、生物化学、群体遗传学以及性能分析、排队论等领域中的基本模型。在 CTMC 中，概率选择不是在选项之间，而是在时间上。此类模型中的事件在时间上随机发生（通常是指数分布），不同事件相互竞争，当第一个事件在某个状态下发生时，状态转移便会发生。虽然我们在第3节中展示了一种在概率程序中编码连续时间的方法（参见图10中对 Lotka-Volterra 种群模型的编码），但该方法因两个原因而不令人满意。首先，该方法是非组合式的。如果我们想在第3节种群模型的三个反应基础上再增加一个反应，图10中的概率程序就需要进行全局修改，必须重写整个程序。这是因为图10中的程序将时间建模为一个变量，并在每个状态下计算启用的转换集，然后通过案例分析来计算每个状态的总速率和均匀化。其次，已知均匀化方法在某些反应速率极低而另一些极高时效果不佳。因此，一种更原生的实时编码方式在组合性和更高效、可扩展的推断方面都会带来益处。然而，添加时间会复杂化概率程序所需的语义和工具，因此必须谨慎进行，以免导致整个系统复杂性爆炸。

工具与基础设施。概率编程的目标是帮助大量具备领域专长但缺乏机器学习知识的程序员。在这一目标成为现实之前，工具和基础设施方面还需要多项进步。我们在此概述了一些此类进步的方向。首先，探索从数据中（在程序员的帮助下）学习概率程序结构是有趣的。类似的想法已在贝叶斯网络 [25] 和马尔可夫逻辑网络 [20] 的结构学习中被探索过。让程序员勾勒出程序的大致框架，然后由系统自动填充细节，将极大地提高可用性。其次，从编译器、推理系统到运行时基础设施的整个工具链都需要多项改进。编译器需要实现针对概率程序的常见编译器优化，运行时需要利用当今 GPU 和云服务提供的大规模并行能力。需要向程序员提供诊断信息，以帮助她识别编程错误并提高所编写程序的质量。在这些领域取得实质性进展，需要编译器分析、机器学习和面向程序员及数据科学家的可用性研究之间的协同作用。

原文链接：https://www.pure.ed.ac.uk/ws/files/19355513/Gordon_Henzinger_ET_AL_2014_Probabilistic_Programming.pdf