继续《深度学习》花书总结，本章主要介绍采样的蒙特卡洛方法，准备结合斯坦福CS 228 - Probabilistic Graphical Models课程相关内容一起总结。

首先，我们为什么需要采样（sampling)呢？因为我们通常要进行许多求和或者积分的近似计算，精确求值很困难，所以要进行采样来减小计算花费，比如前一章（结构化概率模型——深度学习第十六章）介绍的配分函数就涉及到积分运算，就需要进行近似计算。

假设我们数据的概率分布是 p(x) ，我们要求在这一分布上函数 f(x) 的期望，即 s=sum_xp(x)f(x)=E_p[f(x)] ，蒙特卡洛方法即是通过从 p(x) 中采样n个样本 x^{(1)},...,x^{(n)} ，并用经验平均值(empirical average)来近似s，即 hat s_n=frac{1}{n}sum_{i=1}^nf(x^{(i)}) 。Fun fact: 蒙特卡洛(Monte Carlo)名字来源于位于摩纳哥的蒙特卡洛赌场，就是下图中这个酒店，最初由美国曼哈顿计划中的物理学家们当做一种秘密代号。

为什么我们可以采用经验平均值来近似真实的期望呢？一是 hat s_n 是无偏估计(unbiased estimation)，即 E[hat s_n] = frac{1}{n}sum_{i=1}^nE[f(x^{(i)})] = frac{1}{n}sum_{i=1}^ns=s ，且根据大数定理，如果样本 x^{(i)} 是独立同分布，则 lim_{n ightarrowinfty} hat s_n = s ，另一方面， hat s_n 的方差与采样量n是成反比的，当采样量足够多时，我们可以很好的近似真实期望。

观察求和形式 p(x)f(x) 我们可以发现如何选取 p(x) 和 f(x) 并不是唯一的，即我们总可以将其分解为 p(x)f(x)=q(x)frac{p(x)f(x)}{q(x)} 的形式而不改变求和结果，我们可以将 q(x) 当做新的 p(x) 而 frac{p(x)f(x)}{q(x)} 当做新的 f(x) 。因此，我们可以从分布 q(x) 中取样，并利用 hat s_q = frac{1}{n} sum_{i=1,x^{(i)}sim q}^n frac{p(x^{(i)})f(x^{(i)})}{q(x^{(i)})} 求 f(x) 的期望，这一方法被称作重要采样importance sampling。那么我们什么时候需要importance sampling而不是直接从 p(x) 中取样呢？有时是因为相较于 p(x) ， q(x) 更方便采样，或者 q(x) 可使预测的方差更小。通过importance sampling的式子我们可以得到， E_q[hat s_q] = E_p[hat s_p] = s ，即 hat s_q 也是无偏估计，并且当 q^*(x)=frac{p(x)|f(x)|}{Z} ，其中 Z 是使 q^*(x) 归一的常数， Var[hat s_q]=0 ，即当分布q取为 q^*(x) 时，我们仅需要从中采样一个样本就可计算真实期望。当然，最优的 q^*(x) 需要计算原求和，我们又回到最初的问题，实际上无法采用，不过这有助于理解选取合适的 q(x) 可以有效的减小方差。

前一章我们提到对于有向图可以用ancestral sampling的方法采样，而对于无向图由于没法进行拓扑排序不能用ancestral sampling，解决方法之一是利用马尔可夫链蒙特卡罗方法(Markov Chain Monte Carlo， 简称MCMC)。

