《统计学习方法》第十九章 马尔可夫链蒙特卡罗法

马尔可夫链蒙特卡罗法

蒙特卡罗法是通过基于概率模型的抽样进行数值近似计算的方法

蒙特卡罗法可以用于概率分布的抽样、概率分布数学期望的估计、定积分的近似计算

随机抽样是蒙特卡罗法的一种应用，有直接抽样法、接受拒绝抽样法等

接受拒绝法的基本想法是，找一个容易抽样的建议分布

其密度函数的数倍大于等于想要抽样的概率分布的密度函数按照建议分布随机抽样得到样本

再按要抽样的概率分布与建议分布的倍数的比例随机决定接受或拒绝该样本，循环执行以上过程

---

马尔可夫链蒙特卡罗法数学期望估计是蒙特卡罗法的另一种应用

按照概率分布$p(x)$抽取随机变量$x$的$n$个独立样本，根据大数定律可知，当样本容量增大时，函数的样本均值以概率$1$收敛于函数的数学期望

$${\hat{f}}_n\to E_{p(x)}[f(x)],n\to \infty$$

计算样本均值${\hat{f}}_n$，作为数学期望$E_{p(x)}[f(x)]$ 的估计值

---

马尔可夫链是具有马尔可夫性的随机过程

$$P(X_t|X_0{X}_1\cdots X_{t-1})=P(X_t|X_{t-1}),t=1,2,\cdots$$

考虑时间齐次马尔可夫链有离散状态马尔可夫链和连续状态马尔可夫链

分别由概率转移矩阵$P$和概率转移核$p(x,y)$定义

满足$\pi =P\pi$或$\pi (y)=\int p(x,y)\pi (x)dx$的状态分布称为马尔可夫链的平稳分布

马尔可夫链有不可约性、非周期性、正常返等性质一个马尔可夫链若是不可约、非周期、正常返的

则该马尔可夫链满足遍历定理当时间趋于无穷时，马尔可夫链的状态分布趋近于平稳分布，函数的样本平均依概率收敛于该函数的数学期望

$${\lim }_{t\to \infty }P(X_t=i|X_0=j)={\pi }_i,i=1,2,\cdots ;j=1,2$$

$${\hat{f}}_t\to E_{\pi }[f(X)],t\to \infty$$

可逆马尔可夫链是满足遍历定理的充分条件

---

马尔可夫链蒙特卡罗法是以马尔可夫链为概率模型的蒙特卡罗积分方法，其基本想法如下

1. 在随机变量$x$的状态空间$\chi$上构造一个满足遍历定理条件的马尔可夫链，其平稳分布为目标分布$p(x)$；

2. 由状态空间的某一点$X_0$出发，用所构造的马尔可夫链进行随机游走，产生样本序列$X_1,X_2,\cdots ,X_t,\cdots$；

3. 应用马尔可夫链遍历定理，确定正整数$m$和$n(m<n)$，得到样本集合 { x m + 1 , x m + 2 , ⋯   , x n } \{ x _ { m + 1 } , x _ { m + 2 } , \cdots , x _ { n } \} {xm+1​,xm+2​,⋯,xn​}，进行函数$f(x)$的均值（遍历均值）估计

$$\hat{E}f=\frac{1}{n-m}\sum _{i=m+1}^{n}f(x_i)$$

4. Metropolis-Hastings算法是最基本的马尔可夫链蒙特卡罗法假设目标是对概率分布$p(x)$进行抽样，构造建议分布$q(x,x^{\prime })$，定义接受分布$\alpha (x,x^{\prime })$进行随机游走，假设当前处于状态$x$，按照建议分布$q(x,x^{\prime })$机抽样，按照概率$\alpha (x,x^{\prime })$接受抽样，转移到状态 $x^{\prime }$，按照概率$1-\alpha (x,x^{\prime })$拒绝抽样，停留在状态$x$，持续以上操作，得到一系列样本这样的随机游走是根据转移核为$p(x,x^{\prime })=q(x,x^{\prime })\alpha (x,x^{\prime })$的可逆马尔可夫链（满足遍历定理条件）进行的，其平稳分布就是要抽样的目标分布$p(x)$

