下载本文的PDF版本 PDF

用数学赚钱

现代应用程序越来越多地使用概率性机器学习模型。


埃里克·梅耶尔

“如果今天从头开始创建谷歌,那么它的很多部分将是通过学习获得的,而不是编码。”——杰夫·迪恩,谷歌高级研究员,系统和基础设施组


机器学习(ML)是当今的热潮,这有充分的理由。通过机器学习算法为垃圾邮件过滤、语音和图像识别、语言翻译和文本理解等问题创建的模型,比人类开发人员编写的代码具有许多优势。然而,机器学习并不像乍听起来那么神奇。事实上,它与人类开发人员使用测试驱动开发创建代码的方式非常相似。4 给定输入-输出对的训练集 {(a,b)|a∈A,b∈B},猜测一个函数 f∈A➝B,它通过所有给定的测试,并且可以推广到未指定的输入值。

人类编写的代码和学习模型之间的一个主要区别是,后者通常不以文本表示,因此人类开发人员无法理解,也无法通过现有工具进行操作。其结果是,传统的软件工程技术(如代码审查、源代码控制和调试)不再适用。由于不可理解性并非学习代码所独有,因此这些方面在此不予考虑。

机器和人类之间更有趣的分歧是,机器不如人类傲慢,它们通过返回可能的答案 f∈A➝ℙ(B)概率分布置信区间来承认其代码中的不确定性,而不是声称知道每个输入的精确结果。例如,一家主要云提供商的学习图像识别功能将以 95% 的确定性预测我有头发,但对我是否专业不太有信心(图 1)。

Making Money Using Math

在人类编写的代码中融入学习模型的含义是,你无法回避这样一个事实,即人类构成应用程序的构建块本质上是概率性的。这对主流编程语言来说是一个挑战,因为主流编程语言都假设计算结果是精确的和确定性的。幸运的是,18 世纪的长老会牧师托马斯·贝叶斯预见到了处理不确定性的需求,并提出了贝叶斯规则6

ℙ(A|B)*ℙ(B) = ℙ(A&B) = ℙ(B|A)*ℙ(A)

事实证明,在弥合机器学习与现代编程语言之间的差距方面,贝叶斯规则正是对症下药的良方。

许多对贝叶斯规则的数学解释对于工作的计算机科学家来说非常令人困惑,但是,值得注意的是,当从函数式编程的角度解释时,贝叶斯规则是关于单子函数的组合性和可逆性的定理。让我们将贝叶斯规则逐个分解,并根据开发人员的直觉缓慢地重建它。

概率分布

首先,让我们探讨一下概率分布 ℙ(A) 是什么。维基百科的定义是,“概率分布是对随机现象的数学描述,以事件的概率为单位”,从开发人员的角度来看,这相当令人困惑。但是,如果你点击浏览一下,就会发现离散分布只是值和概率对的通用列表 ℙ(A)=[A↦ℝ],使得概率总和为 1。这是分布的贝叶斯表示。同构地,你可以使用分布的频率论表示,即类型为 dist∈[A] 的无限列表,这样,随着 n 变大,从集合中抽样并计算每个元素的频率

from a in dist.Take(n) group by a into g select g.Key↦g.Sum()/n

近似于分布的贝叶斯表示。当从贝叶斯实现转换为频率论实现时,概率不必加起来为 1,抽样过程将确保比率得到适当的归一化。

像真正的数学家一样,我们将在方便时悄悄地在这两种分布表示之间切换。但是,与数学家不同的是,为了保持简单,我们不会考虑连续分布。我们希望我们的分布能够通用地适用于任何类型 A,并且我们在代码中处理的大多数类型都是离散的,而不是“可测量的”或类似实数的。

由于我们关心的值通常甚至不可比较,因此我们也将避免累积分布。数学家喜欢标准连续分布(如高斯分布、贝塔分布、二项分布和均匀分布)的原因之一是它们具有良好的代数性质,称为共轭先验2 例如,均匀先验与二项似然结合会产生贝塔后验。这使得 18 和 19 世纪使用纸和笔进行概率计算成为可能,但现在有了每秒可以运行数百万次模拟的强大计算机,这已不再必要。

