命名实体识别

发表于 更新于

当深度学习遇上动态规划。

命名实体识别任务

Foreign planes to land in China’s popular Guilin.

如果要让机器细化地理解句子中每一个组成部分之间的关系，那么就需要首先拥有找出句子组成部分的能力。这时机器做的就是 __对句子中每一个词分类__。上面句子的分类的结果可能如下（来自于数据集conll2003）：

1
2
3
4
5
6
7
8
9
10
Foreign   JJ      I-NP    O
planes    NNS     I-NP    O
to        TO      I-VP    O
land      VB      I-VP    O
in        IN      I-PP    O
China     NNP     I-NP    I-LOC
's        POS     B-NP    O
popular   JJ      I-NP    O
Guilin    NNP     I-NP    I-LOC
.         .       O       O

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

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

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

DNN/算法设计

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

BiLSTM-CRF模型

BiLSTM

LSTM已经见得多了，其作用就是从输入的词向量序列中抽取上下文信息，提取到的信息送至下游分类任务。BiLSTM由于能同时考虑句子的上下文关系，一般效果比LSTM更好。下游任务可以是使用全连接层直接预测，也可以是后接CRF分类。

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

CRF

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

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

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

  1. 输入模型的待预测序列为$X=(x_1,x_2,\dots,x_n)$；
  2. LSTM等“上游特征提取器”的输出是一个矩阵$P_{n \times k}$，$p_{i,j}$表示第$i$个词是标签$j$的分数，也就是考虑“词-标签”的转化；
  3. 下游预测任务用到了另外一个矩阵$A_{(k+2) \times (k+2)}$，$a_{i,j}$表示从标签$i$和标签$j$相邻的可能性，也就是考虑“标签-标签”的转化；之所以是$k+2$阶矩阵，是考虑到$start$和$end$标签；
  4. 模型输出预测序列为$\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))$。

在BiLSTM-CRF的实现[3]中，_get_lstm_features、_score_sentence、_forward_alg、neg_log_likelihood是计算损失函数时用到的函数。

_get_lstm_features

先提取词向量，然后送到BiLSTM中抽取特征，抽取出来的特征再使用全连接网络做个转换。

1
2
3
4
5
6
7
def _get_lstm_features(self, sentence):
  self.hidden = self.init_hidden()
  embeds = self.word_embeds(sentence).view(len(sentence), 1, -1)
  lstm_out, self.hidden = self.lstm(embeds, self.hidden)
  lstm_out = lstm_out.view(len(sentence), self.hidden_dim)
  lstm_feats = self.hidden2tag(lstm_out)
  return lstm_feats

_score_sentence

1
2
3
4
5
6
7
8
9
10
11
12
13
def _score_sentence(self, feats, tags):
  # 从转移矩阵的角度审视句子的概率，从而给出评分
  score = torch.zeros(1)
  # 加上START_TAG
  tags = torch.cat([
    torch.tensor([self.tag_to_ix[START_TAG]], dtype=torch.long), tags
  ])
  for i, feat in enumerate(feats):
    # transitions(j, i)表示从i到j的可能性
    score += self.transitions[tags[i + 1], tags[i]] + feat[tags[i + 1]]
  # 加上转移到STOP_TAG的分数
  score = score + self.transitions[self.tag_to_ix[STOP_TAG], tags[-1]]
  return score

_forward_alg

如果一个句子很长，并且待标记的标签数众多，枚举每一种可能的路径会导致时间复杂度爆炸。好在实现[3]中，作者在_forward_alg函数中给出了解决方法，不过这一段代码比较难看懂。

