机器学习——第十四章概率图模型

本文主要是介绍机器学习——第十四章概率图模型，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

14.1 隐马尔可夫模型

14.2 马尔可夫随机场

14.3 条件随机场

14.4学习与推断

14.4.1 变量消去

14.4.2 信念传播

14.5 近似推断

14.5.1 MCMC采样

14.5.2 变分推断

14.6 话题模型

14.1 隐马尔可夫模型

隐马尔可夫模型（Hidden Markov Model，简称HMM）是结构最简单的一种贝叶斯网，在语音识别与自然语言处理领域上有着广泛的应用。HMM中的变量分为两组：状态变量与观测变量，其中状态变量一般是未知的，因此又称为“隐变量”，观测变量则是已知的输出值。在隐马尔可夫模型中，变量之间的依赖关系遵循如下两个规则：

观测变量的取值仅依赖于状态变量；
下一个状态的取值仅依赖于当前状态，通俗来讲：现在决定未来，未来与过去无关，这就是著名的马尔可夫性。

基于上述变量之间的依赖关系，我们很容易写出隐马尔可夫模型中所有变量的联合概率分布：

\(P(x_1,y_1,\ldots,x_n,y_n)=P(y_1)P(x_1\mid y_1)\prod_{i=2}^nP(y_i\mid y_{i-1})P(x_i\mid y_i)\)

易知：欲确定一个HMM模型需要以下三组参数：

状态转移概率:模型在各个状态间转换的概率，通常记为矩阵\(A=[a_{ij}]_{N\times N}\)，其中

\(a_{ij}=P(y_{t+1}=s_j\mid y_t=s_i) ,\quad1\leqslant i,j\leqslant N,\)

        表示在任意时刻t，若状态为\(s_i\)，则在下一时刻状态为\(s_j\)的概率.

输出现测概率:模型根据当前状态获得各个观测值的概率,通常记为矩阵\(\mathbf{B}=[b_{ij}]_{N\times M}\),其中

\(b_{ij}=P(x_t=o_j\mid y_t=s_i) ,\quad1\leqslant i\leqslant N ,1\leqslant j\leqslant M\)

        表示在任意时刻t，若状态为\(s_i\), 则观测值\(o_j\)被获取的概率.

初始状态概率:模型在初始时刻各状态出现的概率，通常记为\(\pi=(\pi_1,\pi_2,\ldots,\pi_N)\),其中

\(\pi_{i}=P(y_{1}=s_{i}),\quad1\leqslant i\leqslant N\)

        表示模型的初始状态为\(s_i\)的概率.

当确定了一个HMM模型的三个参数后，便按照下面的规则来生成观测值序列：

(1) 设置t = 1 ，并根据初始状态概率\(\pi\)选择初始状态\(y_1\);
(2) 根据状态\(y_t\)和输出现测概率B 选择观测变量取值\(x_t\);
(3) 根据状态\(y_t\)和状态转移矩阵A 转移模型状态，即确定\(y_t+1\);
(4) 若\(t < n\)，设置\(t = t + 1\) ，并转到第(2) 步，否则停止.

在实际应用中，HMM模型的发力点主要体现在下述三个问题上：

给定模型\( \lambda = [\mathbf{A},\mathbf{B},\pi]\),，如何有效计算其产生观测序列\(\mathbf{x}=\{x_{1},x_{2},\ldots,x_{n}\}\)的概率\(P(\mathbf{x}\mid\lambda)\)?换言之，如何评估模型与观测序列之间的匹配程度?
给定模型\( \lambda = [\mathbf{A},\mathbf{B},\pi]\)和观测序列\(\mathbf{x}=\{x_{1},x_{2},\ldots,x_{n}\}\)，如何找到与此观测序列最匹配的状态序列\(\mathbf{y}=\{y_{1},y_{2},\ldots,y_{n}\}\)?换言之，如何根据观测序列推断出隐藏的模型状态?
给定观测序列\(\mathbf{x}=\{x_{1},x_{2},\ldots,x_{n}\}\),如何调整模型参数\( \lambda = [\mathbf{A},\mathbf{B},\pi]\)使得该序列出现的概率\(P(\mathbf{x}\mid\lambda)\)最大?换言之，如何训练模型使其能最好地描述观测数据?

14.2 马尔可夫随机场

马尔可夫随机场（Markov Random Field）是一种典型的马尔可夫网，即使用无向边来表达变量间的依赖关系。在马尔可夫随机场中，对于关系图中的一个子集，若任意两结点间都有边连接，则称该子集为一个团；若再加一个结点便不能形成团，则称该子集为极大团。MRF使用势函数来定义多个变量的概率分布函数，其中每个（极大）团对应一个势函数，一般团中的变量关系也体现在它所对应的极大团中，因此常常基于极大团来定义变量的联合概率分布函数。具体而言，若所有变量构成的极大团的集合为C，则MRF的联合概率函数可以定义为：

