PRML学习笔记(十一)

第十一章 采样方法

Posted by Pelhans on January 2, 2019

PRML 和 ESL 的学习基本上是学十得一。稳扎稳打再来一次

采样方法

第十章我们介绍了基于确定性近似的推断方法,它包括诸如变分贝叶斯方法及期望传播。现在我们考虑基于数值采样的近似推断方法,也被称为蒙特卡洛方法。在大部分情况下,后验概率分布的主要用途是计算期望,因此,在本章中,我们希望解决的问题涉及到关于一个概率分布p(z)寻找某个函数f(z)的期望。现在我们假设使用解析的方法精确地求出这种期望是十分复杂的。

采样方法背后的一般思想是得到从概率分布p(z)中独立抽取一组变量$z^{(l)}$,其中$l=1,\dots,L$。这使得期望可以通过有限和的方式计算,即:

这要样本$z^{(l)}$是从概率分布p(z)抽取的,那么$E[\hat{f}] = E[f]$,因此估计值$\hat[f]$具有正确的均值。估计的方差为:

它是函数f(z)在概率分布p(z)下的方差。

11.1 基本采样方法

11.1.1 标准概率分布

首先介绍如何从简单的非均匀分布中生成随机数。假设z在区间(0,1)上均匀分布,使用某个函数f(*)对z值进行变换,即$y = f(z) $, y上的概率分布为

我们的目标是选择一个函数f(z)使得产生出的y值具有某种所需的具体的分布形式p(y),对上式进行积分,我们有

它是p(y)的不定积分,因此,$y = h^{-1}(z)$,所以我们必须使用一个函数来对这个均匀分布的随机数进行变换,这个函数是所求的概率分布的不定积分的反函数

例如,我们想让y服从指数分布:

因此,根据上式,对p(y)进行积分,我们有:

也就是说,我们只需要对均匀分布z进行如下变换:

那么 y就会服从指数分布。

11.1.2 拒绝采样

拒绝采样框架使得我们能够在满足某些限制条件的情况下,从相对复杂的概率分布中采样。假设我们希望从概率分布p(z)中采样,而且直接从p(z)中采样是很困难的。此外,假设我们能够很容易地计算对于任意给定的z值的p(z)(不考虑归一化常数Z),即

其中$\tilde{p}(z)$可以很容易的计算,但是$Z_{p}$未知。

在应用拒绝采样法之前,我们先要定义几个概念。首先我们需要一些简单的概率分布q(z),有时被称为提议分布,并且我们已经可以从提议分布中进行采样。而后引入一个常数k,它的值要满足下面的性质:对于所有的z值,都有$kq(z) \geq \tilde{p}(z) $。函数$kq(z)$被称为比较函数。

拒绝采样的每个步骤涉及到生成两个随机数,首先,我们从概率分布q(z)中生成一个数$z_{0}$,而后在区间$[0, kq(z_{0})]$上的均匀分布中生成一个数$u_{0}$。这对随机数在函数$kq(z)$的曲线下方是均匀分布。最后,如果$u_{0} \gt \tilde{p}(z_{0}) $,那么样本被拒绝,否则$u_{0}$被保留。这样剩余的点对在曲线$\tilde{p}(z)$下方是均匀分布的,因此对应的z值服从概率分布$p(z)$。

z的原始值从概率分布q(z)中生成,这些样本之后被接受的概率为$\frac{\tilde{p}(z)}{kq}(z)$,因此一个样本会被接受的概率为:

11.1.4 重要采样

重要采样方法提供了直接近似期望的框架,但是它本身并没有提供从概率分布p(z)中采样的方法。一种简单的计算期望的方法是将z空间离散化为均匀的格点,将北极函数使用求和的方式计算,形式为:

但该方法的明显问题是求和式中的项的数量随着z的维度指数增长,同时只有非常小的一部分样本会对求和式产生巨大的贡献。因此我们希望从p(z)的值较大的区域中采样,或者理想情况下,从$p(z)f(z)$的值较大的区域中采样。

重要采样基于的是对提议分布q(z)的使用,我们很容易从提议分布中采样。之后我们可以通过q(z)中的样本{z^{(l)}}的有限和的形式来表示期望:

$ r_{l} = \frac{p(z^{(l)})}{q(z^{(l)})}$被称为重要性权重,修正了由于从错误的概率分布中采样引入的偏差。注意,与拒绝采样不同,所有生成的样本都被保留。

11.1.6 采样与EM算法

对于EM算法中的E步骤无法解析计算的模型,采样方法也可以用来对其近似。考虑一个模型,它的隐含变量为Z,可见(观测)变量为X,参数为$\theta$,在M步骤中关于$\theta$最大化的步骤为完整数据对数似然的期望,形式为:

对该积分的近似可以通过计算样本${Z^{(l)}}$上的有限和来得到,这些样本从当前对后验概率分布 $p(Z | X, \theta^{旧})$的估计中抽取,即:

然后,Q函数在M步骤使用通常的步骤进行优化。这个步骤被称为蒙特卡洛EM算法。

11.2 马尔科夫链蒙特卡洛

与拒绝采样和重要采样相同,我们再一次从提议分布中采样。但是这次我们记录下当前状态$z^{(\tau)}$以及依赖于这个当前状态的提议分布 $q(z | z^{\tau})$,从而样本序列$z^{(1)}, z^{(2)}, \dots$组成了一个马尔科夫链。

假设提议分布足够简单很容易直接采样,所求分布$\tilde{p}(z)$很容易计算值。

在算法的每次迭代中,我们从提议分布中生成一个候选样本$z^{*}$,然后根据一个恰当的准则接受这个样本。

