隐马尔可夫模型与命名实体识别

搬运自：https://www.bilibili.com/video/BV1MJ411w7xR

我们今天要解决的问题是自然语言处理中的序列标注问题, 在目前, 比较主流的技术是语言模型(如LSTM, BERT)+CRF(条件随机场), 为什么这样组合模型呢? 我稍后会讲到. 但想要了解CRF(条件随机场), 我想首先让大家了解一下隐马尔可夫模型(Hidden Markov Model), 是一种概率图模型, 只要理解了HMM模型和维特比解码算法(viterbi algorothm), 理解条件随机场就成了分分钟的事.
在这节课中, 你不需要有概率图模型的基础, 只要有基本的概率论知识即可.
首先, 先来看一下今天的课程安排:

NER(命名实体识别)问题概述;
什么是隐马尔可夫模型(HMM);
HMM模型的参数;
用HMM解决序列标注问题, HMM的学习算法;
维特比算法(Viterbi Algorithm)(HMM的预测算法).

0. named entity recognition(命名实体识别)问题概述:

命名实体识别（英语：Named Entity Recognition，简称NER）, 是指识别文本中具有特定意义的实体，主要包括人名、地名、机构名、专有名词等等, 并把我们需要识别的词在文本序列中标注出来。
例如有一段文本: 济南市成立自由贸易试验区.
我们要在上面文本中识别一些区域和地点, 那么我们需要识别出来内容有:
济南市(地点), 自由贸易试验区(地点).
在我们今天使用的NER数据集中, 一共有7个标签:

“B-ORG”: 组织或公司(organization)
“I-ORG”: 组织或公司
“B-PER”: 人名(person)
“I-PER”: 人名
“O”: 其他非实体(other)
“B-LOC”: 地名(location)
“I-LOC”: 地名

文本中以每个字为单位, 每个字必须分别对应上面的任一标签.
但为什么上面标签除了"O"(其他)之外都是一个实体类型对应两个标签呢?
请小伙伴们仔细看标签前面有分为"B"和"I"的不同, "B"表示begin, 实体开头的那个字使用"B"对应的标签来标注, 在实体中间或结尾的部分, 用"I"来标注.
比如说"自贸区"对应的标注是: 自(B-LOC)贸(I-LOC)区(I-LOC), 这三个字都对应一个"地名"的标签, 但是第一个字属于实体开头的字, 所以使用"B"开头的标签, 后面两个字的标签都是"I"开头.
注意, "B"后面是不可以跟其他类型的"I"的, 例如: 自(B-PER)贸(I-LOC)区(I-LOC) 就是属于错误的标注, 因为实体开头"B"标注成了人名, 即使实体中间标注成了地名, 这个实体的标注方法也是非法的.
上面的原因就是我们要从语言模型(例如BERT, LSTM)后面再加上概率图模型, 例如条件随机场, 用来约束模型的输出, 防止出现不合规的标注输出.

1. 什么是隐马尔可夫模型 $a.k.a.HMM?$

HMM模型是概率图模型的一种, 属于生成模型, 笼统的说, 我们上面说的"BIO"的实体标签, 就是一个不可观测的隐状态, 而HMM模型描述的就是由这些隐状态序列(实体标记)生成可观测状态(可读文本)的过程.
在我们今天的问题当中, 隐状态序列是实体标记序列, 而可观测序列是我们可读的原始语料文本序列.
例如:
隐藏状态序列: $B-LOC | I-LOC | I-LOC$
观测状态序列: $自 \quad \quad \quad \quad 贸 \quad \quad \quad \quad 区$
设我们的可观测状态序列是由所有汉字组成的集合, 我们用 $V_{Obsevation}$ 来表示:
$V_{obs.}=\{v_1, v_2, ... , v_M \}$
上式中, $v$ 表示字典中单个字, 假设我们已知的字数为 $M$ .
设所有可能的隐藏状态集合为 $Q_{hidden}$ , 一共有 $N$ 种隐藏状态, 例如我们现在的命名实体识别数据里面只有7种标签:
$Q_{hidden} = \{ q_1, q_2, ... , q_N\}$
设我们有观测到的一串自然语言序列文本 $O$ , 一共有 $T$ 个字, 又有这段观测到的文本所对应的实体标记, 也就是隐状态 $I$ :
$I=\{i_1, i_2, ... , i_T \}(隐状态) \quad O=\{o_1, o_2, ... , o_T \}(观测)$
注意上式中, 我们常称 $t$ 为时刻, 如上式中一共有 $T$ 个时刻( $T$ 个汉字).
隐马尔可夫模型与命名实体识别
HMM模型有两个基本假设(非常重要):

