命名实体识别

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

命名实体识别任务

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_algneg_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_decodeforward

_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