IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 人工智能 -> 机器学习—马尔科夫蒙特卡洛 -> 正文阅读

[人工智能]机器学习—马尔科夫蒙特卡洛


MCMC是一种随机的近似推断,其核心就是基于采样的随机近似方法蒙特卡洛方法。对于采样任务来说,有下面一些常用的场景:

  • 采样作为任务,用于生成新的样本
  • 求和/求积分
    采样结束后,我们需要评价采样出来的样本点是不是好的样本集:
  • 样本趋向于高概率的区域
  • 样本之间必须独立
    具体采样中,采样时一个困难的过程:
  • 无法采样得到归一化因子,即无法直接对概率 p ( x ) = 1 Z p ^ ( x ) p(x)=\frac{1}{Z}\hat{p}(x) p(x)=Z1?p^?(x)采样,常常需要对CDF采样,但复杂的情况不行
  • 如果归一化因子可以求得,但是对高维数据依然不能均匀采样(维度灾难),这是由于对p维空间,总的状态空间是 K p K^p Kp这么大,于是在这种情况下,直接采样也不行
    因此需要借助其他手段,如蒙特卡洛方法中的拒绝采样,重要性采样和MCMC。

蒙特卡洛方法

蒙特卡洛方法旨在求得复杂概率分布下的期望值: E z ∣ x [ f ( z ) ] = ∫ p ( z ∣ x ) f ( z ) d z ? 1 N ∑ i = 1 N f ( z i ) \mathbb{E}_{z|x}[f(z)]=\int p(z|x)f(z)dz\simeq\frac{1}{N}\sum\limits_{i=1}^Nf(z_i) Ezx?[f(z)]=p(zx)f(z)dz?N1?i=1N?f(zi?),也就是说,从概率分布中取N个点,从而近似计算这个积分。采样方法有:

  • 概率分布采样,首先求得概率密度的累积密度函数CDF,然后求得CDF的反函数,在0到1之间均匀采样,代入反函数,就得到了采样点。但是实际大部分概率分布不能得到CDF。
  • Rejection Sampling 拒绝采样:对于概率分布 p ( z ) p(z) p(z),引入简单的提议分布 q ( z ) q(z) q(z),使得 ? z i , M q ( z i ) ≥ p ( z i ) \forall z_i,Mq(z_i)\ge p(z_i) ?zi?,Mq(zi?)p(zi?)。我们现在 q ( z ) q(z) q(z)中采样,定义接受率: α = p ( z i ) M q ( z i ) ≤ 1 \alpha=\frac{p(z^i)}{Mq(z^i)}\le1 α=Mq(zi)p(zi)?1。算法描述为:
  • z i ~ q ( z ) z^i\sim q(z) ziq(z)
  • 在均匀分布中选取 u u u
  • 如果 u ≤ α u\le\alpha uα,则接受 z i z^i zi。否则,拒绝这个值。
  • Importance Sampling: 直接对期望: E p ( z ) [ f ( z ) ] \mathbb{E}_{p(z)}[f(z)] Ep(z)?[f(z)]进行采样。
    E p ( z ) [ f ( z ) ] = ∫ p ( z ) f ( z ) d z = ∫ p ( z ) q ( z ) f ( z ) q ( z ) d z ? 1 N ∑ i = 1 N f ( z i ) p ( z i ) q ( z i ) \mathbb{E}_{p(z)}[f(z)]=\int p(z)f(z)dz=\int \frac{p(z)}{q(z)}f(z)q(z)dz\simeq\frac{1}{N}\sum\limits_{i=1}^Nf(z_i)\frac{p(z_i)}{q(z_i)} Ep(z)?[f(z)]=p(z)f(z)dz=q(z)p(z)?f(z)q(z)dz?N1?i=1N?f(zi?)q(zi?)p(zi?)?
    于是采样在q(z)中采样,并通过权重计算和。重要值采样对于权重非常小的时候,效率非常低。重要性采样有一个变种Sampling-Importance-Resampling,这种方法,首先和上面一样进行采样,然后在采样出来的N个样本中,重新采样,这个重新采样,使用每个样本点的权重作为概率分布进行采样。

MCMC

