DL花书阅读笔记-蒙特卡洛方法

date

Jun 22, 2022

Last edited time

Jun 22, 2022 08:28 AM

status

Published

slug

DL花书阅读笔记-蒙特卡洛方法

采样和蒙特卡罗方法

蒙特卡罗采样的基础

当无法精确计算和或积分时，通常可以使用蒙特卡罗采样来近似它。我们将需要估计的和或者积分，写成期望的形式, 如下:

我们可以通过从中抽取个样本来近似并得到一个经验平均值

首先很容易观察到这个估计是无偏的:

此外，根据大数定理（Law of large number），如果样本是独立同分布的，那么其平均值几乎必然收敛到期望值, .

根据中心极限定理, 的分布收敛到以为均值以为方差的正态分布。

重要采样

当我们无法从中采样时，一个备选方案是用重要采样。

可以写为

我们从分布中采样，然后估计在此分布下的均值。使用最优的采样函数对应所谓的最优重要采样。

任意蒙特卡罗估计:

可以被转化为一个重要采样的估计:

其估计的期望与分布无关：. 然而，重要采样的方差可能对 q 的选择非常敏感, . 方差想要取到最小值，需要满足:

在这里表示归一化常数，选择适当的使得之和或者积分为。

有偏重要采样

这种方法的优势为不需要归一化的或分布。在处理离散变量时，有偏重要采样估计可以表示为

其中和分别是分布和的未经归一化的形式，是从分布中抽取的样本。这种估计是有偏的，因为，只有当且收敛到时，等式才渐近地成立。所以这一估计也被称为渐近无偏的。

实际中, 我们会倾向于将采样函数构造成常用的分布形式, 例如高斯分布, 以方便采样. 故有偏重要性采样更为常见.

马尔可夫链蒙特卡罗方法

在深度学习中，当分布表示成无向模型时, 往往又不存在一种简单的方法可以直接从目标分布中精确采样或者一个好的（方差较小的）重要采样分布。因此, 我们引入了一种称为马尔可夫链（Markov Chain）的数学工具。利用马尔可夫链来进行蒙特卡罗估计的这一类算法被称为马尔可夫链蒙特卡罗（Markov Chain Monte Carlo, MCMC）方法。

为什么使用马尔可夫链来采样

在有向模型中, 为了完成原始采样（Ancestral Sampling），在给定每个变量的所有父结点的条件下，我们根据拓扑顺序采样每一个变量，这个变量是确定能够被采样的.

而在无相模型中, 我们考虑一个包含两个变量的 EBM 的例子，记为其分布。为了采，我们必须先从中采样；为了采，我们又必须从中采样。

马尔可夫链的核心思想是从某个可取任意值的状态出发。随着时间的推移，我们随机地反复更新状态。最终成为了一个从中抽出的（非常接近）比较一般的样本。

在正式的定义中，马尔可夫链由一个随机状态和一个转移分布定义而成，是一个概率分布，说明了给定状态的情况下随机地转移到的概率。运行一个马尔可夫链意味着根据转移分布采出的值来更新状态。

证明

从状态到新状态 ′ 。单一状态转移到的概率可以表示为 .

我们可以将转移算子表示成一个矩阵。矩阵的定义如下：. 矩阵有一种特殊的结构，因为它的每一列都代表一个概率分布。这样的矩阵被称为随机矩阵（Stochastic Matrix）。如果对于任意状态到任意其他状态存在一个使得转移概率不为，那么 Perron-Frobenius 定理可以保证这个矩阵的最大特征值是实数且大小为。

另外, 可以用一个向量来描述这个概率分布 , .

则单次转移的马尔可夫过程可写为: .

换言之，我们可以认为这一过程就是关于的幂乘：.

我们可以看到所有的特征值随着时间呈现指数变化: . 这个过程导致了所有不等于 1 的特征值都衰减到 0。所以这个过程收敛到平稳分布.

收敛时，我们得到 . 作为收敛的稳定点，一定是特征值为 1 所对应的特征向量。这个条件保证收敛到了平稳分布以后，再重复转移采样过程不会改变所有不同马尔可夫链上状态的分布. (但是状态会发生改变, 只是分布不变).

