当前课程知识点：大数据机器学习 > 第十七章 概率图模型的学习与推断 > 2.近似推断法：MCMC和变分推断 > 2.近似推断法：MCMC和变分推断
精确推断方法
通常需要很大的计算开销
因此呢
在现实应用中
近似推断方法更为常用
近似推断方法大致分为两大类
第一类是采样
就是通过使用随机化方法完成近似
第二类呢
是使用确定性的近似完成近似推断
典型的代表为变分推断
在很多任务中
我们关心某些概率的分布
并非因为对这些概率本身感兴趣
而是要基于他们去计算某些期望值
并且
还能进一步基于这些期望做出决策
例如刚才我们看到的那个贝叶斯网
我们计算了Px5
就是变量x5的概率
但是
我们进行推断的目的
可能是为了计算变量x5的期望
那么
如果直接计算或逼近这个期望
比推断概率分布更容易的话
那我们干嘛还要舍近求远呢
直接获取期望不是更好吗
那么
采样法正是基于这个思路
具体来说
假定我们的目标是计算函数fx
在概率密度函数px下的期望
也就是Epf等于fx px对x积分
则可以根据抽取一组样本xi到xn
然后呢
计算fx在这些样本上的均值
以此来近似目标期望Ex
如果样本x1 x2一直到xn独立的话
那么 基于大数定理
这种通过大量采样的方法
就能获得较高的近似精度
那么 问题就来了
问题的关键是如何采样呢
对于概率图模型来说
就是如何高效的基于
图模型所描述的概率分布来获取样本
简单说
就是如何采样符合概率分布
然而
如果概率密度函数p(x)很复杂的话
则构造服从p分布的独立同分布样本
也是很困难的
MCMC方法它的关键就在于
通过构造平稳分布
为P的马尔可夫链来产生样本
接下来我们介绍相关的马氏链定理
马氏链定理
如果一个非周期的马氏链
具有转移概率矩阵P
且他的任何两个状态是连通的
那么 马氏链
收敛于一个稳定的状态概率分布πj
（见上图）
π是方程πP=π的唯一非负解
如果马尔可夫链运行时间足够长
也就是收敛到平稳状态
概率分布πix
将收敛到平稳分布πx
那么此时产生出的样本X
就近似的服从于分布P
这样就解决了刚才我们需要采样的问题
那么
如何判断马尔可夫链到达了平稳状态呢
假定
平稳的马尔可夫链T的状态转移概率
也就是从状态x转移到状态x’概率为Txx’
T时刻状态的分布为Px’
则如果在某个时刻
马尔可夫链满足平稳条件
(见上图)的话
那么
px就是该马尔可夫链的平稳分布
并且马尔可夫链
在满足该条件的时候
就已经收敛到平稳状态
也就是说
mcmc方法
先设法构造一条马尔可夫链
使其收敛至平稳分布
恰为待估计参数的后验分布
然后呢
再通过这条马尔可夫链
来产生符合后验分布的样本
并基于这些样本来进行估计
这里呢马尔可夫链
转移概率的构造至关重要
不同的构造方法
将产生不同的MCMC算法
其中一种方法称为
mcmc方法的重要代表
是Metropolis-Hastings方法
它是基于拒绝采样
来逼近平稳分布P的
该算法呢每次
根据上一轮采样的结果Xt-1
来采样获取候选的状态样本x*
但这个候选样本
会以一定的概率被拒绝掉
假定从状态xt-1
到状态x*的转移概率为
（见上图）
其中 Q x* xt-1
是用户给定的先验概率
A x* xt-1是x* 被接受的概率
如果x*最终收敛到平稳状态
那么
就有下式是成立的
为了达到平稳状态
只需要将接受率A x* xt-1
设置为（见上图）
那么 Metropolis-Hastings
算法的具体步骤如下
输入是先验概率Q x* xt-1
具体步骤
第一步初始化X0
就是一开始的状态
第二步呢
执行循环
根据先验的概率Q x* xt-1
采样出候选的样本x*
根据均匀分布从0到1范围内
采样出阈值u
如果u小于等于A x* xt-1
那么 xt=x* 表示接收
如果U大于A x* xt-1
那么 xt=xt-1
结束if循环 返回X1X2的
输出就是采样出的一个样本序列X1X2的
吉布斯采样
有时被视为
Metropolis-Hastings算法的特例
它也使用马尔可夫链获取样本
而且该马尔可夫链的平稳分布
也是采样的目标分布px
具体来说
X等于x1 x2直到xn
目标分布为px
在初始化X的取值后
通过循环执行以下步骤来完成采样
第一步呢是随机
或以某个次序选取某个变量Xi
第二步
根据X中
除Xi外的变量的现有取值
计算条件概率p xi xi-
其中xi-为X序列中
除Xi以外的元素
第三步
根据P xi xi-对变量Xi采样
用采样值来代替原值
我们介绍完了MCMC采样以后
我们下面介绍变分推断
变分推断是通过使用已知简单的分布
来逼近需要推断的复杂分布
并通过限制近似分布的类型
从而得到一种局部的最优
而且是具有确定解的近似后验分布
在学习变分推断之前
我们先介绍概率图模型
一种简洁的表示方法
盘式记法
如图所示
左图中有N个变量
X1X2一直到XN
它们都依赖于另外一个变量Z
右图中
这些相互独立的
而且是由相同机制生成的多个变量
被放在一个方框里或者是盘子
并在方框中标出类似变量
重复出现的个数N
方框可以嵌套
通常用阴影来标注出已知的
并且能观测到的变量
在很多学习任务中
对普通概率图模型
可以使用盘式记法
使得概率图模型更加简洁
更加有利于分析
如果所有能观察到的变量X
它们的联合分布的概率密度函数是下式
就是（见上图）的条件概率的话
那么
所对应的对数似然函数
就可以写为（见上图）
其中 X等于X1X2一直到XN
θ是X与Z服从的分布参数
那么 对刚才的图来说
所对应的推断和学习任务
主要是由观察到的变量X
来估计隐变量Z和分布参数θ
也就是求解
给定条件Xθ下Z的条件概率和θ本身
我们采用常用的
最大化对数似然函数的方法
进行概率模型的参数估计
对于该式我们采用
期望最大算法进行求解
在期望这一步骤的时候
我们根据T时刻的参数θT
对PZ给定条件XθT进行推断
并计算联合似然函数PXZ给定条件θ
在M步也就是最大步
基于E步的结果进行最大化寻优
也就是对关于变量θ的函数
Q θ θt进行最大化
从而求取（见上图）
从公式可以看出
M步实际是对数联合似然函数
LnP x z给定条件θ
在分布Pz给定条件xθt
当分布Pz给定条件xθt
与变量Z的真实后验分布相等的时候
Q函数近似于对数似然函数
于是呢
期望最大算法最终可以获得稳定的参数θ
而隐变量Z的分布
也能通过该参数获得
那么 通过刚才的介绍
我们发现问题就在于Pz给定条件xθt
它未必是隐变量Z的真实分布
它只是隐变量Z的一个近似分布
这样呢
我们就用Qz来表示这个近似分布
那么（见上图）对z的积分
（见上图）对z整体积分
这个公式
应用了信息论中衡量两个分部
相似性的KL分歧度量
虽然我们构造了QZ
而且找到了需要优化的目标
但是呢
在现实任务当中
E步对pz给定条件x θt的推断
很可能会因为Z的模型复杂而难以进行
这个时候呢
我们就需要借助于变分推断
变分推断
是我们通常假设z服从一个分布
qz=πi=1到M qizi
假设复杂的多变量z
可以拆解为一系列
相互独立的多变量zi
这样的话
我们可以令qi分布相对简单
或有更好的结构
例如
我们假设qi为指数族的分布
那么
刚才我们定义的Lq
就可以有如下的形式
在这个展开的式子中
我们对第一项中内部积分
进行一个两次的替代
最后呢
我们用lnp~xzj
替代该内部的积分
ln p xz πi
不等于j qi 对zi积分
后面两项不变
我们把前面两项进行合并
我们发现这其实也是一个KL分歧
我们关心的是qj
就可以固定qi i不等于j的部分
然后呢
再对Lq进行最大化
刚才的Lq
我们发现其实也是一个KL分歧
（见上图）
那么 很明显
当qi=p~x zj时Lq最大
于是呢
我们就可以知道变量子集zj
所服从的最优分布qj*应满足
（见上图）
在i不等于j时的期望加上常数
也就是（见上图）
也就是说
当把z拆解为一系列
相互独立的多变量Zi
变量子集zj
最接近真实情形的分布
是由 qj*zj给出的
注意
这里的分子部分
就是求lnp xz在i不等于j的期望
是可以有闭式解的
也就是说
通过恰当的分割独立变量子集Zj
并选择Qi服从的分布
这就使得qi*
能高效地对隐变量Z进行推断
从上面的内容可以看出
在实践中使用变分方法
最重要的是考虑如何对隐变量进行拆解
以及假设
各变量子集服从何种分布
在此基础上
套用qj*zj的结论
再结合期望最大算法
就可以进行
概率图模型的推断和参数估计
好 这一讲就到这
-1.机器学习定义和典型应用
-2.机器学习和人工智能的关系
-3.深度学习方法和其它人工智能方法的共性和差异
-4.机器学习和数据挖掘的关系
-5.机器学习和统计学习的关系
-6.机器学习的发展历程
-7.大数据机器学习的主要特点
-第一章 概述--7.大数据机器学习的主要特点
-1机器学习的基本术语
-2.监督学习
--2.监督学习
-3.假设空间
--3.假设空间
-4.学习方法三要素
-第二章 机器学习基本概念--4.学习方法三要素
-5.奥卡姆剃刀定理
-6.没有免费的午餐定理
-7.训练误差和测试误差
-8.过拟合与模型选择
-第二章 机器学习基本概念--8.过拟合与模型选择
-9.泛化能力
--9.泛化能力
-10.生成模型和判别模型
-1.留出法
--1.留出法
-2.交叉验证法
--2.交叉验证法
-3.自助法
--3.自助法
-4.性能度量
--4.性能度量
-5.PR曲线
--5.PR曲线
-6.ROC和AUC曲线
-第三章 模型性能评估--6.ROC和AUC曲线
-7.代价敏感错误率
-8.假设检验
--8.假设检验
-9.T检验
--9.T检验
-10.偏差和方差
--10.偏差和方差
-1.感知机模型
--1.感知机模型
-第四章 感知机--1.感知机模型
-2.感知机学习策略
-3.感知机学习算法
-第四章 感知机--3.感知机学习算法
-1.原型聚类描述
--1.原型聚类描述
-第五章 聚类--1.原型聚类描述
-2.性能度量
--2.性能度量
-第五章 聚类--2.性能度量
-3.1原型聚类 k均值算法
-3.2 原型聚类 学习向量算法
-3.3 原型聚类 密度聚类
-第五章 聚类--3.3 原型聚类 密度聚类
-3.4原型聚类 层次聚类
-1.综述
--1.综述
-2.概率图模型
--2.概率图模型
-第六章 贝叶斯分类器及图模型--2.概率图模型
-3.贝叶斯网络
--3.贝叶斯网络
-第六章 贝叶斯分类器及图模型--3.贝叶斯网络
-4.朴素贝叶斯分类器
-第六章 贝叶斯分类器及图模型--4.朴素贝叶斯分类器
-5.半朴素贝叶斯分类器
-第六章 贝叶斯分类器及图模型--5.半朴素贝叶斯分类器
-6.贝叶斯网络结构学习推断
-7.吉布斯采样
--7.吉布斯采样
-第六章 贝叶斯分类器及图模型--7.吉布斯采样
-开头
--开头
-1.决策树模型与学习基本概念
-2.信息量和熵
--2.信息量和熵
-第七章 决策树和随机森林--2.信息量和熵
-3.决策树的生成
--3.决策树的生成
-4.决策树的减枝
--4.决策树的减枝
-5.CART算法
--5.CART算法
-6.随机森林
--6.随机森林
-简介
--简介
-1.逻辑斯谛回归模型
-第八章 逻辑斯谛回归与最大熵模型--1.逻辑斯谛回归模型
-2.最大熵模型
--2.最大熵模型
-3.模型学习的最优化方法
-第八章 逻辑斯谛回归与最大熵模型--3.模型学习的最优化方法
-1.开头
--1.开头
-2.SVM简介
--2.SVM简介
-3.线性可分支持向量机
-第九章 SVM--3.线性可分支持向量机
-4. 凸优化问题的基本概念
-第九章 SVM--4. 凸优化问题的基本概念
-5.支持向量的确切定义
-6.线性支持向量机
-第九章 SVM--6.线性支持向量机
-svm相关拓展资料
-开头
--开头
-第十章 核方法与非线性SVM--开头
-1.泛函基础知识
--1.泛函基础知识
-第十章 核方法与非线性SVM--1.泛函基础知识
-2. 核函数和非线性支持向量机
-第十章 核方法与非线性SVM--2. 核函数和非线性支持向量机
-3. 序列最小最优化算法
-第十章 核方法与非线性SVM--3. 序列最小最优化算法
-开头
--开头
-1. k近邻学习
--1. k近邻学习
-第十一章 降维与度量学习--1. k近邻学习
-2. 降维嵌入
--2.降维嵌入
-第十一章 降维与度量学习--2. 降维嵌入
-3. 主成分分析
--3.主要成分分析
-第十一章 降维与度量学习--3. 主成分分析
-4. 核化线性降维
--4.核化线性降维
-5. 流型学习和度量学习
-1. 提升方法Adaboost算法
-第十二章 提升方法--1. 提升方法Adaboost算法
-2. Adaboost算法的训练误差分析
-3. Adaboost算法的解释
-4. Adaboost的实现
-第十二章 提升方法--4. Adaboost的实现
-adaboost拓展资料
-开头
--开头
-1. 问题提出
--1. 问题提出
-2. EM算法的引入
-3. EM算法的收敛性
-4. EM算法在高斯混合模型学习中的应用
-5. EM算法的推广
-第十三章 EM算法及混合高斯模型--3. EM算法的收敛性
-开头
--开头
-1. 计算学习理论的基础知识
-第十四章 计算学习理论--1. 计算学习理论的基础知识
-2. 概率近似正确学习理论
-3. 有限假设空间
--3.有限假设空间
-4. VC维
--4. VC维
-第十四章 计算学习理论--4. VC维
-5. 学习稳定性
--5. 学习稳定性
-开头
--开头
-1. 隐马尔科夫模型的基本概念
-第十五章 隐马尔可夫模型--1. 隐马尔科夫模型的基本概念
-2. 概率计算算法
-3. 学习算法
--3.学习算法
-第十五章 隐马尔可夫模型--3. 学习算法
-4预测算法
--4. 预测算法
-第十五章 隐马尔可夫模型--4预测算法
-开头
--开头
-1.概率无向图模型
-第十六章 条件随机场--1.概率无向图模型
-2.条件随机场的定义与形式
-第十六章 条件随机场--2.条件随机场的定义与形式
-3.条件随机场的计算问题
-4.条件随机场的学习算法
-5.条件随机场的预测算法
-第十六章 条件随机场--5.条件随机场的预测算法
-开头
--开头
-1.精确推断法：变量消去法和信念传播法
-第十七章 概率图模型的学习与推断--1.精确推断法：变量消去法和信念传播法
-2.近似推断法：MCMC和变分推断
-第十七章 概率图模型的学习与推断--2.近似推断法：MCMC和变分推断
-1.神经网络的发展历程
-2.神经网络的基本概念以及常见的神经网络(一）
-第十八章 神经网络和深度学习--2.神经网络的基本概念以及常见的神经网络(一）
-3.神经网络的基本概念以及常见的神经网络(二）
-4.玻尔兹曼机
--4.玻尔兹曼机
-5.深度学习
--5.深度学习
-第十八章 神经网络和深度学习--5.深度学习
-1. 深度学习简介和架构设计
-2. 计算图形式的反向传播算法
-3.深度学习的正则化方法（一）
-4.深度学习的正则化方法（二）
-1.深度学习的优化问题
-第二十章 深度学习优化方法--1.深度学习的优化问题
-2.神经网络优化的挑战
-3.神经网络的优化算法
-第二十章 深度学习优化方法--3.神经网络的优化算法
-4.相关策略
--4.相关策略
-第二十章 深度学习优化方法--4.相关策略