马尔科夫链式是一种时间状态都是离散的随机变量序列。我们关注的主要是齐次的一阶马尔科夫链。马尔科夫链满足: p ( X t + 1 ∣ X 1 , X 2 , ? ? , X t ) = p ( X t + 1 ∣ X t ) p(X_{t+1}|X_1,X_2,\cdots,X_t)=p(X_{t+1}|X_t) p(Xt+1?X1?,X2?,?,Xt?)=p(Xt+1?Xt?)。这个式子可以写成转移矩阵的形式 p i j = p ( X t + 1 = j ∣ X t = i ) p_{ij}=p(X_{t+1}=j|X_t=i) pij?=p(Xt+1?=jXt?=i)。我们有:
π t + 1 ( x ? ) = ∫ π i ( x ) p x → x ? d x \pi_{t+1}(x^*)=\int\pi_i(x)p_{x\to x^*}dx πt+1?(x?)=πi?(x)pxx??dx
如果存在 π = ( π ( 1 ) , π ( 2 ) , ? ? ) , ∑ i = 1 + ∞ π ( i ) = 1 \pi=(\pi(1),\pi(2),\cdots),\sum\limits_{i=1}^{+\infin}\pi(i)=1 π=(π(1),π(2),?),i=1+?π(i)=1,有上式成立,这个序列就叫马尔科夫链 X t X_t Xt?的平稳分布,平稳分布就是表示在某一个时刻后,分布不再改变。MCMC就是通过构建马尔科夫链概率序列,使其收敛到平稳分布 p ( z ) p(z) p(z)。引入细致平衡: π ( x ) p x → x ? = π ( x ? ) p x ? → x \pi(x)p_{x\to x^*}=\pi(x^*)p_{x^*\to x} π(x)pxx??=π(x?)px?x?。如果一个分布满足细致平衡,那么一定满足平稳分布:
∫ π ( x ) p x → x ? d x = ∫ π ( x ? ) p x ? → x d x = π ( x ? ) \int\pi(x)p_{x\to x^*}dx=\int\pi(x^*)p_{x^*\to x}dx=\pi(x^*) π(x)pxx??dx=π(x?)px?x?dx=π(x?)
细致平衡条件将平稳分布的序列和马尔科夫链的转移矩阵联系在一起了,通过转移矩阵可以不断生成样本点。假定随机取一个转移矩阵 ( Q = Q i j ) (Q=Q_{ij}) (Q=Qij?),作为一个提议矩阵。我们有:
p ( z ) ? Q z → z ? α ( z , z ? ) = p ( z ? ) ? Q z ? → z α ( z ? , z ) p(z)\cdot Q_{z\to z^*}\alpha(z,z^*)=p(z^*)\cdot Q_{z^*\to z}\alpha(z^*,z) p(z)?Qzz??α(z,z?)=p(z?)?Qz?z?α(z?,z)
取:
α ( z , z ? ) = min ? { 1 , p ( z ? ) Q z ? → z p ( z ) Q z → z ? } \alpha(z,z^*)=\min\{1,\frac{p(z^*)Q_{z^*\to z}}{p(z)Q_{z\to z^*}}\} α(z,z?)=min{1,p(z)Qzz??p(z?)Qz?z??}

p ( z ) ? Q z → z ? α ( z , z ? ) = min ? { p ( z ) Q z → z ? , p ( z ? ) Q z ? → z } = p ( z ? ) ? Q z ? → z α ( z ? , z ) p(z)\cdot Q_{z\to z^*}\alpha(z,z^*)=\min\{p(z)Q_{z\to z^*},p(z^*)Q_{z^*\to z}\}=p(z^*)\cdot Q_{z^*\to z}\alpha(z^*,z) p(z)?Qzz??α(z,z?)=min{p(z)Qzz??,p(z?)Qz?z?}=p(z?)?Qz?z?α(z?,z)
于是,迭代就得到了序列,这个算法叫做Metropolis-Hastings算法:

  • 通过在0,1之间均匀分布取点u
  • 生成 z ? ? Q ( z ? ∣ z i ? 1 ) z^*~Q(z^*|z^{i-1}) z??Q(z?zi?1)
  • 计算 α \alpha α
  • 如果 α ≥ u \alpha\ge u αu,则 z i = z ? z^i=z^* zi=z?,否则 z i = z i ? 1 z^{i}=z^{i-1} zi=zi?1
    这样取的样本就服从 p ( z ) = p ^ ( z ) z p ~ p ^ ( z ) p(z)=\frac{\hat{p}(z)}{z_p}\sim \hat{p}(z) p(z)=zp?p^?(z)?p^?(z)
    下面介绍另一种采样方式Gibbs采样,如果z的维度非常高,那么通过固定被采样的维度其余的维度来简化采样过程: z i ~ p ( z i ∣ z ? i ) z_i\sim p(z_i|z_{-i}) zi?p(zi?z?i?):
  • 给定初始值 z 1 0 , z 2 0 , . . . z^0_1,z^0_2,... z10?,z20?,...
  • 在t+1时刻,采样 z i t + 1 ? p ( z i ∣ z ? i ) z_i^{t+1}~p(z_i|z_{-i}) zit+1??p(zi?z?i?),从第一个维度一个个采样。
    Gibbs采样方法是一种特殊的MH采样,可以计算Gibbs采样的接受率:
    p ( z ? ) Q z ? → z p ( z ) Q z → z ? = p ( z i ? ∣ z ? i ? ) p ( z ? i ? ) p ( z i ∣ z ? i ? ) p ( z i ∣ z ? i ) p ( z ? i ) p ( z i ? ∣ z ? i ) \frac{p(z^*)Q_{z^*\to z}}{p(z)Q_{z\to z^*}}=\frac{p(z_i^*|z^*_{-i})p(z^*_{-i})p(z_i|z_{-i}^*)}{p(z_i|z_{-i})p(z_{-i})p(z_i^*|z_{-i})} p(z)Qzz??p(z?)Qz?z??=p(zi?z?i?)p(z?i?)p(zi??z?i?)p(zi??z?i??)p(z?i??)p(zi?z?i??)?
    对于每个Gibbs采样步骤, z ? i = z ? i ? z_{-i}=z_{-i}^* z?i?=z?i??,这是由于每个维度i采样的时候,其余的参数量保持不变。所以上式为1.于是Gibbs采样过程中相当于找到了一个步骤,使得所有的接受率为1.

