关键词：NER，viterbi，命名实体识别
内容摘要
- NER解码任务简述
- viterbi动态规划算法简述
- viterbi算法时间复杂度
- 图解NER中viterbi解码过程
- viterbi解码过程源码分析
NER解码任务简述
在上一节NER系列：CRF条件随机场原理简介，深入理解CRF源码实现中介绍了命名实体识别NER任务的损失求解部分，求解损失的目的是让模型进行训练得到每个位置的发射得分矩阵和相邻两个标签之间的转移得分矩阵，这些矩阵参数使得在训练集中正确路径的得分概率在所有可能路径中得分占比越大，从而模型能够将正确的序列标注结果在所有结果中脱颖而出。
在模型预测阶段，每条样本需要基于训练好的发射矩阵和转移矩阵计算出得分最大的序列标注结果，这个过程就是CRF的解码过程，序列标注的任务阶段如下表格所示
| 任务阶段 | 输入 | 算法 | 输出 |
|---|---|---|---|
| 1.训练 | 序列标注样本 | Bert+CRF | 发射矩阵，转移矩阵 |
| 2.解码 | 发射矩阵，转移矩阵 | viterbi动态规划 | 序列标注结果 |
viterbi动态规划算法简述
viterbi维特比算法是一个求序列最短路径的动态规划算法，如图所示黄色路径是从star到end的最短路径
viterbi维特比算法求解最短路径
viterbi也可以用于很多其他问题，在序列标注或者命名实体识别任务中，它的作为求解序列概率最大的路径，此时将求路径得分最短问题转化为求最大问题，另外不仅要考虑边的得分，也要考虑节点的得分
viterbi算法求解
viterbi算法求解序列标注的目标，是确定每个词位置的隐状态，使得这组隐状态序列的可能性最大，即该序列所经过的边和节点所带来的转移得分和发射得分最大。
viterbi算法时间复杂度
设文本长度为n，每个词位置下有k中实体类别，viterbi算法的计算过程为
- 逐步递归计算每个位置最大得分，并且作为下个位置的起始得分，一共需要递归计算n次
- 每个位置的最大的得分只保留下以各个状态为结尾的唯一一条最大得分路径，删除所有其他路径，因此每个位置下只有k条候选路径，和下一个位置进行一次逐步交叉计算共有k×k条可能路径
viterbi算法在每个位置删除了各状态结尾的非最大得分路径，大大减少了整体求解的复杂度，令t时刻以m状态为结尾的路径一共有s条，累计得分分别为s1,s2,s3...，其中s3为最大得分，则删除所有s1,s2,s4...，只保留下s3，因为从t时刻之后网络的结构完全相同，后续的累计得分相同，若想求得全局最大得分路径，则在t时刻也只能取最大得分s3，示意图如下
保留最大结尾得分路径，删除其他路径
因此viterbi算法的时间复杂读为n×(k方)，而暴力穷举所有实体类别路径一共有k的n方种可能，一般n>>k，暴力穷举的复杂度是文本长度的指数级，而viterbi的复杂读是随着文本长度的线性级。
图解NER中viterbi解码过程
以一个文本长度为3，每个位置的实体类别有2类为例，模拟下viterbi解码过程
viterbi求解NER案例
其中每个位置有2种实体类别m1和m2，节点的数值代表该位置下该实体类别的发射得分，另外转移得分矩阵如下，每个值代表从横轴类别到纵轴类别的转移概率
| 开始矩阵 | m1 | m2 |
|---|---|---|
| start | 0.8 | 0.3 |
| 转移矩阵 | m1 | m2 |
|---|---|---|
| m1 | 0.7 | 0.9 |
| m2 | 0.2 | 1.2 |
| 结束矩阵 | end |
|---|---|
| m1 | 0.2 |
| m2 | 0.6 |
从start开始逐步计算结果如下，其中每个时刻t只保留m1和m2结尾的各唯一一条最大得分路径，并以此作为新的起始发射得分继续递归计算到end结束
viterbi求解结果
最终分别以m1和m2生成2条候选最大得分路径，求他们的最大值为5.3，最大路径为m1，m1，m2，end，viterbi过程结束。
viterbi解码过程源码分析
采用torchcrf实现的CRF来分析viterbi的实现，该源码中CRF包含损失求解和viterbi解码两个过程，本节只关注viterbi解码过程，可以使用pip很方便地安装torchcrf
pip install torchcrf
源码在_viterbi_decode中实现了viterbi过程，该函数的输入是emissions又上层模型产出的发射得分，以及mask句子掩码，另外该类内部会维护CRF产出的转移矩阵，通过发射得分，转移矩阵计算最大路径得分和途径的标签类别，通过掩码判断标签停止位置。
viterbi的递归过程核心代码如下
for i in range(1, seq_length):
...
next_score = broadcast_score + self.transitions + broadcast_emission
# shape: (batch_size, num_tags)
# TODO 当前位置下，以每个类别为结尾的情况，最大的路径得分,保留下最大得分，其他全部忽略
# TODO next_score [batch_size, num_tags] 作为下一个位置的起始发射得分
# indices [batch_size, num_tags] 是最大值，代表每个类别结尾下，最大累计得分是前词是哪个类别编码
next_score, indices = next_score.max(dim=1)
score = torch.where(mask[i].unsqueeze(1), next_score, score)
# TODO 虽然分数受到mask控制不再累加，但是indices继续计算和保存
history.append(indices)
其中循环体的第一行实现了路径累加后词后的最新得分，即前词累计的得分作为发射得分，笛卡尔积加上所有转移得分和后词的发射得分，计算过程可视化如下
累加后词的最新得分
然后对前词维度求最大值，相当于后词不动，所有以后词为结尾的之前累计路径求得分最大值，输出next_score和indices，其中next_score记录了该批次下每条样本累计到该时刻以每个类别为结尾的最大得分，indices记录了该批次下每条样本累计到该时刻以每个类别为结尾的最大得分所对对应的前词所属的索引位置，即类别编码。history记录下了该循环过程记录下了所有时刻下的最大得分对应的前词列表。
递归过程结束后，对每条样本最终输出每个类别结尾的最大得分，对这些候选最大的得分再求一次最大值即可确定最终的得分以及对应的前词类别，该类别为每条样本的最后一个词所对应的标记类别
seq_ends = mask.long().sum(dim=0) - 1
best_tags_list = []
for idx in range(batch_size):
# TODO score[idx] 定位到某条样本,拿到最终最大的以某类别为结尾的得分
# TODO best_last_tag 是一个标量,是最后一个tag的编号
_, best_last_tag = score[idx].max(dim=0)
best_tags = [best_last_tag.item()]
# TODO 从最后一次向前遍历
for hist in reversed(history[:seq_ends[idx]]):
# TODO hist[idx] 拿到属于该条样本的 [num_tags, ], 各种最大得分结尾下前词的编码,已知best_tags是最终路径的最大得分结尾，在这个结尾下那条唯一保留下来的最大前词是谁
# TODO best_tags[-1] 拿到best_tags最后一个词的编码，作为每个步长的结尾,逐步往前递推
# TODO best_last_tag 拿到对应的前词编码
best_last_tag = hist[idx][best_tags[-1]]
best_tags.append(best_last_tag.item())
best_tags.reverse()
best_tags_list.append(best_tags)
获得句尾的类别后，从后依次往前递推，拿到前词对应的实体类别，获得所有类别序列后将最终结果反转即可获得最终的实体类别序列，viterbi求解过程的代码实现结束。
网友评论