MC, MCMC, Gibbs采样原理&实现（in R）_mcmc采样算法-数据分析

MC, MCMC, Gibbs采样原理&实现（in R）

关键词：mcmc采样,mcmc采样算法,mcmc算法原理,ad采样原理,adc采样原理

本文用讲一下指定分布的随机抽样方法：MC(Monte Carlo), MC(Markov Chain), MCMC(Markov Chain Monte Carlo)的基本原理，并用R语言实现了几个例子：

1. Markov Chain （马尔科夫链）

2. Random Walk（随机游走）

3. MCMC具体方法：

3.1 M-H法

3.2 Gibbs采样

PS：本篇blog为ese机器学习短期班参考资料（20140516课程），课上讲详述。

下面三节分别就前面几点简要介绍基本概念，并附上代码。这里的概念我会用最最naive的话去概括，详细内容就看我最下方推荐的链接吧(*^__^*)

0. MC(Monte Carlo)

生成指定分布的随机数的抽样。

1. Markov Chain （马尔科夫链）

假设 f(t) 是一个时间序列，Markov Chain是假设f(t+1)只与f(t)有关的随机过程。

Implement in R:

2. Random Walk（随机游走）

如布朗运动，只是上面Markov Chain的二维拓展版：

Implement in R:

3. MCMC具体方法：

MCMC方法最早由Metropolis（1954）给出，后来Metropolis的算法由Hastings改进，合称为M-H算法。M-H算法是MCMC的基础方法。由M-H算法演化出了许多新的抽样方法，包括目前在MCMC中最常用的Gibbs抽样也可以看做M-H算法的一个特例[2]。

概括起来，MCMC基于这样的理论，在满足【平衡方程】（detailed balance equation）条件下，MCMC可以通过很长的状态转移到达稳态。

【平衡方程】：

pi(x) * P(y|x) = pi(y) * P(x|y)

其中pi指分布，P指概率。这个平衡方程也就是表示条件概率（转化概率）与分布乘积的均衡.

3.1 M-H法

1. 构造目标分布，初始化x0

2. 在第n步，从q(y|x_n) 生成新状态y

3. 以一定概率（(pi(y) * P(x_n|y)) / (pi(x) * P(y|x_n))）接受y <PS: 看看上面的平衡方程，这个概率表示什么呢？参考这里和[1]>

implementation in R:

#author: rachel @ ZJU
#email: zrqjennifer@gmail.com
N = 10000
x = vector(length = N)
x[1] = 0
# uniform variable: u
u = runif(N)
m_sd = 5
freedom = 5
for (i in 2:N)
{
y = rnorm(1,mean = x[i-1],sd = m_sd)
print(y)
#y = rt(1,df = freedom)
p_accept = dnorm(x[i-1],mean = y,sd = abs(2*y+1)) / dnorm(y, mean = x[i-1],sd = abs(2*x[i-1]+1))
#print (p_accept)
if ((u[i] <= p_accept))
{
x[i] = y
print(“accept”)
}
else
{
x[i] = x[i-1]
print(“reject”)
}
}
plot(x,type = ‘l’)
dev.new()
hist(x)

3.2 Gibbs采样

第n次，Draw $\theta_i^{n+1}$ from $pi(\theta_i | \theta_1^n,\theta_2^n, ... \theta_p^n \,\,without\,\, \theta_i^n)$ ，迭代采样结果接近真实p(\theta_1, \theta_2, …)

也就是每一次都是固定其他参数，对一个参数进行采样。比如对于二元正态分布，其两个分量的一元条件分布仍满足正态分布：

$f(x|y) \sim N(\mu_1+\rho \sigma_1/\sigma_2(y-\mu_2),\,\,(1-\rho^2)\sigma_1^2)$

$f(y|x) \sim N(\mu_2+\rho \sigma_2/\sigma_1(x-\mu_1),\,\,(1-\rho^2)\sigma_2^2)$

那么在Gibbs采样中对其迭代采样的过程，实现如下：

#author: rachel @ ZJU
#email: zrqjennifer@gmail.com
#define Gauss Posterior Distribution
p_ygivenx <– function(x,m1,m2,s1,s2)
{
return (rnorm(1,m2+rho*s2/s1*(x-m1),sqrt(1-rho^2)*s2 ))
}
p_xgiveny <– function(y,m1,m2,s1,s2)
{
return (rnorm(1,m1+rho*s1/s2*(y-m2),sqrt(1-rho^2)*s1 ))
}
N = 5000
K = 20 #iteration in each sampling
x_res = vector(length = N)
y_res = vector(length = N)
m1 = 10; m2 = -5; s1 = 5; s2 = 2
rho = 0.5
y = m2
for (i in 1:N)
{
for(i in 1:K)
{
x = p_xgiveny(y, m1,m2,s1,s2)
y = p_ygivenx(x, m1,m2,s1,s2)
# print(x)
x_res[i] = x;
y_res[i] = y;
}
}
hist(x_res,freq = 1)
dev.new()
plot(x_res,y_res)
library(MASS)
valid_range = seq(from = N/2, to = N, by = 1)
MVN.kdensity <– kde2d(x_res[valid_range], y_res[valid_range], h = 10) #估计核密度
plot(x_res[valid_range], y_res[valid_range], col = “blue”, xlab = “x”, ylab = “y”)
contour(MVN.kdensity, add = TRUE)#二元正态分布等高线图
#real distribution
# real = mvrnorm(N,c(m1,m2),diag(c(s1,s2)))
# dev.new()
# plot(real[1:N,1],real[1:N,2])