命名實體識別（NER）：BiLSTM-CRF原理介紹+Pytorch_Tutorial程式碼解析
命名實體識別任務（NER）定義
命名實體識別屬於自然語言處理中的序列標註任務，是指從文本中識別出特定命名指向的詞，比如人名、地名和組織機構名等。具體而言，輸入自然語言序列 ，給出對應標籤序列 ，見下圖。
序列標註里標記法有很多，包括BIO、BIOSE、IOB、BILOU、BMEWO、BMEWO+等，最常見的是 BIO 與 BIOES 這兩種。不同標註方法會對模型效果有些許影響，例如有些時候用BIOES會比BIO有些許優勢。
在BIO和BIOSE中，Beginning 表示某個實體詞的開始，Inside表示某個實體詞的中間，Outside表示非實體詞，End表示某個實體詞的結尾，Single表示這個實體詞僅包含當前這一個字。IOB與BIO字母對應的含義相同，其不同點是IOB中，標籤B僅用於兩個連續的同類型命名實體的邊界區分。BILOU 等價於 BIOES，Last等同於End，Unit等同於Single。BMEWO 等價於 BIOES，Middle等同於Inside，Whole等同於Single。BMEWO+是在命名實體邊界外的標註，即『O plus『。
命名實體識別的常用方法是BiLSTM-CRF和BERT-CRF，可以完美的匹配該任務。
BiLSTM-CRF模型
下文，我們使用BIO標註進行解析，同時加入START和END來使轉移矩陣更加健壯，其中，START表示句子的開始，END表示句子的結束。這樣，標註標籤共有5個：[B, I, O, START, END]。
BiLSTM-CRF模型主體由雙向長短時記憶網路（Bi-LSTM）和條件隨機場（CRF）組成，模型輸入是字元特徵，輸出是每個字元對應的預測標籤。
模型輸入
對於輸入的自然語言序列，可通過特徵工程的方法定義序列字元特徵，如詞性特徵、前後詞等，將其輸入模型。但現在多數情況下，可以直接選擇句中每個字元的字嵌入或詞嵌入向量，可以是事先訓練好的或是隨機初始化。對於中文，我個人傾向於將字元向量和其所屬的詞向量進行拼接，詞嵌入使用預訓練好的，字嵌入隨機初始化。
LSTM
BiLSTM接收每個字元的embedding，並預測每個字元的對5個標註標籤的概率。
LSTM是一種特殊的循環神經網路，可以解決RNN的長期依賴問題，其關鍵就是細胞狀態，見下圖中貫穿單元結構上方的水平線。細胞狀態在整個鏈上運行，只有一些少量的線性交互，從而保存長距離的資訊流。具體而言，LSTM一共有三個門來維持和調整細胞狀態，包括遺忘門，輸入門，輸出門。
遺忘門接收h_{t-1}和x_t，通過公式1輸出一個在 0 到 1 之間的數值f_t，該數值會作用於上一個細胞狀態C_{t-1}，1 表示「完全保留」，0 表示「完全忘記」；輸入門接收h_{t-1}和x_t，通過公式2輸出一個在 0 到 1 之間的數值，已控制當前候選狀態\hat{C_t}有多少資訊需要保留，至於候選狀態\hat{C_t}，則通過公式3由tanh 層創建一個新的候選值向量，然後根據上一個細胞狀態C_{t-1}和遺忘值f_t、新的細胞狀態C_{t}和輸入值i_t，由公式4更新細胞狀態；輸出門接收h_{t-1}和x_t，通過公式5輸出一個在 0 到 1 之間的數值o_t，最後公式6決定了當前狀態C_t有多少資訊需要輸出。
題外話：LSTM的理解
一般來說，循環神經網路是MLP增加了一個時間維度，那麼該怎樣理解這個時間維度呢？可以參考以下兩張圖可視化LSTM。
在
torch.nn.LSTM()中，有以下幾個重要的參數：input_size，在這裡就是每個字元嵌入的維度；hidden_size，經過一個LSTM單元後輸入h的維度；num_layers，即上圖中depth的深度，若干個LSTMcell的堆疊；bidirectional，默認False，在實驗中將其設為True。LSTM輸入包括input和(h_0, c_0)兩部分，其中input大小為 (seq_len, batch, input_size)，h_0和c_0大小均為(num_layers * num_directions, batch, hidden_size)。輸出包括output和(h_n, c_n)兩部分，其中output大小為(seq_len, batch, num_directions * hidden_size)，h_n和c_n大小均為(num_layers * num_directions, batch, hidden_size)。
我們知道，CNN在空間上共享參數，而RNN是在時間上共享參數。也就是在每一層depth中只有一個LSTMcell，即上面第二張圖中每一層只有一個LSTM單元。
在BiLSTM-CRF中，一般使用一層的雙向LSTM是足夠的。因此，BiLSTM對輸入embeddings的特徵提取過程如下圖。
本部分一開始就說過，BiLSTM接收每個字元的embedding，並預測每個字元的對5個標註標籤的概率。但是，我們也知道上圖得到的拼接向量維度大小為num_directions * hidden_size。為將輸入表示為字元對應各個類別的分數，需要在BiLSTM層加入一個全連接層，通過softmax將向量映射為一個5維的分布概率。
到了這一步，似乎我們通過BiLSTM已經找到每個單詞對應的最大標籤類別，但實際上，直接選擇該步驟最大概率的標籤類別得到的結果並不理想。原因在於，儘管LSTM能夠通過雙向的設置學習到觀測序列之間的依賴，但softmax層的輸出是相互獨立的，輸出相互之間並沒有影響，只是在每一步挑選一個最大概率值的label輸出，這樣的模型無法學習到輸出的標註之間的轉移依賴關係（標籤的概率轉移矩陣）以及序列標註的約束條件，如句子的開頭應該是「B」或「O」，而不是「I」等。為此，引入CRF層學習序列標註的約束條件，通過轉移特徵考慮輸出label之間的順序性，確保預測結果的有效性。
CRF
CRF層將BiLSTM的Emission_score作為輸入，輸出符合標註轉移約束條件的、最大可能的預測標註序列。
在開始之前，我們先了解一下線性鏈條件隨機場。見李航老師的《統計學習方法》第11章。
赫然發現，NER問題就是條件隨機場，即給定自然語言序列X，最大概率的標註序列Y用來表示NER標註結果。至於P(y|x)，由公式（11.10）和（11.11）求得。齊活！
上圖中標出，公式（11.10）中有三個值得注意的部分：t_k，s_l和Z(x)，理解這三個部分是理解BiLSTM-CRF模型中CRF的關鍵，以下面這張圖進行說明。
在我們的例子中，輸入x為c_0,c_1,c_2,c_3,c_4，理想輸出y 為B,I,O,O,B，上圖中紅色線路。
- Z(x)，稱規範化因子或配分函數。在公式（11.10）中，「Z(x)是規範化因子，求和是在所有可能的輸出序列上進行的」。對應到我們的圖中，其實就是圖中所有可能的路徑組合，由於輸入序列長度為5，標註類型也為5，因此上圖中共有$5^5條不同路徑。每條路徑根據exp(*)計算該路徑的得分，加和得到Z(x)$。
- s_t是節點上的狀態特徵，取決於當前節點；t_k是邊上的轉移特徵，取決於當前和前一個節點。根據它們的定義，可以很自然的將它們與BiLSTM-CRF中的Emission Score和Transition Score匹配：Emission Score是由BiLSTM生成的、對當前字元標註的概率分布；Transition Score是加入CRF約束條件的、字元標註之間的概率轉移矩陣。從這個意義上講，BiLSTM-CRF其實就是一個CRF模型，只不過用BiLSTM得到狀態特徵值s_t，用反向傳播演算法更新轉移特徵值t_k。
在模型訓練過程中，模型損失函數定義如下：
P(\bar{y}|x)=\frac{exp(\operatorname{score}(x,\bar{y}))}{\sum_y{exp(\operatorname{score}(x,y))}}
\operatorname{score}(x,y)=\sum_{i=1}^{n} P_{i, y_{i}}+\sum_{i=0}^{n} A_{y_{i-1}, y_{i}}
其中，P_{i, y_{i}}和A_{y_{i-1}, y_{i}}分別表示標註序列y中y_i的Emission Score和Transition Score，通過查找上圖中的」BiLSTM的Emission Score「和」序列標註轉移矩陣「可以得到每個字元位置的得分，整個序列相加得到\operatorname{score}(x,y)。
模型訓練過程中最大化對數似然函數：
\log P\left(\bar{y}\mid x\right)=\operatorname{score}\left(x, \bar{y}\right)-\log \left(\sum_{y} \exp \left(\operatorname{score}\left(x, y\right)\right)\right)
真實路徑得分
在我們的例子中，真實路徑\bar{y}=(B,I,O,O,B)，\operatorname{score}(x,\bar{y})=\sum\operatorname{EmissionScores}+\sum\operatorname{TransitionScores}，其中:
\sum\operatorname{EmissionScores}=P_{0,START}+P_{1, B}+P_{2, I}+P_{3,O}+P_{4, O}+P_{5,B}+P_{6,END}
\sum\operatorname{TransitionScores}=A_{START,B}+A_{B,I}+A_{I,O}+A_{O,O}+A_{O,B}+A_{B,END}
EmissionScores來自BiLSTM層的輸出，至於P_{0,START}和P_{6,END}，則設為0；TransitionScores來自於CRF層；將真實路徑中這兩類分數加和，即可得到真實路徑得分，上圖中紅色路線。
所有路徑得分
對於所有路徑的總分\sum_{y} \exp \left(\operatorname{score}\left(x, y\right)\right)，一種直接的想法是列舉出所有可能的路徑，然後查找每條路徑的Emission Score和Transition Score，計算出每條路徑的得分，之後加和。
這種方法顯然效率低下，在我們的例子中，僅有5個字元和5個標註序列，就已經有了約5^5種路徑組合，在實際工作中，我們顯然會有更長的序列和更多的標註標籤，提高計算效率是必要的。於是，我們以分數累積的方法計算所有路徑得分，即先計算出到達c_0的所有路徑的總得分，然後，計算c_0{->}c_1的所有路徑的得分，依次類推，直到計算出c_0->c_1\dots->c_n的所有路徑的得分，這就是我們需要的結果。通過下圖可以看出這兩種計算方式的不同。
上面的圖是直觀的、計算所有路徑得分加和的示意圖，這種方法思想上是深度優先的；下面的圖是改進的、分數累計求和的示意圖，這種方法思想上是廣度優先的。
在第一種方法中，圖示以[(S,S,S,S,S),(S,S,S,S,B),(S,S,S,S,I),(S,S,S,S,O),(S,S,S,S,E)]五條可能的標註路徑為例，每一條路徑得分由該路徑上節點得分（EmissionScore）和邊得分（TransitionScore）相加得到，可以發現，如果計算分別計算每一條路徑的話，存在大量的冗餘，如對於上述五條路徑，前四個標註是相同的，理論上只需分別計算最後一項不同標註即可。
分數累積的方法更為激進。要知道，在計算Z(x)時我們並不是要排列組合出所有可能路徑，只是要一個All值，即圖中所有邊和節點的總值。因此，我們可以先計算出到達某一字元的路徑得分之和(s_S^i,s_B^i,s_I^i,s_O^i,s_E^i)，然後依次計算下一字元的路徑得分之和(s_S^{i+1},s_B^{i+1},s_I^{i+1},s_O^{i+1},s_E^{i+1})，這類似於動態規劃的思想。如在上圖示例中，我們在得知到達y_1的路徑得分之和(s_S^1,s_B^1,s_I^1,s_O^1,s_E^1)後，根據s_{tag’}^2=\sum_{tags}{s_{tag}^1+t_{(tag,tag’)}}可分別計算出y_2的路徑得分之和(s_S^2,s_B^2,s_I^2,s_O^2,s_E^2)，圖中紅/綠/藍/黃/紫分別根據y_1各標註的得分計算到達y_2的(S,B,I,O,E)各標註的得分之和。依次類推，計算出整個圖中所有路徑得分之和。
在圖中可以直觀看到上述兩種方法是等價的，其數學上的等價性見下：
\log \left(\sum e^{\log \left(\Sigma e^{x}\right)+y}\right)=\log \left(\sum \sum e^{x+y}\right)
證明過程：
\begin{aligned}
\log \left(\sum e^{\log \left(\Sigma e^{x}\right)+y}\right) &=\log (\sum e^{\log (\Sigma e^{x})+\log e^y}) \\
&=\log (\sum e^{\log (\Sigma e^{x})*e^y})\\
&=\log (\sum e^{\log (\Sigma e^{x+y})})\\ &=\log \left(\sum \sum e^{x+y}\right) \end{aligned}
第二種方法有效減少了計算冗餘。第一種方法的計算複雜度為O（nm^n)，其中，m為標註標籤類別數，第二種方法的計算複雜度為O(nm^2)。當然，第二種方法還可以以下圖這種方式計算，下文Pytorch Tutorial中的實現_forward_alg()就是如此，但本質上就是一回事。
建議推薦參照Bi-LSTM-CRF演算法詳解-1中的推導過程進行理解或自行推導。
最終BiLSTM-CRF模型如下：
Pytorch Tutorial NER程式碼解析
網上多數Pytorch NER解析來自官方示例，見ADVANCED: MAKING DYNAMIC DECISIONS AND THE BI-LSTM CRF，以下程式碼添加有個人備註解析。以下幾點需要注意：
- 前文提到，模型目標是最大化對數似然函數\log P\left(\bar{y}\mid x\right)=\operatorname{score}\left(x, \bar{y}\right)-\log \left(\sum_{y} \exp \left(\operatorname{score}\left(x, y\right)\right)\right)，但在深度學習中，我們一般通過最小化損失函數優化模型參數。因此，取負得到損失函數Loss=\log (\sum_{y} \exp (\operatorname{score}(x, y)))-\operatorname{score}(x, \bar{y})。
- 在NER問題中，訓練過程與測試過程是不同的。在訓練中，我們需要計算所有路徑的得分以正確更新轉移矩陣，但在測試過程中，我們以然得到合理的標籤概率轉移矩陣，因此只需要結合Emission Score選擇一條概率最大的路徑。該過程為解碼過程，採用Vertibe演算法，參見如何通俗地講解 viterbi 演算法？。
- Pytorch Tutorial僅提供最基本的程式碼幫助理解BiLSTM-CRF，具體的到實踐，該程式碼還有很大的優化空間。如批次訓練、GPU訓練、維特比解碼和配分函數計算優化等。
import torch
import torch.autograd as autograd
import torch.nn as nn
import torch.optim as optim
torch.manual_seed(1)
def prepare_sequence(seq, to_ix):
idxs = [to_ix[w] for w in seq]
return torch.tensor(idxs, dtype=torch.long)
def argmax(vec):
# 得到最大的值的索引
_, idx = torch.max(vec, 1)
return idx.item()
def log_sum_exp(vec):
max_score = vec[0, argmax(vec)] # max_score的維度為1
max_score_broadcast = max_score.view(1, -1).expand(1, vec.size()[1]) # 維度為1*5
return max_score + torch.log(torch.sum(torch.exp(vec - max_score_broadcast)))
#等同於torch.log(torch.sum(torch.exp(vec)))，防止e的指數導致電腦上溢
class BiLSTM_CRF(nn.Module):
def __init__(self, vocab_size, tag_to_ix, embedding_dim, hidden_dim):
super(BiLSTM_CRF, self).__init__()
self.embedding_dim = embedding_dim
self.hidden_dim = hidden_dim
self.vocab_size = vocab_size
self.tag_to_ix = tag_to_ix
self.tagset_size = len(tag_to_ix)
self.word_embeds = nn.Embedding(vocab_size, embedding_dim)
self.lstm = nn.LSTM(embedding_dim, hidden_dim // 2, num_layers=1, bidirectional=True)
self.hidden2tag = nn.Linear(hidden_dim, self.tagset_size)
# 轉移矩陣，transitions[i][j]表示從label_j轉移到label_i的概率,雖然是隨機生成的但是後面會迭代更新
self.transitions = nn.Parameter(torch.randn(self.tagset_size, self.tagset_size))
self.transitions.data[tag_to_ix[START_TAG], :] = -10000 # 從任何標籤轉移到START_TAG不可能
self.transitions.data[:, tag_to_ix[STOP_TAG]] = -10000 # 從STOP_TAG轉移到任何標籤不可能
self.hidden = self.init_hidden() # 隨機初始化LSTM的輸入(h_0, c_0)
def init_hidden(self):
return (torch.randn(2, 1, self.hidden_dim // 2),
torch.randn(2, 1, self.hidden_dim // 2))
def _forward_alg(self, feats):
'''
輸入：發射矩陣(emission score)，實際上就是LSTM的輸出——sentence的每個word經BiLSTM後，對應於每個label的得分
輸出：所有可能路徑得分之和/歸一化因子/配分函數/Z(x)
'''
init_alphas = torch.full((1, self.tagset_size), -10000.)
init_alphas[0][self.tag_to_ix[START_TAG]] = 0.
# 包裝到一個變數裡面以便自動反向傳播
forward_var = init_alphas
for feat in feats: # w_i
alphas_t = []
for next_tag in range(self.tagset_size): # tag_j
# t時刻tag_i emission score（1個）的廣播。需要將其與t-1時刻的5個previous_tags轉移到該tag_i的transition scors相加
emit_score = feat[next_tag].view(1, -1).expand(1, self.tagset_size) # 1*5
# t-1時刻的5個previous_tags到該tag_i的transition scors
trans_score = self.transitions[next_tag].view(1, -1) # 維度是1*5
next_tag_var = forward_var + trans_score + emit_score
# 求和，實現w_(t-1)到w_t的推進
alphas_t.append(log_sum_exp(next_tag_var).view(1))
forward_var = torch.cat(alphas_t).view(1, -1) # 1*5
# 最後將最後一個單詞的forward var與轉移 stop tag的概率相加
terminal_var = forward_var + self.transitions[self.tag_to_ix[STOP_TAG]]
alpha = log_sum_exp(terminal_var)
return alpha
def _get_lstm_features(self, sentence):
'''
輸入：id化的自然語言序列
輸出：序列中每個字元的Emission Score
'''
self.hidden = self.init_hidden() # (h_0, c_0)
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) # len(s)*5
return lstm_feats
def _score_sentence(self, feats, tags):
'''
輸入：feats——emission scores；tags——真實序列標註，以此確定轉移矩陣中選擇哪條路徑
輸出：真實路徑得分
'''
score = torch.zeros(1)
# 將START_TAG的標籤３拼接到tag序列最前面
tags = torch.cat([torch.tensor([self.tag_to_ix[START_TAG]], dtype=torch.long), tags])
for i, feat in enumerate(feats):
score = score + \
self.transitions[tags[i + 1], tags[i]] + feat[tags[i + 1]]
score = score + self.transitions[self.tag_to_ix[STOP_TAG], tags[-1]]
return score
def _viterbi_decode(self, feats):
# 預測序列的得分，維特比解碼，輸出得分與路徑值
backpointers = []
init_vvars = torch.full((1, self.tagset_size), -10000.)
init_vvars[0][self.tag_to_ix[START_TAG]] = 0
forward_var = init_vvars
for feat in feats:
bptrs_t = []
viterbivars_t = []
for next_tag in range(self.tagset_size):
next_tag_var = forward_var + self.transitions[next_tag] # forward_var保存的是之前的最優路徑的值
best_tag_id = argmax(next_tag_var) # 返回最大值對應的那個tag
bptrs_t.append(best_tag_id)
viterbivars_t.append(next_tag_var[0][best_tag_id].view(1))
forward_var = (torch.cat(viterbivars_t) + feat).view(1, -1)
backpointers.append(bptrs_t) # bptrs_t有５個元素
# 其他標籤到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]
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)
# 無需返回最開始的START位
start = best_path.pop()
assert start == self.tag_to_ix[START_TAG]
best_path.reverse() # 把從後向前的路徑正過來
return path_score, best_path
def neg_log_likelihood(self, sentence, tags): # 損失函數
feats = self._get_lstm_features(sentence) # len(s)*5
forward_score = self._forward_alg(feats) # 規範化因子/配分函數
gold_score = self._score_sentence(feats, tags) # 正確路徑得分
return forward_score - gold_score # Loss（已取反）
def forward(self, sentence):
'''
解碼過程，維特比解碼選擇最大概率的標註路徑
'''
lstm_feats = self._get_lstm_features(sentence)
score, tag_seq = self._viterbi_decode(lstm_feats)
return score, tag_seq
START_TAG = "<START>"
STOP_TAG = "<STOP>"
EMBEDDING_DIM = 5 # 由於標籤一共有B\I\O\START\STOP 5個，所以embedding_dim為5
HIDDEN_DIM = 4 # 這其實是BiLSTM的隱藏層的特徵數量，因為是雙向所以是2倍，單向為2
training_data = [(
"the wall street journal reported today that apple corporation made money".split(),
"B I I I O O O B I O O".split()
), (
"georgia tech is a university in georgia".split(),
"B I O O O O B".split()
)]
word_to_ix = {}
for sentence, tags in training_data:
for word in sentence:
if word not in word_to_ix:
word_to_ix[word] = len(word_to_ix)
tag_to_ix = {"B": 0, "I": 1, "O": 2, START_TAG: 3, STOP_TAG: 4}
model = BiLSTM_CRF(len(word_to_ix), tag_to_ix, EMBEDDING_DIM, HIDDEN_DIM)
optimizer = optim.SGD(model.parameters(), lr=0.01, weight_decay=1e-4)
for epoch in range(300):
for sentence, tags in training_data:
model.zero_grad()
# 輸入
sentence_in = prepare_sequence(sentence, word_to_ix)
targets = torch.tensor([tag_to_ix[t] for t in tags], dtype=torch.long)
# 獲取loss
loss = model.neg_log_likelihood(sentence_in, targets)
# 反向傳播
loss.backward()
optimizer.step()
with torch.no_grad():
precheck_sent = prepare_sequence(training_data[0][0], word_to_ix)
print(model(precheck_sent))
#TODO
- NER實戰
- BERT-CRF
- …
參考
序列標註方法BIO、BIOSE、IOB、BILOU、BMEWO、BMEWO+的異同
ADVANCED: MAKING DYNAMIC DECISIONS AND THE BI-LSTM CRF
《統計學習方法（第二版）》
