马尔可夫链蒙特卡罗概率方法简明入门

概率推断涉及使用概率模型估计期望值或密度。

通常，直接推断值对于概率模型来说是不可行的，因此必须使用近似方法。

马尔可夫链蒙特卡洛采样提供了一类算法，用于从高维概率分布中进行系统随机采样。与能够从分布中抽取独立样本的蒙特卡洛采样方法不同，马尔可夫链蒙特卡洛方法抽取样本时，下一个样本依赖于现有样本，这被称为马尔可夫链。这使得算法即使在有大量随机变量的情况下，也能聚焦于分布中正在被近似的量。

在本文中，您将了解马尔可夫链蒙特卡洛方法在机器学习中的入门知识。

阅读本文后，你将了解：

• 对于高维概率模型，蒙特卡洛采样无效且可能难以处理。
• 马尔可夫链蒙特卡洛提供了一种替代方法，用于从高维概率分布中进行随机采样，其中下一个样本依赖于当前样本。
• 吉布斯采样和更通用的Metropolis-Hastings算法是马尔可夫链蒙特卡洛采样中最常用的两种方法。

启动您的项目，阅读我的新书《机器学习中的概率》，其中包括分步教程和所有示例的Python源代码文件。

让我们开始吧。

马尔可夫链蒙特卡罗概率方法简明入门
照片由 Murray Foubister 拍摄，保留部分权利。

概述

本教程分为三个部分；它们是：

1. 概率推断的挑战
2. 什么是马尔可夫链蒙特卡洛
3. 马尔可夫链蒙特卡洛算法

概率推断的挑战

从概率模型计算某个量通常被称为概率推断，或简称为推断。

例如，我们可能对计算期望概率、估计密度或其他概率分布的属性感兴趣。这是概率模型的目的，所执行的推断名称通常也采用概率模型的名称，例如，贝叶斯推断使用贝叶斯概率模型进行。

对于除最平凡的概率模型之外的所有模型，从模型中直接计算所需量都是不可行的。相反，必须通过其他方式近似期望概率或密度。

对于大多数实际感兴趣的概率模型，精确推断是不可行的，因此我们必须采用某种形式的近似。

— 第 523 页，《模式识别与机器学习》，2006年。

所需计算通常是许多随机变量离散分布的求和，或许多变量连续分布的积分，而这些计算难以直接求出。这个问题存在于概率的两个学派中，但可能在贝叶斯概率和对模型后验分布进行积分时更为普遍或常见。

贝叶斯主义者，有时也包括频率主义者，需要对可能的高维概率分布进行积分，以便对模型参数进行推断或进行预测。贝叶斯主义者需要对给定数据的模型参数的后验分布进行积分，而频率主义者可能需要对给定参数值的可观测量的分布进行积分。

— 第 1 页，《马尔可夫链蒙特卡洛实践》，1996年。

典型的解决方案是从概率分布中抽取独立样本，然后多次重复此过程以近似所需的量。这被称为蒙特卡洛采样或蒙特卡洛积分，其名称来源于摩纳哥的蒙特卡洛市，那里有很多赌场。

蒙特卡洛采样的问题在于它在高维空间中效果不佳。这首先是因为维度灾难，即样本空间的体积随参数（维度）的数量呈指数级增长。

其次，也许最关键的是，这是因为蒙特卡洛采样假设从目标分布中抽取的每个随机样本都是独立的，并且可以独立抽取。这通常不是贝叶斯结构化或图模型概率模型的推断中的情况，或者难以实现。

什么是马尔可夫链蒙特卡洛

在高维空间中对概率分布进行采样的解决方案是使用马尔可夫链蒙特卡洛，简称MCMC。

从高维分布采样最流行的方法是马尔可夫链蒙特卡洛或MCMC

— 第 837 页，《机器学习：概率视角》，2012年。

与蒙特卡洛方法一样，马尔可夫链蒙特卡洛方法最早是在第一台计算机开发的同时开发的，并用于曼哈顿计划中计算粒子物理所需的部分，该计划旨在开发原子弹。

蒙特卡洛

蒙特卡洛是一种随机采样概率分布并近似所需量的方法。

蒙特卡洛算法，[…] 在科学的许多分支中用于估计难以精确计算的量。

— 第 530 页，《人工智能：现代方法》，第三版，2009年。

蒙特卡洛方法通常假设我们可以有效地从目标分布中抽取样本。从抽取的样本中，我们可以将和或积分量估计为所抽取样本的均值或方差。

