文档结构  
可译网翻译有奖活动正在进行中,查看详情 现在前往 注册?
原作者:未知    来源:www.cs.cornell.edu [英文]
CY2    计算机    2016-11-28    0评/829阅
翻译进度:75%   参与翻译: wuQAQ (21)

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

1. 是什么和为什么

1.1. 概率规划不是什么

相反的,概率性编程不是关于编写具有概率性的软件。例如,如果你的程序调用rand(3)作为工作的一部分,它打算做-如在加密密钥生成器或ASLR实现在操作系统内核,或者甚至simulated-annealing优化器的电路设计)-这是最好的,但这不是这个主题是相关的。

第 1 段(可获 1.6 积分)

最好不要想“编写软件(writing software)”。通过类比,如C ++,Haskell和Python这些传统语言,在原理上显然是非常不同的,但你可以想象(如果强制的话)使用他们任意一种语言为猫的图片或一个更好的新的可替代LaTeX系统编写编目系统。对于给定的范围内,它们可能一个比一个好,但它们都是可行的。不是用概率编程语言(PPL)。它更像是Prolog:肯定的,它是一种编程语言 - 但它不是正确的用于编写完整的软件的工具。

第 2 段(可获 1.25 积分)

1.2. 概率编程是什么

相反,概率编程是用于统计建模的工具。这个想法是从编程语言世界中借鉴的教训,并将其应用于设计和统计模型。专家们在纸上使用数学符号手工构建统计模型,但是这是一个专家级的过程,很难支持机器的推理。概率编程的关键是能够建立统计模型,当你做的足够多时,开始很像编程。如果我们实现跨越并且在实际上使用真正的语言来建模,那么许多工具变得可行。我们可以开始自动完成为每个实例编写文件的任务.。

第 3 段(可获 1.53 积分)

这里是第二个定义:概率编程语言是一个随机的,有一大堆相关工具的普通的编程语言,可以帮助您了解程序的统计行为。

这两个定义都是准确的。他们只是强调在同一核心思想上的不同角度。哪一个对你有意义将取决于你想要使用的概率编程。但不要因为PPL程序看起来像普通软件实现那样而心烦意乱,它的目标是运行程序并获得某种输出。而概率编程的目标是分析,而不是执行。

第 4 段(可获 1.3 积分)

1.3. 一个例子:论文推荐

Figure 1. 一个论文推荐问题。细圆圈里的内容是已知变量;加粗的圆圈里面的内容是我们想要的输出。

作为一个运行的例子,让我们想象一下,我们正在建立一个系统,根据他们所上的课程,向学生推荐研究论文。为了让事情简单化,让我们说世界上只有两个研究主题:编程语言和统计/机器学习。论文都是编程语言论文,统计论文或两者都是。我们将考虑在Cornell的三门课程:CS 4110(编程语言),CS 4780(机器学习)和一个虚构的选修课,“CS 4242”,概率编程。

第 5 段(可获 1.35 积分)

我们很容易想到机器学习应该适用于这个问题:你的课程安排所显示的混合区域应该说明你想要阅读的论文。问题是,确切的关系可能很难直接推理。明显地,如果你选了CS 4780(机器学习课程)意味着你更可能对统计学感兴趣,但是到底有多大的可能呢?如果你注册了4780(机器学习课程),只是因为它是唯一适合你日程的课程怎么办?我们对于那些选择虚构的CS 4242(概率编程)课程,而不是另外两个真正课程的人,该怎么判断呢- 只是假设编程语言和统计学的比例都是50%吗?

第 6 段(可获 1.39 积分)

1.3.1. 建模问题

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

第 7 段(可获 1.23 积分)

Figure 2. 兴趣如何影响所选的班级和论文相关性的模型。虚线圆是潜在变量:既不是输入也不是输出。

这里有一个模型介绍了几个关于每个人对统计和编程语言的兴趣的潜在变量。我们将得到更具体的模型,但现在的箭头至少是有含义的:它们的意味着一个变量以某种方式影响另一个。因为我们都知道你不会因为感兴趣就去上那门课程,所以我们引入了第三个隐藏因素:你太忙了,以至于你无法去上任何课程。

第 8 段(可获 1.29 积分)

该图描绘了贝叶斯网络,该网络图中的每个顶点都是一个随机变量并且每条边是统计关系。它们之间没有边的变量在统计学上是独立的。(也就是说,知道其中一个变量不会告诉你其他变量的结果)。 为了完成模型,我们还将绘制节点和边用来描述我们的潜在的兴趣变量如何影响论文的相关性:

Figure 3. 模型的其余部分:兴趣如何影响论文相关性。

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

第 9 段(可获 1.73 积分)

1.3.2. 人类的一个模型