通常在一些宽松的条件下，一个带有转移算子的马尔可夫链都会收敛到一个不动点，这个不动点可以写成如下形式：

运行马尔可夫链直到它达到均衡分布的过程通常被称为马尔可夫链的磨合（Burning-in）过程。

在马尔可夫链达到均衡分布之后，我们可以从均衡分布中抽取一个无限多数量的样本序列。这些样本服从同一分布，但是两个连续的样本之间会高度相关。一种解决这个问题的方法是每隔 n 个样本返回一个样本, 从而使得我们对于均衡分布的统计量的估计不会被MCMC方法的样本之间的相关性所干扰。

特点

马尔可夫链的计算代价很高, 主要源于达到均衡分布前需要磨合的时间以及在达到均衡分布之后从一个样本转移到另一个足够无关的样本所需要的时间。

我们无法预先知道马尔可夫链需要运行多少步才能到达均衡分布。这段时间通常被称为混合时间（Mixing Time）。我们只能运行一定量时间马尔可夫链直到我们粗略估计这段时间是足够的，然后使用启发式的方法来判断马尔可夫链是否混合成功。

Gibbs采样

我们希望马尔可夫链的分布就是。为了得到所期望的分布，我们必须选取合适的。

Gibbs 采样（Gibbs Sampling）构造一个从中采样的马尔可夫链，其中在基于能量的模型中从采样是通过选择一个变量，然后从中该点关于在无向图（定义了基于能量的模型结构）中邻接点的条件分布中采样。

即选择的为无向图所定义的因子的条件分布.

不同的峰值之间的混合挑战

使用MCMC方法的主要难点在于马尔可夫链的混合（Mixing）通常不理想。MCMC方法采出的样本可能会具有很强的相关性，尤其是在高维的情况下。我们把这种现象称为慢混合甚至混合失败。

举一个简单的例子，考虑两个变量的基于能量的模型，这两个变量都是二值的，取值或者。如果对某个较大的正数，，那么这个模型传达了一个强烈的信息，和有相同的符号。当时用 Gibbs 采样更新。给定时的条件分布满足。如果的值很大，sigmoid 函数趋近于饱和，那么也取到的概率趋近于。同理，如果，那么取到的概率也趋于。根据模型，两个变量取一样的符号的概率几乎相等。根据，两个变量应该有相同的符号。这也意味着 Gibbs 采样很难会改变这些变量的符号。

即MCMC采样的样本会与原来的初始值强相关, 难以离开这个低能量的区域, 到达另一个低能量的区域

不同峰值之间通过回火来混合

一些加速混合的方法是基于构造一个概率分布替代目标分布，这个概率分布的峰值没有那么高，峰值周围的低谷也没有那么低。

基于能量的模型为这个想法提供一种简单的做法。目前为止，我们一直将基于能量的模型描述为定义一个概率分布：.

基于能量的模型可以通过添加一个额外的控制峰值尖锐程度的参数来加强：

参数可以被理解为温度（temperature）的倒数，反映了基于能量的模型的统计物理学起源。当温度趋近于 0 时，趋近于无穷大，此时的基于能量的模型是确定性的。当温度趋近于无穷大时，趋近于零，基于能量的模型（对离散的）成了均匀分布。

回火（tempering）作为一种通用的策略，它通过从模型中采样来实现在的不同峰值之间快速混合。

基于回火转移（tempered transition）的马尔可夫链临时从高温度的分布中采样使其在不同峰值之间混合，然后继续从单位温度的分布中采样。

并行回火（parallel tempering）中马尔可夫链并行地模拟许多不同温度的不同状态。最高温度的状态混合较慢，相比之下最低温度的状态，即温度为时，采出了精确的样本。转移算子包括了两个温度之间的随机跳转，所以一个高温度状态分布槽中的样本有足够大的概率跳转到低温度分布的槽中。

深度也许会有助于混合

当我们从潜变量模型中采样时，我们可以发现如果将编码得非常好，那么从中采样时，并不会太大地改变，那么混合结果会很糟糕。解决这个问题的一种方法是使得成为一种将编码为的深度表示，从而使得马尔可夫链在空间中更容易混合。