\(P(\mathbf{x})=\frac{1}{Z}\prod_{Q\in\mathcal{C}}\psi_Q(\mathbf{x}_Q)\)

对于条件独立性，马尔可夫随机场通过分离集来实现条件独立，若A结点集必须经过C结点集才能到达B结点集，则称C为分离集。书上给出了一个简单情形下的条件独立证明过程，十分贴切易懂，此处不再展开。基于分离集的概念，得到了MRF的三个性质：

全局马尔可夫性：给定两个变量子集的分离集，则这两个变量子集条件独立。
局部马尔可夫性：给定某变量的邻接变量，则该变量与其它变量条件独立。
成对马尔可夫性：给定所有其他变量，两个非邻接变量条件独立。

对于MRF中的势函数，势函数主要用于描述团中变量之间的相关关系，且要求为非负函数，直观来看：势函数需要在偏好的变量取值上函数值较大，例如：若x1与x2成正相关，则需要将这种关系反映在势函数的函数值中。一般我们常使用指数函数来定义势函数：

\(\psi_Q(\mathbf{x}_Q)=e^{-H_Q(\mathbf{x}_Q)}\)

\(H_Q(\mathbf{x}_Q)=\sum_{u,v\in Q,u\neq v}\alpha_{uv}x_ux_v+\sum_{v\in Q}\beta_vx_v\)

14.3 条件随机场

条件随机场(Conditional Random Field，简称CRF) 是一种判别式无向图模型。

隐马尔可夫模型和马尔可夫随机场都属于生成式模型，即对联合概率进行建模，条件随机场则是对条件分布进行建模。

CRF试图在给定观测值序列后，对状态序列的概率分布进行建模，即P(y | x)。直观上看：CRF与HMM的解码问题十分类似，都是在给定观测值序列后，研究状态序列可能的取值。CRF可以有多种结构，只需保证状态序列满足马尔可夫性即可，一般我们常使用的是链式条件随机场：

与马尔可夫随机场定义联合概率类似地，CRF也通过团以及势函数的概念来定义条件概率P(y | x)。在给定观测值序列的条件下，链式条件随机场主要包含两种团结构：单个状态团及相邻状态团，通过引入两类特征函数便可以定义出目标条件概率：

\(P(\mathbf{y}\mid\mathbf{x})=\frac{1}{Z}\exp\left(\sum\sum_{i=1}^{n-1}\lambda_{j}t_{j}(y_{i+1},y_{i},\mathbf{x},i)+\sum_{k}\sum_{i=1}^{n}\mu_{k}s_{k}(y_{i},\mathbf{x},i)\right)\)

以词性标注为例，如何判断给出的一个标注序列靠谱不靠谱呢？转移特征函数主要判定两个相邻的标注是否合理，例如：动词+动词显然语法不通；状态特征函数则判定观测值与对应的标注是否合理。因此我们可以定义一个特征函数集合，用这个特征函数集合来为一个标注序列打分，并据此选出最靠谱的标注序列。也就是说，每一个特征函数（对应一种规则）都可以用来为一个标注序列评分，把集合中所有特征函数对同一个标注序列的评分综合起来，就是这个标注序列最终的评分值。可以看出：特征函数是一些经验的特性。

14.4学习与推断

对于生成式模型，通常我们都是先对变量的联合概率分布进行建模，接着再求出目标变量的边际分布（marginal distribution），那如何从联合概率得到边际分布呢？这便是学习与推断。下面主要介绍两种精确推断的方法：变量消去与信念传播。

14.4.1 变量消去

变量消去利用条件独立性来消减计算目标概率值所需的计算量，它通过运用乘法与加法的分配率，将对变量的积的求和问题转化为对部分变量交替进行求积与求和的问题，从而将每次的运算控制在局部，达到简化运算的目的。

\(\begin{aligned}
P(x_{5})& =\sum_{x_{4}}\sum_{x_{3}}\sum_{x_{2}}\sum_{x_{1}}P(x_{1},x_{2},x_{3},x_{4},x_{5}) \\
&=\sum_{x_{4}}\sum_{x_{3}}\sum_{x_{2}}\sum_{x_{1}}P(x_{1})P(x_{2}\mid x_{1})P(x_{3}\mid x_{2})P(x_{4}\mid x_{3})P(x_{5}\mid x_{3})\end{aligned}\)

14.4.2 信念传播

若将变量求和操作看作是一种消息的传递过程，信念传播可以理解成：一个节点在接收到所有其它节点的消息后才向另一个节点发送消息，同时当前节点的边际概率正比于他所接收的消息的乘积：

\(P(x_i)\propto\prod_{k\in n(i)}m_{ki}(x_i)\)

