HMM到CRF 理解与学习笔记

原创

大鹅

修改于 2021-05-13 00:03:29

4.1K0

修改于 2021-05-13 00:03:29

文章被收录于专栏：大鹅专栏：大数据到机器学习

背景

最近学习NLP总是会遇到HMM与CRF模型，一直都是一知半解，这篇博客用户整理一下两个模型的推导与学习笔记。

下图为概率图模型贝叶斯 LR HMM CRF之间的关系，理清楚模型之间的关系有助于我们理解。

下文也会对在介绍模型同时比各个模型之间的关系。

HMM 隐马尔可夫模型

解决什么问题？

使用HMM模型时我们的问题一般有这两个特征：

我们的问题是基于序列的，比如时间序列，或者状态序列。
我们的问题中有两类数据，一类序列数据是可以观测到的，即观测序列；而另一类数据是不能观察到的，即隐藏状态序列，简称状态序列。

基本概念

HMM是一个关于时序的概率模型，可以用于根据一些已知的来推断未知的东西；
马尔可夫链是一个随机过程模型，服从马尔可夫性质：无记忆性，某一时刻的状态只受前一个时刻的影响；
状态序列是由马尔可夫链随机生成的，是隐藏的，不可观测的；每个状态又有其对应的观测结果，这些观测结果根据时序排序后即为观测序列；也可以说观测序列长度跟时刻长度是一致的；

HMM基本假设：

假设隐藏的马尔可夫链在任意时刻的状态只依赖于前一个时刻（t−1时）的状态，与其他时刻的状态及观测无关，也与时刻t无关；
假设任意时刻的观测只依赖于该时刻的马尔可夫链状态，与其它观测及状态无关；

因此组成HMM有两个空间（状态空间Q和观测空间V），三组参数（状态转移矩阵A，观测概率矩阵以及状态初始概率分布π），有了这些参数，一个HMM就被确定了.

HMM三个基本问题：

评估观测序列的概率，在给定HMM模型λ=(A,B,π)和观测序列O下，计算模型λ下观测序列的出现概率P(O|λ)，用到的是前向-后向算法
预测（解码）问题，在给定HMM模型λ=(A,B,π)和观测序列O下，求解观测序列的条件概率最大的条件下，最可能出现的状态序列，用到的是维特比算法
模型参数学习问题，在给定观测序列O下，估计模型λ的参数，使得该模型下观测序列的条件概率P(O|λ)最大，用到的是EM算法的鲍姆-韦尔奇算法

具体解法可以参考统计学习方法

CRF 条件随机场

General CRF

条件随机场（Conditional random field，CRF）是条件概率分布模型 P(Y|X) ，表示的是给定一组输入随机变量 X 的条件下另一组输出随机变量 Y 的马尔可夫随机场，也就是说 CRF 的特点是假设输出随机变量构成马尔可夫随机场。条件随机场可被看作是最大熵马尔可夫模型在标注问题上的推广。

如果随机变量 Y 构成一个由无向图 G=(V, E) 表示的马尔可夫随机场，对任意节点 𝑣∈𝑉 都成立，即

P(Y_v|X,Y_w,w\not=v)=P(Y_v|X,Y_w,w\sim v)

对任意节点 𝑣 都成立，则称 P(Y|X) 是条件随机场。式中 𝑤≠𝑣 表示 w 是除 v 以外的所有节点，𝑤∼𝑣 表示 w 是与 v 相连接的所有节点。

不妨把等式两遍的相同的条件 X 都遮住，那么式子可以用下图示意：

从问题描述上看，对于序列标注问题，X 是需要标注的观测序列，Y 是标记序列（状态序列）。

在学习过程时，通过 MLE 或带正则的 MLE 来训练出模型参数；

在测试过程，对于给定的观测序列，模型需要求出条件概率最大的输出序列。

linear CRF

用于序列标注问题的线性链条件随机场（linear chain conditional CRF），是由输入序列来预测输出序列的判别式模型。

在定义中并没有要求 X 和 Y 具有相同的结构，而在现实中，一般假设 X 和 Y 有相同的图结构。对于线性链条件随机场来说，图 G 的每条边都存在于状态序列 Y 的相邻两个节点，最大团 C 是相邻两个节点的集合，X 和 Y 有相同的图结构意味着每个 𝑋𝑖 都与 𝑌𝑖 一一对应。

V=\{1,2,...,n\},\quad E=\{(i, i+1)\},\quad i=1,2,...,n-1

设两组随机变量 𝑋=(𝑋1,...,𝑋𝑛),𝑌=(𝑌1,...,𝑌𝑛) ，那么线性链条件随机场的定义为

