机器学习笔记(十四)概率图模型

14.概率图模型14.1隐马尔可夫模型1、概率模型机器学习是根据一些已观察到的证据（如训练样本）来对感兴趣的未知变量（如类别标记）进行估计和预测。概率模型（probabilistic model）提供了一种描述框架，将学习任务归结于计算变量的概率分布在概率模型中，利用已知变量推测未知变量的分布称为推断（inference），其核心是如何基于可观测变量推断出未知变量的条件分布。假定未

fjssharpsword

11022人浏览 · 2017-05-17 11:44:53

fjssharpsword · 2017-05-17 11:44:53 发布

14.概率图模型

14.1隐马尔可夫模型

1、概率模型

机器学习是根据一些已观察到的证据（如训练样本）来对感兴趣的未知变量（如类别标记）进行估计和预测。概率模型（probabilistic model）提供了一种描述框架，将学习任务归结于计算变量的概率分布

在概率模型中，利用已知变量推测未知变量的分布称为推断（inference），其核心是如何基于可观测变量推断出未知变量的条件分布。假定未知变量集合是Y，可观察变量集合是O，其他变量集合是R，生成式（generative）模型考虑联合分布P(Y,R,O)；判别式（discriminative）模型考虑条件分布P(Y,R|O)；给定一组观测变脸值，推断就是由P(Y,R,O)或P(Y,R|O)得到条件概率分布P(Y|O)。

直接利用概率求和规则消去变量R不可行，因为即便每个变量只有简单的两种取值，复杂度已去到至少O(2^|Y|+|R|)；并且属性变量之间还可能存在复杂的联系；因此概率模型的学习，即基于训练样本来估计变量分布的参数是困难的。为此需要能表达变量间关系的工具，用于推断和学习算法，概率图模型即是。

2、概率图模型

概率图模型（probabilisticgraphical model）是一类用图来表达变量相关关系的概率模型。概率图模型，以图为表示工具，如一个结点表示一个或一组随机变量，结点之间的边表示变量间的概率相关关系，即变量关系图。

根据边的性质不同，概率图模型大致可分为两类：

1）使用有向无环图表示变量间的依赖关系，称为有向图模型或贝叶斯网（Bayesian network）；

2）使用无向图表示变量间的相关关系，称为无向图模型或马尔可夫网（Markov network）；

隐马尔可夫模型属于第一种有向网类型。

3、隐马尔可夫模型

隐马尔可夫模型（Hidden Markov Model，HMM）是结构最简单的动态贝叶斯网（dynamic Bayesian network），是著名的有向图模型，主要用于时序数据建模，在语音识别、自然语言处理等领域有广泛应用。

1）HMM结构信息

HMM的变量可分为两组：第一组是状态变量{y₁,y₂,…,y_n}，其中y_i∈Y表示第i时刻的系统状态，通常假定状态变量是隐藏的、不可观测的，因此状态变量也叫隐变量（hidden variable）；第二组是观测变量{x₁,x₂,…,x_n}，其中x_i∈X表示第i时刻的观测值。

在HMM中，系统通常在多个状态{ s₁,s₂,…,s_N }之间转换，因此状态变量y_i的取值范围Y（状态空间）通常是有N个可能取值的离散空间。观测变量x_i可以是离散型也可以使连续型，这里仅考虑离散型观测变量，并假定其取值范围X为{ o₁,o₂,…,o_M}。

HMM图结构如下：

图中箭头表示了变量间的依赖关系。在任一时刻，观测变量的取值仅依赖于状态变量，即x _t由y _t确定；与其他状态变量及观测变量的取值无关。t时刻的状态y _t仅依赖于t-1时刻的状态y _t-1，与其余n-2个状态无关。此为马尔科夫链（Markov chain），即：系统下一时刻的状态仅由当前状态决定，不依赖于以往的任何状态。基于这种依赖关系，所有变量的联合概率分布为：

14.2马尔可夫随机场

马尔可夫随机场（Markov Random Field，MRF）是典型的马尔可夫网，是一种著名的无向图模型。图中每个结点表示一个或一组变量，结点之间的边表示两个变量之间的依赖关系。马尔可夫随机场有一组势函数（potential function），也称因子（factor），这是定义在变量子集上的非负实函数，主要用于定义概率分布函数。