在编程示例中,分布通常来自外部数据,作为具有未知分布的离散频率论数据集合,或者通过枚举值/概率对列表显式定义为贝叶斯表示。例如,以下是根据 CDC(疾病控制中心)的数据,美国成年人体重的分布

CDC∈ℙ(Weight)
CDC = [肥胖↦0.4, 苗条↦0.6]

从组合分布中高效抽样确实是火箭科学。就像数据库查询优化器一样,高级抽样方法利用叶分布的属性以及计算分布的查询9 或程序3 的结构。它利用了深刻而复杂的数学技术,如重要性抽样、Metropolis-Hastings、马尔可夫链蒙特卡罗和吉布斯抽样,这些技术远远超出了本文的范围,但对于使概率分布上的实际计算成为可能非常重要。正如贝叶斯分析顾问 John D. Cook 所说,“……贝叶斯统计可以追溯到 200 多年前,但直到 20 世纪 80 年代才兴起,因为那时人们才发现了用于计算它的实用数值方法……”

为了说明 高效抽样已知离散分布 所涉及的复杂性,想象一下将示例分布 CDC 转换为频率论表示。8

也许最明显的方法是将 苗条肥胖 的列堆叠在一起,并抽取一个介于 01 之间的随机数(比如 p),然后检查 p ≤ 0.4 是否产生 肥胖,否则产生 苗条。一般来说,这种搜索与分布中的值数量呈线性关系,但使用二叉搜索树等技巧可以加快速度。数学家称之为逆变换方法。

另一种方法是首先选择一个随机整数(比如 体重)来选择 肥胖苗条 之间,然后选择一个介于 01 之间的随机双精度数(比如 p),如果 CDC[体重] ≤ p,则产生 体重,如图 2 所示。数学家称此算法为拒绝抽样,直方图显示,尝试从分布中抽样值的一半尝试将失败(粉红色部分)。可以通过选择更严格的包络分布(如图 2 中的第二个直方图所示)来改进这一点,但这仍然拒绝了 12 个样本中的 2 个。

最后一种方法是通过借用较高概率来填充较低概率。令人惊讶的是,总是可以以这样一种方式做到这一点,即每列最多代表两个值的概率,因此我们只需要一次比较即可选择正确的值。此比较可以使用第二个索引表来实现,因此数学家称此抽样算法为别名方法

Making Money Using Math

条件概率分布

现在我们已经解释了概率分布 ℙ(A),让我们检查条件概率分布 ℙ(B|A),根据维基百科,它是“在(通过假设、推定、断言或证据)另一个事件已经发生的情况下,对事件概率的度量”。在开发人员看来,这听起来很像一个函数 A➝ℙ(B),它返回一个分布,就像一个学习模型一样。本文的其余部分互换使用符号 ℙ(B|A)A➝ℙ(B)

回到示例,我们有以下模型 Doctor∈ℙ(Food|Weight),用于表示给定体重时的食物偏好,我们可以通过询问患者他们消费的食物种类来获得该模型

Doctor∈ℙ(Food|Weight) = Weight➝ℙ(Food)
Doctor(肥胖) = [汉堡包↦0.9, 芹菜↦0.1]
Doctor(苗条) = [汉堡包↦0.3 芹菜↦0.7]

正如引言中论证的那样,这些概率函数,如 ℙ(Object|Image)ℙ(Text|Audio)ℙ(Spam|Text) 等,越来越多地是训练某些机器学习算法或神经网络的结果,而不是由昂贵且不可靠的人类开发人员编码的结果。

既然你知道条件概率是概率函数,事情开始变得有趣起来,因为这意味着贝叶斯规则中使用的乘法 (*) 是一个运算符,它将概率函数应用于概率分布作为参数,也就是说,它具有以下类型签名

ℙ(B|A)*ℙ(A)∈ℙ(A&B)

使用分布的贝叶斯表示,你可以实现概率函数应用 likelihood*prior,其中 likelihood∈ℙ(B|A)prior∈ℙ(A),使用以下相关查询

likelihood*prior =
   from a↦p in prior
   from b↦q in likelihood(a)
   select (a,b)↦p*q

应用此定义来计算 Doctor*CDC 的结果,我们得到图 3 中显示的联合概率分布 ℙ(Food&Weight) 的表。

Making Money Using Math

