简单过了一遍高数线代概率论数理统计的知识后,进入了随机过程和拒绝采样,MCMC采样方法的学习。
拒绝采样
对于
概率分布不是常见的分布
,一个可行的办法是采用
接受-拒绝采样
来得到该分布的样本。既然 p(x) 太复杂在程序中没法直接采样,那么我设定一个程序可采样的分布 q(x) 比如高斯分布,然后按照一定的方法拒绝某些样本,以达到接近 p(x) 分布的目的,其中q(x)叫做 proposal distribution。
具体采样过程如下:
-
设定一个方便采样的常用概率分布函数 q(x),以及一个常量 k,使得 p(x) 总在
k∗
(
q
(
z
0
)
)
k*(q(z_0))
k
∗
(
q
(
z
0
)
)
的下方。如上图。 -
首先,采样得到q(x)的一个样本
z0
z_0
z
0
-
从均匀分布
[0
,
k
∗
(
q
(
z
0
)
]
[0,k*(q(z_0)]
[
0
,
k
∗
(
q
(
z
0
)
]
中采样得到一个值u - 如果u落在了上图中的灰色区域,则拒绝这次抽样,否则接受这个样本z0(即可认为这个样本是p(x)采样得到的样本)
-
重复以上过程得到n个接受的样本
z0
,
z
1
,
.
.
.
,
z
n
−
1
z_0,z_1,…,z_{n−1}
z
0
,
z
1
,
.
.
.
,
z
n
−
1
,则最后的蒙特卡罗方法求解结果为:
1n
∑
i
=
0
n
−
1
f
(
z
i
)
p
(
z
i
)
\frac{1}{n}\sum_{i=0}^{n-1}\frac{f(z_i)}{p(z_i)}
n
1
i
=
0
∑
n
−
1
p
(
z
i
)
f
(
z
i
)
整个过程中,我们通过一系列的接受拒绝决策来达到用q(x)模拟p(x)概率分布的目的。
MCMC采样
MCMC是什么?
作为一种
随机采样
方法,马尔科夫链蒙特卡罗(Markov Chain Monte Carlo,以下简称MCMC)
是马尔可夫链与蒙特卡罗方法这2个采样方法的结合
。在机器学习,深度学习以及自然语言处理等领域都有广泛的应用,是很多复杂算法求解的基础。
蒙特卡罗方法
蒙特卡罗方法是一种随机模拟的方法,最初的蒙特卡罗方法正如我们第一次在概率论课本的计算pi的“蒲丰投针”实验,主要用于测算不太好求解的求和、积分问题等。以[a,b]上
f
(
x
)
f(x)
f
(
x
)
的积分问题为例,蒙特卡罗方法就是采样[a,b]区间的n个值:x0,x1,…xn−1,用它们的均值来代表[a,b]区间上所有的f(x)的值,这样定积分求解问题便简化为
b
−
a
n
∑
i
=
0
n
−
1
f
(
x
i
)
\frac{b-a}{n}\sum_{i=0}^{n-1}f(x_i)
n
b
−
a
i
=
0
∑
n
−
1
f
(
x
i
)
虽然上面的方法可以一定程度上求解出近似的解,但是它隐含了一个假定,即x在[a,b]之间是均匀分布的,而绝大部分情况,x在[a,b]之间不是均匀分布的。如果我们用上面的方法,则模拟求出的结果很可能和真实值相差甚远。
怎么解决这个问题呢? 如果我们可以得到x在[a,b]的概率分布函数
p
(
x
)
p(x)
p
(
x
)
,那么我们的定积分求和可以这样进行:
θ
=
∫
a
b
f
(
x
)
d
x
=
∫
a
b
f
(
x
)
p
(
x
)
p
(
x
)
d
x
≈
1
n
∑
i
=
0
n
−
1
f
(
x
i
)
p
(
x
i
)
\theta=\int_{a}^{b} f(x)dx=\int_{a}^{b} \frac{f(x)}{p(x)}p(x)dx\approx \frac{1}{n}\sum_{i=0}^{n-1}\frac{f(x_i)}{p(x_i)}
θ
=
∫
a
b
f
(
x
)
d
x
=
∫
a
b
p
(
x
)
f
(
x
)
p
(
x
)
d
x
≈
n
1
i
=
0
∑
n
−
1
p
(
x
i
)
f
(
x
i
)
上式最右边的这个形式就是蒙特卡罗方法的一般形式。当然这里是
连续函数
形式的蒙特卡罗方法,但是在
离散
时一样成立。
马氏链
就是马尔可夫链,特征是某一时刻状态转移的概率只依赖于它的前一个状态。
作业:绘制Rosenbrock函数图并寻找局部最小值和全局最小值
给定下述Rosenbrock函数
f
(
x
)
=
(
a
−
x
1
)
2
+
b
∗
(
x
2
−
x
1
2
)
2
f(x)=(a-x_1)^2+b*(x_2-x_{1}^{2})^2
f
(
x
)
=
(
a
−
x
1
)
2
+
b
∗
(
x
2
−
x
1
2
)
2
,其中
a
,
b
∈
R
2
a,b\in R^2
a
,
b
∈
R
2
。试编写程序完成下述工作:
1)为不同的a,b取值,绘制该函数的3D表面。请问 a,b取值对该表面形状有大的影响吗?所谓大影响就是形状不再相似。对a,b的取值区间,能否大致给出一个分类。
解:通过编写python代码求解得:
a ∈ R a \in R a ∈ R |
|
---|---|
b ∈ ( − ∞ , 0 ) b\in(-\infty ,0) b ∈ ( − ∞ , 0 ) |
开口向下的曲面 |
b = 0 b=0 b = 0 |
斜平面 |
b ∈ ( 0 , ∞ ) b\in(0 ,\infty) b ∈ ( 0 , ∞ ) |
开口向上的曲面 |
2)编写一个算法来找到它的全局最小值及相应的最小解,并在3D图中标出。分析一下你的算法时空效率、给出运行时间。
(未完待补充)