机器学习–概率图模型

7月 20

一、隐马尔可夫模型

隐马尔可夫模型是结构最简单的动态贝叶斯网，这是一种著名的有向图模型，主要用于时序数据建模，在语音识别、自然语言处理等领域有广泛应用。
首先我们来看看什么样的问题解决可以用HMM模型。使用HMM模型时我们的问题一般有这两个特征：１）我们的问题是基于序列的，比如时间序列，或者状态序列。２）我们的问题中有两类数据，一类序列数据是可以观测到的，即观测序列；而另一类数据是不能观察到的，即隐藏状态序列，简称状态序列。
有了这两个特征，那么这个问题一般可以用HMM模型来尝试解决。这样的问题在实际生活中是很多的。比如：我现在在打字写博客，我在键盘上敲出来的一系列字符就是观测序列，而我实际想写的一段话就是隐藏序列，输入法的任务就是从敲入的一系列字符尽可能的猜测我要写的一段话，并把最可能的词语放在最前面让我选择，这就可以看做一个HMM模型了。再举一个，我在和你说话，我发出的一串连续的声音就是观测序列，而我实际要表达的一段话就是状态序列，你大脑的任务，就是从这一串连续的声音中判断出我最可能要表达的话的内容。
从这些例子中，我们可以发现，HMM模型可以无处不在。但是上面的描述还不精确，下面我们用精确的数学符号来表述我们的HMM模型。

1.1HMM模型的定义

对于HMM模型，首先我们假设 $Q$ 是所有可能的隐藏状态的集合， $V$ 是所有可能的观测状态的集合，即：

Q = {q 1, q 2, . . ., q N}, V = {v 1, v 2, . . . v M}

其中， $N$ 是可能的隐藏状态数， $M$ 是所有的可能的观察状态数。
对于一个长度为 $T$ 的序列， $I$ 对应的状态序列, $O$ 是对应的观察序列，即：

I = {i 1, i 2, . . ., i T}, O = {o 1, o 2, . . . o T}

其中，任意一个隐藏状态 $i_{t} \in Q$ ,任意一个观察状态 $o_{t} \in V$
HMM模型做了两个很重要的假设如下：
1）齐次马尔科夫链假设。即任意时刻的隐藏状态只依赖于它前一个隐藏状态。当然这样假设有点极端，因为很多时候我们的某一个隐藏状态不仅仅只依赖于前一个隐藏状态，可能是前两个或者是前三个。但是这样假设的好处就是模型简单，便于求解。如果在时刻 $t$ 的隐藏状态是 $i_{t} = q_{i}$ ,在时刻 $t + 1$ 的隐藏状态是 $i_{t + 1} = q_{j}$ , 则从时刻t到时刻t+1的HMM状态转移概率 $a_{i j}$ 可以表示为：

a i j = P (i t + 1 = q j | i t = q i)

这样 $a_{i j}$ 可以组成马尔科夫链的状态转移矩阵 $A$ :

A = [a i j] N \times N

2）观测独立性假设。即任意时刻的观察状态只仅仅依赖于当前时刻的隐藏状态，这也是一个为了简化模型的假设。如果在时刻t的隐藏状态是 $i_{t} = q_{j}$ , 而对应的观察状态为 $o_{t} = v_{k}$ , 则该时刻观察状态 $v_{k}$ 在隐藏状态 $q_{j}$ 下生成的概率为 $b_{j} (k)$ ,满足：

b j (k) = P (o t = v k | i t = q j)

这样 $b_{j} (k)$ ,可以组成观测状态生成的概率矩阵B:

B = [b j (k)] N \times M

除此之外，我们需要一组在时刻t=1的隐藏状态概率分布 $Π$ ,也称初始概率分布:

Π = [π (i)] N 其 中 π (i) = P (i 1 = q i)

一个HMM模型，可以由隐藏状态初始概率分布 $Π$ , 状态转移概率矩阵A和观测状态概率矩阵B决定。 $Π, A$ 决定状态序列， $B$ 决定观测序列。因此，HMM模型可以由一个三元组 $λ$ 表示如下：

λ = (A, B, Π)

1.2HMM模型的三个基本问题