因此只需要经过下面两个步骤，便可以完成所有的消息传递过程。利用动态规划法的思想记录传递过程中的所有消息，当计算某个结点的边际概率分布时，只需直接取出传到该结点的消息即可，从而避免了计算多个边际分布时的冗余计算问题。

指定一个根节点，从所有的叶节点开始向根节点传递消息，直到根节点收到所有邻接结点的消息（从叶到根）；
从根节点开始向叶节点传递消息，直到所有叶节点均收到消息（从根到叶）。

14.5 近似推断

在现实应用中近似推断方法更为常用，近似推断方法大致可分为两大类: 第一类是采样(sampling)，通过使用随机化方法完成近似; 第二类是使用确定性近似完成近似推断，典型代表为变分推断(variational inference)。

14.5.1 MCMC采样

采样法直接计算或逼近这个期望，比较高效，若样本\({x_1,x_2,...,x_n}\)独立，基于大数定律，这种通过大量来样的办法就能获得较高的近似精度。问题的关键变为如何采样。对概率图模型来说，就是如何高效地基于图模型所描述的概率分布来获取样本.。概率图模型中最常用的采样技术是马尔可夫链蒙特卡罗(Markov Chain Monte Carlo，简称 MCMC)方法。

MCMC 方法的关键就在于通过构造"平稳分布为 p 的马尔同夫链"来产生样本。若马尔可夫链运行时间足够长(即收敛到平稳状态)，则此时产出的样本 x 近似服从于分布 p。如何判断马尔可夫链到达平稳状态呢？？？

若在某个时刻马尔可夫链满足平稳条件，

\(p(\mathbf{x}^t)T(\mathbf{x}^{t-1}\mid\mathbf{x}^t)=p(\mathbf{x}^{t-1})T(\mathbf{x}^t\mid\mathbf{x}^{t-1})\)

则 p(x) 是该马尔可夫链的平稳分布，且马尔可夫链在满足该条件时巳收敛到平稳状态。

MCMC 方法先设法构造一条马尔可夫链，使其收敛至平稳分布恰为待估计参数的后验分布，然后通过这条马尔可夫链来产生符合后验分布的样本，并基于这些样本来进行估计。这里马尔可夫链转移概率的构造至关重要、不同的构造方法将产生不同的 MCMC 算法。

Metropolis-Hastings (简称 MH) 算法是 MCMC 的重要代表。它基于"拒绝采样" (rejeet sampling) 来逼近平稳分布 p。

吉布斯采样(Gibbs sampling)有时被视为MH 算法的特例，它也使用马尔可夫链获取样本，而该马尔可夫链的平稳分布也是采样的目标分布p(x). 具体来说，假定\(\mathbf{x}=\{x_{1},x_{2},\ldots,x_{N}\}\)，目标分布为p(x) ，在初始化x 的取值后，通过循环执行以下步骤来完成采样:

随机或以某个次序选取某变量\(x_i\);
根据x中除\(x_i\)外的变量的现有取值，计算条件概率\(p(x_{i}\mid\mathbf{x}_{\bar{i}})\)，其中\(\mathbf{x}_{\bar{i}}=\{x_{1},x_{2},\ldots,x_{i-1},x_{i+1},\ldots,x_{N}\}\);
根据\(p(x_{i}\mid\mathbf{x}_{\bar{i}})\)对变量\(x_i\)采样，用来样值代替原值

14.5.2 变分推断

变分推断通过使用己知简单分布来逼近需推断的复杂分布，并通过限制近似分布的类型，从而得到一种局部最优、但具有确定解的近似后验分布。

概率图模型一种简洁的表示方法一一盘式记法

使用变分法时，最重要的是考虑如何对隐变量进行拆解，以此假设各变量子集服从何种分布，结合 EM 算法可进行概率图模型的推断和参数估计。显然，若隐变量的拆解或变量子集的分布假设不当，将会导致变分法效率低、效果差。

14.6 话题模型

话题模型主要用于处理文本类数据，其中隐狄利克雷分配模型（Latent Dirichlet Allocation，简称LDA）是话题模型的杰出代表。在话题模型中，有以下几个基本概念：词（word）、文档（document）、话题（topic）。

词：最基本的离散单元；
文档：由一组词组成，词在文档中不计顺序；
话题：由一组特定的词组成，这组词具有较强的相关关系。

在现实任务中，一般我们可以得出一个文档的词频分布，但不知道该文档对应着哪些话题，LDA话题模型正是为了解决这个问题。具体来说：LDA认为每篇文档包含多个话题，且其中每一个词都对应着一个话题。因此可以假设文档是通过如下方式生成：

(1) 根据参数为α 的狄利克雷分布随机采样一个话题分布\(\Theta_{t};\);

(2) 按如下步骤生成文档中的N个词:

(a) 根据\(\Theta_{t};\)进行话题指派，得到文档t 中词n的话题\(z_t,n\)

(b) 根据指派的话题所对应的词频分布\(\beta_{k}\)随机采样生成词