近似概率编程文献综述
摘要：概率编程是一个新兴的编程范式，在概率编程的推理过程中，近似算法可以大大优化效率。概率编程中的近似算法主要有边界近似算法和模拟近似算法。边界近似算法通过计算查询为真的所有可能世界的子集或超集，可以得到查询成功的概率的上界和下界。模拟近似算法通过采样随机产生大量的可能世界。当查询在某个样本片断上成立，就可以从此样本中计算查询成功的概率。我在PPL课程学习中产生了对概率编程的兴趣，收集了一些资料，希望与大家一起学习了解一下这块知识。
关键词：近似概率编程、模拟采样、近似边界
1 研究意义
概率编程（Probabilisticprogramming）本身是一个新兴的编程范式，这一编程范式的含义在于编程者可以在程序中指定概率模型并由概率程序自动进行这些模型的推断[1]。概率编程代表了统一概率模型和传统通用编程的一种尝试，传统的概率验算停留在纸面上，而概率编程可以动态地根据概率规则做概率运算。这使得概率模型可以更加容易并更广泛得被应用于建立在面对不确定时做出决定的系统。
概率编程有两类应用很广的模型范式，第一类是在给定约束条件下使得某事件发生概率的最大化或最小化，第二类模型是约束条件为概率信息，在此环境下进行编程[2]。无论是哪一种概率编程模型，传统的概率编程的目标是得到精确的解。但对于一些处于高阶空间的问题来说，求得精确解的时间代价与空间代价都是不可接受的。那么，根据模拟或者边界夹逼而高效得生成具有置信概率的近似的成果或边界便是一种不错的解决思路。由此催生出了近似概率编程这一新兴领域。
这里作者希望通过举一个概率编程的例子来说明近似概率编程的大致含义与意义。
考虑以下概率模型（ProbLog语言）：
0.4:: A //(我及时取外卖)0.5:: B(X) //(有外卖小偷)0.2:: B(我) //(外卖小偷选择了我的外卖)D(吃上外卖): - AD(吃上外卖): - !BD(吃上外卖): - B(X)，X != 我
概率模型解释：
前三条是概率事实，即带概率标记的基事实。随后三条是规则，当我及时取外卖的时候可以吃上外卖，当没有外卖小偷的时候我可以吃上外卖，当外卖小偷没有选择偷我的外卖的时候可以我吃上外卖。在给定的概率事实与规则约束下，现需要求解我能吃上外卖的概率是多少。
经典概率程序求解：
以基于析取范式的概率程序为例，
{F1{A,!B()},F2{A,B(X)},F3{A,B(Me)},F4{!A,!B()},F5{!A,B(X)}}
在这五种可能世界下，我们可以取到外卖，则我们取得外卖的概率就是将所有接受的可能世界的概率累加。即
0.4\*0.5 + 0.4\*0.5\*0.8 + 0.4\*0.5\*0.2 + 0.6\*0.5 + 0.6\*0.5\*0.8 =0.76
近似概率程序：
但是随着事实数量与规则数量的增加，多项式时间的精确求解算法在现在是没有人可以给出的。近似算法大致可分为两类，其一是基于边界的近似推理，其二是使用采样的近似推理。
什么是基于边界的近似推理呢？以上面的模型为例，当没有外卖小偷时，即!B()时，结果一定为true，那么我们可以得到这一边界:
P(吃上外卖) ≥ 0.5
那么什么是使用采样的近似推理呢？在这类方法中，采样用于随机产生大量的可能世界。当查询在某个样本片断上成立，就可以从此样本中计算查询成功的概率。以上面的模型为例，我们可以连续一年定外卖并记录是否取得外卖的结果，并根据结果的分布情况与收敛情况对结果的真实概率进行估计。
随着概率编程不断应用到自然语言处理、生物信息学、活动和行为识别、机器人、网络分析和音乐分析等方面[3]，计算性能越来越成为广泛应用的瓶颈。而在许多的应用场合，确定一个合理精度的近似结果就足以解决问题，反而精确解会消耗大量计算资源且丧失实时性。所以对于现有概率算法的近似优化，对近似算法的误差估计等研究工作对于该领域发展具有重大意义。
2研究背景和发展脉络
2.1 研究背景
概率编程已有20多年的历史，近年来该领域的研究进展非常迅速，涌现出一大批研究成果。
当然，有关概率编程的研究是建立在不同的层次上的。
在最抽象的层面上，研究对象主要是概率逻辑程序设计语言，也就是如果抽象地表达概率语义。例如有独立的选择逻辑程序[4]、随机逻辑程序[5]、贝叶斯逻辑程序[6]、带注释析取的逻辑程序[7]、CP逻辑程序[8]等等。
随后是概率逻辑推理方面的研究，近似思想几乎始终伴随着各种推理方法。各种推理算法在他们的内部都有相应的近似修约方法。简而盖之，近似算法是在概率编程推理过程中的一种范式与思想，与各种精确算法存在紧密联系。
比如Vennekens与Bruynooghe等人的基于CP逻辑定义语义的向前推理法，其推理过程可以表示为向前推理树[8]，从根节点开始，使用概率事实得到子节点，根据程序将相应的概率值标记在对应的边上。达到一个完全的可能世界则视为叶节点。那么其中运用修约可以在到达完全的叶节点之前便停止树的增长，达成性能的优化。
在推理逻辑中使用比较广泛的还有向后推理、加权模型计数归约和提升推理。向后推理，也叫作SLD方法或证明。该方法从一个查询开始，使用规则反方向进行推理。近似算法体现在SLD中便是通过提前结束来完成近似修约。加权模型计数归约是Fierens等人从逻辑的角度提出一种概率逻辑程序的推理方法[9]，该方法利用逻辑程序的命题逻辑语义将MARG推理（在给定条件e下，求每个基原子q的边缘概率）归约到加权计数模型，而通过基原子的合并和给定条件的放缩可以达成基于加权模型计数归约的近似算法。可见在这些概率推理模型中，近似算法都有用武之地。
2.2 近似概率编程发展脉络
前文已经提到，近似编程中有边界近似与模拟近似两大方向。这两种近似思想被运用于概率编程是早在1974年的事情[10]，这意味着近似概率编程在最早阶段就伴随着概率编程。1974年Prekopa等人开创性地在概率性质上下文中使用了模拟与优化混合使用的算法[10]。这些工作是概率编程领域中最早的近似方面的尝试。
然而究其根本，近似概率编程的数学基础研究早在1967年就已经开展。析取-合取范式的研究是近似概率编程乃至更大范围意义上的概率编程的重要数学基础，这方面的重要工作由Takas等人在1965年的研究奠定[11]，Prekopa等人在1995年对于这个领域的数学如何运用于概率编程做了比较完整的提取与总结[12]。
随后在这一领域，边界近似法（bounding approximation）与模拟近似法（simulation approximation）两种近似思想的算法研究分别开始被越来越多的研究者研究。
在边界近似方面，随着时间推演，研究者逐步地对更高的近似维度与更精确的预测上下界展开研究。我们能看出一条非常明显的研究脉络。早在1967年，Dawson与Sankoff等人就对于二阶近似的下界范围进行了分析[13]。随后由Kewel在1975的工作和Sathe等人在1980年的工作得出了二阶近似的上界[14]。数年之后，三阶近似和四阶近似的精度估量由Prekopa与Boros等人在1989年研究得出[16]。最终，广泛的高维算法与Bonferroni边界确定方法由Prekopa在1988年提出设想[15]，并在2001年提出更加完善的理论[17]。
在模拟近似方面，碍于计算机系统的运算性能与存储性能，研究起步不算早。但我们也能看出清晰的研究脉络。在模拟近似研究的初始阶段，研究者研究得出了较多关于模拟分析正态类函数的结论，这主要归功于Deak的课题组在1980年-2002年[18] [19] [20] [21] [22]陆续做的研究。接下来，为了提升算法的普遍适用性，Szantai在1986年和2000年提出了通过概率模拟预测相较于正态函数更为普通的函数的方法[23] [24]。基于以上两组研究者，1988年Gassmann等人提出了正态预测与通用预测的混合算法，并把这一集大成的概率模拟近似算法称为DSG方法(Deak，Szantai，Gassmann三者名字的缩写)
[25]。随后在2002年Gassmann进一步改进DSG算法，尤其在多变量模拟预测上提出了先锋性的见解[26]。
3.目前研究进展
近年来，概率编程越来越多地走向实际应用领域而不再只是停留在理论层面。例如在一个50行的概率计算机视觉程序被用于基于人脸的2D图像来生成这些人脸的3D模型[29]。在医学领域，Stanley E等人使用Turing.jl概率编程系统构建贝叶斯学习模型来分析药物的肝脏损失风险并取得重大成就[30]。就在最近的，斯坦福大学的一个研究组基于概率编程开发了实用的Gen概率编程库，已经被用于各种视觉和机器人任务[31]。在这些实际应用中，数据量与数据维度都是相当庞大的，这使得近似算法在概率编程中的地位越来越重要。
我们已经知道近似概率编程呈现明显的双线发展脉络，分别是边界近似与模拟近似，两者思路相异。我们这里也分这两部分介绍。
3.1 边界近似概率编程
关于目前的边界近似概率算法，现阶段很多成果是基于用向后推理得到的DNF（析取范式）进行近似优化得到的，关于向后推理，研究背景一章有所介绍。比如Angelika
Kimmig等人在的研究工作[28]。他们的研究是基于Prolog的，在Prolog中，概率事实可以用它们在属于不同的随机抽样程序下的相互独立的概率变量来标记。所以在近似过程中，向模型提出大量的不同请求是相当方便的。首先，在向后推导中，会生成推导树。
这类推导树的每条边代表特定约束下发生某种情况的概率，叶子节点则代表一种可能世界。通过迭代的贝叶斯概率计算，精确的解是可以得到的。但是据Kimmig分析，哪怕应用于一个很小的网络，得到精确解的算法时间复杂度将达到O(106)，这是实际应用中难以忍受的计算代价。在论文中，Kimmig详细分析了DNF范式如何作边界近似。其数学思想基础是由Poole在1993年奠定的[32]。其主要思想是将完全形态的LSD树修约为不完整的LSD树，树枝仅仅分叉到给定的精度阈值之内，这样可以省略大量的情况讨论。这一方法中，使用者即可以确定上界也可以确定下界。当算法只统计发生可能性高于阈值的事实时，所得到的是下界；当算法将所有到达了阈值而没有继续分类讨论的分支都统计进来时，便得到了上界。
3.2模拟近似概率编程
关于模拟近似算法，近来出现的纯理论研究并不多，更多的是如何在各种概率编程模型中实现蒙特卡洛等模拟过程。相较于边界近似，模拟近似在许多概率逻辑语言中比较流行。而其数理基础已经由概率统计学研究得较为深入。其基本实现思路是通过采样随机产生大量的可能世界。当查询在某个样本片断上成立，就可以从此样本中计算查询成功的概率。例如，在向后推理过程中只需随机选择概率事实的真值，就可以对其进行采样，直到发现证明或者穷举所有的选择时采样结束[3]。例如Fierens和Van
den
Broeck在的一项研究中，使用MC—SAT在CNF（合取范式）上做近似的WMC[33]。他们研究了如何从图形模型集合中作经典的推理（经典CNF）和可以用于概率逻辑程序的学习任务。他们贡献了一个加权布尔公式，该公式可基于程序和查询转换到概率证明。其次他们贡献了一套动态的参数学习算法，可以使程序对不同任务进行充分研究。这系列算法采用期望最大化目标，并被建立在已开发的推理算法之上。结果表明，推理算法在概率逻辑规划的基础上得到了改进，从解释中学习概率逻辑规划的参数是可行的[33]。而Milch等人则看向了另一个经典的概率推理算法，他们在BLOG中使用向前推理来产生样本。他们贡献了一种在无环形定义的约束语境下，指定一个唯一的概率分布后可以产生变化的和无限可能世界的方法。此外，他们还贡献了完整的存在于语言内部的推理算法。并且还引入了一种处理证据的概率形式的Skolemization[34]。此外比较有分量的工作还有Gutmann等人在分布子句中使用向前推理来产生样本[35]。Arora等人在BLOG使用MCMC产生样本[36]。Moldovan等人在ProbLog中使用MCMC产生样本[37]。
3.3 k-Best
此外，最近还有科学家致力于结合起边界近似概率算法和模拟近似概率算法，比较有名的例如Stefano
Bragaglia和Fabrizio
Riguzzi在的工作[27]。他们的工作目的是在LPADs语言上发展高效的概率推理算法。LPADs，即带注释析取的逻辑程序，是近来一种很有前途的概率归纳逻辑编程语言，这种语言本身是基于Prolog的。这项研究最引人注意的点在于，采用k-Best算法来估算概率请求的结果下界。而k-Best算法的思路是融合了边界近似与模拟近似的创新思路。这个k-Best算法首先使用蒙特卡罗算法对可能世界空间进行巧妙抽样来模拟估计子世界概率。随后识别k个最具可能的世界进行详细计算得到一个大致的估算值。由于是修约掉了发生概率较低的可能世界，所以此方法可以达成下界的估计。通过理论分析，这种k-Best算法对于偏重分支型的概率问题具有较好的近似精度。经过，实际数据测验后，这种k-Best算法的下界相对误差基本可以控制在5%以内，但和模拟近似的问题一样，这些误差的精确度是实验得出了，没有严格的数学支持，在对于精确要求高的应用场合下使用是具有风险的。
4进一步发展方向概述
多年来，许多研究者提出了各种概率逻辑程序语言，取得了丰富的研究成果，可以预见，概率逻辑程序的研究将是一个非常有前景的领域。虽然近似概率编程已经取得了许多丰富的成果，但是仍然称不上一个十分成熟的技术，还有很大的挑战，可以在以下几个方面进行进一步研究。
其一是加大与各学科的交叉，近几年，近似概率编程越来越与具体应用场合相结合，毕竟不同应用场合下的数据集特征都是不同的。针对不同的数据特征制定更加精确的近似策略是近来很显著的发展方向。Van Der Heijden,Lucas等人利用CP逻辑和动态贝叶斯网络生成Allen的区间微积分来对疾病的产生过程进行模拟建模[38]。Ingo Thon等人通过将CP逻辑专门化来表示关系状态，以此描述序列上的概率布，并采用马尔可夫假设，使得推理和学习变得更容易处理和有效。而为一个游戏（Travian）建立了AI模型[39]。，Wang等人则将概率近似编程结合进了数据库领域，设计了一个ProPPR对大且不确定的知识库进行推理和学习[40]。
其二是提升推理逻辑的效率，这也是近似概率编程一路以来的主线任务。例如前文提到的引入MCMC近似推理方法[37]，以及融合了模拟与边界的k-Best算法[27]，都揭示了概率编程的近似方法不断推陈出新的过程。区别于传统的近似推理，也有科学家提出在数据挖掘中引入概率推理的学习机制[33]，实现概率逻辑程序和数据挖掘的融合以大大提升效率，但目前这一设想还在研究阶段[3]。
5我的见解与感想
如果说程序是生活的模拟的话，那么概率编程自然是最贴近生活的。每个人，对生活中的什么东西是确定的呢？我们做出的每个决定不都是在考虑到诸多概率事实后在那个时间点上做出的局部最优解吗。但是我们的每个决定都要面面俱到地考虑清楚吗，那可能点个菜都得半小时了，事实上我们不过是早早估算一下，就做出了某个决定。所以近似概率编程思想在生活中是处处得以体现的。这是从生活的角度上去谈论概率编程。
从应用角度来说，近似思想在概率编程中的重要性更是不言而喻。几乎没有哪个现实中的概率编程项目是求精确解的。因为概率的分支结构天然使得算法规模是树状生长的，其复杂度是随规模指数增长的。当我们用概率模型来对疾病、路径、图像等等对象建模时，虽然可以有数据分析学的降温操作，但是得到的数据一般维度还是较高的。我暑假做过一段金融科技的研究，每只股票都有47个维度的数据。那么在这样的数据规模下，近似优化是不可避免的。
从概率编程语言角度来说，我个人的见解如下：无论是基于Java开发设计的Dimple[42]和Chimple[43]，基于Prolog的PRISM[44]，还是基于NET架构设计的语言[45]，又或是独立的概率编程语言Stan[41]。他们之间的差别更多是编译层面和语法层面的区别，在核心的概率编程方面，其表达方式较为类似。有概率事实作为基础变量，规则作为推演过程的指导知识，任务也基本分为SUCC任务（计算基查询成功概率）,MARG任务（在给定条件下每个基原子的边缘概率）,MAP任务（给定条件下找到最有可能的真值赋给原子）,MPE任务（对于某个条件找到一个最有可能世界）,VIT任务（查询某个事件的可能性证明）。其根本原因在于，现今的概率语义基本是以Sato的分布语义为基础的[46]，自然实现效果也大同小异。
如果说不同的概率逻辑程序语言可以看作是对这一领域的核心概念(如概率选择)的不同实现，则概率编程的核心就是推理，推理的重要部分便是近似。本文介绍了不同的概率推理机制和研究脉络（主要是边界近似和模拟近似），并讨论了它们支持概率逻辑程序不同领域的适合度。我个人认为这是概率编程这门学科的核心所在，所以我选择针对这方面做综述。我认为接下来可以借鉴神经网络、联邦学习、数据挖掘等原理来更深刻地模拟学习概率事实的过程，而不仅仅停留于可解释的参数生成。这样生成单一函数的参数，也许对某个数据集表现不错，但是可移植性较差，不如动态地生成概率判断网络。
总的来说，概率编程是非常新颖非常迷人的研究领域，许多传统的任务经过概率的描述可以由非常简洁优雅的模型来描述。但仍然还不成熟，还有很大的挑战。我写这篇综述是为了更深入地学习了解该领域，为将来的研究工作奠定基础。
参考文献：
[1] Probabilistic programming does in 50 lines of code what used to
take thousands. . April 13, [-04-13].
[2] Prekopa, Probabilistic Programming.
[3] 谢刚，张文生. 概率逻辑程序研究综述 [J]. 山西大学学报,3(11)
[4] Poole D．The independent choice Logic and Beyond[J]
，：222—243
[5] Muggleton S．Stochastic Logic Programs[J]．Advance in Inductive
Logic Programming, 1996, 32:254-264
[6] Kersting K，De Raedt L．Basic Principles of Learning Bayesian
Logic Programs[J]．Probabilistic Inductive Logic Programming,
[7] Vennekens J，Verbaeten s，Bruynooghe M．Logic Programs with
Annotated Disjunctions [J]
[8] Vennekens J，Denecker M，Bruynooghe M．CP—logic：A Language of
causal Probabilistic Events and Its Relation to Logic,
[9] Fierens D，Van den Broeck G，Renkens J，Inference and Learning in
Probabilistic Logic Programs using weighted Boolean formulas [J]
[10] Prekopa, A. (1974b). Programming under probabilistic constraints
with a random technology matrix.
Matematische Operationsforschung und Statistik, Ser. Optimization 5,
109-116
[11] Takacs, L. (1967). On the method of inclusion and exclusion. J.
of the Amer. Math. Association 62,
102–113.
[12] Prekopa, A. (1995). Stochastic Programming, Kluwer Academic
Publishers, Dordrecht, Boston.
[13] Dawson, D., A. Sankoff (1967). A inequality for probabilities.
Proc. Am. Math. Soc. 18, 504–507.
[14] Kwerel, S.M. (1975a). Most stringent bounds on aggregated
probabilities of partially specified
dependent probability systems. J. Am. Statist. Assoc. 472–479.
[15] Prekopa, A. (1988). Boole-Bonferoni inequalities and linear
programming. Operations Research 36,
145–162.
[16] Boros, E., A. Prekopa (1989). Closed form two-sided bounds for
probabilities that exactly r and at
least r out of n events occur. Math. Opns. Res. 14, 317–342.
[17] Prekopa, A. (2001b). Discrete higher order convex functions and
their applications. Generalized
convexity and monotonicity, in: N. Hadjisavvas et al. (eds.), Lecture
Notes in Economics and Mathematical Systems, Springer, Berlin, pp.
21–47.
[18] Deak, I. (1980). Three digit Accurate Multiple Normal
Probabilities. Numerische Mathematik, 35,369–380.
[19] Deak, I. (1990). Random Number Generators and Simulation, Akade
miai Kiado , Budapest.
[20] Deak, I. (1998). Linear regression estimators for multinormal
distributions in optimization of stochastic programming problems. EJOR
III, 555–568.
[21] Deak, I. (2000b). Subroutins for computing normal probabilities
of sets – computer experinces. Annals of Oper. Res. 100, 103–122.
[22] Deak, I. (2001). Two-stage stochastic problems with correlated
normal variables: computational experiences. Annals of Oper. Res., to
appear.
[23]Szantai, T. (1986). Evaluation of a special multivariate gamma
distribution. Mathematical
Programming Study 27, 1–16.
[24]Szantai, T. (2000). Improved bounds and simulation procedures on
the value of the multivariate
normal probability distribution function. Annals of Oper. Res.100,
85–101.
[25]Gassmann, H.I. (1988). Conditional probability and conditional
expectation of a random vector, in:Y. Ermeliev, R.J.-B. Wets (eds.),
Numerical Techniques for Stochastic Optimization, Springer Verlag,
Berlin, Heidelberg, New York, pp. 237–254.
[26]Gassmann, H.I., I. Deak, T. Szantai (2002). Computing multivariate
normal probabilities. J. of Computational and Graphical Stat. 11,
920–949.
[27] Stefano Bragaglia, Fabrizio Riguzzi, Approximate Inference for
Logic Programs with Annotated Disjunctions
[28] Angelika Kimmig，Vıtor Santos Costa, Ricardo Rocha, Bart Demoen,
and Luc De Raedt On the Efficient Execution of ProbLog Programs
[29] Hardesty, Larry. Graphics in reverse. April 13,
[30] Predicting Drug-Induced Liver Injury with Bayesian Machine
Learning
[31] MIT’s Gen programming system flattens the learning curve for AI
projects. VentureBeat. -06-27 [-06-27]
[32] Poole, D.: Abducing through negation as failure: stable models
within the independent choice logic. J. Log. Program. 44(1-3) (2000)
5–35
[33] DAAN FIERENS,GUY VAN DEN BROECK,JORIS RENKENS,DIMITAR SHTERIONOV
Inference and learning in probabilistic logic programs using weighted
Boolean formulas
[34] Brian Milch, Bhaskara Marthi Probabilistic Models with Unknown
Objects
[35]Bernd Gutmann,The Magic of Logical Inference in Probabilistic
Programming
[36] Nimar S. Arora, Rodrigo de Salvo Braz, Erik B. Sudderth, Stuart
Russell Gibbs Sampling in Open-Universe Stochastic Languages
[37] Bogdan Moldovan, MCMC Estimation of Conditional Probabilities in
Probabilistic Programming Languages
[38] Maarten van der Heijden 1, Peter J F Lucas Describing disease
processes using a probabilistic logic of qualitative time
[39] Ingo Thon Stochastic relational processes: Efficient inference
and applications
[40] William Yang Wang, Programming with Personalized PageRank:A
Locally Groundable First-Order Probabilistic Logic
[41] Stan. mc-.
[42] Dimple Home Page. .
[43] Chimple Home Page. .
[44] . . Microsoft.
[45] PRISM: PRogramming In Statistical Modeling. rjida.meijo-u.ac.jp.
[July 8, ].
[46] Taisuke SATO, PRISM : A Languag e fo r Symbolic-Statistica l
Modeling 1997
A review on approximation probabilistic programming
Abstract:
Probabilistic programming is a new programming paradigm, in the process
of probabilistic programming reasoning, approximate algorithm can
greatly optimize efficiency. Approximation algorithms in probabilistic
programming can be divided into boundary approximation algorithm and
simulation approximation algorithm. The boundary approximation algorithm
calculates the subsets or supersets of all possible worlds for which the
query is true to obtain the upper and lower bounds of the probability of
the query’s success. The analog approximation algorithm randomly
generates a large number of possible worlds through sampling. When a
query is valid on a sample fragment, the probability of a successful
query can be calculated from that sample. I have developed interest in
probabilistic programming in PPL courses and collected some materials. I
hope to learn about this knowledge with you.
Key words:Approximate probabilistic programming, analog sampling,
approximate boundaries
sample fragment, the probability of a successful
query can be calculated from that sample. I have developed interest in
probabilistic programming in PPL courses and collected some materials. I
hope to learn about this knowledge with you.
Key words:Approximate probabilistic programming, analog sampling,
approximate boundaries
