【机器学习】六、概率图模型

今天我们对概率图模型（Probabilistic Graphical Model，PGM）做一个总结。

模型表示

概率图模型，是指一种用图结构来描述多元随机变量之间条件独立关系的概率模型。

它提出的背景是为了更好研究复杂联合概率分布的数据特征，假设一些变量的条件独立性，由此我们把概率图模型分为有向图和无向图，并且介绍了它们的模型表示、条件独立性。

有向图模型又称贝叶斯网络或信念网络，其联合概率分布可以分解为每个随机变量Xk的局部条件概率的乘积形式：

贝叶斯网络的条件独立性体现在三种形式：tail-to-tail，head-to-tail，head-to-head。

无向图模型又称马尔科夫随机场或马尔科夫网络，它的联合概率分布由Hammersley Clifford定理保证，能够因子分解为定义在最大团上的正函数的乘积：

马尔科夫随机场的条件独立性体现在局部马尔可夫性、全局马尔可夫性和成对马尔可夫性，他们是相互等价的：

接着我们介绍了判断变量条件独立性的方法——D分离，最后我们得到更一般的算法来确定以下形式之一的独立性问题：

• 给定Z，X和Y是否条件独立

• X和Y边际独立吗

文章链接：

概率图模型(模型表示)

概率图模型(D分离)

模型推断

概率图模型只是为了简便研究模型方便而提出的工具，通常我们把得到联合概率分布参数的过程称为Learning问题，得到参数后，最终要进行推断，称为Inference问题，一般情况下，推断问题分为精确推断和近似推断。

精确推断有变量消除法（VE）和信念传播法（BP）。变量消除法的思想，它的核心是每次对一个变量求积分。

VE算法存在很明显的两个缺点：计算步骤无法存储；消除的最优次序是一个NP-hard问题。因此要对此算法进行改进，得到信念传播算法（BP），该算法的流程主要有三步：

step1:任取⼀个节点 作为根节点

step2:对这个根节点的邻居中的每⼀个节点，收集信息

step3:对根节点的邻居，分发信息

近似推断又分为确定性近似和随机性近似。

很多情况，无法用最大似然估计（MLE）直接求得参数，模型由一些不可观测的变量决定，它们无法直接观测，需要引入隐变量来定义它们。通常情况可以用期望最大化（EM算法）求解，它是一种迭代算法，主要思想是把一个难于处理的似然函数最大化问题用一个易于最大化的序列取代，而其极限是原始问题的解。

E步本质是求隐变量z的后验分布p(z|x,θ)，想方设法把隐变量z积分掉，M步求似然函数最大值的参数θ。

变分推断（VI）是一种确定性近似方法，它的初始算法是基于平均场假设理论，不过该算法存在两个局限：假设太强，期望的积分可能无法计算。由此对算法改进，得到随机梯度变分推断（SGVI），利用重参数技巧和蒙特卡洛采样得到目标函数的梯度，进而采取梯度下降得到近似解。

随机性近似推断的典型是马尔科夫链蒙特卡洛方法（MCMC），主要思想是通过构建马尔可夫链概率序列，使其收敛到平稳分布p(z)。

蒙特卡洛采样是一种随机模拟方法，核心是求解x的概率分布p(x)，以及如何基于概率分布去采集n个样本点。采样的目标是采集到的样本能够代表总体，要满足两点：

• 样本趋向于高概率的区域

• 样本之间必须独立

常用的采样方法有概率分布采样（CDF Sampling）、拒绝采样（Rejection Sampling）和重要性采样（Importance Sampling）。

马尔可夫链是一种时间和状态都是离散的随机变量序列，它由状态空间和转移矩阵定义，通常情况我们研究齐次马尔可夫链（未来状态的条件概率分布仅依赖于现在状态）。

平稳分布就是表示在某一个时刻后，分布不再改变。我们通过蚱蜢的例子来深入介绍了平稳分布，它表示了停留在某一状态的概率与从随机采样的前期状态转移到它的概率相同。