HMM模型一共有三个经典的问题需要解决：
(1)评估观察序列概率。即给定模型 $λ = (A, B, Π)$ 和观测序列 $O = {o 1, o 2, . . . o T}$ ，计算在模型λ下观测序列O出现的概率 $P (O | λ)$ 。这个问题的求解需要用到前向后向算法。
(2)模型参数学习问题。即给定观测序列 $O = {o 1, o 2, . . . o T}$ ，估计模型 $λ = (A, B, Π)$ 的参数，使该模型下观测序列的条件概率P(O|λ)最大。这个问题的求解需要用到基于EM算法的鲍姆-韦尔奇算法。
(3)预测问题，也称为解码问题。即给定模型 $λ = (A, B, Π)$ 和观测序列 $O = {o 1, o 2, . . . o T}$ ，求给定观测序列条件下，最可能出现的对应的隐藏状态序列，这个问题的求解需要用到基于动态规划的维特比算法。

二、马尔科夫随机场

马尔科夫网是使用无向图描述的图模型，是刻画X上联合分布的一种方法，表示一个分解方式,也表示一组条件独立关系。马尔科夫随机场( Markov random field , MRF),也被称为马尔科夫网络( Markov network )或者无向图模型( undirected graphical model )( Kindermann and Snell, 1980 ),包含一组结点,每个结点都对应着一个变量或一组变量。链接是无向的,即不含有箭头。

与贝叶斯网一样，马尔可夫网可以视为定义了一系列由图结构确定的独立性假设。

2.1条件独立性质

定义一种概率分布的图语义表示,使得条件独立性由单一的图划分确定。

假设在一个无向图中,我们有三个结点集合,记作 A, B, C 。我们考虑条件独立性质
为了判定由图定义的概率分布是否满足这个性质,我们考虑连接集合 A 的结点和集合 B 的结点的所有可能路径。如果所有这些路径都通过了集合 C 中的一个或多个结点,那么所有这样的路径都被“阻隔”,因此条件独立性质成立。

条件独立性包含三种：成对、局部、全局马尔可夫性

成对马尔可夫性（最大团的由来）：

设u和v是无向图G中任意两个没有边连接的节点，节点u和v分别对应随机变量 $Y_{u}$ 和 $Y_{v}$ 。其他所有节点为O，对应的随机变量是 $Y_{o}$ 。成对马尔可夫性是指给定随机变量组 $Y_{o}$ 的条件下随机变量 $Y_{u}$ 和 $Y_{v}$ 是条件独立的，即:

P (Y u, Y v | Y o) = P (Y u | Y o) P (Y v | Y o)

局部马尔可夫性（马尔科夫毯）：

设 $v \in V$ 是无向图 $G$ 中任意一个节点， $W$ 是与 $v$ 有边连接的所有节点， $O$ 是 $v 、 W$ 以外的其他所有节点。v表示随机变量是 $Y_{v} ， W$ 表示的随机变量组是 $Y_{W}$ ，O表示的随机变量组是 $Y_{o}$ 。局部马尔可夫性是指在给定随机变量组 $Y_{W}$ 的条件下随机变量 $Y_{v}$ 与随机变量组 $Y_{o}$ 是独立的，即:

P (Y o, Y v | Y w) = P (Y v | Y w) P (Y o | Y w)

马尔科夫毯：对于一个无向图,结点 $x i$ 的马尔科夫毯由相邻结点的集合组成。它的性质为:以图中所有剩余变量为条件, $x i$ 的条件概率分布只依赖于马尔科夫毯中的变量。即结点只条件依赖于相邻结点,而条件独立于任何其他的结点。

全局马尔可夫性：

设节点集合A，B是在无向图G中被节点集合C分开的任意节点集合，如下图所示：

节点集合A，B和C所对应的随机变量组分别是 $Y_{A} ， Y_{B} ， Y_{C}$ 。全局马尔可夫性是指给定随机变量组YC条件下随机变量组 $Y_{A}$ 和 $Y_{B}$ 是条件独立的，即:

P (Y A, Y B | Y C) = P (Y A | Y C) P (Y B | Y C)

2.2无向图的分解

我们更关心如何求其联合概率分布。于是，为了求解给定的概率无向图模型，我们希望将整体的联合概率写成若干个子联合概率的乘积形式，也就是将概率进行因子分解，这样便于模型的学习与计算。而事实上，概率无向图模型的最大特点就是便于因子分解。

