精华内容
下载资源
问答
  • 马尔可夫链蒙特卡罗法 蒙特卡罗法 思想:假设概率分布的定义已知,然后通过随机抽样获得概率分布的随机样本,通过得到的随机样本对概率分布的特征进行分析。 for example:从随机抽出的样本中计算出样本均值,...

    马尔可夫链蒙特卡罗法

    蒙特卡罗法

    思想:假设概率分布的定义已知,然后通过随机抽样获得概率分布的随机样本,通过得到的随机样本对概率分布的特征进行分析。
    for example:从随机抽出的样本中计算出样本均值,从而得到总体的期望。
    蒙特卡罗方法的核心:随机抽样
    主要有直接抽样,接受-拒绝抽样,重要性抽样

    随机抽样

    接受拒绝抽样
    input:抽样的目标概率分布的概率密度函数 p ( x ) p(x) p(x)
    output:概率分布的随机样本 x 1 , x 2 , . . . , x n x_1,x_2,...,x_n x1,x2,...,xn
    parameters:样本数n
    建议分布: q ( x ) q(x) q(x),概率分布: p ( x ) p(x) p(x)
    u < = p ( x ∗ ) c q ( x ∗ ) u<= \frac{p(x^* )}{cq(x^ * )} u<=cq(x)p(x)

    数学期望估计

    样本均值: f n ^ \hat{f_n} fn^
    f n ^ = 1 n ∑ i = 1 n f ( x i ) \hat{f_n} = \frac{1}{n}\sum_{i=1}^nf(x_i) fn^=n1i=1nf(xi)
    根据大数定律可知,当样本容量增大时,样本均值以概率1收敛于数学期望:
    KaTeX parse error: Undefined control sequence: \verfy at position 34: …x)}[f(x)]~,~n->\̲v̲e̲r̲f̲y̲
    E p ( x ) [ f ( x ) ] = 1 n ∑ i = 1 n f ( x i ) E_{p(x)}[f(x)] = \frac{1}{n}\sum_{i=1}^nf(x_i) Ep(x)[f(x)]=n1i=1nf(xi)

    积分计e算

    ∫ X h ( x ) d x \int_{\mathcal{X}}h(x)dx Xh(x)dx
    h ( x ) h(x) h(x)分解成为一个函数 f ( x ) f(x) f(x)和一个密度函数 p ( x ) p(x) p(x)
    ∫ X h ( x ) d x = ∫ X f ( x ) p ( x ) d x = E p ( x ) [ f ( x ) ] \int_{\mathcal{X}}h(x)dx = \int_{\mathcal{X}}f(x)p(x)dx = E_{p(x)}[f(x)] Xh(x)dx=Xf(x)p(x)dx=Ep(x)[f(x)]

    summery

    一般的蒙特卡罗法中的抽样分布是独立的,而马尔可夫链蒙特卡罗法中的抽样样本不是独立的,样本序列形成马尔可夫链

    马尔可夫链

    基本定义

    马尔可夫性:
    P ( X t ∣ X 0 , X 1 , X 2 , . . . , X t − 1 ) = P ( X t ∣ X t − 1 )   ,   t = 1 , 2 , . . . , n P(X_t|X_0,X_1,X_2,...,X_{t-1}) = P(X_t|X_{t-1})~,~t=1,2,...,n P(XtX0,X1,X2,...,Xt1)=P(XtXt1) , t=1,2,...,n
    马尔可夫链(具有马尔可夫性的随机序列)也称之为马尔可夫过程:
    X = { X 0 , X 1 , X 2 , . . . , X t , . . . } X = \lbrace X_0,X_1,X_2,...,X_t,...\rbrace X={X0,X1,X2,...,Xt,...}
    马尔可夫链的转移概率分布(决定了马尔可夫链的特性):
    P ( X t ∣ X t − 1 )   ,   t = 1 , 2 , 3 , . . . , n P(X_t|X_{t-1})~,~t=1,2,3,...,n P(XtXt1) , t=1,2,3,...,n
    时间齐次的马尔可夫链(转移概率分布 P ( X t ∣ X t − 1 ) P(X_t|X_{t-1}) P(XtXt1)与t无关):
    P ( X t + s ∣ X t − 1 + s ) = P ( X t ∣ X t − 1 )   ,   t = 1 , 2 , 3 , . . . , n P(X_{t+s}|X_{t-1+s}) = P(X_t|X_{t-1})~,~t=1,2,3,...,n P(Xt+sXt1+s)=P(XtXt1) , t=1,2,3,...,n
    另外,还有n阶马尔可夫链,n阶马尔可夫链可以转化成为1阶马尔可夫链。

    离散状态马尔可夫链
    • 转移概率矩阵和状态分布
      p i j = ( X t = i ∣ X t − 1 = j )   ,   i = 1 , 2 , . . . p_{ij} = (X_t = i | X_{t-1} = j)~,~i=1,2,... pij=(Xt=iXt1=j) , i=1,2,...满足 p i j > = 0 , ∑ i p i j = 1 p_{ij}>=0,\sum_ip_{ij}=1 pij>=0,ipij=1,且满足这两个条件的矩阵称之为随机矩阵,马尔可夫链 X = { X 0 , X 1 , . . . , X t , . . . } X=\lbrace X_0,X_1,...,X_t,... \rbrace X={X0,X1,...,Xt,...}在时刻t的概率分布称之为t的状态分布,其中, π i ( t ) \pi_i(t) πi(t)指的是时刻t状态为i的概率 P ( X t = i ) P(X_t = i) P(Xt=i)记做,:
      π ( t ) = [ π 1 ( t ) , . . . , π n ( t ) ] T \pi(t) = [\pi_1(t),...,\pi_n(t)]^T π(t)=[π1(t),...,πn(t)]T
    • 平稳分布(P:状态转移矩阵 P = ( p i j ) P = (p_{ij}) P=(pij)
      π = P π \pi = P\pi π=Pπ
      直观上,如果马尔可夫链的平稳分布存在,那么以该平稳分布作为初始分布,而向未来随机状态转移,之后的任何一个状态也是平稳状态。
      平稳分布的充分必要条件
      x i = ∑ j p i j x j x_i = \sum_{j}p_{ij}x_j xi=jpijxj
      x i > = 0 x_i>=0 xi>=0
      ∑ i x i = 1 \sum_ix_i=1 ixi=1
      马尔可夫链X在时刻t的状态分布,可以由在时刻(t-1)的状态分布,以及转移概率决定:
      π ( t ) = P π ( t − 1 ) \pi(t) = P\pi(t-1) π(t)=Pπ(t1)
      π ( t ) = P t π ( 0 ) \pi(t) = P^t\pi(0) π(t)=Ptπ(0),这里的 P t P^t Pt称为t步转移概率矩阵。
    连续状态马尔可夫链

    转移核 P ( x , A ) P(x,A) P(x,A)定义为:
    P ( x , A ) = ∫ A p ( x , y ) d y P(x,A) = \int_Ap(x,y)dy P(x,A)=Ap(x,y)dy
    P ( X t = A ∣ X t − 1 = x ) = P ( x , A ) P(X_t = A|X_t-1 = x) = P(x,A) P(Xt=AXt1=x)=P(x,A)

    马尔可夫链的额性质
    • 不可约
      P ( X t = i ∣ X 0 = j ) > 0 P(X_t = i|X_0=j)>0 P(Xt=iX0=j)>0
      从任意状态出发,当经过充分长的时间后,可以达到任意一个状态。
    • 非周期
      t : P ( X t = i ∣ X ) = i ) > 0 的最大公约数为1 {t:P(X_t=i|X_)=i)>0}\text{的最大公约数为1} t:P(Xt=iX)=i)>0的最大公约数为1
      一个非周期的马尔可夫链,不存在一个状态,从这一个状态出发,再返回这个状态所经历的时间呈现一定的周期性。
    • 正常返
      lim ⁡ t − > + ∞ p i j t > 0 \lim_{t->+\infty}p_{ij}^t>0 limt>+pijt>0
      一个正常返的马尔可夫链,其中任意一个状态,从其他任何一个状态出发,时间趋于无穷时,首次转移到这个状态的概率不为0
    • 遍历定理
      不可约的非周期的正常返的马尔可夫链,当时间趋于无穷时,马尔可夫链的状态总会趋于平稳分布
    • 可逆马尔可夫链
      p i j π j = p j i π i p_{ij}\pi_j = p_{ji}\pi_i pijπj=pjiπi
      可逆的马尔可夫链,无论是面向未来还是面向过去,任意一个时刻的状态分布均是平稳分布。
    • 细致平衡方程
      P π = π P\pi = \pi Pπ=π

    马尔可夫链蒙特卡罗法

    基本想法

    燃烧期(0~m)
    f ( x ) ^ = 1 n − m ∑ i = n − m + 1 n f ( x i ) \hat{f(x)} = \frac{1}{n-m}\sum_{i=n-m+1}^nf(x_i) f(x)^=nm1i=nm+1nf(xi)

    基本步骤

    step 1:在随机变量 x x x的状态空间里构造一个满足条件的马尔可夫链,使得其平稳分布为目标分布 p ( x ) p(x) p(x)
    step 2:从状态空间的某一点 x 0 x_0 x0出发,用构造的马尔可夫链进行随机游走,产生样本序列 x 0 , x 1 , x 2 , . . x_0,x_1,x_2,.. x0,x1,x2,..
    step 3:应用马尔可夫链的遍历定理,确定正整数m和n,得到样本集合 x m + 1 , . . . , x n {x_{m+1},...,x_n} xm+1,...,xn得到函数的均值 f ( x ) ^ = 1 n − m ∑ i = n − m + 1 n f ( x i ) \hat{f(x)} = \frac{1}{n-m}\sum_{i=n-m+1}^nf(x_i) f(x)^=nm1i=nm+1nf(xi)
    important questions:
    one:如何定义马尔可夫链,保证马尔可夫链蒙特卡罗法的条件成立
    two:如何确定m,保证样本的无偏性
    three:如何确定n,保证遍历均值的精度

    Metropolis-Hastings算法

    基本原理
    • 马尔可夫链
      Metropolis-Hastings算法采用转移核为 p ( x , x ′ ) p(x,x^{\prime}) p(x,x)
      p ( x , x ′ ) = q ( x , x ′ ) α ( x , x ′ ) p(x,x^{\prime}) = q(x,x^{\prime})\alpha(x,x^{\prime}) p(x,x)=q(x,x)α(x,x)
    • 建议分布 q ( x , x ′ ) q(x,x^{\prime}) q(x,x)和接受分布 α ( x , x ′ ) \alpha(x,x^{\prime}) α(x,x)
      α ( x , x ′ ) = min ⁡ { 1 , p ( x ′ q ( x ′ , x ) ) p ( x ) q ( x , x ′ ) } \alpha(x,x^{\prime}) = \min\lbrace1, \frac{p(x^{\prime}q(x^{\prime},x))}{p(x)q(x,x^{\prime})}\rbrace α(x,x)=min{1,p(x)q(x,x)p(xq(x,x))}
      转移核:
      p ( x , x ′ ) = ? ? p(x,x^{\prime}) = ?? p(x,x)=??
      构造出来了:
      p ( x ) p ( x , x ′ ) = p ( x ′ ) p ( x ′ , x ) p(x)p(x,x^{\prime}) = p(x^{\prime})p(x^{\prime},x) p(x)p(x,x)=p(x)p(x,x)
    • 满条件分布
      $$$$
    Metropolis-Hastings算法

    input:抽样的目标分布的密度函数 p ( x ) p(x) p(x),函数 f ( x ) f(x) f(x)
    output: p ( x ) p(x) p(x)的随机样本 x m + 1 , . . , x n x_{m+1},..,x_n xm+1,..,xn,函数样本的均值
    parameters:m,n

    单分量Metropolis-Hastings法

    Metropolis-Hastings算法需要对多变量分布进行抽样,有时候对多元变量分布的抽样是苦难的,可以对多元变量的每一个变量的条件分布依次进行抽样,这就是单分量Metropolis-Hastings法

    吉布斯抽样

    基本做法是,从联合概率分布定义满条件概率分布,依次对满条件分布进行抽样,得到样本的序列。

    展开全文
  • 统计学习方法-马尔可夫链蒙特卡罗法-读书笔记1、前言2、蒙特卡罗法2.1随机抽样2.2树学期望估计2.3积分计算3、马尔可夫链3.1基本定义3.2连续状态马尔可夫链3.3马尔可夫链的性质4、马尔可夫链蒙特卡罗法4.2吉布斯抽样...

    1、前言

    蒙特卡罗法(也称为统计模拟方法),是通过从概率模型的随机抽样进行近似数据的计算方法。MCMC则是以马尔可夫链为概率模型的蒙特卡罗法。
    MCMC方法的基本思想是:通过蒙特卡罗法构建一个马尔可夫链,使其平稳分布就是要进行抽样的分布,首先基于该马尔可夫链进行随机游走,产生岩本序列,之后使该平稳分布的样本进行近似的数值计算。

    2、蒙特卡罗法

    2.1随机抽样

    蒙特卡罗法要解决的问题是,假设概率分布的定义已知,通过抽样获得概率分布的随机样本,通过得到的样本对概率分布进行分析,蒙特卡罗法的核心是随机抽样
    一般地蒙特卡罗法右直接抽样法,接受-拒绝抽样法,重复性抽样法等。后两种方法适合于概率密度函数复杂,不能直接抽样的方法。

    • 接受-拒绝抽样法
      假设有随机变量,其概率密度函数为p(x),目标是得到该概率分布的随机样本,而对这个概率分布进行分析。基本思想如下:假设p(x)不可以直接抽样,找一个可以直接抽样的分布,称为建议分布。假设q(x)是建议分布的概率密度函数,并且有cq(x)>=p(x),对q(x)进行抽样,假设得到的结果是x*,再按照$\frac{p(x)}{cq(x)}$的例随即决定是否接受x,接受拒绝法实际就是按照p(X)的涵盖面积占cq(X)的涵盖面积的比例进行抽样。
      算法:
      输入:抽样的目标概率分布的概率密度函数p(x)
      输出:概率分布的随机样本x1,xn
      参数:样本n
      (1)选择概率密度函数为q(X)的概率分布作为建议分布,使其对任一x满足cq(X)>=p(X)
      (2)按照建议分布q(X)随机抽样得到样本x^
      ,再按照均匀分布在(0,1)范围内进行抽样等到U。
      (3)如果u<=p(x*)/cq(x*),则将x^*作为抽样结果,否则,回到步骤(2)
      (4)直到n个随机样本,结束
      接受-拒接法的有点是容易实现,缺点是效率可能不高。

    2.2树学期望估计

    蒙特卡罗法按照概率分布p(x)独立的选择n个样本,计算函数f(X)的样本均值
    f ^ n = 1 n ∑ i = 1 n f ( x i ) \hat{f}_n=\frac{1}{n}\sum_{i=1}^n{f(x_i)} f^n=n1i=1nf(xi)
    作为数学期望的近似值,根据大数定理可知,当样本容量增大时,样本均以概率1收敛于数学期望
    E p ( x ) [ f ( x ) ] = 1 x = n ∑ i = 1 n f ( x i ) E_{p(x)}[f(x)]=\frac{1}{x=n}\sum_{i=1}^n{f(x_i)} Ep(x)[f(x)]=x=n1i=1nf(xi)

    2.3积分计算

    ∫ x h ( x ) d x = ∫ x f ( x ) p ( x ) d x = E p ( x ) [ f ( x ) ] = 1 n ∑ i = 1 n f ( x i ) \int^{}_x{h(x)}{\rm d}x=\int^{}_x{f(x)p(x)}{\rm d}x=E_{p(x)[f(x)]}=\frac{1}{n}\sum_{i=1}^nf(x_i) xh(x)dx=xf(x)p(x)dx=Ep(x)[f(x)]=n1i=1nf(xi)

    3、马尔可夫链

    3.1基本定义

    3.2连续状态马尔可夫链

    连续状态的马尔可夫链定义在连续状态空间,转移概率分布由概率转移核或转移核表示。
    设S是连续状态空间,对任意x,A,转移核P(x,A),表示从x-A的转移概率定义为
    P ( x , A ) = ∫ A p ( x , y ) d y P(x,A)=\int^{}_A{p(x,y)}{\rm d}y P(x,A)=Ap(x,y)dy
    若马尔可夫链的状态空间S上的概率分布 π ( y ) = ∫ p ( x , y ) π ( x ) d x \pi(y)=\int^{}_{}{p(x,y)\pi(x)}{\rm d}x π(y)=p(x,y)π(x)dx则称分布为该马尔可夫链的平稳分布

    3.3马尔可夫链的性质

    • 不可约时刻0从状态j出发,时刻t到达i的状态i的概率大于0,则称不可约。直观上,一个不可约的马尔可夫链从任意状态出发,经过充分长时间后可以达到任意状态。

    • 非周期如果时刻0从状态i出发,t时刻返回状态的所有时常的最大公约数是1,则称是非周期的。直观的,一个非周期性得马尔可夫链,不存在一个状态,从这个状态出发,再返回这个状态时所经历得时间长呈一定得周期性。

    • 正常返一个正常返得马尔可夫链,其中任意一个状态,从其他任意一个状态出发,当时间趋于无穷时,首次转移到这个状态得概率不为0.
      不可约、非周期、正常返得马尔可夫链,有唯一平稳分布存在。

    • 遍历定理若马尔可夫链不可约、非周期、正常返,则该马尔可夫链有唯一平稳分布 π \pi π,并且转移概率得极限分布时马尔可夫链的平稳分布。样本均值可以认为是时间均值,数学期望是空间均值。当时间趋于无穷时,时间均值等于空间均值。

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

    • 可逆的马尔可夫链一定有唯一的平稳分布,给出一个马尔可夫链有平稳分布的充分条件。也就是说,可逆马尔可夫链满足遍历定理。

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

    MCMC适合于随机变量是多元的,密度函数是非标准形式的,随机变量各分量不独立的情况。
    常用的MCMC有Metropolis-Hastings算法,吉布斯抽样
    基本步骤:
    (1)在随机变量x的状态空间S上构造一个满足遍历定理的马尔可夫链,使其平稳分布为目标分布p(x)
    (2)从状态空间的某一点x0出发,用构造的马尔可夫链进行随机游走,产生样本序列
    (3)应用马尔可夫链的遍历定理,确定正整数m,n,得到样本集合,求得函数的均值。

    4.1Metropolis-Hastings算法

    输入:抽样的目标分布的密度函数p(x),函数f(x)
    输出:p(x)的随机样本,函数样本均值fmn
    参数:收敛步数m,迭代步数n
    (1)任意选取一个初始值x0
    (2)对i=0,…n循环执行
    (a)设状态xi-1=x,按照建议分布q(x,x’)随机抽取一个候选状态x’
    (b)计算接受概率 α ( 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,若u<=接受概率,则xi=x’,否则xi=x
    (3)得到样本集合
    (4)计算 f m n = 1 n − m ∑ i = m + 1 n f ( x i ) f_{mn}=\frac{1}{n-m}\sum_{i=m+1}^n{f(x_i)} fmn=nm1i=m+1nf(xi)

    4.2吉布斯抽样(Gibbs Sampling)

    吉布斯抽样用于多元变量联合分布的抽样和估计。基本做法是,从联合概率分布定义满条件概率分布,依次对满条件概率分布进行抽样,得到联合分布的随机样本。
    输入:目标概率分布的密度函数p(x),函数f(x)
    输出:p(x)的随机样本,样本均值
    参数:收敛步数m,迭代步数n
    (1)初始化。给出初始样本x(0)
    (2)对i循环执行
    由满条件分布p(x1|x2,xk)抽取xi

    …xk
    得到第i次迭代值
    (3)得到样本集合
    (4)计算均值

    展开全文
  • 马尔可夫链蒙特卡罗法4. Metropolis-Hastings 算法5. 吉布斯抽样 蒙特卡罗法(Monte Carlo method),也称为统计模拟方法(statistical simulation method),是通过从概率模型的随机抽样进行近似数值计算的方法 ...

    蒙特卡罗法(Monte Carlo method),也称为统计模拟方法(statistical simulation method),是通过从概率模型随机抽样进行近似数值计算的方法

    马尔可夫链蒙特卡罗法(Markov Chain Monte Carlo,MCMC),则是以马尔可夫链(Markov chain)为概率模型的蒙特卡罗法

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

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

    1. 蒙特卡罗法

    • 核心思想:随机抽样(直接抽样法、接受-拒绝抽样法、重要性抽样法 等)
    • 可用于数学期望估计、积分近似计算
    • 一般的蒙特卡罗法中的抽样样本是独立的,而马尔可夫链蒙特卡罗法中的抽样样本不是独立的,样本序列形成马尔科夫链。

    2. 马尔可夫链

    马尔可夫性:随机变量 X t X_t Xt 只依赖于前一个时刻 X t − 1 X_{t-1} Xt1,不依赖于更早的时刻

    齐次性:转移概率 P ( X t ∣ X t − 1 ) P(X_t|X_{t-1}) P(XtXt1) t t t 无关, P ( X t + s ∣ X t − 1 + s ) = P ( X t ∣ X t + 1 ) P(X_{t+s}|X_{t-1+s}) = P(X_t|X_{t+1}) P(Xt+sXt1+s)=P(XtXt+1)

    马尔可夫链的状态分布初始分布转移概率分布决定 π ( t ) = P t π ( 0 ) \pi(t) = P^t \pi(0) π(t)=Ptπ(0)

    马尔可夫链的平稳分布 π ( π 1 , π 2 , . . . ) T \pi(\pi_1,\pi_2,...)^T π(π1,π2,...)T 的充要条件是: π \pi π 是下列方程组的解
    x i = ∑ j p i j x j , i = 1 , 2 , . . . x i ≥ 0 , i = 1 , 2 , . . . ∑ i x i = 1 x_i = \sum\limits_j p_{ij}x_j, i = 1,2,...\\ x_i \ge 0, i=1,2,...\\ \sum\limits_i x_i = 1 xi=jpijxj,i=1,2,...xi0,i=1,2,...ixi=1

    马尔可夫链可能存在唯一平稳分布,无穷多个平稳分布,或不存在平稳分布

    性质:

    1. 不可约
      P ( X t = i ∣ X 0 = j ) > 0 P(X_t=i|X_0=j)>0 P(Xt=iX0=j)>0 时刻0从状态 j 出发,时刻 t 到达状态 i 的概率大于 0,该链不可约
      在这里插入图片描述

    2. 非周期
      P ( X t = i ∣ X 0 = i ) > 0 P(X_t=i|X_0=i)>0 P(Xt=iX0=i)>0 时刻0从状态 i 出发,时刻 t 返回状态的所有时间长度的最大公约数是1,称该链是非周期的
      在这里插入图片描述
      定理:不可约非周期有限状态马尔可夫链,有唯一平稳分布存在

    3. 正常返
      概率 p i j t p_{ij}^t pijt 为时刻 0 从状态 j 出发,时刻 t 首次转移到状态 i 的概率,若对所有状态 i, j,都满足 lim ⁡ t → ∞ p i j t > 0 \lim\limits_{t\rightarrow \infty} p_{ij}^t >0 tlimpijt>0,称该链是正常返的

    在这里插入图片描述
    定理:不可约非周期正常返的马尔可夫链,有唯一平稳分布存在

    1. 可逆马尔可夫性
      对任意状态 i,j,在任意时间 t 满足: p j i π j = p i j π i , i , j = 1 , 2 , . . . p_{ji}\pi_j = p_{ij}\pi_i, i,j=1,2,... pjiπj=pijπi,i,j=1,2,...(细致平衡方程)
      如果有可逆的马尔可夫链,那么平稳分布作为初始分布,进行随机状态转移,无论是面向未来还是面向过去,任何一个时刻的状态分布都是该平稳分布。

    定理:满足细致平衡方程的状态分布 π \pi π 就是该马尔可夫链的平稳分布

    可逆马尔可夫链一定有唯一平稳分布,给出了一个马尔可夫链有平稳分布的充分条件(不是必要条件)

    3. 马尔可夫链蒙特卡罗法

    常用的马尔可夫链蒙特卡罗法 有Metropolis-Hastings算法吉布斯抽样

    马尔可夫链蒙特卡罗法的收敛性的判断通常是经验性的

    • 比如,在马尔可夫链上进行随机游走,检验遍历均值是否收敛
    • 再比如,在马尔可夫链上并行进行多个随机游走,比较各个随机游走的遍历均值是否接近一致

    4. Metropolis-Hastings 算法

    在这里插入图片描述

    5. 吉布斯抽样

    在这里插入图片描述

    展开全文
  • 第十九章:马尔可夫链蒙特卡罗法 蒙特卡罗法,也称为统计模拟方法,是通过从概率模型的随机抽样\color{red}{随机抽样}随机抽样进行数值计算的方法;而马尔可夫链蒙特卡罗法是特例,是以马尔可夫链\color{red}{以...

    第十九章:马尔可夫链蒙特卡罗法

    蒙特卡罗法,也称为统计模拟方法,是通过从概率模型的 随 机 抽 样 \color{red}{随机抽样} 进行数值计算的方法;而马尔可夫链蒙特卡罗法是特例,是 以 马 尔 可 夫 链 \color{red}{以马尔可夫链} 为概率模型的蒙特卡罗法;

    蒙特卡罗法

    蒙特卡罗法的核心是 随 机 抽 样 \color{red}{随机抽样} 要 解 决 的 问 题 是 \color{red}{要解决的问题是} :假设概率分布已知,通过抽样获得概率分布的随机样本,并通过得到的随机样本对概率分布的特征进行分析。其实就是 样 本 估 计 总 体 \color{red}{样本估计总体}

    一般的方法有 直 接 抽 样 、 接 受 − 拒 绝 抽 样 、 重 要 性 抽 样 法 等 \color{red}{直接抽样、接受-拒绝抽样、重要性抽样法等} ,后面两者适合概率密度函数复杂的情况,不适合直接抽样的情况。

    数学期望估计

    对于随机变量 x ,目标是求函数 f ( x ) f(x) f(x)关于概率密度 p ( x ) p(x) p(x)的数学期望,根据大数定律,当样本容量增大时,样本均值以概率1收敛于数学期望:

    E p ( x ) [ f ( x ) ] ≈ 1 n ∑ i = 1 n f ( x i ) \color{red}{E_{p(x)}[f(x)]\approx{\frac{1}{n}\displaystyle\sum_{i=1}^nf(x_i)}} Ep(x)[f(x)]n1i=1nf(xi)

    积分计算

    任意函数的积分都可以表示为某一个函数的数学期望的形式,而数学期望又可以用样本均值进行估计:

    ∫ χ h ( x )   d x = ∫ χ f ( x ) p ( x ) d x = E p ( x ) [ f ( x ) ] ≈ 1 n ∑ i = 1 n f ( x i ) \color{red}{\int_\chi {h(x)} \,{\rm d}x=\int_\chi{f(x)p(x)}dx=E_{p(x)}[f(x)]\approx{\frac{1}{n}\displaystyle\sum_{i=1}^nf(x_i)}} χh(x)dx=χf(x)p(x)dx=Ep(x)[f(x)]n1i=1nf(xi)

    p ( x ) 和 n 的 选 取 直 接 影 响 到 最 终 结 果 , n 值 越 大 , 计 算 越 精 确 \color{red}{p(x)和n的选取直接影响到最终结果,n值越大,计算越精确} p(x)nn

    马尔可夫链

    定义:具有马尔可夫性的随机变量序列 X = ( X 0 , X 1 , ⋯   , X t , ⋯   ) X=(X_0,X_1,\cdots,X_t,\cdots) X=(X0,X1,,Xt,)称为马尔可夫链;

    马尔可夫性: P ( X t ∣ X 0 , X 1 , ⋯   , X t − 1 ) = P ( X t ∣ X t − 1 ) P(X_t|X_0,X_1,\cdots,X_{t-1})=P(X_t|X_{t-1}) P(XtX0,X1,,Xt1)=P(XtXt1), 直 观 解 释 : 未 来 只 依 赖 现 在 , 而 与 过 去 无 关 \color{red}{直观解释:未来只依赖现在,而与过去无关} ,若转移概率分布 P ( X t ∣ X t − 1 ) \color{red}{P(X_t|X_{t-1})} P(XtXt1) t t t无关,则称为 时 间 齐 次 马 尔 可 夫 链 \color{red}{时间齐次马尔可夫链}

    离散状态马尔可夫链
    • 转移概率矩阵 P P P
      p i j = P ( X t = i ∣ X t − 1 = j ) , i = 1 , 2 , ⋯   ; j = 1 , 2 , ⋯   ; \color{red}{p_{ij}=P(X_t=i|X_{t-1}=j),i=1,2,\cdots;j=1,2,\cdots;} pij=P(Xt=iXt1=j),i=1,2,;j=1,2,;
      p i j ≥ 0 , ∑ i p i j = 1 , 满 足 这 两 个 条 件 的 矩 阵 又 称 为 随 机 矩 阵 \color{red}{p_{ij}\geq0,\displaystyle\sum_ip_{ij}=1,满足这两个条件的矩阵又称为随机矩阵} pij0,ipij=1,

    • 状态分布 π ( t ) \pi(t) π(t):$\color{red}{\pi_i(t)=P(X_t=i),是一个列向量,长度为随机变量可能的取值个数
      π ( t ) = P π ( t − 1 ) = P t π ( 0 ) \color{red}{\pi(t)=P\pi(t-1)=P^t\pi(0)} π(t)=Pπ(t1)=Ptπ(0),由此可见,马尔可夫链的状态分布由 初 始 分 布 \color{red}{初始分布} 转 移 概 率 分 布 \color{red}{转移概率分布} 决定

    • 平稳分布 π \pi π π = P π \color{red}{\pi=P\pi} π=Pπ,马尔可夫链可能存在唯一的、无穷多个平稳分布,有可能不存在平稳分布;求解方法之一是线性方程组的解: x i = ∑ j p i j x j , i = 1 , 2 , ⋯ \color{red}{x_i=\displaystyle\sum_jp_{ij}x_j,i=1,2,\cdots} xi=jpijxj,i=1,2,
      x i ≥ 0 , i = 1 , 2 , ⋯ \color{red}{x_i\geq0,i=1,2,\cdots} xi0,i=1,2,
      ∑ i x i = 1 \color{red}{\displaystyle\sum_ix_i=1} ixi=1

    连续状态马尔可夫链

    转移概率分布由 概 率 转 移 核 或 转 移 核 \color{red}{概率转移核或转移核} 来表示:
    转移核: P ( X t = A ∣ X t − 1 = x ) = P ( x , A ) = ∫ A p ( x , y ) d y \color{red}{P(X_t=A|X_{t-1}=x)=P(x,A)=\int_Ap(x,y)dy} P(Xt=AXt1=x)=P(x,A)=Ap(x,y)dy
    其 中 概 率 密 度 函 数 p ( x , ⋅ ) 满 足 : p ( x , ⋅ ) ≥ 0 , P ( x , S ) = ∫ S p ( x , y ) d y = 1 \color{red}{其中概率密度函数p(x,\cdot)满足:p(x,\cdot)\geq0,P(x,S)=\int_Sp(x,y)dy=1} p(x,)p(x,)0,P(x,S)=Sp(x,y)dy=1

    S是连续状态空间,A是某一子集;

    若有: π ( y ) = ∫ p ( x , y ) π ( x ) d x , ∀ y ∈ S \color{red}{\pi(y)=\int{p(x,y)}\pi(x)dx,\forall{y}\in{S}} π(y)=p(x,y)π(x)dx,yS,则 π ( x ) \pi(x) π(x)称为该马尔可夫链的平稳分布;

    马尔可夫链的性质
    1. 不可约性:从任意状态出发,当经过充分长时间后,可以到达任意状态;
    2. 周期性:对任意状态,如果时刻 t 从 i 状态出发,t 时刻返回状态的所有时间长 { t : P ( X t = i ∣ X 0 = i ) > 0 } \{t:P(X_t=i|X_0=i)>0\} {tP(Xt=iX0=i)>0}的最大公约数是1,则为非周期,否则是周期的;
      不 可 约 且 非 周 期 的 有 限 状 态 马 尔 可 夫 链 , 有 唯 一 平 稳 分 布 存 在 \color{red}{不可约且非周期的有限状态马尔可夫链,有唯一平稳分布存在}
    3. 正常返: 时间趋于无穷时,转移到任意一个状态的概率不为0
      不 可 约 、 非 周 期 、 正 常 返 的 马 尔 可 夫 链 存 在 唯 一 的 平 稳 分 布 \color{red}{不可约、非周期、正常返的马尔可夫链存在唯一的平稳分布}
    4. 遍历定理:对于有唯一平稳分布的马尔可夫链,存在遍历定理
      • 当 时 间 趋 于 无 穷 时 , 马 尔 可 夫 链 的 状 态 分 布 趋 于 平 稳 分 布 , 随 机 变 量 的 函 数 \color{red}{当时间趋于无穷时,马尔可夫链的状态分布趋于平稳分布,随机变量的函数}
        的 样 本 均 值 以 概 率 1 收 敛 于 该 函 数 关 于 平 稳 分 布 的 数 学 期 望 ; \color{red}{的样本均值以概率1收敛于该函数关于平稳分布的数学期望;} 1

      • 样 本 均 值 可 以 认 为 是 时 间 均 值 , 而 数 学 期 望 是 空 间 均 值 ( 总 体 ) 。 \color{red}{样本均值可以认为是时间均值,而数学期望是空间均值(总体)。}

      • 遍 历 定 理 实 际 说 明 了 当 时 间 趋 向 无 穷 时 , 时 间 均 值 等 于 空 间 均 值 ; \color{red}{遍历定理实际说明了当时间趋向无穷时,时间均值等于空间均值;}

      • 遍历均值: E ^ f = 1 n − m ∑ i = m + 1 n f ( x i ) \color{red}{\hat{E}_f=\frac{1}{n-m}\displaystyle\sum_{i=m+1}^nf(x_i)} E^f=nm1i=m+1nf(xi),m表示一个足够大的整数,迭代 m 次后的状态分布就是平稳分布;

    5. 可逆马尔可夫链(可逆性是存在唯一平稳分布的 充 分 条 件 \color{red}{充分条件} ):如果存在一个状态分布 π \pi π对于任意一个时刻 t 满足细致平衡方程:
      P ( X t = i ∣ X t − 1 = j ) π j = P ( X t − 1 = j ∣ X t = i ) π i \color{red}{P(X_t=i|X_{t-1}=j)\pi_j=P(X_{t-1}=j|X_t=i)\pi_i} P(Xt=iXt1=j)πj=P(Xt1=jXt=i)πi
      或 者 : p i j π j = p j i π i \color{red}{或者:p_{ij}\pi_j=p_{ji}\pi_i} pijπj=pjiπi
      则该马尔可夫链可逆;且 π \pi π就是该马尔可夫链的唯一平稳分布;

    马尔可夫链蒙特卡罗法

    适合随机变量是多元的、密度函数是非标准形式的、随机变量各分量不独立的情况;

    1. 在随机变量x的状态空间 S 上构造一个满足遍历定理的马尔可夫链(这一步是关键)
    2. 从状态空间的某一点 x 0 x_0 x0出发,用构造的马尔可夫链进行随机游走,产生样本序列: x 0 , x 1 , ⋯   , x t , ⋯   . x_0,x_1,\cdots,x_t,\cdots. x0,x1,,xt,.
    3. 应用遍历定理,确定正整数 m 和 n ,得到样本集合 { x m + 1 , x m + 2 , ⋯   , x n } , \{x_{m+1},x_{m+2},\cdots,x_n\}, {xm+1,xm+2,,xn}根据遍历均值公式求解函数期望;

    由此法得到的样本序列相邻的样本点是相关的,若要得到独立的样本点,可以在样本序列中再次抽样,比如每隔一段时间选取一个样本点;

    Metropolis-Hastings算法:马尔可夫蒙特卡罗法的一个具体实现

    • 算 法 \color{red}{算法}
      输入:抽样的目标分布的密度函数p(x),函数f(x)
      输出:p(x)的随机样本 x m + 1 , x m + 2 , ⋯   , x n x_{m+1},x_{m+2},\cdots,x_n xm+1,xm+2,,xn,函数样本均值 f m n f_{mn} fmn;
      参数:收敛步数 m ,迭代步数 n
    1. 任意选择一个初值 x = x 0 x=x_0 x=x0
    2. 对于 i = 1 , 2 , ⋯   , n i=1,2,\cdots,n i=1,2,,n循环执行
      1. 设状态 x i − 1 = x x_{i-1}=x xi1=x,按照建议分布 q ( x , x ′ ) \color{red}{q(x,x')} q(x,x)随机抽取一个候选状态 x ′ x' x
      2. 计算接收概率: α ( x , x ′ ) = m i n ( 1 , p ( x ′ ) q ( x ′ , x ) p ( x ) q ( x , x ′ ) ) \color{red}{\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))
    3. 从区间(0,1)中按均匀分布随机抽取一个数 u。
      μ ≤ α ( x , x ′ ) , \mu\leq\alpha(x,x'), μα(x,x),则状态 x i = x ′ , x_i=x', xi=x,否则, x i = x x_i=x xi=x
    4. 得到样本集合,计算函数均值

    上述马尔可夫链的转移核为 p ( x , x ′ ) = q ( x , x ′ ) α ( x , x ′ ) \color{red}{p(x,x')=q(x,x')\alpha(x,x')} p(x,x)=q(x,x)α(x,x)
    且有: p ( x ) p ( x . x ′ ) = p ( x ′ ) p ( x , x ′ ) \color{red}{p(x)p(x.x')=p(x')p(x,x')} p(x)p(x.x)=p(x)p(x,x),也即该马尔可夫链是可逆的,并且 p ( x ) p(x) p(x)是该马尔可夫链的平稳分布;

    • 建 议 分 布 q ( x , x ′ ) : \color{red}{建议分布q(x,x'):} q(x,x):建议分布时另一个马尔可夫链的转移核,并且是不可约的,同时还是一个 容 易 抽 样 的 分 布 \color{red}{容易抽样的分布}

      1. 对称形式: q ( x , x ′ ) = q ( x ′ , x ) \color{red}{q(x,x')=q(x',x)} q(x,x)=q(x,x),这样的建议分布称为 M e t r o p o l i s 选 择 \color{red}{Metropolis选择} Metropolis;特点是 x ′ x' x x x x接近时, q ( x , x ′ ) q(x,x') q(x,x)的概率值高,否则概率值低,也就是说 状 态 转 移 在 附 近 点 的 可 能 性 更 大 \color{red}{状态转移在附近点的可能性更大}
      2. 独立抽样: q ( x , x ′ ) = q ( x ′ ) \color{red}{q(x,x')=q(x')} q(x,x)=q(x),即 q ( x , x ′ ) q(x,x') q(x,x)与当前状态 x x x无关,建议分布按照 q ( x ′ ) q(x') q(x)独立抽样进行;常常选用接近目标分布的分布作为建议分布;
    • 满 条 件 分 布 : \color{red}{满条件分布:} 马尔可夫蒙特卡罗法的目标分布通常是多元联合分布 p ( x ) = p ( x 1 , x 2 , ⋯   , x k ) p(x)=p(x_1,x_2,\cdots,x_k) p(x)=p(x1,x2,,xk)为 k 维随机变量、如果条件概率分布 P ( x I ∣ x − I ) \color{red}{P(x_I|x_{-I})} P(xIxI)中所有k个变量全部出现( I ⊂ K = ( 1 , 2 , ⋯   , k ) ) I\subset{K={(1,2,\cdots,k}})) IK=(1,2,,k)),那么这种条件分布为满条件分布;且有:
      p ( x I ′ ∣ x − I ′ ) p ( x I ∣ x − I ′ ) = p ( x ′ ) p ( x ) \color{red}{\frac{p(x'_I|x'_{-I})}{p(x_I|x'_{-I})}=\frac{p(x')}{p(x)}} p(xIxI)p(xIxI)=p(x)p(x),利用此式可以简化计算,因为计算满条件概率的比要比计算联合概率的比要容易;

    单分量Metropolis-Hastings算法

    • 由于对多元变量的抽样是困难的,所以可以对多元变量的 每 一 变 量 的 条 件 分 布 \color{red}{每一变量的条件分布} 依次进行抽样,从而实现对整个多元变量的一次抽样;每一次迭代分为k步进行,步骤与整体的MH算法是一致的;

    • 这 个 方 法 的 关 键 在 于 单 一 变 量 的 条 件 分 布 是 易 于 抽 样 的 一 种 分 布 ( 此 时 , 将 其 他 变 量 看 做 常 数 ) \color{red}{这个方法的关键在于单一变量的条件分布是易于抽样的一种分布(此时,将其他变量看做常数)}

    吉布斯抽样算法

    • 吉布斯抽样 是 单 分 量 M − H 算 法 的 特 殊 情 况 \color{red}{是单分量M-H算法的特殊情况} MH。定义的建议分布是当前变量 x j , j = 1 , 2 , ⋯   , k x_j,j=1,2,\cdots,k xj,j=1,2,,k的满条件概率分布: q ( x , x ′ ) = p ( x j ′ ∣ x − j ) \color{red}{q(x,x')=p(x'_j|x_{-j})} q(x,x)=p(xjxj)

    • 这时的接受概率 α = 1 \alpha=1 α=1;
      也就是说 转 移 核 就 是 满 条 件 概 率 , 并 且 对 每 一 次 的 抽 样 结 果 都 接 收 ; \color{red}{转移核就是满条件概率,并且对每一次的抽样结果都接收;} 这时,条件概率后面的变量都是 看 做 常 数 \color{red}{看做常数} ;且假设条件概率不为0,即 马 尔 可 夫 链 是 不 可 约 的 ; \color{red}{马尔可夫链是不可约的;}

    • 具体的抽样过程可与单分量的M-H抽样进行对比,参见书籍;

    • 吉 布 斯 抽 样 适 合 满 条 件 概 率 容 易 抽 样 的 情 况 \color{red}{吉布斯抽样适合满条件概率容易抽样的情况}

    • 而 单 分 量 M − H 算 法 适 合 满 条 件 概 率 不 容 易 抽 样 的 情 况 \color{red}{而单分量M-H算法适合满条件概率不容易抽样的情况} MH

    • 这 时 使 用 容 易 抽 样 的 条 件 分 布 作 为 建 议 分 布 \color{red}{这时使用容易抽样的条件分布作为建议分布} 使

    • 吉布斯抽样可以利用概率分布的性质提高抽样效率,比如贝叶斯学习中,依满条件概率分布的抽样就医通过 依 这 些 条 件 概 分 布 的 乘 积 的 抽 样 进 行 \color{red}{依这些条件概分布的乘积的抽样进行} ,具体可参见下一章;

    展开全文
  • 马尔可夫链蒙特卡罗(MCMC)法是以马尔可夫链为概率模型的蒙特卡罗法。   MCMC方法的基本思想是:通过蒙特卡罗法构建一个马尔可夫链,使其平稳分布就是要进行抽样的分布,首先基于该马尔可夫链进行随机游走,产生...
  • 第19章 马尔可夫链蒙特卡罗法本文是李航老师的《统计学习方法》一书的代码复现。作者:黄海广备注:代码都可以在github中下载。我将陆续将代码发布在公众号“机器学习初学者”,可以在这个专...
  • 在《蒙特卡罗法及其应用》中介绍了传统的蒙特卡罗法,其核心思想是从概率模型的随机抽样进行近似数值计算,具体的应用包括随机抽样、数学期望计算以及定积分计算( 转化为数学期望 ). 在《马尔可夫模型》的最后补充了...
  • 马尔科夫链蒙特卡罗法的应用背景及基本思想和方法
  • 19.1 蒙特卡罗法 【重点】蒙特卡罗法要解决的问题是:假设概率分布的定义已知, 通过抽样获得概率分布的随机样本,并通过得到的随机样本对概率分布的特征进行分析。 【补充解释】直接抽样法:直接利用分布函数抽样...
  • 马尔可夫链蒙特卡罗法 作业19.7 import numpy as np import matplotlib.pyplot as plt from scipy.stats import beta class MCMC: def __init__(self,scale=0.5): self.ta = np.random.random(1) self.scale = ...
  • 因此,给定固定的迭代总数 ,具有高相关性的马尔可夫链的独立样本的总数小于具有低相关性的马尔可夫链的独立样本的总数 。 我们可以通过计算 有效样本量 (ESS)表示单个马尔可夫链的参数。了解ESS后,我们可以...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 725
精华内容 290
关键字:

马尔可夫链蒙特卡罗法