P(Y_i|X,Y_1,...,Y_{i-1},Y_{i+1},...,Y_n)=P(Y_i|X,Y_{i-1},Y_{i+1}),\quad i=1,...,n

其中当 i 取 1 或 n 时只考虑单边。

线性链条件随机场的参数化形式：特征函数及例子

此前我们知道，马尔可夫随机场可以利用最大团的函数来做因子分解。给定一个线性链条件随机场 P(Y|X) ，当观测序列为 x=x1x2⋯ 时，状态序列为 𝑦=𝑦1𝑦2 的概率可写为（实际上应该写为 𝑃(𝑌=𝑦|𝑥;𝜃) ，参数被省略了）

P(Y=y|x)=\frac{1}{Z(x)}\exp\biggl(\sum_k\lambda_k\sum_it_k(y_{i-1},y_i,x,i)+\sum_l\mu_l\sum_is_l(y_i,x,i)\biggr)

Z(x)=\sum_y\exp\biggl(\sum_k\lambda_k\sum_it_k(y_{i-1},y_i,x,i)+\sum_l\mu_l\sum_is_l(y_i,x,i)\biggr)

𝑍(𝑥)作为规范化因子，是对 y 的所有可能取值求和。

序列标注 vs 分类问题对比

是不是和Softmax回归挺像的？它们都属于对数线性模型（log linear model）

线性链CRF用来解决序列标注问题；
Softmax回归、最大熵模型都是用来解决分类问题；

但需要注意，这两类问题存在非常大的区别：

（1）如果把序列标注问题看作分类问题，也就是为每一个待标注的位置都当作一个样本然后进行分类，那么将会有很大的信息损失，因为一个序列的不同位置之间存在联系：比如说有一系列连续拍摄的照片，现在想在照片上打上表示照片里的活动内容的标记，当然可以将每张照片单独做分类，但是会损失信息，例如当有一张照片上是一张嘴，应该分类到“吃饭”还是分类到“唱K”呢？如果这张照片的上一张照片内容是吃饭或者做饭，那么这张照片表示“吃饭”的可能性就大一些，如果上一张照片的内容是跳舞，那这张照片就更有可能在讲唱K的事情。

（2）不同的序列有不同的长度，不便于表示成同一维度的向量。

（3）状态序列的解集随着序列长度指数级增长，穷举法是不可行的。

特征函数

对于线性链CRF，特征函数是个非常重要的概念：

转移特征 𝑡𝑘(𝑦𝑖−1,𝑦𝑖,𝑥,𝑖) 是定义在边上的特征函数（transition），依赖于当前位置 i 和前一位置 i-1 ；对应的权值为 𝜆𝑘 。

状态特征 𝑠𝑙(𝑦𝑖,𝑥,𝑖)是定义在节点上的特征函数（state），依赖于当前位置 i ；对应的权值为 𝜇𝑙 。

一般来说，特征函数的取值为 1 或 0 ，当满足规定好的特征条件时取值为 1 ，否则为 0 。

linear-CRF vs HMM

linear-CRF模型和HMM模型有很多相似之处，尤其是其三个典型问题非常类似，除了模型参数学习的问题求解方法不同以外，概率估计问题和解码问题使用的算法思想基本也是相同的。同时，两者都可以用于序列模型，因此都广泛用于自然语言处理的各个方面。

现在来看看两者的不同点。

最大的不同点是

linear-CRF模型是判别模型，而HMM是生成模型，即linear-CRF模型要优化求解的是条件概率P(y|x),则HMM要求解的是联合分布P(x,y);
linear-CRF是利用最大熵模型的思路去建立条件概率模型，对于观测序列并没有做马尔科夫假设。而HMM是在对观测序列做了马尔科夫假设的前提下建立联合分布的模型。

只有linear-CRF模型和HMM模型才是可以比较讨论的。但是linear-CRF是CRF的一个特例，CRF本身是一个可以适用于很复杂条件概率的模型，因此理论上CRF的使用范围要比HMM广泛的多。

http://blog.echen.me/2012/01/03/introduction-to-conditional-random-fields/ 比较了 HMM 和 CRF在序列标注的异同，作者认为CRF更加强大，理由如下：

- 可以为每个 HMM 都建立一个等价的 CRF

- CRF 的特征可以囊括更加广泛的信息：HMM 基于“上一状态to当前状态”的转移概率以及“当前状态to当前观测”的释放概率，使得当前位置的词（观测）只可以利用当前的状态（词性）、当前位置的状态又只能利用上一位置的状态。但 CRF 的特征函数中，输入包含 (𝑦𝑖−1,𝑦𝑖,𝑥,𝑖)，对于当前位置 i 来说可以利用完整的 x 信息。