如果我们考虑两个结点 x i 和 x j ,它们不存在链接,那么给定图中的所有其他结点,这两个结点一定是条件独立的。

于是,联合概率分布的分解一定要让 x i 和 x j 不出现在同一个因子中,从而让属于这个图的所有可能的概率分布都满足条件独立性质。（lz: 成对马尔科夫性）

2.3团Clique和因子

团( clique )：对于图中结点的一个子集，若其中任意两结点间都有边连接，则称该结点子集为一个团。
最大团( maximal clique )：若在一个团中加入另外任何一个结点都不再形成团，则称该团为极大团。

图中有五个具有两个结点的团块,即 {x 1 , x 2 }, {x 2 , x 3 }, {x 3 , x 4 }, {x 4 , x 2 } 和 {x 1 , x 3 } ,还有两个最大团块 {x 1 , x 2 , x 3 } 和 {x 2 , x 3 , x 4 } 。集合 {x 1 , x 2 , x 3 , x 4 } 不是一个团块,因为在 x 1 和 x 4 没有链接。

因子：定义为团块中变量的函数。事实上,我们可以考虑最大团块的函数而不失一般性, 因为其他团块一定是最大团块的子集。因此, 如果 {x 1 , x 2 , x 3 } 是一个最大团块,并我们在这个团块上定义了任意一个函数,那么定义在这些变量的一个子集上的其他因子都是冗余的。

2.4Hammersley-Clifford定理

概率无向图模型的联合概率分布P(Y)可以表示为如下形式：

其中，C是无向图的最大团， $Y_{C}$ 是C的节点对应的随机变量，ΨC(YC)是C上定义的严格正函数，乘积是在无向图所有的最大团上进行的。
说明：

让我们将团块记作 C ,将团块中的变量的集合记作 $x_{C}$ 。这样,联合概率分布可以写成图的最大团块的势函数( potential function ) ψ C (x C ) 的乘积的形式。通过只考虑满足 $ψ_{C} (x_{C}) \geq 0$ 的势函数,我们确保了 p(x) ≥ 0 。

这里, Z 有时被称为划分函数( partition function ),是一个归一化常数,等于
这里写图片描述
由于我们的势函数被限制为严格大于零,因此将势函数表示为指数的形式更方便,即

三、条件随机场

设X与Y是随机变量，P(Y|X)是在给定X的条件下Y的条件概率分布。若随机变量Y构成一个由无向图G=(V,E)表示的马尔可夫随机场，即

对任意结点v成立，则称条件概率分布P(Y|X)为条件随机场。式中w~v表示在图G=(V,E)中与结点v有边连接的所有结点w，w≠v表示结点v以外的所有结点 $Y_{V} ， Y_{u}, Y_{w}$ 与为结点v，u与w对应的随机变量。

3.1线性链条件随机场

设 $X = (x_{1}, x_{2}, x_{3} \dots, x_{n}), Y = (y_{1}, y_{2}, y_{3} \dots, y_{n})$ 均为线性链表示的随机变量序列，若在给定随机变量序列X的条件下，随机变量序列Y的条件概率分布P(Y|X)构成条件随机场，即满足马尔可夫性:

则称P(Y|X)为线性链条件随机场

线性链条件随机场

X和Y有相同的图结构的线性链条件随机场

在标注问题中，X表示输入观测序列，Y表示对应的输出标记序列或状态序列。

3.2条件随机场的不同形式

3.2.1条件随机场的参数化形式

设P(Y|X)为线性链条件随机场，则在随机变量X取值为x的条件下，随机变量Y取值为y的条件概率具有如下形式：

其中，Z(x)是规范化因子:

参数解释：

（1） $t_{k}$ 是定义在边上的特征函数，称为转移特征，依赖于当前和前一个位置
（2） $s_{l}$ 是定义在及结点上的特征函数，称为状态特征，依赖于当前位置
（3） $λ_{k}$ , $μ_{i}$ 是 $t_{k}$ ， $s_{l}$ 对应的权值
（4）特征函数 $t_{k}$ ， $s_{l}$ 取值为1或0：当满足特征条件时取值为1，否则为0。
这里写图片描述

ps:是3.2不是3：2

机器学习, 概率图, 模型

一	二	三	四	五	六	日
« 12月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30

博客水木