第 $t$ 个隐状态(实体标签)只跟前一时刻的 $t-1$ 隐状态(实体标签)有关, 与除此之外的其他隐状态(如 $t-2,\ t+3$ )无关.
例如上图中: 蓝色的部分指的是 $i_t$ 只与 $i_{t-1}$ 有关, 而与蓝色区域之外的所有内容都无关, 而 $P(i_{t}|i_{t-1})$ 指的是隐状态 $i$ 从 $t-1$ 时刻转向 $t$ 时刻的概率, 具体转换方式下面会细讲.
观测独立的假设, 我们上面说过, HMM模型中是由隐状态序列(实体标记)生成可观测状态(可读文本)的过程,
观测独立假设是指在任意时刻观测 $o_t$ 只依赖于当前时刻的隐状态 $i_t$ , 与其他时刻的隐状态无关.
例如上图中: 粉红色的部分指的是 $i_{t+1}$ 只与 $o_{t+1}$ 有关, 跟粉红色区域之外的所有内容都无关.

2. HMM模型的参数:

HMM的转移概率(transition probabilities):
我们上面提到了 $P(i_{t}|i_{t-1})$ 指的是隐状态 $i$ 从 $t-1$ 时刻转向 $t$ 时刻的概率, 比如说我们现在实体标签一共有 $7$ 种, 也就是 $N=7$ (注意 $N$ 是所有可能的实体标签种类的集合), 也就是 $Q_{hidden} = \{ q_0, q_1, ... , q_6\}$ (注意我们实体标签编号从 $0$ 算起), 假设在 $t-1$ 时刻任何一种实体标签都可以在 $t$ 时刻转换为任何一种其他类型的实体标签, 则总共可能的转换的路径一共有 $N^2$ 种, 所以我们可以做一个 $N*N$ 的矩阵来表示所有可能的隐状态转移概率.

上图就是转移概率矩阵, 也就是 $transition \ matrix$ , 我们设这个矩阵为 $A$ 矩阵, 则 $A_{ij}$ 表示矩阵中第i行第j列:
$A_{ij}=P(i_{t+1}= q_j | i_{t} = q_i) \quad q_i \in Q_{hidden}$
上式表示指的是在 $t$ 时刻实体标签为 $q_i$ , 而在 $t+1$ 时刻实体标签转换到 $q_j$ 的概率.

HMM的发射概率(emission probabilities):
我们之前提到了任意时刻观测 $o_t$ 只依赖于当前时刻的隐状态 $i_t$ , 也就是 $P(o_t | i_t)$ , 也叫做发射概率, 指的是隐状态生成观测结果的过程.
设我们的字典里有 $M$ 个字, $V_{obs.}=\{v_0, v_1, ... , v_{M-1} \}$ (注意这里下标从0算起, 所以最后的下标是 $M-1$ , 一共有 $M$ 种观测), 则每种实体标签(隐状态)可以生成 $M$ 种不同的汉字(也就是观测), 这一过程可以用一个发射概率矩阵来表示, 他的维度是 $N*M$ .

上图就是发射概率矩阵, 也就是 $emission \ matrix$ , 我们设这个矩阵为 $B$ 矩阵, 则 $B_{jk}$ 表示矩阵中第 $j$ 行第 $k$ 列:
$B_{jk}=P(o_{t}= v_k | i_{t} = q_j) \quad q_i \in Q_{hidden} \quad v_k \in V_{obs.}=\{v_0, v_1, ... , v_{M-1} \}$
上式表示指的是在 $t$ 时刻由实体标签(隐状态) $q_j$ 生成汉字(观测结果) $v_k$ 的概率.
3. HMM的初始隐状态概率: 又称为 $initial \ probabilities$ , 我们通常用 $\pi$ 来表示, 注意这里可不是圆周率:
$\pi=P(i_1=q_i) \quad q_i \in Q_{hidden} = \{ q_0, q_1, ... , q_{N-1}\}$
上式指的是自然语言序列中第一个字 $o_1$ 的实体标记是 $q_i$ 的概率, 也就是初始隐状态概率.

3. 用HMM解决序列标注问题, HMM的学习算法;