平稳分布

定义随机矩阵:
Q = ( Q 11 Q 12 ? Q 1 K ? ? ? ? Q k 1 Q k 2 ? Q K K ) Q=\begin{pmatrix}Q_{11}&Q_{12}&\cdots&Q_{1K}\\\vdots&\vdots&\vdots&\vdots\\Q_{k1}&Q_{k2}&\cdots&Q_{KK}\end{pmatrix} Q=????Q11??Qk1??Q12??Qk2??????Q1K??QKK??????
这个矩阵每一行或者每一列的和都是1.随机矩阵的特征值都小于等于1.假设只有一个特征值为 λ i = 1 \lambda_i=1 λi?=1。于是在马尔科夫过程中:
q t + 1 ( x = j ) = ∑ i = 1 K q t ( x = i ) Q i j ? q t + 1 = q t ? Q = q 1 Q t q^{t+1}(x=j)=\sum\limits_{i=1}^Kq^t(x=i)Q_{ij}\\ \Rightarrow q^{t+1}=q^t\cdot Q=q^1Q^t qt+1(x=j)=i=1K?qt(x=i)Qij??qt+1=qt?Q=q1Qt
于是有:
q t + 1 = q 1 A Λ t A ? 1 q^{t+1}=q^1A\Lambda^t A^{-1} qt+1=q1AΛtA?1
如果 m m m 足够大,那么, Λ m = d i a g ( 0 , 0 , ? ? , 1 , ? ? , 0 ) \Lambda^m=diag(0,0,\cdots,1,\cdots,0) Λm=diag(0,0,?,1,?,0),则: q m + 1 = q m q^{m+1}=q^{m} qm+1=qm ,则趋于平稳分布了。马尔可夫链可能具有平稳分布的性质,所以我们可以构建马尔可夫链使其平稳分布收敛于需要的概率分布(设计转移矩阵)。
在采样过程中,需要经历一定的时间(燃烧期/混合时间)才能达到平稳分布。但是MCMC方法有一些问题:

  • 无法判断是否已经收敛
  • 燃烧期过长(维度太高,并且维度之间有关,可能无法采样到某些维度),例如在GMM中,可能无法采样到某些峰。于是在一些模型中,需要对隐变量之间的关系作出约束,如RBM假设隐变量之间无关。
  • 样本之间一定是有相关性的,如果每个时刻都取一个点,那么每个样本一定和前一个相关,这可以通过间隔一段时间采样。
  人工智能 最新文章
2022吴恩达机器学习课程——第二课(神经网
第十五章 规则学习
FixMatch: Simplifying Semi-Supervised Le
数据挖掘Java——Kmeans算法的实现
大脑皮层的分割方法
【翻译】GPT-3是如何工作的
论文笔记:TEACHTEXT: CrossModal Generaliz
python从零学(六)
详解Python 3.x 导入(import)
【答读者问27】backtrader不支持最新版本的
上一篇文章      下一篇文章      查看所有文章
加:2022-06-01 15:13:42  更:2022-06-01 15:16:57 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 4:40:15-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码