概率式编程

在过去几年中，编程语言和机器学习社区在概率规划的保护下开发了一组共享的研究兴趣。 这个想法是，我们 可能能够“出口”强大的PL概念，如抽象和重用到统计建模，这是一个奥秘和艰巨的任务。

（您可能想阅读这些演讲笔记的最新版本，源代码在GitHub上，如果您注意到任何错误，请打开PR。）

1. 是什么和为什么

1.1 概率式编程不是

直观上，概率式编程不是关于编写具有概率性的软件。 例如，如果你的程序调用rand（3）作为工作的一部分 ，它打算做 - 比如加密密钥生成器或ASLR在操作系统内核的实现，甚至模拟退火优化器的电路设计 - 这些都是可以的，但这不是这个主题关心的。

最好不要想到“写软件”。 通过类比，传统的语言如C ++，Haskell和Python在哲学上显然是非常不同的， 但你可以想象（如果强制的话）使用任何他们写一个编目系统为你的扫描图片或一个伟大的新的LaTeX替代品。 对于特定的领域，一种可能比另一种更好，但它们都是可行的。 这对概率式编程语言（PPL）不一样，它更像 是Prolog：肯定的，它是一种编程语言 - 但它不是用来编写完整软件的正确工具。

1.2 概率式编程是

相反，概率式编程是一个统计模型的工具。这个想法是借鉴了编程语言的世界并将他们应用到设计和使用 统计模型的问题。专家用纸上的数学符号手动构建统计模型，但它是一个专家级的过程，很难用机械推理来支持。 PP的关键洞察是，统计建模可以，当你做到足够，开始感觉很像编程。 如果我们实现跨越并且实际上使用真 正的语言来建模，许多新工具变得可行。 我们可以开始自动完成为每个实例写一篇论文的任务。

这是第二个定义：一种概率式编程语言是一种普通的编程语言，它使用随机数和很多相关工具来帮助你理解程 序的统计学行为。

这两种定义都是准确的。他们都从不同的角度强调了同一个核心的思想。哪一个对你更有兴趣取决于你期望使用 PP做什么。但不要因为PPL程序看起来像目标是运行程序并获得某种输出的普通软件实现那样而分心，因为PP的 目标是分析，而不是执行。

1.3 一个例子：论文推荐

作为一个运行的例子，让我们想象一下，我们正在建立一个系统，根据他们采取的类，向学生推荐研究论文。 为了保持简单，让我们说世界上只有两个研究主题：编程语言和统计/机器学习。每张纸都是PL纸，统计纸或 两者。我们将考虑Cornell的三门课程：CS 4110（编程语言），CS 4780（机器学习）和一个虚构的选修课， “CS 4242”，概率编程。

很容易想象机器学习应该适用于这个问题：你的课程安排所显示的区域的混合应该说明你想要阅读的论文。问 题是，确切的关系可能很难直接推理。明显地，4780意味着你更可能对统计数据感兴趣，但究竟有多少可能性？ 如果你注册了4780，因为它是唯一的类，适合你的日程表怎么办？我们对于那些只使用虚拟CS 4242而不是真 正课程的人做什么 - 我们只是假设他们是50/50 PL / stats人？

####1.3.1 对问题建模

接近这个问题的机器学习方法是使用随机变量对情况进行建模，其中一些是潜在的。 关键的见解是，图1中的 箭头没有多大意义：它们不真正代表因果关系！ 这不是4110让你对一个给定的纸更感兴趣; 还有一些其他因 素可能导致这两个事件。 这些是用于解释情况的模型中的潜在随机变量。 允许自己的潜在变量使得直接解释 问题更容易。

这里有一个模型，引入了两个潜在的变量，每个人对统计和编程语言的兴趣。 我们将得到更具体的模型，但现 在的箭头至少是有道理的：它们的意思是一个变量以某种方式影响另一个。 因为我们都知道你不会接受每一个 你感兴趣的类，我们包括第三个隐藏因素：你是多么忙，这使你不太可能去任何类。

该图描绘了贝叶斯网络，其是其中每个顶点是随机变量并且每个边缘是统计相关性的图。 没有它们之间的边的 变量在统计学上是独立的。 （也就是说，知道其中一个变量不会告诉你其他变量的结果）。

为了完成模型，我们还将绘制节点和边以描述我们的潜在利益变量如何影响纸张相关性：

这个想法不是我们会问人们他们的兴趣水平和业务是什么：我们会尝试从我们可以观察到的推断。 然后我们可 以使用这个推断的信息来做我们实际想做的：猜测给定学生的论文相关性。