5. 吉布斯抽样（Gibbs sampling）用于多元联合分布的抽样和估计吉布斯抽样是单分量 Metropolis-Hastings-算法的特殊情况这时建议分布为满条件概率分布$$q(x,x^{\prime })=p(x_j^{\prime }|x_{-j})$$

吉布斯抽样的基本做法是，从联合分布定义满条件概率分布，依次从满条件概率分布进行抽样

得到联合分布的随机样本假设多元联合概率分布为$p(x)=p(x_1,x_2,\cdots ,x_k)$

吉布斯抽样从一个初始样本$x^{(0)}=(x_1^{(0)},x_2^{(0)},\cdots ,x_k^{(0)}{)}^T$出发，不断进行迭代

每一次迭代得到联合分布的一个样本$x^{(i)}=(x_1^{(i)},x_2^{(i)},\cdots ,x_k^{(i)}{)}^T$

在第$i$次迭代中，依次对第$j$个变量按照满条件概率分布随机抽样$p(x_j|x_1^{(i)},\cdots ,x_{j-1}^{(i)},x_{j+1}^{(i-1)},\cdots ,x_k^{(i-1)}),j=1,2,\cdots ,k$

得到$x_j^{(i)}$最终得到样本序列 { x ( 0 ) , x ( 1 ) , ⋯   , x ( n ) } \{ x ^ { ( 0 ) } , x ^ { ( 1 ) } , \cdots , x ^ { ( n ) } \} {x(0),x(1),⋯,x(n)}

---

蒙特卡洛法（Monte Carlo method)

蒙特卡洛法也称为统计模拟方法 (statistical simulation method) ， 是通过从概率模型的随机抽样进行近似数值计

算的方法 马尔可夫链陟特卡罗法 (Markov Chain Monte Carlo, MCMC)， 则是以马尔可夫链 (Markov chain）为概率模型的蒙特卡洛法

马尔可夫链蒙特卡罗法构建一个马尔可夫链，使其平稳分布就是要进行抽样的分布， 首先基于该马尔可夫链进行随机游走

产生样本的序列

之后使用该平稳分布的样本进行近似数值计算

Metropolis-Hastings算法是最基本的马尔可夫链蒙特卡罗法，Metropolis等人在 1953年提出原始的算法，Hastings在1970年对之加以推广

形成了现在的形式吉布斯抽样(Gibbs sampling)是更简单、使用更广泛的马尔可夫链蒙特卡罗法，1984 年由S. Geman和D. Geman提出

马尔可夫链蒙特卡罗法被应用于概率分布的估计、定积分的近似计算、最优化问题的近似求解等问题

特别是被应用于统计学习中概率模型的学习

与推理，是重要的统计学习计算方法

---

一般的蒙特卡罗法有直接抽样法、接受-拒绝抽样法、 重要性抽样法等

接受-拒绝抽样法、重要性抽样法适合于概率密度函数复杂 （如密度函数含有多个变量，各变量相互不独立，密度函数形式复杂）

不能直接抽样的情况

---

数学期望估计

一舣的蒙特卡罗法， 如直接抽样法、接受·拒绝抽样法、重要性抽样法， 也可以用于数学期望估计 （estimation Of mathematical expectation)

假设有随机变量$x$， 取值 $x\in X$, 其概率密度函数为 $p(x)$, $f(x)$ 为定义在 $X$ 上的函数， 目标是求函数 $f(x)$ 关于密度函数 $p(x)$ 的数学期望 $E_{p(x)}[f(x)]$

针对这个问题，蒙特卡罗法按照概率分布 $p(x)$ 独立地抽取 $n$ 个样本$x_1,x_2,...,x_n$，比如用以上的抽样方法，之后计算函

数$f(x)$的样本均值${\hat{f}}_n$

${\hat{f}}_n=\frac{1}{n}{\sum }_{i=1}^{n}f(x_i)$

作为数学期望$E_{p(x)}[f(x)]$近似值

根据大数定律可知， 当样本容量增大时， 样本均值以概率1收敛于数学期望：

${\hat{f}}_n\to E_{p(x)}[f(x)],n\to \infty$

这样就得到了数学期望的近似计算方法：

$E_{p(x)}[f(x)]\approx \frac{1}{n}{\sum }_{i=1}^{n}f(x_i)$

---

马尔可夫链