Markov Chain的核心思想是我们最初可以随机的选取初始状态，再不断的更新这一状态，最终使其分布近似于真实分布 p(x) 。假设Markov Chain可以由一序列状态 S_0,S_1,... 来表示，其中 S_iin {left{ 1,2,...,d ight}} ，代表系统可取的各种状态。初始状态满足 p(S_0) 分布，而之后的分布是依赖于前一时间点的条件概率分布，即 p(S_i|S_{i-1}) 。Markov假设对于每一步i， p(S_i|S_{i-1}) 是相同的，即当前状态仅依赖于前一时刻状态，而不依赖于其他历史状态。我们可以用转移矩阵来表示这一概率 T_{ij}=p(S_{new}=i|S_{prev}=j) ，假设初始的 S_0 分布为 p_0 ，则经过t步采样后，概率分布为 p_t = T^tp_0 ，其极限 pi = lim_{t ightarrowinfty}p_t 被称作平稳分布(stationary distribution)，在进入平稳分布后，后续的每一步 S=TS=S ，即进入稳态分布后，随著更多的采样的进行，分布并不会再进行改变。那么，在什么条件下，存在稳态分布呢？以下两条构成充分条件:

1.不可约性(Irreducibility)，在有限步骤中，可以从任一状态S到达另一状态S。这一条件保证不存在我们无法离开的黑洞状态。

2.非周期性(Aperiodicity)，任意时刻可以返回任意状态，即对于 ngeq n ， P(S_{n}=i|S_n=i)>0 。这一条件保证我们不存在这样的转移矩阵 T=egin{bmatrix} 0 & 1 \ 1 & 0 end{bmatrix} ，即在两个状态间来回变动而不能达到平稳分布。

为了满足以上条件，通常在利用MCMC方法时，我们采取基于能量的模型 p(x) propto exp(-E(x))。

假设我们有了转移矩阵为T且平稳分布为p的Markov Chain，我们怎么进行MCMC取样呢？

假设初始状态为 x_0 ，则我们先进行B次步进，使Markov Chain达到稳态，这一过程称为burn in，这一过程所需的时间称为混合时间mixing time。达到稳态后，我们再进行若干次Markov Chain采样，并利用这些样本来近似估计期望。当然实际应用中，达到稳态后，连续两次取样间还是强相关的，所以通常是采取每n次连续markov chain操作后取一个样本。为了使取样是相互独立的，我们也可以同时进行多个Markov Chain取样。

那么如何选取合适的转移操作使平稳分布接近真实分布p呢？一种方法是吉布斯采样(Gibbs Sampling)，即对于每一个变数，从依赖于图中其邻居节点的条件概率分布p中采样，对于相互条件独立的变数，我们也可以同时进行Gibbs Sampling。以如下所示的简单的无向图作为例子。

  • 随机初始化a,s,b。
  • 将下述步骤重复n次：
    • 从P(a|s)中采样a，从P(b|s)中采样b，由于a,b在s给定的条件下是条件独立的，所以a,b的采样可以同时进行。
    • 从P(s|a,b)中采样s。

Gibbs Sampling是Metropolis-Hastings采样演算法的一种特殊形式，关于这一类采样方法为什么会收敛于真实分布p可参见斯坦福cs228讲义Sampling methods中的推导。

利用MCMC方法的难点是如何判断我们已经达到稳态了，暂时还没有明确的理论指导markov chain是否到达稳态，何时能到达稳态，所以需要一些直观判断方法如人为的检验样本或观察连续采样间的关联。

另一个难点是混合时间过长，尤其是对于维数较多，变数间关联较强或者有若干峰值的概率分布，其混合时间很长。对于有若干峰值的情况，我们可以通过引入一个反比于温度（来源于统计物理概念）的参数 eta 来改变基于能量的模型的分布 p_eta (x) propto exp(-eta E(x)) ，当 eta <1 时，我们可以有效地混合不同峰值的分布。

总结一下，这一章主要介绍了用于近似某些求和或积分运算的蒙特卡洛采样方法如无向图中的Gibbs Sampling方法，下一章我们会看到如何将这些方法应用到配分函数的计算中, to be continued。

注：截图均来自Ian Goodfellow等合著的Deep Learning一书，推荐阅读原书。


推荐阅读：
查看原文 >>
相关文章