2021-07-13

  • Post author:
  • Post category:其他


简单过了一遍高数线代概率论数理统计的知识后,进入了随机过程和拒绝采样,MCMC采样方法的学习。



拒绝采样

对于

概率分布不是常见的分布

,一个可行的办法是采用

接受-拒绝采样

来得到该分布的样本。既然 p(x) 太复杂在程序中没法直接采样,那么我设定一个程序可采样的分布 q(x) 比如高斯分布,然后按照一定的方法拒绝某些样本,以达到接近 p(x) 分布的目的,其中q(x)叫做 proposal distribution。

在这里插入图片描述

具体采样过程如下:

  1. 设定一个方便采样的常用概率分布函数 q(x),以及一个常量 k,使得 p(x) 总在




    k

    (

    q

    (

    z

    0

    )

    )

    k*(q(z_0))






    k













    (


    q


    (



    z










    0


















    )


    )





    的下方。如上图。

  2. 首先,采样得到q(x)的一个样本



    z

    0

    z_0







    z










    0




















  3. 从均匀分布



    [

    0

    ,

    k

    (

    q

    (

    z

    0

    )

    ]

    [0,k*(q(z_0)]






    [


    0


    ,




    k













    (


    q


    (



    z










    0


















    )


    ]





    中采样得到一个值u

  4. 如果u落在了上图中的灰色区域,则拒绝这次抽样,否则接受这个样本z0(即可认为这个样本是p(x)采样得到的样本)
  5. 重复以上过程得到n个接受的样本



    z

    0

    ,

    z

    1

    ,

    .

    .

    .

    ,

    z

    n

    1

    z_0,z_1,…,z_{n−1}







    z










    0


















    ,





    z










    1


















    ,




    .


    .


    .


    ,





    z











    n





    1






















    ,则最后的蒙特卡罗方法求解结果为:





    1

    n

    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图中标出。分析一下你的算法时空效率、给出运行时间。

(未完待补充)



版权声明:本文为weixin_41215684原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。