- CRF 的参数的取值没有限制，而 HMM 的参数（转移概率矩阵、释放概率矩阵、初始概率向量）都需要满足一些限制。

线性链条件随机场的简化形式

需要注意的是，以 \sum_k\lambda_k\sum_it_k(y_{i-1},y_i,x,i)这项为例，可以看出外面那个求和号是套着里面的求和号的，这种双重求和就表明了对于同一个特征（k），在各个位置（i）上都有定义。

基于此，很直觉的想法就是把同一个特征在各个位置 i 求和，形成一个全局的特征函数，也就是说让里面那一层求和号消失。在此之前，为了把加号的两项合并成一项，首先将各个特征函数 t（设其共有 𝐾1个）、s（设共 𝐾2 个）都换成统一的记号 f ：

t_1=f_1,t_2=f_2,\cdots,t_{K_1}=f_{K_1},\quad s_1=f_{K_1+1},s_2=f_{K_1+2},\cdots,s_{K_2}=f_{K_1+K_2}

相应的权重同理：

\lambda_1=w_1,\lambda_2=w_2,\cdots,\lambda_{K_1}=w_{K_1},\quad \mu_1=w_{K_1+1},\mu_2=w_{K_1+2},\cdots,\mu_{K_2}=w_{K_1+K_2}

那么就可以记为

f_k(y_{i-1},y_i,x,i)=\begin{cases}t_k(y_{i-1},y_i,x,i), & k=1,2,...,K_1 \\s_l(y_i,x,i), & k=K_1+l;l=1,2,...,K_2\end{cases}

w_k=\begin{cases}\lambda_k, & k=1,2,...,K_1 \\\mu_l, & k=K_1+l;l=1,2,...,K_2\end{cases}

其中𝐾=𝐾1+𝐾2。进而可以得到简化表示形式

P(Y=y|x)=\frac{1}{Z(x)}\exp\sum_{k=1}^Kw_kf_k(y,x)

Z(x)=\sum_y\exp\sum_{k=1}^Kw_kf_k(y,x)

如果进一步记 \textbf w=(w_1,w_2,...,w_K)^{\top}F(y,x)=(f_1(y,x),...,f_K(y,x))^{\top}，那么可得内积形式：

P_{\textbf w}(Y=y|x)=\frac{1}{Z_{\textbf w}(x)}\exp(\textbf w^{\top}F(y,x))

Z_{\textbf w}(x)=\sum_y\exp(\textbf w^{\top}F(y,x))

线性链条件随机场的矩阵形式

种形式依托于线性链条件随机场对应的图模型仅在两个相邻节点之间存在边。在状态序列的两侧添加两个新的状态 y_0=start, y_{n+1}=stop。

这里，引入一个新的量 M_i(y_{i-1},y_i|x)

M_i(y_{i-1},y_i|x)=\exp\sum_{k=1}^Kw_kf_k(y_{i-1},y_i,x,i),\quad i=1,2,...,n+1

首先，这个量融合了参数和特征，是一个描述模型的比较简洁的量；

其次，不难发现，这个量相比于原来的非规范化概率P(Y=y|x)\propto\exp\displaystyle\sum_{k=1}^Kw_kf_k(y,x)，少了对位置的内层求和，换句话说这个量是针对于某个位置 i （及其前一个位置 i-1 ）的。

那么，假设状态序列的状态存在 m 个可能的取值，对于任一位置 i = 1,2,...,n+1 ，定义一个 m 阶方阵：

\begin{aligned}M_i(x)&=[\exp\sum_{k=1}^Kf_k(y_{i-1},y_i,x,i)]_{m\times m}\\&=[M_i(y_{i-1},y_i|x)]_{m\times m}\end{aligned}

因为有等式\displaystyle\prod_i\biggl[\exp\sum_{k=1}^Kw_kf_k(y_{i-1},y_i,x,i)\biggr]=\exp\biggl(\sum_{k=1}^Kw_k\sum_i f_k(y_{i-1},y_i,x,i)\biggr) 成立，所以线性链条件随机场可以表述为如下的矩阵形式：

P_{\textbf w}(Y=y|x)=\frac{1}{Z_{\textbf w}(x)}\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)

Z_{\textbf w}(x)=(M_1(x)M_2(x)\cdots M_{n+1}(x))_{(start,stop)}

其中规范化因子𝑍𝐰(𝑥)是这 n+1 个矩阵的乘积矩阵的索引为(𝑠𝑡𝑎𝑟𝑡,𝑠𝑡𝑜𝑝)的元素。 𝑍𝐰(𝑥) 它就等于以 start 为起点、以 stop 为终点的所有状态路径的非规范化概率\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x) 之和。