1）MRF定义

马尔可夫随机场是一个无向图模型，图中结点的一个子集，若其中任意两结点间都有边连接，则称该结点子集为一个团（clique）。若在一个团中加入另外任何一个结点都不再形成团，则称该团为极大团（maximalcliuqe），极大团不能被其他团所包含。每个结点至少出现在一个极大团中。如下图：

{x2,x5,x6}构成极大团，{x1,x2,x3}不构成团。

在MRF中，多个变量之间的联合概率分布能基于团分解为多个因子的乘积，每个因子仅与一个团相关；就是将原来按结点（变量）的分布分解为按团（变量集合）的分布。具体来说，对于n个变量X={x ₁,x ₂,…,x _n}，所有团构成的集合为C，与团Q∈C对应的变量集合记为X _Q，则联合概率P(x)定义为：

2）全局马尔可夫性

概率模型最重要前提就是条件独立，在MRF中如何得到条件独立性呢？如下图，借助分离概念，若从结点集A中的结点到B中的结点都必须经过结点集C中的结点，则称结点集A和B被结点集C分离，C称为分离集（separating set）。

14.3条件随机场

条件随机场（ConditionalRandom Field，CRF）是一种判别式无向图模型。生成式概率模型是直接对联合分布进行建模；而判别式概率模型则是对条件分布进行建模。HMM和MRF都是生成式模型，CRF则是判别式模型。

条件随机场试图对多个变量在给定观测值后的条件概率进行建模。令x={x₁,x₂,…,x_n}为观测序列，y={y₁,y₂,…,y_n}为与之相应的标记序列，则条件随机场的目标是构建条件概率模型P(y|x)。标记变量y可以是结构型变量，即其分量之间具有某种相关性。如在自然语言处理的词性标注任务中，观测数据为语句（即单词序列），标记为相应的词性序列，具有线性序列结构；在语法分析任务中，输出标记则是语法树，具有树形结构。

令G=(V,E)表示结点与标记变量y中元素一一对应的无向图，y _v表示与结点v对应的标记变量，n(v)表示结点v的邻接结点，若图G的每个变量y _v都满足马尔可夫性，即：P(y _v|x, y _V\{v})= P(y _v|x, y _n(v))，则(y,x)构成一个条件随机场。

理论上，图G可具有任意结构，只要能表示标记变量之间的条件独立性关系即可。在现实应用中，对标记序列建模时，最常用的就是链式结构，即链式（chain-structured）条件随机场，如下图。

14.4学习与推断

基于概率图模型定义的联合概率分布，可对目标变量的边际分布（marginal distribution）或以某些可观测变量为条件的条件分布进行推断。边际分布是指对无关变量求和或积分后得到结果。如在马尔可夫网中，变量的联合分布被表示成极大团的势函数乘积，给定参数Θ求解某个变量x的分布，就变成对联合分布中其他无关变量进行积分的过程，称为边际化（marginalization）。

对概率图模型，还要确定具体分布的参数，称为参数估计或参数学习问题，通常使用极大似然估计或最大后验概率估计求解。若将参数视为待推测的变量，则参数估计过程和推断类似，也可以和变量推断问题一致求解。

具体来说，假设图模型所对应的变量集x={x ₁,x ₂,…,x _N}能分为x _E和x _F两个不相交的变量集，推断问题的目标就是计算边际概率P(x _F)或条件概率P(x _F|x _E)。条件概率：

概率图模型的推断方法大致可分为两类。第一个是精确推断方法，希望能计算出目标变量的边际分布，或条件分布的精确值；一般情形下，精确算法的计算复杂度随着极大团规模的增长呈指数增长，适用范围有限；第二个是近似推断方法，希望在较低的时间复杂度下获得原问题的近似解，此类方法在现实任务中更常用。下面两个方法是具有代表性的精确推断方。

1）变量消去

精确推断是一类动态规划算法，利用图模型所描述的条件独立性来削减目标概率值所需的计算量。变量消去法是最直观的精确推断算法，也是构建其他精确推断算法的基础。