考虑一个随机变量的序列 $X=X_0,X_1,...,X(t),...$ 这里 $X_t$，表示时刻 $t$ 的随机变量， $t=0,1,2...$.

每个随机变量 $X_t(t=0,1,2,...)$ 的取值集合相同， 称为状态空间， 表示为$S$. 随机变量可以是离散的， 也可以是连续的

以上随机变量的序列构成随机过程（stochastic process)

假设在时刻 $0$ 的随机变量 $X_0$ 遵循概率分布 $P(X_0)=\pi$，称为初始状态分布在某个时刻 $t>=1$ 的随机变量 $X_t$与前

一个时刻的随机变量 $X_{t-1}$ 之间有条件分布 $P(X_t|X_{t-1})$ 如果 $X_t$ 只依赖于 $X_{t-1}$, 而不依赖于过去的随机变量

$X_0，X_1,...，X_{t-2}$ 这一性质称为马尔可夫性，即

$P(X_t|X_0,X_1,...,X_{t-1})=P(X_t|X_{t-1}),t=1,2,...$

具有马尔可夫性的随机序列$X=X_0,X_1,...,X(t),...$称为马尔可夫链， 或马尔可夫过程（Markov process) 条件概率分布

$P(X_t|X_{t-1})$ 称为马尔可夫链的转移概率分布 转移概率分布决定了马尔可夫裢的特性\n

---

平稳分布

设有马尔可夫链$X=X_0,X_1,...,X(t),...$，其状态空间为 $S$,转移概率矩阵为 $P=(p_{ij})$， 如果存在状态空间 $S$ 上的一个分布

π = [ π 1 π 2 ⋮ ] \pi =

π=⎣⎢⎢⎢⎢⎢⎡​π1​π2​⋮​⎦⎥⎥⎥⎥⎥⎤​

使得

$\pi =P\pi$

则称丌为马尔可夫裢$X=X_0,X_1,...,X(t),...$的平稳分布

直观上，如果马尔可夫链的平稳分布存在，那么以该平稳分布作为初始分布

面向未来进行随机状态转移，之后任何一个时刻的状态分布都是该平稳分布

---

引理

给定一个马尔可夫链$X=X_0,X_1,...,X(t),...$, 状态空间为$S$, 移概率矩阵为$P=(p_{ij})$， 则分布 $\pi =({\pi }_1,{\pi }_2,...{)}^T$ 为 $X$ 的平稳分布的充要条件是$\pi =({\pi }_1,{\pi }_2,...{)}^T$是下列方程组的解

$x_i={\sum }_j{p}_{ij}{x}_j,i=1,2,...$

$x_i>=0,i=1,2,...$

${\sum }_i{x}_i=1$ \n

---

吉布斯采样

输入： 目标概率分布的密度函数$p(x)$, 函数$f(x)$;

输出： $p(x)$的随机样本 $x_{m+1},x_{m+2},...,x_n$，函数样本均值 $f_{mn}$;

参数： 收敛步数$m$, 迭代步数 $n$.

1. 初始化给出初始样本 $x^{0} = $($x^{0}{1}, x^{0}{2},…, x^{0}_{k}$)${T}$.

2. 对$i$循环执行
   设第$i-1$次迭代结束前的样本为$x^{i-1} = $($x^{i-1}{1}, x^{i-1}{2},…, x^{i-1}_{k}$)${T}$，则第$i$次迭代进行如下几步操作：

• (1)由满条件分布 $p(x_1|x_2^{i-1},...,x_k^{i-1})$ 抽取 $x_1^i$

• …

• (j)由满条件分布 $p(x_j|x_1^i,...,x_{j-1}^i,x_{j+1}^{i-1},...,x_k^{i-1})$ 抽取 $x_j^i$

• (k)由满条件分布 $p(x_k|x_1^i,...,x_k^i)$ 抽取 $x_k^i$

得到第 $i$ 次迭代值 $x^{(i)}=(x_1^{(i)},x_2^{(i)},...,x_k^{(i)}{)}^T$.

3. 得到样本集合

{$x^{(m+1)},x^{(m+2)},...,x^{(n)}$}

4. 计算

$f_{mn}=\frac{1}{n-m}{\sum }_{i=m+1}^{n}f(x^{(i)})$

---