美文网首页统计
统计学习方法——修炼学习笔记19:马尔可夫链蒙特卡罗法

统计学习方法——修炼学习笔记19:马尔可夫链蒙特卡罗法

作者: Sam_L | 来源:发表于2020-04-16 21:15 被阅读0次

    蒙特卡罗法也称统计模拟方法,是通过从概率模型的随机抽样进行近似数值计算的方法。
    马尔可夫链蒙特卡罗法是以马尔可夫链为概率模型的蒙特卡罗法。

    马尔可夫链蒙特卡罗法构建一个马尔可夫链,使其平稳分布就是要进行抽样的分布,首先基于该马尔可夫链进行随机游走,产生样本的序列,之后使用该平稳分布的样本进行近似数值计算。

    Metropolis-Hastings算法是最基本的马尔可夫链蒙特卡罗法。
    吉布斯抽样是更简单、使用更广泛的马尔可夫链蒙特卡罗法。

    马尔可夫链蒙特卡罗法被应用于概率分布的估计、定积分的近似计算、最优化问题的近似求解等问题,特别是被应用于统计学习中概率模型的学习与推理,是重要的统计学习计算方法。

    一、蒙特卡罗法

    1、随机抽样

    蒙特卡罗法要解决的问题是:

    假设概率分布的定义已知,通过抽样获得概率分布的随机样本,并通过得到的随机样本对概率分布的特征进行分析。
    比如:
    从样本得到经验分布,从而估计总体分布。
    或者从样本计算出样本均值,从而估计总体期望。
    所以蒙特卡罗法的核心是随机抽样。

    蒙特卡罗法
    • 直接抽样法
    • 接收-拒绝抽样法
    • 重要性抽样法

    接收-拒绝抽样法,重要性抽样法适合于概率密度函数复杂(如密度函数含有多个变量,各变量相互不独立,密度函数形式复杂),不能直接抽样的情况。

    接收-拒绝抽样法
    image.png image.png

    接收-拒绝法优点:容易实现,缺点是效率可能不高。
    如果p(x)的涵盖体积占cq(x)的涵盖体积的比例很低,就会导致拒绝的比例很高,抽样效率很低。
    注意:p(x)与cq(x)很接近,两者涵盖体积的差异也可能很大。

    2、数学期望估计

    一般的蒙特卡罗法也可用于数学期望估计。


    image.png

    3、积分计算

    一般的蒙特卡罗法也可用于定积分的近似计算,称为蒙特卡罗积分

    image.png

    二、马尔可夫链

    1、基本定义

    image.png

    2、离散状态马尔可夫链

    (1)转移概率矩阵和状态分布
    转移概率矩阵
    image.png
    状态分布
    image.png

    有限离散状态的马尔可夫链可以由有向图表示
    结点表示状态,边表示状态之间的转移,边上的数组表示转移概率。
    从一个初始状态出发,根据有向边上定义的概率在状态之间随机跳转(或随机转移),就可以产生状态的序列。
    马尔可夫链实际上是刻画随时间在状态之间转移的模型,假设未来的转移状态只有依赖于现在的状态,而与过去的状态无关。

    image.png

    2、平稳分布

    image.png

    直观上,如果马尔可夫链的平稳分布存在,那么以该平稳分布作为初始分布,面向未来进行随机状态转移,之后任何一个时刻的状态分布都是该平稳分布

    image.png

    3、连续状态马尔可夫链

    image.png

    4、马尔可夫链性质

    (1)不可约
    image.png

    直观上,一个不可约的马尔可夫链,从任意状态出发,当经过充分长时间后,可以到达任意状态

    (2)非周期
    image.png

    直观上,一个非周期性的马尔可夫链,不存在一个状态,从这一个状态出发,再返回到这个状态时所经历的时间长呈一定的周期性

    (3)正常返
    image.png

    直观上,一个正常返的马尔可夫链,其中任意一个状态,从其他任意一个状态出发,当时间趋于无穷时,首次转移到这个状态的概率不为0。

    (4)遍历定理
    image.png

    遍历定理的直观解释:
    满足相应条件的马尔可夫链,当时间趋于无穷时,马尔可夫链的状态分布趋近于平稳分布,随机变量的函数的样本均值以概率1收敛于该函数的数学期望。
    样本均值可以认为是时间均值,二数学期望是空间均值。遍历定理实际表述了遍历性的含义:当时间趋于无穷时,时间均值等于空间均值。
    遍历定理的三个条件:不可约,非周期,正常返,保证了当时间趋于无穷时达到任意一个状态的概率不为0。

    遍历均值
    image.png
    (5)可逆马尔可夫链
    image.png

    直观上,如果有可逆的马尔可夫链,那么以该马尔可夫链的平稳分布作为初始分布,进行随机状态转移,无论是面向未来还是面向过去,任何一个时刻的状态分布都是该平稳分布。

    细致平衡方程
    image.png

    三、马尔可夫链蒙特卡罗法

    1、基本想法

    马尔可夫链蒙特卡罗法更合适于随机变量是多元的、密度函数是非标准形式的、随机变量各分量不独立等情况。


    image.png
    马尔可夫链蒙特卡罗法的基本想法:
    image.png
    构建具体的马尔可夫链:
    • 连续变量的时候,需要定义转移核函数。
    • 离散变量的时候,需要定义转移矩阵。

    一个方法是定义特殊的转移核函数或者转移矩阵,构建可逆马尔可夫链,这样可以保证遍历定理成立。
    常用的马尔可夫链蒙特卡罗法有Metropolis-Hastings算法,吉布斯抽样。

    由于这个马尔可夫链满足遍历定理,随机游走的起始点并不影响得到的结果,即从不同的起始点出发,都会收敛到同一平稳分布。

    马尔可夫链蒙特卡罗法的收敛性的判断通常是经验性的。
    比如在马尔可夫链上进行随机游走,检验遍历均值是否收敛。具体地,每隔一段时间取一次样本,得到多个样本以后,计算遍历均值。
    再比如,在马尔可夫链上并行进行多个随机游走,比较各个随机游走的遍历均值是否接近一致。

    马尔科夫链蒙特卡罗法中得到的样本序列,相邻的样本是相关的,而不是独立的。
    因此,在需要独立样本时,可以在该样本序列中再次进行随机抽样。
    比如,每隔一段时间取一次样本,将主要得到的子样本集合作为独立样本集合。

    马尔可夫链蒙特卡罗法比接受-拒绝法更容易实现,因为只需要定义马尔可夫链,而不需要定义建议分布。
    一般来说马尔可夫链蒙特卡罗法比接受-拒绝法效率更高,没有大量被拒绝的样本,虽然燃烧期的样本也要抛弃。

    2、基本步骤

    可以将马尔可夫链蒙特卡罗法概括为以下三步。


    image.png

    3、马尔可夫链蒙特卡罗法与统计学习

    image.png

    贝叶斯学习中经常需要进行三种积分运算:

    • 归范化
    • 边缘化
    • 数学期望
    image.png

    马尔可夫链蒙特卡罗法为这些计算提供了一个通用的有效解决方案。

    四、Metropolis-Hastings算法

    1、基本原理

    (1)马尔可夫链
    image.png
    定理
    image.png
    (2)建议分部

    两种常用形式:


    image.png
    (3)满条件分部
    image.png

    2、Metropolis-Hastings算法

    image.png

    3、单分量Metropolis-Hastings算法

    在Metropolis-Hastings算法中,通常需要对多元变量分布进行抽样,有时对多元变量分布的抽样是困难的。
    可以对多元变量的每一变量的条件分布依次分别进行抽样,从而实现对整个多元变量的一次抽样,这就是单分量Metropolis-Hastings算法。


    image.png image.png

    五、吉布斯抽样

    吉布斯抽样是马尔可夫链蒙特卡罗法的常用算法。可认为是Metropolis-Hastings算法的特殊情况,但是更容易实现,因而被广泛使用。

    1、基本原理

    吉布斯抽样用于多元变量联合分布的抽样和估计。
    基本做法:从联合概率分布定义满条件概率分布,依次对满条件概率分布进行抽样,得到样本的序列。
    可以证明这样的抽样过程是在一个马尔可夫链上的随机游走,每一个样本对应着马尔可夫链的状态,平稳分布就是目标的联合分布。
    整体成为一个马尔可夫链蒙特卡罗法,燃烧期之后的样本就是联合分布的随机样本。

    image.png
    吉布斯抽样是单分量Metropolis-Hastings算法的特殊情况。
    image.png

    2、吉布斯抽样算法

    image.png
    单分量Metropolis-Hastings算法
    • 抽样会在样本点之间移动,但其间可能在某一些样本点上停留(由于抽样被拒绝)
    • 适合于满条件概率分布不容易抽样的情况,使用容易抽样的条件分布作建议分布。
    吉布斯抽样算法
    • 抽样会在样本点之间持续移动
    • 适合于满条件概率分布容易抽样的情况。

    3、抽样计算

    吉布斯抽样中需要对满条件概率分布进行重复多次抽样。可以利用概率分布的性质提供抽样的效率。
    以贝叶斯学习为例介绍这个技巧


    image.png

    相关文章

      网友评论

        本文标题:统计学习方法——修炼学习笔记19:马尔可夫链蒙特卡罗法

        本文链接:https://www.haomeiwen.com/subject/enidvhtx.html