在基本的 Metropolis 算法中,我们假定提议分布是对称的,即 $q(z_{A} | z_{B}) = q(z_{B} | z_{A}) $对于所有的 $z_{A}$ 和 $z_{B}$都成立。这样,候选样本被接受的概率为:

当接受概率大于预设值u时,则接受这个样本。如果候选样本被接受,那么$z^{(\tau + 1)} = z^{\ast}$,否则候选样本点$z^{\ast}$被抛弃,$z^{(\tau + 1)}$被设置为$z^{(\tau)}$,然后从概率分布 $q(z | z^{(\tau+1)})$中再次抽取一个候选样本。

可以看到,在 Metropolis 算法中,当一个候选点被拒绝时,前一个样本点会被包含到是最终的样本的列表中,从而产生了这个样本点的多个副本。虽然在实际中我们只会保留一个样本副本,以及一个整数的权因子,记录状态出现了多少次。设计马尔科夫链蒙特卡洛方法的一个中心目标就是避免随机游走行为。

11.2.1 马尔科夫链

一阶马尔科夫链被定义为一系列随机变量$z^{(1)}, \dots, z^{(M)}$,使得下面的条件独立性质对于 $m\in {1, \dots, M-1}$成立:

我们可以如下构建一个马尔科夫链:给定初始变量的概率分布$p(z^{(0)})$,以及后续变量的条件概率,用转移概率 $T_{m}(z^{(m)}, z^{(m+1)}) \equiv p(z^{(m+1)} | z^{(m)}) $的形式表示。如果对所有的m,转移概率都相同,那么马尔科夫链被称为同质的。

确保所求边缘概率p(z)不变的一个充分(非必要)条件是令转移概率满足细节平衡性质,定义为:

满足细节平衡性质的马尔科夫链被称为可翻转的。我们的目标是使用马尔科夫链从一个给定的概率分布中采样。如果我们构造一个马尔科夫链使得所求的概率分布是不变的,那么我们就可以达到这个目标。除此之外,我们还要求对于$m\rightarrow \infty$,概率分布$p(z^{(m)})$收敛到所求的不变的概率分布$p^{*}(z)$,与初始概率分布$p(z^{(0)})$无关,这种性质被称为各态历经性,这个不变的概率分布被称为均衡分布。

11.2.2 Metropolis-Hasting 算法

与 Metropolis 算法相比,提议分布不再是参数的一个对称函数,特别低,在算法的步骤$\tau$中,当前状态为$z^{\tau}$,我们从概率分布 $q_{k}(z | z^{\tau})$中抽取一个样本$z^{\ast}$,然后以概率$A_{k}(z^{*}, z^{(\tau)})$接受它,其中:

其中k标记出可能的转移集合中的成员,对于一个对称的提议分布, Metropolis-Hasting 准则会退化为 Metropolis 准则。

提议分布的具体选择会对算法的表现产生重要的影响,对于连续状态空间来说,一个常见的选择是一个以当前状态为中心的高斯分布,这会在确定分布的方差参数时需要一个重要的折中,如果方差过小,那么接受的转移的比例会很高,但是便利状态空间的形式是一个缓慢的随机游走过程,导致较长的开销时间。反之方差过大导致拒绝率较高。因此提议分布的标度赢尽可能的大,同时要避免达到较高的拒绝率。

11.3 吉布斯采样

吉布斯采样是一个简单的并且广泛应用的马尔科夫链蒙特卡洛算法,可以看做 Metropolis-Hasting 算法的一个具体的情形

考虑我们项采样的概率分布$ p(z) = p(z_{1}, \dots, z_{M})$,并且假设我们已经选择了马尔科夫链的某个初始状态。吉布斯采样的每个步骤涉及到将一个变量的值替换为以剩余变量的值为条件,从这个概率分布中抽取的那个变量的值。具体流程如下:

  • 初始化 ${z_{i}: i=1, \dots, M}$。
  • 对于$\tau = 1,\dots, T$:
    • 采样$z_{1}^{(\tau+1)} ~ p(z_{1} z_{2}^{(\tau)}, z_{3}^{(\tau)}, \dots, z_{M}^{(\tau)})$
    • 采样 $z_{2}^{(\tau+1)} ~ p(z_{2} z_{1}^{(\tau+1)}, z_{3}^{(\tau)}, \dots,z_{M}^{(\tau)})$
    • $\vdots$
    • 采样 $z_{j}^{(\tau+1)} ~ p(z_{j} z_{1}^{(\tau+1)}, \dots, z_{j-1}^{(\tau+1)}, z_{j+1}^{(\tau)}, z_{M}^{(\tau)})$
    • $\vdots$
    • 采样 $z_{M}^{(\tau+1)} ~ p(z_{M} z_{1}^{(\tau+1)}, z_{2}^{(\tau+1)}, \dots, z_{M-1}^{(\tau+1)})$

11.4 切片采样

切片采样算法提供了一个可以自动调节步长来匹配分布特征的方法。首先考虑一元变量的情形。切片采样涉及到使用额外的变量p对z进行增光,然后从联合的(z,u)空间中采样。目标是从下面的概率分布:

}

中均匀的采样,其中$Z_{p} \int\tilde{p}(z)dz$。z上的边缘概率分布为:

因此我们可以通过从$\hat{p}(z,u)$中采样,然后忽略u值的方式得到p(z)的样本。通过交替的对z和u进行采样即可完成这一点。首先给定z的值,我们可以计算$\tilde{p}(z)$的值,然后在$0\leq u \leq\tilde{p}(z)$上均匀地对u进行采样。而后我们固定u,在由${z:\tilde{p}(z) > u}$定义的分布的“切片”上进行均匀地采样。一个例子如下图所示: