一、目录

1、采样方法的原理

2、常见的几种蒙德卡罗采样方法

  a.均匀采样

  b.接受-拒绝采样

  c.重要性采样

3、马尔科夫链简介

4、MCMC算法

  a.Metropolis-Hasting算法

  b.Gibbs Sampling算法

二、采样方法的原理

  我们通常求一个积分时，对于可以直接积分出来的函数是非常好求解的，但是当我们遇到一个积分不好算或者说根本积分积不出来的函数 p ( x ) p(x) p(x)时，我们应该怎么做呢？
  我们的方法就是通过采样的方法来计算他的积分，我们假设X是一个随机变量，他的概率密度函数是 p ( x ) p(x) p(x)，我们要求解的是函数 f ( x ) f(x) f(x)的积分：
∫ a b f ( x ) d x \int^b_a{f(x)}{\rm d}x ∫ab​f(x)dx
  那么由于我们对于 f ( x ) f(x) f(x)积分没办法积出来，那么我们可以引入概率密度函数 p ( x ) p(x) p(x)，即：
∫ a b f ( x ) p ( x ) p ( x ) d x \int^b_a{\frac{f(x)}{p(x)}p(x)}{\rm d}x ∫ab​p(x)f(x)​p(x)dx
  我们将对概率密度函数 p ( x ) p(x) p(x)进行采样，得到N个x（N要足够大）,然后我们可以用得到的N个x来近似计算得到 f ( x ) p ( x ) \frac{f(x)}{p(x)} p(x)f(x)​的期望，即：
∫ a b f ( x ) d x = ∫ a b f ( x ) p ( x ) p ( x ) d x = E [ f ( x ) p ( x ) ] = 1 N ∑ i = 1 N f ( x i ) p ( x i ) \int^b_a{f(x)}{\rm d}x=\int^b_a{\frac{f(x)}{p(x)}p(x)}{\rm d}x=E[\frac{f(x)}{p(x)}]=\frac{1}{N}\displaystyle\sum_{i=1}^{N} \frac{f(x_i)}{p(x_i)} ∫ab​f(x)dx=∫ab​p(x)f(x)​p(x)dx=E[p(x)f(x)​]=N1​i=1∑N​p(xi​)f(xi​)​

三、常见的蒙德卡罗采样方法

a、均匀采样（略）

  在这里就步过多阐述，在matlab中可以直接生成均匀分布 U ( a , b ) U(a,b) U(a,b)中的随机数。

b、接受-拒绝采样

  对于一个未知的分布 p ( x ) p(x) p(x)，我们采样不容易进行，所以在这里我们就要引入一个 q ( x ) q(x) q(x)分布，被称之为提议分布(proposal distribution).（注：我们提出的 q ( x ) q(x) q(x)的分布是一个已知的，易于采样的，比如所高斯分布），然后根据一定的规则，我们接受一部分样本，拒绝一部分样本。
  具体的算法如下：
    a、首先选取一个已知的分布 q ( x ) q(x) q(x)并且取一个常数K使得对于所有的x都有 K q ( x ) ≥ p ( x ) Kq(x)\geq p(x) Kq(x)≥p(x);
    b、我们从 q ( x ) q(x) q(x)中抽样得到一个随机数x0;
    c、然后，我们再从均匀分布 U ( 0 , K q ( x 0 ) ) U(0,Kq(x0)) U(0,Kq(x0))中随机抽样得到一个数b0;
    d、看b0的位置是在 p ( x ) p(x) p(x)的上方还是下方，如果是在 p ( x ) p(x) p(x)的下方则接受随机数x0；如果是在 p ( x ) p(x) p(x)的上方则拒绝x0.
    e、重复上述b到d过程N次，得到m个接受的x值，以此来计算均值。
  接受-拒绝采样算法图如下：

c、重要性采样

  当我们在一定的采样频率条件下，要求提高采样的精度，此时我们就应该用到重要性采样，假设我们已知x服从 p ( x ) p(x) p(x)的概率分布，但是 p ( x ) p(x) p(x)比较复杂，不容易采样得到样本x，那我由此我们引入一个与 p ( x ) p(x) p(x)有相同定义域的概率分布 q ( x ) q(x) q(x)，我们将 p ( x ) q ( x ) \frac{p(x)}{q(x)} q(x)p(x)​称之为重要性权重。式子如下所示：