我们现在已经了解了HMM的三大参数 $A, \ B, \ \pi$ , 假设我们已经通过建模学习, 学到了这些参数, 得到了模型的概率, 我们怎么使用这些参数来解决序列标注问题呢?
设目前在时刻 $t$ , 我们有当前时刻的观测到的一个汉字 $o_t=v_k$ (指的第 $t$ 时刻观测到 $v_k$ ), 假设我们还知道在 $t-1$ 时刻(前一时刻)对应的实体标记类型 $i_{t-1} = \hat{q}^{t-1}_i$ (指的 $t-1$ 时刻标记为 $\hat{q}^{t-1}_i$ ). 我们要做的仅仅是列举所有 $i_{t}$ 可能的实体标记 $\hat{q}^{t}_{j}$ , 并求可以使下式输出值最大的那个实体类型 $q^{t}_{j}$ (也就是隐状态类型):
$\hat{q}_j^{t} = argmax_{\hat{q}_j^{t} \in Q_{hidden}} P(i_t = \hat{q}_j^{t} | i_{t-1} = \hat{q}^{t-1}_i) P(o_t=v_k| i_t = \hat{q}_j^{t})$
将所有 $t$ 时刻当前可取的实体标签带入下式中, 找出一个可以使下式取值最大的那个实体标签作为当前字的标注:
$P(当前可取实体标签|上一时刻实体标签)P(测到的汉字|当前可取实体标签)$
注意: 我们这里只讲到了怎样求第 $t$ 时刻的最优标注, 但是在每一时刻进行这样的计算, 并不一定能保证最后能得出全局最优序列路径, 例如在第 $t$ 时刻最优实体标签是 $q_j$ , 但到了下一步, 由于从 $q_j$ 转移到其他某些实体标签的转移概率比较低, 而降低了经过 $q_j$ 的路径的整体概率, 所以到了下一时刻最优路径就有可能在第 $t$ 时刻不经过 $q_j$ 了, 所以每一步的局部最优并不一定可以达成全局最优, 所以我们之后会用到维特比算法来找到全局最优的标注序列, 这个后面会有详细讲解.
生成模型与判别模型:
对于生成模型与判别模型, 因为篇幅问题, 暂不做讲述, 网上有很多资料.
这里稍稍回顾一下, 我们假设 $x$ 为数据点, $y$ 为数据标记, 比如说逻辑回归属于典型的判别模型, 我们要计算 $P(y|x)$ 并形成一条分类边界, 而在HMM中, 我们计算的是 $P(x|y)$ , 而且要计算出所有 $y$ 可取的类型, 并比较一下所有 $P(x|y=y_{i})$ 的结果, 并取可以使 $P(x|y)$ 最大的那个, 而得到预测结果.
HMM参数学习(监督学习):
我们今天要用HMM解决的是序列标注问题, 所以我们解决的是监督学习的问题. 也就是说我们现在有一些文本和与之对应的标注数据, 我们要训练一个HMM来拟合这些数据, 以便之后用这个模型进行数据标注任务, 最简单的方式是直接用极大似然估计来估计参数:

初始隐状态概率 $\pi$ 的参数估计:
$\hat{\pi}_{q_i}=\frac{count(q^{1}_{i})}{count(o_1)}$
上式指的是, 计算在第 $1$ 时刻, 也就是文本中第一个字, $q^{1}_{i}$ 出现的次数占总第一个字 $o_1$ 观测次数的比例, $q^{1}_{i}$ 上标1指的是第1时刻, 下标 $i$ 指的是第 $i$ 种标签(隐状态), $count$ 是的是记录次数.
转移概率矩阵 $A$ 的参数估计:
我们之前提到过 $transition \ matrix$ 里面 $A_{ij}$ (矩阵的第i行第j列)指的是在 $t$ 时刻实体标签为 $q_i$ , 而在 $t+1$ 时刻实体标签转换到 $q_j$ 的概率, 则转移概率矩阵的参数估计相当与一个二元模型 $bigram$ , 也就是把所有的标注序列中每相邻的两个实体标签分成一组, 统计他们出现的概率:
$\hat{A}_{ij}=P(i_{t+1}= q_j | i_{t} = q_i)=\frac{count(q_i后面出现q_j的次数)}{count(q_i的次数)}$
发射概率矩阵 $B$ 的参数估计:
我们提到过 $emission \ matrix$ 中的 $B_{jk}$ (矩阵第j行第k列)指的是在 $t$ 时刻由实体标签(隐状态) $q_j$ 生成汉字(观测结果) $v_k$ 的概率.
$\hat{B}_{jk}=P(o_{t}= v_k | i_{t} = q_j)=\frac{count(q_j与v_k同时出现的次数)}{count(q_j出现的次数)}$
到此为止, 我们就可以遍历所有语料, 根据上面的方式得到模型的参数 $A, \ B, \ \pi$ 的估计.
注意, 通过上面的计算过程, 我们可以得出HMM的参数 $(A, B, \pi)$ 有以下特性:
$\sum_{i}\pi_{q_i} = 1$
$\sum_{j}A_{ij} = \sum_{j}P(i_{t+1}= q_j | i_{t} = q_i) = 1$
$\sum_{k}B_{jk} = \sum_{k}P(o_{t}= v_k | i_{t} = q_j) =1$