但并不是所有马氏链都是平稳分布，所以我们想找到一种构建有平稳分布的马氏链。这就引入了平稳分布的充分条件——细致平衡。

细致平衡条件将平稳分布的序列和⻢尔可夫链的转移矩阵联系在⼀起，把转移矩阵作为提议矩阵（提议函数），通过它可以不断⽣成样本点，就可以完成采样了，这个就是MCMC。主要用到MH算法，面对高维空间的话，用到MH的优化算法——Gibbs采样

文章传送门：

模型推断：VE与BP

EM算法

变分推断（Variational Inference）

MCMC（蒙特卡洛采样）

MCMC（马尔可夫链）

MCMC（MH算法）

具体模型

最简单的图模型是朴素贝叶斯，它是一个强假设：即给定y的情况下，特征之间相互独立：

引⼊单个隐变量后，发展出了高斯混合模型（GMM） ：

如果单个隐变量变成序列的隐变量，就得到了动态空间模型（Dynamic Model）：

引⼊齐次马尔科夫假设和观测独立假设就有隐马尔科夫模型（HMM），卡尔曼滤波和粒子滤波.

HMM的隐状态假设是离散的，卡尔曼滤波的隐状态假设是连续的，但观测变量服从高斯分布，而粒子滤波是非线性非高斯情况下的动态模型。

为了打破观测独立性，引⼊了⼀种最大熵马尔科夫模型（MEMM），它把最大熵原理与隐马尔科夫模型结合：

为了克服 MEMM 中的局域问题，⼜引⼊了条件随机场（CRF），CRF 是⼀个⽆向图，其中，破坏了⻬次⻢尔可夫假设，如果隐变量是⼀个链式结构，那么⼜叫线性链 CRF。

在⽆向图的基础上，引⼊隐变量得到了玻尔兹曼机，这个图模型的概率密度函数是⼀个指数族分布。对隐变量和观测变量作出⼀定的限制，就得到了受限玻尔兹曼机（RBM）

我们看到，不同的概率图模型对下⾯⼏个特点作出假设：

1. 方向-边的性质

2. 离散/连续/混合-点的性质

3. 条件独立性-边的性质

4. 隐变量-点的性质

5. 指数族-结构特点

此外，我们介绍五种聚类算法：基于质心的K-means算法，基于概率分布的GMM算法，基于密度的DBSCAN算法，基于无向图的谱聚类，以及基于层次聚类的BIRCH算法，其中K-means可以看成GMM的特殊情形。

最后，我们很久前介绍过了贝叶斯线性回归和高斯过程回归（GPR），它也可以看成概率图模型，我们是专门为了介绍一种调参方法而提前介绍这两个模型——贝叶斯优化（BOA），它可以在无法确定函数表达式的前提下，找到函数的最值点。

文章传送门：

高斯混合模型（GMM）

隐马尔可夫模型（背景介绍）

隐马尔可夫模型（前向算法与后向算法）

隐马尔可夫模型（Baum Welch算法与Viterbi算法）

隐马尔可夫模型（模型推断五大问题）

隐马尔可夫模型（算法流程&实例演示）

线性动态系统LDS（别名:卡尔曼滤波）

粒子滤波（Particle Filter）

条件随机场CRF（一）

条件随机场CRF（二）

条件随机场CRF（三）

受限波尔茨曼机（RBM）

高斯网络（GBN与GMN）

聚类算法（K-means）

聚类算法（谱聚类）

聚类算法（BIRCH）

聚类算法（DBSCAN）

聚类算法（相似度与性能度量）

贝叶斯线性回归

高斯过程回归(GPR)

贝叶斯优化

对于上面的概率图模型，我们有部分给出了编程实现，有部分还没有，以后会陆续介绍。目前重点是把原理介绍清楚，对机器学习有个整体把握。熟悉这些工具，加上其原理的思想，在我们工作中灵活应用，希望对亲爱的读者你有用！

我们不久后开始深度学习的内容，再难，我也想你一起学算法！！！