E ( f ( x ) ) = ∫ a b f ( x ) p ( x ) d x = ∫ a b f ( x ) p ( x ) q ( x ) q ( x ) d x E(f(x))=\int^b_a{f(x)p(x)}{\rm d}x=\int^b_a{f(x)\frac{p(x)}{q(x)}q(x)}{\rm d}x E(f(x))=∫ab​f(x)p(x)dx=∫ab​f(x)q(x)p(x)​q(x)dx
  所以由上式可以得到，当我们从概率分布 p ( x ) p(x) p(x)中，不容易采样得到样本时，我们可以引入一个容易采样的概率分布 q ( x ) q(x) q(x)，这样我们就可以求得函数 f ( x ) p ( x ) q ( x ) f(x)\frac{p(x)}{q(x)} f(x)q(x)p(x)​关于概率分布 q ( x ） ) q(x）) q(x）)的期望值。即：
∫ a b f ( x ) p ( x ) q ( x ) q ( x ) d x = E q ( x ) [ f ( x ) p ( x ) q ( x ) ] = 1 N ∑ i = 1 N f ( x i ) p ( x i ) q ( x i ) \int^b_a{f(x)\frac{p(x)}{q(x)}q(x)}{\rm d}x=E_{q(x)}[f(x)\frac{p(x)}{q(x)}]=\frac{1}{N}\displaystyle\sum_{i=1}^{N} f(x_i)\frac{p(x_i)}{q(x_i)} ∫ab​f(x)q(x)p(x)​q(x)dx=Eq(x)​[f(x)q(x)p(x)​]=N1​i=1∑N​f(xi​)q(xi​)p(xi​)​

四：马尔科夫链简介

  马尔科夫链实际上是一个概率图模型，他是状态空间中一个状态转向另一个状态的随机过程，如下图所示（描述的是三个状态之间的转移）：

  各个状态之间转移的概率可以构成状态转移矩阵 a i j a_{ij} aij​，我们给定一个状态，那么在时间序列下，状态会随着状态转移矩阵而发生改变。并且，下一个时刻的状态只与前一时刻的状态相关，而与k-2…时刻的状态无关。

马尔科夫链平稳状态

  以上面三个状态为例，假设一开始我们选择初始概率分布 π ( 0 ) \pi(0) π(0)时，随着采样的进行，最后的三个状态的概率分布会趋于一个定值分布，也就是平稳分布。即：
π ( n ) = π ( n − 1 ) a i j = π ( 0 ) a i j n \pi(n)=\pi(n-1)a_{ij}=\pi(0)a_{ij}^n π(n)=π(n−1)aij​=π(0)aijn​

五、MCMC算法

基本想法：
  假设目标是对一个概率分布进行随机抽样或者求的是函数关于该概率分布的数学期望，我们可以采用传统的蒙德卡罗的采样方法，比如说：接受-拒绝采样、重要性采样等等。当然我们也可以用马尔可夫链蒙德卡罗采样法。他一般来说更适用于随机变量是多元的、密度函数是非标准的（无法直接采样的）等情况。
  我们假设多元随机变量x，其概率密度函数是 p ( x ) p(x) p(x)， f ( x ) f(x) f(x)为定义在多元随机变量定义域上的函数，现在我们的目标是要得到关于概率分布 p ( x ) p(x) p(x)的样本集合，或者是求得 f ( x ) f(x) f(x)关于概率密度 p ( x ) p(x) p(x)的期望 E p ( x ) [ f ( x ) ] E_{p(x)}[f(x)] Ep(x)​[f(x)]。
  基本思路：在随机变量x的状态空间S上定义一个满足遍历定理的马尔可夫链X={X0,X1,…Xt,…}，使得平稳分布就是抽样的目标分布 p ( x ) p(x) p(x)。然后在这个马尔可夫链上开始随机游走，每个时刻得到一个样本。根据遍历定理，当时间趋于无穷时，样本的分布是趋于平稳分布的，样本的函数均值趋于函数的期望均值。所以说当时间足够长时(比如说当n>m时)(从时刻1到m我们称之为燃烧期)，在m时刻之后的时间里随机游走得到的样本值就是对目标分布抽样的结果，得到的函数均值就是近似函数的数学期望。
  马尔可夫蒙特卡罗法基本步骤：
    a、首先，在随机变量x的状态空间S上构造一个满足遍历定理的马尔科夫链，使其平稳分布为目标分布 p ( x ) p(x) p(x)。
    b、从状态空间中的某一点开始出发，用构造的马尔科夫链进行随机游走，产生样本序列x0,x1,…xt。
    c、确定正整数m和n，得到样本值集合{xm+1,…xn}。求的函数 f ( x ) f(x) f(x)的均值：