这是一个简单的模型的很多数学！它甚至不是硬的部分。硬和有用的位是统计推断，其中我们基于我们的观 察猜测潜变量。统计推理是机器学习研究的基石，这不容易。传统上，专家为他们手动设计的每个新模型设计 定制推理算法。

即使这个微小的例子应该展示手动统计建模的苦差事。它就像编写汇编代码：我们做的东西感觉有点像编程， 但没有抽象，没有重用，没有描述性变量名，没有意见，没有调试器，没有类型系统。看看类注册的方程，例 如：我厌倦了写出所有的数学，因为它的重复。这显然是一个老式编程语言抽象的工作：一个函数。 PPL的目 标是将统计世界中你已经知道和喜欢的编程语言的旧的和强大的魔法。

2. 基本概念

为了介绍概率编程语言的基本概念，我将使用一个名为webppl的项目，它是嵌入在JavaScript中的PPL。 你可以在概念性编程语言的设计和实现，诺亚古德曼和斯坦福的AndreasStuhlmüller的一本正在进行的书 中阅读更多关于这门语言。 这是一个很好的语言作为介绍使用，因为你可以在你的浏览器中播放它。

2.1 随机基元

使一门语言成为概率式的第一件事是一个获取随机数的源语集合。从一这点上，PPL看起来像是任何古老的调用 rand的过程式语言。这里有一个令人难以置信的无聊的webppl程序：

var b = flip(0.5);
b ? "yes" : "no"

这个无聊的程序只是使用公平的硬币抛出的结果返回一个字符串或另一个。 它的工作原理就像一个普通的程序， 可以访问一个翻转函数，用于生成随机布尔值。 像翻转这样的函数有时被称为基本随机基元，它们是这些程序 中所有随机性的来源。

如果你在webppl的编辑器里运行这个小程序，你将会看到它正如你所预料得那样：有时候输出”yes”，有时候 输出”no”。

当我们意识到webppl可以代表整个分布而不是独立的变量，情况变得有趣了。webppl语言有一个Enumerate 操作，可以输出一个用函数定义的分布的所有概率：

var roll = function () {
  var die1 = randomInteger(6) + 1;
  var die2 = randomInteger(6) + 1;
  return die1 + die2;
}

var dist = Enumerate(roll);
print(dist);
viz.auto(dist);

你可以得到一个所有可能的die的值在2到14之间和它相对应的概率的输出。viz.auto控制webppl的浏览 器内部接口来展示一幅漂亮的图片。

这可能看起来并不是那么令人惊奇，因为你可以通过一次又一次调用roll函数用你喜欢的语言写一个Enumerate。 但事实上，Enumerate做了更强大的一些事。它不是抽样执行以获得分布的近似; 它实际上枚举了函数的 每个可能的执行以获得精确的分布。 这开始揭示概率式编程语言的重点：分析PPL程序的工具是重要的部分，而不 是直接执行程序。

2.2 我们的示例模型在webppl

这已经足够码出我们论文推荐模型的数学了。我们可以写一个函数来解码相关度部分和选课部分，然后我们可以 随机生成学生信息来测试它。

// Class attendance model.
var attendance = function(i_pl, i_stats, busy) {
  var attendance = function (interest, busy) {
    if (interest) {
      return busy ? flip(0.3) : flip(0.8);
    } else {
      return flip(0.1);
    }
  }
  var a_4110 = attendance(i_pl, busy);
  var a_4780 = attendance(i_stats, busy);
  var a_4242 = attendance(i_pl && i_stats, busy);

  return {cs4110: a_4110, cs4780: a_4780, cs4242: a_4242};
}

// Relevance of our three papers.
var relevance = function(i_pl, i_stats) {
  var rel1 = i_pl && i_stats;
  var rel2 = i_pl;
  var rel3 = i_stats;

  return {paper1: rel1, paper2: rel2, paper3: rel3};
}

// A combined model.
var model = function() {
  // Some even random priors for our "student profile."
  var i_pl = flip(0.5);
  var i_stats = flip(0.5);
  var busy = flip(0.5);

  return [relevance(i_pl, i_stats), attendance(i_pl, i_stats, busy)];
}

var dist = Enumerate(model);
viz.auto(dist);

运行这个程序会展示从观察到的数据得到的分布律。这不是很糟的使用，而且很有趣。我们可以看到，如果我们 对一个学生一无所知，我们的模型会说他极有可能不选取任何课程并对任何论文都不感兴趣。

2.3 条件控制

PPL另一个重要的部分是条件流的构造。条件控制允许你决定对一个程序给定的执行多大的权重。至关重要的是， 您可以在执行一些计算后通过运行选择执行的重要性。 您甚至可以将执行标记为完全不相关，有效地将执行过 滤到一个子集。