4. 维特比算法(Viterbi Algorithm)(HMM的预测算法).

维特比算法 $viterbi \ algorithm$ 使用了动态规划算法来解决类似HMM和CRF的预测问题, 用维特比算法可以找到概率最大路径, 也就是最优路径, 在我们今天要解决的序列标注问题中, 就要通过维特比算法, 来找到文本所对应的最优的实体标注序列.
如果用一句话来概括维特比算法, 那就是:
在每一时刻, 计算当前时刻落在每种隐状态的最大概率, 并记录这个最大概率是从前一时刻哪一个隐状态转移过来的, 最后再从结尾回溯最大概率, 也就是最有可能的最优路径. 这话对于没有学过维特比算法的同学是无法理解的, 但是我觉得今天学完维特比算法之后再来看这句话, 可以加深记忆.
我们这里为了学习维特比方便, 所以转换一下标签:

$A_{i, j}^{t-1, t}$ , 是转移概率矩阵 $A$ 中的第 $i$ 行第 $j$ 列(下标), 指的是在 $t-1$ 时刻实体标签为 $q_i$ , 而在 $t$ 时刻实体标签转换到 $q_j$ 的概率.
$B_{jk}$ 是发射矩阵的第j行第k列, 指的是在第 $t$ 时刻, 由隐状态 $q_j$ 生成观测 $v_k$ 的概率.
有了上面两点, 则 $\hat{q}_j = A_{ij}B_{jk}$ 表示在 $t$ 时刻的隐状态为 $q_j$ 的概率估计.

在这里我们直接以实例的方式来说明维特比算法的计算过程(注意我们在这里下标从 $0$ 开始算起):

假设我们现在有所有可能的观测结果的集合 $V_{obs.}=\{v_0, v_1\}$ ;
所有可能的隐状态的集合 $Q_{hidden}=\{q_0, q_1, q_2\}$ ;
已经观测到的观测结果序列 $O=(o_1=v_0, \ o_2=v_1, \ o_3 = v_0)$ ;
然后假设我们通过HMM建模并学习, 得到了模型所估计的参数 $(A, B, \pi)$ , 注意下面的 $A, B$ 矩阵按行求和为 $1$ ;
我们要求出对应当前观测结果 $O$ 的最有可能的隐状态序列 $I=(i_0, i_1, i_2)$ .
我们现在要初始化两个暂存表格, 来暂存我们在每一时刻的计算结果, 稍后我们会说明怎么使用这两个表, 下面我们看到T1表格和T2表格, 他们的规格都是 $num\_hidden\_states * sequence\_length$ , 这两个表格在每一时刻 $t$ 都由 $3$ 个方块组成, $3$ 是所有可能隐状态的个数, 即 $|Q_{hidden}|=3$ , 注意这里表格内填充的颜色无意义, 只有好看的作用.

计算过程:

首先我们有初始隐状态概率矩阵 $\pi$ , 和第1时刻的观测结果 $o_1=v_0$ , 则在第一时刻, 由隐状态生成观测结果的概率计算可以写成 $q_j^{t=1} = \pi_{j}B_{jk}$ .
我们现在说明 $T1, T2$ 表格的用途: 如果 $T1, T2$ 表格是 $i*j$ 的矩阵, 则矩阵中第 $j$ 列指的是第 $j$ 时刻, 第 $i$ 行指的是第 $i$ 种隐状态, $T1[i, \ j]$ 指的是在第 $j$ 时刻, 落到隐状态 $i$ 的最大可能的概率是多少(不要着急, 到了下一个时刻就会明白最大是什么意思), 而 $T2[i, \ j]$ 记录的是这个最大可能的概率是从第 $j-1$ 时刻(上一时刻)的哪一种隐状态 $i$ 转移过来的, 也就是说我们记录的是最大可能的概率的转移路径.
我们现在将第一时刻的计算结果填入 $T1, T2$ 表格, 注意在第 $0$ 时刻的隐状态是由初始隐状态概率矩阵提供的, 而不是从上一时刻的隐状态转移过来的, 所以我们直接在 $T2$ 表格上记为 $NAN(not \ a \ number)$
我们现在来到第 $1$ 时刻(时刻下标从 $0$ 起算), 首先我们先计算 $T1[i=0, j=1]$ (也就是第 $j=1$ 时刻, 落到隐状态 $i=q_0$ 上的最大可能的概率是多少), 我们可以看出, 从上一时刻到当前时刻, 要想让当前时刻的隐状态为 $i_1=q_0$ , 则有3条路径可走, 分别是: $(i_0=q_0, i_1=q_0), \ (i_0=q_1, i_1=q_0), \ (i_0=q_2, i_1=q_0)$ ,
我们在 $T1[i=0, j=1]$ 的位置就是要算出, 这三条路径哪一条是最有可能的路径, 也就是取概率最大的一条, 这样的话, 计算公式为:
$T1[0, 1]=\max_{i} (P(i_1 = q_0 | i_0 = q_i) P(o_1=v_1| i_1 = q_0)) = T1[q_i, time\_step=0] * A_{t-1=q_i, \ t=q_0} * B_{i_1 = q_0, o_1=v_1}$
上式最右边 $T1[q_i, time\_step=0]$ 也就是 $T1[:, \ 0]$ 的意思是在 $t-1$ 时刻(也就是上一时刻), 每个隐状态对应的概率, 是长度为 $3$ 的向量;
$A_{t-1=q_i, \ t=q_0}$ 是 $A$ 矩阵的第 $i$ 行第 $0$ 列, 指的是在 $t-1$ 时刻隐状态为 $q_i$ , 而在 $t$ 时刻隐状态为 $q_0$ 的概率, 一共有三种可能的路径, 所以也是长度为 $3$ 的向量;
$B_{i_1 = q_0, o_1=v_1}$ 是 $B$ 矩阵的第 $0$ 行第 $1$ 列, 指的是隐状态 $q_0$ 生成观测 $v_1$ 的概率, 是一个数值.
通过查表计算, 我们算出:
$T1[0,1]=max\{0.10 * 0.5 * 0.5, \ 0.16 * 0.3* 0.5, \ 0.28*0.2* 0.5\}=0.028$
我们之前说过, 我们还要知道目前计算出来的这个最大可能的概率前一时刻的哪一种隐状态 $i$ 转移过来的, 也就是我们要在 $T2[0,1]$ 记录转移路径, 计算公式为:
$T2[0,1]=argmax\{0.10 * 0.5 * 0.5, \ 0.16 * 0.3* 0.5, \ 0.28*0.2* 0.5\}=2$
我们把计算结果填到表里, 注意在下图中, 红色的线表示最大的转移路径, 是从前一时刻的 $q_2$ 转移过来的.
接下来我们用同样的方式, 把表填完, 下面我们开始讲维特比算法是怎样通过这些暂存的概率和路径找到最优路径的:

最优路径有以下特性: 假设我们有一条最优路径在 $t$ 时刻通过一个隐状态 $i_t$ , 那么这一路径从 $i_t$ 到最优路径的终点 $i_T$ 相对于在这段距离里所有可能出现的路径里, 也必须是最优的. 否则从 $i_t$ 到 $i_T$ 就会有更优的一条路径, 如果把他和从 $i_1$ 到 $i_t$ 的路径(最优路径 $i_t$ 之前的部分)连起来, 等于我们又有一条更优路径, 这是矛盾的.
利用这一特性, 我们只要按上面的步骤计算直到得出最后一步达到的最大概率的隐状态, 再确认最大概率是从前一步哪一个隐状态转移过来的, 然后从 $T2$ 表格里面递推回溯直到第一时刻(也就是 $NAN$ 的地方), 就可以找出最优路径了.

回溯的计算:

首先算出最后一步达到最大路径的隐状态, 也就是在 $T1$ 表格的第 $3$ 列求 $argmax$ :
$i_2 = argmax \ T1[:, \ time\_step = 2] = 2$
之后我们通过 $T2$ 表格向前追溯一步, 当前最大概率是从前一步哪个隐状态转移过来的:
$i_1 = T2[i_2 = 2, \ time\_step = 2] = 2$
我们到达了倒数第一步, 我们追溯最优路径是从哪个起始隐状态转移过来的:
$i_0 = T2[i_1 = 2, \ time\_step = 1] = 2$
至此我们得出了最有可能的隐状态序列:
$I=(q_2, \ q_2, \ q_2)$

结论:

时间复杂度: 假设我们有 $N$ 种隐状态, 在每个时刻之间, 一共可能的路径一共有 $N^2$ 种, 假设我们有 $T$ 个时刻, 则维特比算法的时间复杂度为 $O(TN^2)$ .
在实际的预测计算当中, 为了防止计算结果下溢, 我们通常将乘法变为取对数之后的加法.
具体范例代码见视频讲解.