由于 ℙ(Weight)ℙ(Food) 的分布出现在此表的边缘,因此数学家称之为边缘概率,类似地,对列/行求和的过程称为边缘化。当使用 (*) 计算联合分布时,数学家通常使用名称似然表示函数,使用先验表示参数。

频率论表示的优点在于,不需要乘以概率。抽样确保结果中值出现的潜在比率将自动反映先验和似然中值的适当乘积。例如,如果我们通过赔率 肥胖:苗条 = 4:6 的无限集合来实现先验 CDC,并通过赔率 汉堡包:芹菜 = 3:7 的无限集合来实现 Doctor(苗条) 的结果,并分别通过赔率 汉堡包:芹菜 = 9:1 的集合来实现 Doctor(肥胖) 的结果,那么从无限集合 Doctor*CDC 中抽样(这是将先验应用于似然的结果)将具有比率 (肥胖:汉堡包):(肥胖,芹菜):(苗条,汉堡包):(苗条:芹菜) = 36:4:18:24

敏锐的读者会注意到,(*) 是众所周知的单子绑定运算符的轻微变体,根据你喜欢的编程语言,该运算符以名称 (>>=)SelectManyflatMap 而闻名。事实上,概率分布形成一个单子。数学家称之为 Giry 单子,但贝叶斯牧师在近两个世纪前就击败了所有人。

请注意,按照公式,贝叶斯规则有一个类型错误,这个错误被忽视了几个世纪。左侧返回成对的分布 ℙ(A&B),而右侧返回成对的分布 ℙ(B&A)。对于数学家来说,这不是什么大问题,因为 & 是可交换的。为了简洁起见,我们也将对此含糊其辞。由于我们经常想通过删除对的一侧从 ℙ(A&B) 转换为 ℙ(A)ℙ(B),因此我们更喜欢 C# 版本的 SelectMany,它采用组合器函数 A⊕B∈C 来后处理来自先验和似然的样本对

likelihood*prior =
   from a↦p in prior
   from b↦q in likelihood(a)
   select a⊕b↦p*q

现在我们知道 (*) 是单子绑定,我们可以开始使用语法糖,例如 LINQ 查询或 for/monad 推导。真正要说的是,从任何对分布编写的查询中删除概率的显式跟踪是安全的(即,图 4 左侧的代码只是右侧代码的语法糖,右侧代码本身可以使用频率论方法使用抽样来替代实现)。

Making Money Using Math

换句话说,我们可以使用查询推导作为 DSL(领域特定语言)来指定概率函数。这为探索除应用程序之外的其他可以在分布上工作的标准查询运算符以及可以添加到我们的技能库中的运算符开辟了道路。首先想到的是过滤,或者数学家更喜欢称之为投影

给定一个谓词 (A➝𝔹),我们可以使用除法运算符 (÷) 删除分布中所有谓词不成立的值

ℙ(A)÷(A➝𝔹)∈ℙ(A)
prior ÷ condition = from a in prior where condition(a) select a

分布 ℙ(A&B) 除以分布 ℙ(B) 的传统除法可以类似地定义为

joint ÷ evidence =
   λb.from (a,b) in joint from b' in evidence where b=b' select (a,b)

我们可以证明 (f*d)÷d = f。将后一个版本应用于贝叶斯规则,得到以下等价性

ℙ(A|B) = ℙ(B|A)*ℙ(A) ÷ ℙ(B)

在实践中,最方便的是直接使用查询推导而不是运算符,并编写如下代码

posterior∈ℙ(C|B)=B➝ℙ(C)
posterior(b) =
   from a in prior
   from b' in likelihood(a) where b = b'
   select a⊕b

无论你怎么看,这都非常酷!贝叶斯规则展示了如何使用条件将类型为 ℙ(B|A) = A➝ℙ(B) 的概率函数反转为类型为 ℙ(A|B) = B➝ℙ(A) 的概率函数。

当将函数反转应用于正在运行的示例时,可以将概率函数 PredictWeightFromFood∈ℙ(Weight|Food) 定义如下

PredictWeightFromFood∈Food➝ℙ(Weight)
PredictWeightFromFood(food) = (Doctor*CDC) ÷ (_ = food)

删除所有语法糖并使用值/概率对实现,相当于以下概率函数