理解蒙特卡洛采样过程的一个有用方法是考虑一个复杂的二维形状，例如螺旋线。我们很难定义一个函数来描述螺旋线，但我们可以从域中抽取样本，并确定它们是否属于螺旋线。总之，从域中抽取的许多样本将使我们能够总结螺旋线的形状（概率密度）。

马尔可夫链

马尔可夫链是一种生成随机变量序列的系统方法，其中当前值在概率上依赖于前一个变量的值。具体来说，选择下一个变量仅依赖于链中的最后一个变量。

马尔可夫链是一种特殊的随机过程，它处理随机变量序列的特征。特别关注序列的动态和极限行为。

— 第 113 页，《马尔可夫链蒙特卡洛：贝叶斯推断的随机模拟》，2006年。

考虑一个涉及掷骰子的棋盘游戏，例如“蛇与梯子”（或梯子与蛇）。骰子的掷出在6个阶段（整数1到6）上具有均匀概率分布。您在棋盘上的位置，但您在棋盘上的下一个位置仅取决于当前位置和随机掷骰子。您在棋盘上的特定位置构成了一个马尔可夫链。

马尔可夫链的另一个例子是一维随机游走，其中可能的移动是1或-1，以相等的概率选择，并且游走中数轴上的下一个点仅取决于当前位置和随机选择的移动。

从高层次来看，马尔可夫链是根据状态图定义的，采样算法在其上进行随机游走。

— 第 507 页，《概率图模型：原理与技术》，2009年。

马尔可夫链蒙特卡洛

结合这两种方法，马尔可夫链和蒙特卡洛，通过构建包含蒙特卡洛样本的马尔可夫链，可以对高维概率分布进行随机采样，同时尊重样本之间的概率依赖性。

MCMC本质上是使用马尔可夫链进行蒙特卡洛积分。[…] 蒙特卡洛积分从所需的分布中抽取样本，然后形成样本均值来近似期望值。马尔可夫链蒙特卡洛通过长时间运行巧妙构建的马尔可夫链来抽取这些样本。

— 第 1 页，《马尔可夫链蒙特卡洛实践》，1996年。

具体来说，MCMC用于对无法抽取独立样本，或者无法轻松抽取独立样本的概率分布进行推断（例如，估计某个量或密度）。

因此，不能使用蒙特卡洛采样。

取而代之的是，通过构建一个马尔可夫链来从概率分布中抽取样本，其中从概率分布中抽取的下一个样本依赖于抽取的最后一个样本。其思想是链将收敛（找到平衡）到我们正在推断的所需量。

然而，我们仍然从目标概率分布中采样，目的是近似所需的量，因此将收集到的样本称为蒙特卡洛样本是合适的，例如，抽取的样本数量通常会形成一条长的马尔可夫链。

施加样本之间的依赖性这个想法起初可能看起来很奇怪，但如果我们考虑诸如随机游走或蛇与梯子游戏之类的领域，那么这种样本之间的依赖性是必需的，这样会更容易理解。

马尔可夫链蒙特卡洛算法

有许多马尔可夫链蒙特卡洛算法，它们主要通过在执行每个蒙特卡洛样本时定义构建马尔可夫链的不同方法。

随机游走为构建样本的马尔可夫链提供了良好的比喻，但效率非常低。考虑这种情况，我们可能希望计算期望概率，比起在域中漫无目的的游走，更有效的方法是聚焦于该数量或密度。马尔可夫链蒙特卡洛算法是试图仔细利用问题本身的性质来高效地构建链。

此序列的构建方式是，尽管第一个样本可能来自先验分布，但后续样本是从概率分布中生成的，这些分布被证明越来越接近所需的后验分布。

— 第 505 页，《概率图模型：原理与技术》，2009年。

MCMC算法对其起始点很敏感，通常需要预热阶段或燃烧期才能进入搜索空间的有利部分，之后可以丢弃先前的样本并收集有用的样本。

此外，要确定链是否已收敛并收集了足够多的步数可能具有挑战性。通常需要大量的样本，并且在固定步数时停止运行。

……有必要丢弃一些初始样本，直到马尔可夫链燃烧完毕，或者进入其平稳分布。

— 第 838 页，《机器学习：概率视角》，2012年。

最常见的通用马尔可夫链蒙特卡洛算法称为吉布斯采样；一个更通用的版本称为Metropolis-Hastings算法。

