传统意义上的算法一直都很优雅。

命名实体识别任务

Hong Kong is part of China.

如果要让机器理解上面的句子的“情感”，那么实际上就是将句子视为一个整体并做分类；如果要让机器细化地理解句子中每一个组成部分之间的关系，那么就需要首先拥有找出句子组成部分的能力，比如，机器要能识别出其中的"Hong Kong"是一个实体，而不是两个独立的单词。这时机器做的就是 对句子中每一个词分类。分类的结果可能如下：

这就是命名实体识别（named entity recognition，以下简称NER）的通俗理解。NER需要将文本中的元素分成预定的类，粗粒度为3大类（实体类、时间类、数字类），细粒度7小类（人名、地名、组织名、机构名、时间、日期、货币、百分比）或更加精细的类别。

而NER处理过的命名实体序列可以为更多的下游任务提供方便，比如知识图谱、文本理解、舆情分析。

和情感分类任务不同的是，NER任务也是 大小写敏感的，很好理解，一个词如果由大写开始，那么该词很有可能是人名、地名等，因此有很多模型在设计上考虑到了字符级（character-level）特征的提取。有用LSTM的[1]，也有用CNN的[2]。

DNN/算法设计

我在PyTorch的官网找到了有关序列标注的详尽代码：ADVANCED: MAKING DYNAMIC DECISIONS AND THE BI-LSTM CRF[3]，这份教程的代码写得十分精炼，且和论文[1]中的思路有很多相似之处。

LSTM-CRF模型

LSTM

LSTM已经见得多了，其作用就是从输入的词向量序列中抽取上下文信息，提取到的信息送至下游分类任务。而下游任务可以是使用全连接层直接预测，也可以是后接CRF分类。

在论文[1]中，作者对比了多种不同结构模型的效果，最终得出结论：LSTM+CRF的组合性能最好

CRF

CRF的核心思想就是：在为某一个词分类的时候，同时考虑该词附近的词的性质。

举个例子，“主-谓-宾”符合语法，是一种概率很大的分类序列，而“主-系-宾”这种序列，虽然系语出现在句子中间部分的概率很大，但是“系-宾”搭配就很怪异。

借用论文[1]中的表示方式：

输入模型的待预测序列为 $X=(x_1,x_2,\dots,x_n)$ ；
LSTM等“上游特征提取器”的输出是一个矩阵 $P_{n \times k}$ ， $p_{i,j}$ 表示第 $i$ 个词是标签 $j$ 的分数，也就是考虑“词-标签”的转化；
下游预测任务用到了另外一个矩阵 $A_{(k+2) \times (k+2)}$ ， $a_{i,j}$ 表示从标签 $i$ 和标签 $j$ 相邻的可能性，也就是考虑“标签-标签”的转化；之所以是 $k+2$ 阶矩阵，是考虑到 $start$ 和 $end$ 标签；
模型输出预测序列为 $\textbf{y}=(y_1,y_2,\dots,y_n)$ ，其中序列长度为 $n$ ,预测类别数为 $k$ ；

为了确定一个标注序列的好坏，定义评分标准如下：

s(X,\textbf{y}) = \sum_{i=0}^{n}{A_{y_i,y_{i+1}}} + \sum_{i=1}^{n}{P_{i,y_i}}

自定义的损失函数

以上的 $s(X,\textbf{y})$ 仅是分数，需要再使用Softmax从分数映射到概率：

p(\textbf{y}|X) = \frac{\exp{s(X,\textbf{y})}}{\sum_{\tilde{y} \in Y_X}{\exp{s(X,\tilde{\textbf{y}})}}}

$Y_X$ 是所有可能的序列。训练过程就是让目标序列概率最大化，作者对上式求了对数，是一种等价的做法：

\begin{aligned}
\log(p(\textbf{y}|X)) &= s(X,\textbf{y}) - \log(\sum_{\tilde{y} \in Y_X}{\exp{s(X,\tilde{\textbf{y}})}}) \\
&= s(X,\textbf{y}) - logadd_{\tilde{y} \in Y_X}\exp{s(X,\tilde{\textbf{y}})}
\end{aligned}

这便是该模型的损失函数，模型的学习过程就是使用 梯度上升 最大化 $\log(p(\textbf{y}|X))$ ，或者使用__梯度下降__ 最小化 $-\log(p(\textbf{y}|X))$ 。

这里还有另外一个问题：如果一个句子很长，并且待标记的标签数众多，枚举每一种可能的路径会导致时间复杂度爆炸。

在代码实现[1]中，作者在BiLSTM_CRF._forward_alg函数中实现了……

解码

LSTM-CRF模型的解码方式用到了动态规划——Viterbi算法，对应代码实现[1]中的BiLSTM_CRF._viterbi_decode。因为“从网络输出中解码出固定个数的标签”这个问题实际上可以抽象为图论问题，即从源点到终点的最优路径。

与Beam Search的区别

Viterbi是动态规划算法，而与其有着相似算法步骤的Beam search，却沦为贪心算法。

个人理解，实际上这两者的本质区别不在于其算法本身，而在于应用场景。Viterbi算法被广泛应用于分类，而Beam search通常用于翻译，这两类任务预测数据规模上的区别造就了算法类型的本质区别。分类任务输出值是标签，标签空间大小通常不会很大，因此可以枚举每一种状态，便于找出全局最优解；而翻译任务的输出是词，词库的大小不允许算法精确枚举每一种情况，只能退而求其次记录局部最优，因此退化为贪心算法。

LSTM-Stack模型

学过编译原理的人一定记得SR算法。在论文[1]中除了使用LSTM外，还是借用了SR算法的思想，

参考

Neural Architectures for Named Entity Recognition
End-to-end Sequence Labeling via Bi-directional LSTM-CNNs-CRF
ADVANCED: MAKING DYNAMIC DECISIONS AND THE BI-LSTM CRF

当深度学习遇上动态规划