PredictWeightFromFood∈Food➝ℙ(Weight)
PredictWeightFromFood(汉堡包) = [肥胖↦36, 苗条↦18]
PredictWeightFromFood(芹菜) = [肥胖↦4, 苗条↦42]

在实践中,大多数单子都有一个类型为 ℙ(A)➝M(A) 的不安全运行函数,它可以将你从单子中传送到某个具体容器 M 中。数学家称之为遗忘函子。对于分布 dist∈ℙ(A),退出单子的一种常见方法是选择 dist 中概率最高的值 a∈A。数学家为此使用高阶函数 arg max,并称之为 MLE(最大似然估计器)或 MAP(最大后验)。在实践中,从 dist 返回概率最高的对 a↦p 通常更方便。

从分布的频率论表示中找到具有最大似然性的值的一种简单方法是将源分布 ℙ(A) 扩展为分布的分布 ℙ(ℙ(A)),其中外部分布是内部贝叶斯分布 [A↦ℝ] 的无限频率论列表,通过分组和求和计算,随着时间的推移,它将收敛到真实的底层分布。然后,你可以选择第 n 个内部分布并取其最大值。

WeightFromFood∈Food➝[A↦ℝ]
WeightFromFood food = PredictWeightFromFood(food).Run().ElementAt(1000)

使用查询样式 DSL 来组合和条件化概率函数非常棒,但它还不足以成为具有任意控制流、循环、try/catch 块、递归等的真正编程语言。由于分布是延续单子的变体,因此可以将概率计算集成到类似于现在许多编程语言中可用的 async await 语法的常规命令式语言中。命令式概率编程语言的一个示例是 WebPPL (http://webppl.org),它将分布单子嵌入到常规 JavaScript 中。在 WebPPL 中,正在运行的示例如下所示

var cdc = function() {
   return Categorical({ ps: [4, 6], vs: ["obese", "skinny"] })
}
 
var doctor = function(weight) {
   if("obese" == weight)
      return Categorical({ ps: [9, 1], vs: ["burger", "celery"] } })
   if("skinny" == weight)
      return Categorical({ ps: [3, 7], vs: ["burger", "celery"] } })
}
 
var predict = function(food) {
   var weight = sample(cdc())
   var food_ = sample(doctor(weight))
   condition(food == food_)
   return weight;
}

赋值 + 抽样语句

var a = sample(prior)
... 程序其余部分...

与查询片段完全一样

from a in prior
... 查询的其余部分 ...

并从分布 prior∈ℙ(A) 中随机选择一个值 a∈Acondition(p) 语句对应于查询中的 where 子句。

要“运行”此程序,我们将 predict 函数传递到 WebPPL 推理引擎中,如下所示

Infer({method: enumerate, samples: 10000}, function(){return predict("burger")})

这使用指定的抽样方法(包括 enumeraterejectionMCMC)从程序描述的分布中抽样,该方法将生成的分布具体化为贝叶斯表示。

概率编程的应用

假设普通开发人员可以使用概率编程语言。这将开启哪些场景?

如果我们退后一步,看看典型的 Web 或移动应用程序,它实现了图 5 所示的标准强化学习设计模式。我们必须根据用户的状态和从用户那里提取的美元价值来预测要发送给用户的操作,以便随着时间的推移最大化奖励的总和。

Making Money Using Math

对于 AlphaGo10 等游戏,代理代码通常是神经网络,但如果我们抽象出应用于整个应用程序的模式,它很可能是机器学习学习模型和常规命令式代码的组合。即使在今天,这种混合情况也是如此,广告投放和搜索结果排名等都是概率性的,但以不透明的方式嵌入到命令式代码中。概率编程和机器学习将使开发人员能够创建高度针对每个用户的应用程序。

IDE(集成开发环境)的吸引力之一是自动完成,其中 IDE 根据迄今为止键入的内容预测用户将要键入的内容。在大多数 IDE 中,自动完成由静态类型信息驱动。例如,如果用户键入 ppl,则 JetBrains Rider IDE 会显示 string 类型的所有属性作为可能的完成项,如图 6 所示。

Making Money Using Math