E p ( x ) [ f ( x ) ] = 1 n − m ∑ i = m + 1 n f ( x i ) E_{p(x)}[f(x)]=\frac{1}{n-m}\displaystyle\sum_{i=m+1}^{n} f(x_i) Ep(x)​[f(x)]=n−m1​i=m+1∑n​f(xi​)

a、Metropolis-Hasting算法

  首先先定义采样时刻t-1的采样值为 x x x，t时刻的采样值为 x ′ x' x′，所以对于要抽样的概率分布 p ( x ) p(x) p(x),采用转移核为 p ( x , x ′ ) p(x,x') p(x,x′)的马尔科夫链：
p ( x , x ′ ) = q ( x , x ′ ) α ( x , x ′ ) p(x,x')=q(x,x')\alpha(x,x') p(x,x′)=q(x,x′)α(x,x′)其中 q ( x , x ′ ) q(x,x') q(x,x′)和 α ( x , x ′ ) \alpha(x,x') α(x,x′)分布被称之为提议分布和接受率。而提议分布是另一个马尔可夫链的转移核，是一个比较容易抽样的分布。而接受分布 α ( x , x ′ ) \alpha(x,x') α(x,x′)是:
α ( x , x ′ ) = m i n { 1 , p ( x ′ ) q ( x ′ , x ) p ( x ) q ( x , x ′ ) } \alpha(x,x')=min\{1,\frac{p(x')q(x',x)}{p(x)q(x,x')}\} α(x,x′)=min{1,p(x)q(x,x′)p(x′)q(x′,x)​}所以对于Metropolis-Hasting算法他的步骤是：
  输入：抽样的目标分布函数 p ( x ) p(x) p(x)，函数 f ( x ) f(x) f(x)；
  (1)、任意选择一个初值 x 0 x_0 x0​;
  (2)、对于 i = 1 , 2 , . . . . . . . . n i=1,2,........n i=1,2,........n循环执行以下操作：
    a、设状态 x i − 1 = x x_{i-1}=x xi−1​=x,按照提议分布 q ( x , x ′ ) q(x,x') q(x,x′)随机抽取一个候选状态 x ′ x' x′。
    b、计算接受率 α ( x , x ′ ) \alpha(x,x') α(x,x′):
α ( x , x ′ ) = m i n { 1 , p ( x ′ ) q ( x ′ , x ) p ( x ) q ( x , x ′ ) } \alpha(x,x')=min\{1,\frac{p(x')q(x',x)}{p(x)q(x,x')}\} α(x,x′)=min{1,p(x)q(x,x′)p(x′)q(x′,x)​}
    c、从区间(0,1)中按照均匀分布随机抽取一个数u。若 α ( x , x ′ ) ≥ u \alpha(x,x') \geq u α(x,x′)≥u则状态 x i = x ′ x_i=x' xi​=x′，否则，状态 x i = x x_i=x xi​=x。
  (3)、得到样本集合{xm+1,…xn}，计算：
f m n = 1 n − m ∑ i = m + 1 n f ( x i ) f_{mn}=\frac{1}{n-m}\displaystyle\sum_{i=m+1}^{n} f(x_i) fmn​=n−m1​i=m+1∑n​f(xi​)

b、Gibbs Sampling算法(多元的，Metropolis-Hasting算法是其一个特例)