……

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
def _forward_alg(self, feats):
  # Do the forward algorithm to compute the partition function
  forward_var = torch.full((1, self.tagset_size), -10000.)
  # START_TAG has all of the score.
  forward_var[0][self.tag_to_ix[START_TAG]] = 0.

  # Iterate through the sentence
  for feat in feats:
    alphas_t = []  # The forward tensors at this timestep
    for next_tag in range(self.tagset_size):
      # broadcast the emission score: it is the same regardless of
      # the previous tag
      emit_score = feat[next_tag].view(1, -1).expand(1, self.tagset_size)
      # the ith entry of trans_score is the score of transitioning to
      # next_tag from i
      trans_score = self.transitions[next_tag].view(1, -1)
      # The ith entry of next_tag_var is the value for the
      # edge (i -> next_tag) before we do log-sum-exp
      next_tag_var = forward_var + trans_score + emit_score
      # The forward variable for this tag is log-sum-exp of all the
      # scores.
      alphas_t.append(log_sum_exp(next_tag_var).view(1))
    forward_var = torch.cat(alphas_t).view(1, -1)
  terminal_var = forward_var + self.transitions[self.tag_to_ix[STOP_TAG]]
  alpha = log_sum_exp(terminal_var)
  return alpha

neg_log_likelihood

1
2
3
4
5
6
def neg_log_likelihood(self, sentence, tags):
  # 上游LSTM提取的句子特征
  feats = self._get_lstm_features(sentence)
  forward_score = self._forward_alg(feats)
  gold_score = self._score_sentence(feats, tags)
  return forward_score - gold_score

解码

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

实现[3]中涉及解码过程的函数有_get_lstm_features、_viterbi_decode、forward

_viterbi_decode

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
31
32
33
34
35
36
37
38
39
40
41
42
43
def _viterbi_decode(self, feats):
  backpointers = []

  # Initialize the viterbi variables in log space
  init_vvars = torch.full((1, self.tagset_size), -10000.)
  init_vvars[0][self.tag_to_ix[START_TAG]] = 0

  # forward_var at step i holds the viterbi variables for step i-1
  forward_var = init_vvars
  for feat in feats:
    bptrs_t = []  # holds the backpointers for this step
    viterbivars_t = []  # holds the viterbi variables for this step

    for next_tag in range(self.tagset_size):
      # next_tag_var[i] holds the viterbi variable for tag i at the
      # previous step, plus the score of transitioning
      # from tag i to next_tag.
      # We don't include the emission scores here because the max
      # does not depend on them (we add them in below)
      next_tag_var = forward_var + self.transitions[next_tag]
      best_tag_id = argmax(next_tag_var)
      bptrs_t.append(best_tag_id)
      viterbivars_t.append(next_tag_var[0][best_tag_id].view(1))
    # Now add in the emission scores, and assign forward_var to the set
    # of viterbi variables we just computed
    forward_var = (torch.cat(viterbivars_t) + feat).view(1, -1)
    backpointers.append(bptrs_t)

  # Transition to STOP_TAG
  terminal_var = forward_var + self.transitions[self.tag_to_ix[STOP_TAG]]
  best_tag_id = argmax(terminal_var)
  path_score = terminal_var[0][best_tag_id]

  # Follow the back pointers to decode the best path.
  best_path = [best_tag_id]
  for bptrs_t in reversed(backpointers):
    best_tag_id = bptrs_t[best_tag_id]
    best_path.append(best_tag_id)
  # Pop off the start tag (we dont want to return that to the caller)
  start = best_path.pop()
  assert start == self.tag_to_ix[START_TAG]  # Sanity check
  best_path.reverse()
  return path_score, best_path

forward

使用viterbi算法找出最佳的路径，forward函数没啥技术含量。

1
2
3
4
def forward(self, sentence):
  lstm_feats = self._get_lstm_features(sentence)
  score, tag_seq = self._viterbi_decode(lstm_feats)
  return score, tag_seq

Viterbi与Beam Search的区别

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

个人理解，实际上这两者的本质区别不在于其算法本身，而在于应用场景。Viterbi算法应用的任务多为具有条件独立性的，转移状态可以用$P(S_t|S_{t-1})$描述，也就是当前状态只和前一个状态有关，而与更久远的状态无关，因此当前状态只要选择当下最优也就是全局最优了，算法的时间复杂度为$O(N^2\times T)$。而Beam search通常用于翻译等任务，其状态转移概率需要用$P(S_t|S_{1:t-1})$建模，当前状态不仅需要考虑前一个状态，还要考虑整条路经的转移，因此搜索空间不免巨大，如果要求出全局最优解，就要枚举所有的可能性，那么时间复杂度将为$O(N^T)$，只能退而求其次记录局部最优。

LSTM-Stack模型

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

参考

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