请注意,完成列表以确定性的字母顺序显示,而不是使用一些基于学习模型的概率排名,该模型基于在给定上下文中 string 上的哪些方法最有可能。因此,IDE 应该使用概率函数 autoComplete∈ℙ([Completion]|Context) 实现自动完成,该函数根据当前用户上下文返回可能的完成项分布。7 编译器空间中 ML 和概率编程的另一个最新应用是通过从大型代码语料库 prettyPrint∈ℙ(String|AST) 中的模式学习来推断漂亮打印规则。5

对于公开分布表示的示例应用程序,让我们重新审视用户和应用程序之间的反馈循环。假设在这种情况下,我们想要确定本文的最佳标题,以最大化 网站上的点击率。也就是说,我们应该使用“面向傻瓜的概率编程”而不是当前的标题“用数学赚钱”吗?

在这种情况下,我们创建了图 7 中所示的模型,即所有用户的集合,作为给定标题时用户点击文章的条件分布

user∈ℙ(Click|Title)

Making Money Using Math

请注意,除了接收到的点击的频率流(给定提供给用户的标题的频率流)之外,我们不想对底层分布做出任何先验假设。

在这种情况下,代理想要随着时间的推移找出哪个故事标题将从用户那里产生最多的点击,因此我们将通过高阶函数对代理进行建模,该函数接受用户并从中创建标题分布

agent∈(Title➝ℙ(Click))➝ℙ(Title)

数学家称 user 的实现为贝叶斯匪徒11,他们利用伯努利分布和贝塔分布是共轭先验的事实12。他们将我们将要使用的 run 函数的变体称为汤普森抽样1

从计算机科学家的角度来看,操作解决方案相对简单。我们将返回点击分布的用户行为 user∈Title➝ℙ(Click) 转换为函数 Title➝ℙ(Title&Click↦ℝ),该函数使用前面解释的 run 返回标题和点击对的分布(这对应于算法的贝塔分布部分。我们不跟踪关于 ℙ(Click) 的“不确定性”,但如果有用,我们可以轻松地计算出它以及点击概率)。需要进行一个小小的调整,即我们只对 true 的点击感兴趣,而对 false 的点击不感兴趣(这是算法的伯努利部分)。

这使我们能够观察到随着我们看到来自用户的更多点击,用户将点击每个标题的概率如何随时间演变。每当我们需要生成新标题时,我们都使用最新的 Title&Click↦ℝ 具有最高概率的 Title(这是算法的汤普森抽样部分)。换句话说,贝叶斯匪徒本质上是对来自用户的点击的物化底层概率分布进行归并排序。

现代应用程序(如自动驾驶汽车、语音和图像识别、个性化推荐等)底层的计算模型正在从经典的确定性计算转变为概率性机器学习模型。目前,构建此类应用程序需要深入了解和掌握使用自定义工具的机器学习算法的底层细节。

结论

概率编程旨在通过允许普通程序员在通用编程语言中无摩擦地融入机器学习来普及机器学习的应用。正如本文所示,从语义学的角度来看,概率语言只是在环境副作用集中添加了概率单子,并利用贝叶斯规则来组合和条件化概率分布。然而,高效地实现概率语言并提供适当的软件工程工具将使编译器和编程语言专家忙碌很长时间。

参考文献

1. Agrawal, S., Goyal, N. 2012. 多臂匪徒问题的汤普森抽样分析。机器学习研究杂志:研讨会和会议记录 23; http://jmlr.org/proceedings/papers/v23/agrawal12/agrawal12.pdf

2. Fink, D. 1997. 共轭先验纲要。蒙大拿州立大学; http://www.johndcook.com/CompendiumOfConjugatePriors.pdf

3. Goodman, N. D. 2013. 概率编程的原理与实践。第 40 届 SIGPLAN-SIGACT 编程语言原理研讨会论文集; http://dl.acm.org/citation.cfm?id=2429117

4. Norvig, P. 2015. 机器学习用于编程。InfoQueue; https://www.infoq.com/presentations/machine-learning-general-programming

5. Parr, T., Vinju, J. 2016. 通过机器学习实现通用代码格式化器。 SIGPLAN 国际软件语言工程会议论文集; http://dl.acm.org/citation.cfm?id=2997383