到目前为止,我们已经在我们的模型中绘制了依赖关系的图片,但是我们需要具体说明我们的想法。下面是它正常情况下的行为:你写下一堆关联随机变量的数学。

 
 
 
 
 
 
 
 
 
 

这里有很多很简单的数学模型!它甚至不是很难的部分。难的和有用的是统计推理,它基于我们在观察中猜测到的潜变量。统计推理是研究机器学习的基石,这不容易的事。传统上,专家亲手为每个新模型设计定制推理算法。

第 10 段(可获 1.39 积分)

即使这是个很小的例子也展示手工建立统计模型是一份苦差事。它就像编写汇编代码:我们做的东西感觉有点像编程,但没有抽象,没有重用,没有描述性变量名,没有注释,没有调试器,没有类型。看看选择班级的方程,例如:我厌倦了写出所有的数学,因为它一直重复。这显然是一个老式的抽象编程语言:一个函数。 概率编程语言的目标将你已经知道和喜欢的编程语言的旧的和强大的魔法带到统计的世界中。

第 11 段(可获 1.35 积分)

2. 基本概念

为了介绍概率编程语言的基本概念,我将使用一个名为webppl的项目,它是嵌入在JavaScript中的概率编程语言。你可以在概念性编程语言的设计和实现,来自斯坦福的Noah GoodmanAndreas Stuhlmüller所写的一本书中阅读更多关于这门语言。作为介绍,这是一个很好的语言,因为你可以在你的浏览器中使用它。

2.1. 随机基元

使语言成为概率编程语言(PPL)的第一件事是一组用于绘制随机数的基元。在这一点上,PPL看起来像任何具有rand调用的旧命令式语言。这里有一个令人难以置信的无聊的webppl程序:

第 12 段(可获 1.51 积分)
var b = flip(0.5);
b ? "yes" : "no"

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

如果你在webppl编辑器中运行这个小程序,你会发现它正好符合你的期望:有时它输出“是”,有时它输出“不”。

当我们意识到webppl可以表示整个分布,而不仅仅是单个值时,事情变得更有趣。 webppl语言具有枚举操作,该操作打印由函数定义的分布中的所有概率:

第 13 段(可获 1.49 积分)
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函数一遍又一遍地枚举你的最喜欢的语言。但事实上,枚举是做一些更强大的东西。它不是抽样执行以获得分布的近似;它实际上枚举了函数的每一个可能的执行以获得精确的分布。这开始揭示概率编程语言的重点:分析概率编程语言程序的工具是重要的部分,而不是直接执行程序。

第 14 段(可获 1.48 积分)

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);

 

第 15 段(可获 0.55 积分)

运行此操作将显示所有观察数据的分布。这不是非常有用,但它是有趣的。例如,我们可以看到,如果我们不知道有关一个学生的事,我们的模型说,他们很可能不选择任何课程,也不对任何论文感兴趣。

2.3. 调节

PPL的下一个重要部分是调节结构。调节允许您确定在程序中给予给定执行的权重。至关重要的是,您可以在执行一些计算后选择执行的重要程度。您甚至可以将执行标记为完全不相关,有效地将执行过滤到子集。

第 16 段(可获 1.53 积分)

这种调节操作对于编码观察是特别有用的。如果你知道一个过程的结果,你可以使用条件来传达观察必须是真的(或者可能是真的)。让我们回到我们的骰子例子一个有价值的例子。该例子说我们看到了第一个骰子的值,它是一个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;
}
第 17 段(可获 1.04 积分)

不出所料,分布是平坦的,除了结果8,因为可能性很低,只有当另一个骰子滚到4时可以产生该总和。像2和12的结果有概率零,因为有一个骰子出现4时它们不会发生。
另一方面,如果我们不能看到任何一个骰子,但有人告诉我们,骰子上的总数是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;
}
第 18 段(可获 1.2 积分)

结果可能不会让你感到惊讶,但我们可以使用相同的我们的推荐的原理。

2.4. 实际推荐论文

让我们现在使用同样的原理来提供实际的建议。它很简单:我们只需要对我们感兴趣的人的班级注册进行条件化。这里有我一个例子来描述:我自己参加的课程,CS 4110和虚构的概率编程课程,CS 4242,但没有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);
}
第 19 段(可获 0.99 积分)

(在这个例子中,我们定义了require去包装factor(-无穷),并完全消除了不满足条件的程序执行。)对这个rec​​函数调用Enumerate最终给了我们一些有用的东西:这是一个更容易理解,如果我们一次只看一份论文:

return relevance(i_pl, i_stats).paper1;

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

第 20 段(可获 1.51 积分)

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

2.5. 推理

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

第 21 段(可获 2.08 积分)