让我们仔细看看这两种方法。

吉布斯采样算法

吉布斯采样算法是一种构建马尔可夫链的方法，其中下一个样本的概率是根据先验样本的条件概率计算的。

样本是通过一次更改一个随机变量来构建的，这意味着后续样本在搜索空间中非常接近（例如，局部）。因此，链有陷入困境的风险。

吉布斯采样的思想是，我们依次对分布中的每个变量进行采样，条件是其他所有变量的值。

— 第 838 页，《机器学习：概率视角》，2012年。

吉布斯采样适用于那些可以计算其条件概率的概率模型，例如，分布是离散的而不是连续的。

… 吉布斯采样仅在某些情况下适用；特别是，我们必须能够从分布 P(Xi | x-i) 中进行采样。尽管对于离散图模型，此采样步骤很容易，但在连续模型中，条件分布可能不是一个具有允许采样的参数形式的分布，因此吉布斯不适用。

— 第 515 页，《概率图模型：原理与技术》，2009年。

Metropolis-Hastings算法

对于那些我们无法直接采样所谓下一个状态概率分布的概率模型（例如吉布斯采样使用的条件概率分布），Metropolis-Hastings算法是适用的。

与吉布斯链不同，该算法不假定我们可以从特定的目标分布生成下一个状态样本。

— 第 517 页，《概率图模型：原理与技术》，2009年。

相反，Metropolis-Hastings算法涉及使用一个替代或建议的概率分布进行采样（有时称为核），然后使用一个接受标准来决定新样本是否被接受到链中或被丢弃。

它们基于马尔可夫链，其对前驱的依赖性分为两部分：提案和提案的接受。提案建议链轨迹中的任意下一步，接受则通过拒绝不需要的链移动来确保保持适当的极限方向。

— 第 6 页，《马尔可夫链蒙特卡洛：贝叶斯推断的随机模拟》，2006年。

接受标准是概率性的，基于提案分布与真实下一个状态概率分布的差异程度。

Metropolis-Hastings算法是一种更通用、更灵活的马尔可夫链蒙特卡洛算法，它包含了许多其他方法。

例如，如果使用下一个条件概率分布作为提案分布，那么Metropolis-Hastings通常等同于吉布斯采样算法。如果使用像高斯分布这样的对称提案分布，该算法则等同于另一种称为Metropolis算法的MCMC方法。

进一步阅读

如果您想深入了解，本节提供了更多关于该主题的资源。

书籍

• 马尔可夫链蒙特卡洛实践, 1996.
• 马尔可夫链蒙特卡洛：贝叶斯推断的随机模拟, 2006.
• 马尔可夫链蒙特卡洛手册, 2011.
• 概率图模型：原理与技术, 2009.

章节

• 第 24 章 马尔可夫链蒙特卡洛 (MCMC) 推断，《机器学习：概率视角》，2012年。
• 第 11.2 节 马尔可夫链蒙特卡洛，《模式识别与机器学习》，2006年。
• 第 17.3 节 马尔可夫链蒙特卡洛方法，《深度学习》，2016年。

文章

• 蒙特卡洛方法，维基百科.
• 马尔可夫链，维基百科.
• 马尔可夫链蒙特卡洛，维基百科.
• 吉布斯采样，维基百科.
• Metropolis–Hastings算法，维基百科.
• MCMC采样入门, 2015.
• 您会如何向普通人解释马尔可夫链蒙特卡洛 (MCMC)？

总结

在本文中，您了解了马尔可夫链蒙特卡洛方法在机器学习中的入门知识。

具体来说，你学到了：

• 对于高维概率模型，蒙特卡洛采样无效且可能难以处理。
• 马尔可夫链蒙特卡洛提供了一种替代方法，用于从高维概率分布中进行随机采样，其中下一个样本依赖于当前样本。
• 吉布斯采样和更通用的Metropolis-Hastings算法是马尔可夫链蒙特卡洛采样中最常用的两种方法。

你有什么问题吗？
在下面的评论中提出你的问题，我会尽力回答。

掌握机器学习中的概率！

增进你对概率的理解

...只需几行python代码

在我的新电子书中探索如何实现
机器学习概率

它提供了关于以下内容的自学教程和端到端项目：
贝叶斯定理、贝叶斯优化、分布、最大似然、交叉熵、校准模型
以及更多...

最终在你的项目中驾驭不确定性

跳过学术理论。只看结果。

查看内容