这种条件控制操作对于编码观察是特别有用的。如果你知道一个过程的结果，你可以使用条件来传达观察必须 是真的（或者可能是真实的）。让我们回到我们的骰子例子一个有价值的例子。 假设我们看到了第一个die， 它是一个4.我们可以对这些信息进行条件化，给出我们对总值的分布，因为一个骰子是4。

var roll = function () {
  var die1 = randomInteger(6) + 1;
  var die2 = randomInteger(6) + 1;

  // Only keep executions where at least one die is a 4.
  if (!(die1 === 4 || die2 === 4)) {
    factor(-Infinity);
  }

  return die1 + die2;
}

不出所料，除了结果8之外，分布是平坦的，这是不太可能的，因为只有一个含有4的辊可以产生该总量。像2 和12这样的结果有概率零，因为当一个骰子出现时它们不会发生。

如果，另一方面，我们不能看到任何一个骰子，但有人告诉我们，骰子上的总数是10。这告诉我们骰子本身的 价值？ 我们可以通过调整卷的结果编码这个观察。

var roll_condition = function () {
  var die1 = randomInteger(6) + 1;
  var die2 = randomInteger(6) + 1;

  // Discard any executions that don't sum to 10.
  var out = die1 + die2;
  if (out !== 10) {
    factor(-Infinity);
  }

  // Return the values on the dice.
  return die1 + "+" + die2;
}

2.4 实际推荐论文

让我们使用相同的哲学来产生推荐吧。这很简单：我们只要控制选择了一门课程的我们感兴趣的人。这里有一 个例子描述了我：我参加了我自己的课程，CS 4110,和PPL课程，CS4242，但是没有ML课程，4780.

// A model query that describes my class attendance.
var rec = function() {
  var i_pl = flip(0.5);
  var i_stats = flip(0.5);
  var busy = flip(0.5);

  // Require my conference attendance.
  var att = attendance(i_pl, i_stats, busy);
  require(att.cs4242 && att.cs4110 && !att.cs4780);

  return relevance(i_pl, i_stats);
}

（在这个例子中，我们定义了require to wrap factor（-Infinity），并完全消除了不满足条件的程序 执行。）对这个rec​​函数调用Enumerate最终给了我们一些有用的东西：这是一个更容易理解，如果我们一次只看一张纸：

return relevance(i_pl, i_stats).paper1;

突然，这是漂亮的漂亮！通过告诉调查员哪些执行与我们相关，它可以告诉我们它在这些条件下对数据的了解。 对我来说，我认为对大多数程序员来说，这已经是一个更自然的工具，用于表达概率模型。而不是仔细写下哪些 随机变量取决于哪些其他，你使用程序执行流建立那些依赖。

本节的要点：编写生成模型感觉非常舒适和直接，编程语言是记下生成算法的一个好方法。通过将这些简单模型 的推理负担转移到编译器和工具，我们已经成功地简化了我们的工作。

2.5 推导

Enumerate操作可能看起来不是很多，但它实际上是PPLs旨在解决的中心问题的一个实现：统计推断。特 别是在条件的存在下，推断一般概率程序是一个困难的问题。 想想Enumerate如何工作：它需要知道一个程 序的结果对程序的随机原始绘制的每一个评估。 不难看出这是如何成倍增长。 如果你引入浮点数，你甚至不 太清楚：如果你画一个介于0.0和1.0之间的数字，这是很多可能的估值 - 它不能表示为直方图。

Enumerate只是不会做的非平凡问题。 正是由于这个原因，PPL的高效推理算法是社区的一个巨大的焦点。 这里有一些其他的推理算法，不涉及探索一个程序的每一个可能的执行。

2.5.1 拒绝采样

第二个最明显的推理算法使用抽样。 想法是大量运行程序，在每次执行时为每个随机基元绘制不同的随机值。 应用程序的条件以加权每个样品，并将它们总计。与加权的相互作用使这种策略拒绝采样，所谓的，因为你拒 绝一些执行，当你达到条件声明。

webppl有称为ParticleFilter的内建策略，我们可以用以下例子来运行：

var sampled = ParticleFilter(rec('paper1'), 1000);

2.5.2 MCMC

拒绝抽样适用于小例子，但它在有条件的情况下运行内部麻烦。 它可以浪费大量的工作，采取无关紧要的样本 （即，他们注定要被拒绝，当他们打一个因素调用）。 存在更智能的抽样策略，其中最突出的是马尔可夫链蒙 特卡罗方法。

webppl标准库提供MCMC算法。 使MCMC正确和高效是PPL研究中的流行问题，并且全面讨论目前超出本讲座 的范围。