Enumerate just won't do for nontrivial problems. It's for this reason that efficient inference algorithms for PPLs are a huge focus in the community. Here are a couple of other inference algorithms that don't involve exploring every possible execution of a program.

2.5.1. Rejection Sampling

The second most obvious inference algorithm uses sampling. The idea is to run the program a large number of times, drawing different random values for each random primitive on each execution. Apply the program's conditioning to weight each sample and total them all up. The interaction with weighting makes this strategy rejection sampling, so called because you reject some executions when you reach a conditioning statement.

第 22 段(可获 1.45 积分)

The webppl language has this strategy built in. It's called ParticleFilter, and we can run it on our examples from above:

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

2.5.2. MCMC

Rejection sampling works for small examples, but it runs intro trouble in the presence of conditioning. It can waste a lot of work taking samples that don't matter (i.e., they're destined to be rejected when they hit a factor call). Smarter sampling strategies exist, the most prominent of which are Markov chain Monte Carlo methods.

The webppl standard library provides MCMC algorithms. Making MCMC correct and efficient is a popular problem in PPL research, and a full discussion is currently out of scope of this lecture.

第 23 段(可获 1.41 积分)

3. Applications

To be as starry-eyed as possible, the promise of PP is nothing less than the democratization of machine learning. In case you're not convinced yet, here are a sampling of popular applications of probabilistic programming.

  • TrueSkill is perhaps the most widely cited example, originally laid out in this ESOP'11 paper. It's the model used by multiplayer Xbox games to find good matchups among players. The idea is to model latent variables for the player's skills and to match people up so that the predicted win probability is close to 50/50.
  • The webppl book has a nifty computer vision demo that shows how a generative “forward”model can also be used “backward” to solve a complementary problem.
  • Forest is a dizzying resource of generative models written in PPLs for domains from cognition and NLP to document retrieval.
  • This is not quite an application yet, but Gamalon is a new startup founded by Ben Vigoda of Lyric SemiconductorNoah Goodman, and others. It seems to be centered around probabilistic programming.
  • Then there's my favorite application: understanding normal programs that deal with probabilities. There is a lot of ordinary software that deals with probabilistic behavior:
    • approximate computing
    • dealing with sensors
    • security/obfuscation
第 24 段(可获 2.59 积分)

4. Techniques

This section gives a few examples of recent work from the programming languages community that focuses on probabilistic programming.

4.1. Probabilistic Assertions

At the very beginning of the lecture, I said that probabilistic programming was not about writing real software that you actually want to execute. But some research has worked to apply the lessons of PPL research to ordinary programming with probabilistic behavior.

One project I worked on myself used this philosophy to help express correctness constraints for software that behaves statistically. The idea is to introduce a probabilistic assertion, written passert, to generalize the familiar assert statement to work probabilistically. The goals in that project are to:

第 25 段(可获 1.38 积分)
  • Work on messy programs in a real-world programming language (here, LLVM programs, so think C and C++).
  • Make it fast to check statistical properties on the output. Think quality thresholds for approximate programs.
  • Not care about conditioning. Regular software doesn't need factor statements, which simplifies the job of checking passerts.

4.2. R2

R2 is a probabilistic programming language and implementation from Microsoft. The tool is available for download.

One particularly nifty component of R2 is the application of classic PL ideas to improve statistical inference. Most prominently, the R2 people use weakest preconditions analysis to improve rejection sampling—that naive randomized inference strategy we talked about before.

第 26 段(可获 1.35 积分)

The WP approach addresses the most frustrating aspect of conditioning: the fact that you find out after doing a bunch of work that you have to throw it all away. In this passage from earlier:

var die1 = randomInteger(6) + 1;
var die2 = randomInteger(6) + 1;

// Discard any executions that don’t sum to 10.
var out = die1 + die2;
require(out === 10);

we condition late in the program, which is inefficient if we use a naive strategy. (Bear with me here and pretend that the addition in the second-to-last line is expensive.) We can improve this program by making the assertion earlier in the program. And, in fact, that is the essence of a WP analysis, which asks, What must be true at program point A in order to make a different property true at a later point B? In our example, we can “move up” the condition to fail faster:

第 27 段(可获 1.55 积分)
var die1 = randomInteger(6) + 1;
var die2 = randomInteger(6) + 1;

require((die1 == 3 && die2 == 7) || ...);
var out = die1 + die2;

If we're lucky, we can even move the condition all the way back into the primitive sampling call—and avoid doing any work at all that will eventually be rejected later.

4.3. Porting PL Ideas to PP

Part of the promise of probabilistic programming is that we should be able to “port” ideas from the standard PL literature to the PPL world. Here are some examples:

第 28 段(可获 0.98 积分)

文章评论