6. Paulos, J. A. 2011. 改变想法的数学。纽约时报周日书评; http://www.nytimes.com/2011/08/07/books/review/the-theory-that-would-not-die-by-sharon-bertsch-mcgrayne-book-review.html

7. Raychev, V., Bielik, P., Vechev, M. 2016. 使用决策树的代码概率模型。 SIGPLAN 国际面向对象编程、系统、语言和应用会议论文集; http://dl.acm.org/citation.cfm?doid=2983990.2984041

8. Schwarz, K. 2011. 飞镖、骰子和硬币:从离散分布中抽样; http://www.keithschwarz.com/darts-dice-coins/

9. Ścibior, A., Ghahramani, Z., Gordon, A. D. 2015. 使用单子进行实用的概率编程。2015 SIGPLAN Haskell 研讨会论文集; http://dl.acm.org/citation.cfm?id=2804317

10. Silver, D., et al. 2016. 通过深度神经网络和树搜索掌握围棋游戏; https://gogameguru.com/i/2016/03/deepmind-mastering-go.pdf

11. Stucchio, C. 2013. 贝叶斯匪徒——使用统计数据优化点击率; https://www.chrisstucchio.com/blog/2013/bayesian_bandit.html

12. 维基百科。共轭先验:离散分布; https://en.wikipedia.org/wiki/Conjugate_prior#Discrete_distributions

相关文章

信息提取
从非结构化文本中提取结构化数据
- 安德鲁·麦卡勒姆
https://queue.org.cn/detail.cfm?id=1105679

算法决策中的问责制
来自计算新闻学的观点
- 尼古拉斯·迪亚科普洛斯
https://queue.org.cn/detail.cfm?id=2886105

从网络学习
网络教会了我们很多关于分布式计算的课程,但其中一些最重要的课程尚未完全站稳脚跟。
- 亚当·博斯沃思
https://queue.org.cn/detail.cfm?id=1103833

埃里克·梅耶尔在过去 15 年中一直致力于“普及云计算”。他最出名的事迹或许是他对 Haskell、C#、Visual Basic 和 Dart 编程语言的工作,以及他对 LINQ 和响应式框架 (Rx) 的贡献。

版权所有 © 2017,所有者/作者所有。出版权已授权给 。

acmqueue

最初发表于 Queue vol. 15, no. 1
数字图书馆 中评论本文





更多相关文章

马克·鲁西诺维奇、艾哈迈德·萨利姆、圣地亚哥·扎内拉-贝格林、约纳坦·祖格 - 智能的代价
大型语言模型容易出现幻觉、提示注入和越狱,这对它们的广泛采用和负责任的使用构成了重大但可克服的挑战。我们认为这些问题是固有的,当然在当前这一代模型中是这样,并且可能在大型语言模型本身中也是如此,因此我们的方法永远不能基于消除它们;相反,我们应该应用“纵深防御”策略来缓解它们,并且在构建和使用这些系统时,假设它们有时会在这些方面失败。


索尼娅·约翰逊-于、桑克特·沙阿 - 你对人工智能一窍不通
长期以来,很难确定人工智能到底是什么。几年前,此类讨论会演变成长达数小时的会议,勾勒出维恩图并试图绘制出人工智能的不同子领域。快进到 2024 年,我们现在都知道人工智能到底是什么。人工智能 = ChatGPT。或者不是。


吉姆·沃尔多、索琳·布萨尔 - GPT 和幻觉
本实验的发现支持了以下假设:基于大型语言模型的 GPT 在更受欢迎且已达成普遍共识的提示下表现良好,但在有争议的主题或数据有限的主题上表现不佳。应用程序响应的可变性突显了模型依赖于其训练数据的数量和质量,这与依赖于多样化和可信贡献的众包系统类似。因此,虽然 GPT 可以作为许多日常任务的有用工具,但应谨慎解读它们与晦涩和两极分化主题的互动。


埃里克·梅耶尔 - 虚拟阴谋:将大型语言模型用作神经计算机
我们探索了大型语言模型 (LLM) 如何不仅可以充当数据库,还可以充当动态的、最终用户可编程的神经计算机。这种神经计算机的本机编程语言是一种受逻辑编程启发的声明性语言,它形式化和外部化了思维链推理,因为它可能发生在一个大型语言模型内部。





© 保留所有权利。

© . All rights reserved.