Chinese NER Using Lattice LSTM
ACL 2018, The Best Character-Based Chinese NER model
Preface
Chinese NER Using Lattice LSTM 收錄於 ACL 2018 Long Papers，為目前中文命名實體標註(NER, Named Entity Recognition)最佳的模型，NER 為自然語言處理和資訊擷取中一項不可或缺的技術，在分析文本的過程中，我們必須將其中重要的詞彙進行標註，例如地名、人名、機構名…等等，當機器能理解文本中這些重要的資訊，也就代表機器能進一步作出符合語意的決策。
NER可視為一種序列標註(Sequential labeling)問題，序列標註將每個序列單位給予標籤，例如中文分詞、詞性標註、依存句法分析、NER…等等，都是其子應用，在深度學習尚未蓬勃前，Conditional Random Fields (CRF)一直是解決序列標註最好的方法，由於 CRF 目的是在文本對應標籤的輸出空間中，學習到語言的各種結構(例如：組織名常接在地名的後方)，以便正確地進行標註，因此我們稱之為結構化學習(structured learning)，而隨著深度學習的演進，現階段則以 LSTM-CRF 為目前state-of-the art模型，其中 LSTM 用來作特徵擷取，CRF 則基於特徵計算標籤組合的全局最優解。
這兩年來，許多研究者基於 LSTM-CRF 進行改進，有些針對input representation來作改善，有些則針對模型架構作改良，本篇也是針對此兩點進行優化和變形，並在許多中文 NER 任務中取得state-of-the-art的成果。
Character-based v.s. Word-based NER
中文有別於英文，詞彙與詞彙之間沒有空格隔開，全部相連在一起，因此中文的語言特性及規則增加了 NER 的難度。
首先使用 word-based NER 可以讓模型預先知道最小語意單位(詞彙)，也因此在標註時，模型僅需要針對每一個詞彙來進行標註，但優點也是缺點，由於 word-based 需要先作分詞前處理，也意味著當前處理錯誤時，錯誤會往後傳遞(error propagation)到 NER 階段，意思是，當分詞錯誤時，NER 就永遠不可能標註正確了。
老蔡/英文/很爛 →老蔡<person>/英文/很爛
老/蔡英文/很爛 →老/蔡英文<person>/很爛
而 character-based NER 則是對每一個字元進行標註，並使用 BIOES( Begin，Inside，Outside，End，Single) 等標註編碼方法，來描述一個完整 entity 所囊括的字元範圍，並幫助機器學習每個字元在該 entity 中所扮演的腳色，但這個方法卻無法利用分詞的資訊，也就是說，character-based NER 除了進行實體標註外，某方面它也必須同步進行分詞的工作。
老蔡英文很好
→老<begin-person>/蔡<end-person>/英<o>/文<o>/很<o>/好<o>
作者提到，經前人的實驗發現在中文 NER，character-based 仍略優於 word-based，因此除非有高品質的人工分詞，否則現階段在實現中文NER模型仍是以 character-based 為大宗。
本篇論文基於 character-based NER，希望可透過某些方法間接地利用到word 資訊，讓模型不僅能避免分詞錯誤而造成 error propagation 的問題，也能同時基於 character & word information 達到不錯的成果，以下將進行模型介紹。
Model
論文共分為三個部分:
- Character-Based Model
- Word-Based Model
- Lattice Model
其中最核心的部分為 Lattice Model，本文將由第一點開始依序介紹：
1. Character-Based Model
Character-Based Model 架構如下圖所示，模型為 LSTM-CRF 架構，每一個時間點的輸入都是一個單詞(Character)。
每一個時間點的輸入 c_j 會透過字元嵌入向量的 lookup table e^c，找到其對應的字元向量。
模型是採用 bi-directional LSTM，上圖為了簡化架構而只畫了單向，因此每一個隱藏層的輸出由正向和反向組合而成：
最終我們將隱藏層輸出作為 linear-chain CRF 的輸入以進行序列標註。
- Char + bichar
在 input representation 的部分，加入了 bichar 資訊，例如「果汁」、「果醋」，其中「果」有水果的意涵，而「果然」、「導果為因」則「果」有結果的意涵，字元會因為前後語境而產生不同的意思，因此我們將「果」和「果」在文本中接續的下一個字元一起作為該字元的表示，能有效解決語意歧異問題，實驗顯示有助於提升分詞的精準度，因此也將此向量一併(concatenate)加入作為模型的輸入向量。
南京市長
vector(南)=[embedding_table(南) ; bichar_embedding_table(南,京)]
vector(京)=[embedding_table(京) ; bichar_embedding_table(京,市)]
vector(市)=[embedding_table(市) ; bichar_embedding_table(京,長)]
vector(長)=[embedding_table(長) ; bichar_embedding_table(京,<end>)]
2. Char + softword
除了 bichar 外，softword 的資訊亦可有效幫助 NER 準確率的提升，softword 代表每一個字元在分詞後所處位置，以 BMES scheme 為例：詞彙的第一個字元被標註為 B(Begin)、中間字元被標註為 M(Middle)、最後一個字元被標註為 E(End)、單字詞則被標註為 S(Single)，如下所示，我們預先訓練一個B、M、E、S 四個字母的 embedding table，並將每個字元通過分詞器得到 BMES 其中一個字母作為標籤，再藉由 table 來獲取 BMES 標籤的向量，將之與字元向量結合，作為模型輸入。
南京市長 → 南京 / 市長 → 南/B 京/E 市/B 長/E
vector(南)=[embedding_table(南) ; BMES_embedding_table(B)]
vector(京)=[embedding_table(京) ; BMES_embedding_table(E)]
vector(市)=[embedding_table(市) ; BMES_embedding_table(B)]
vector(長)=[embedding_table(長) ; BMES_embedding_table(E)]
2. Word-Based Model
Word-Based Model 架構如下圖所示，模型為 LSTM-CRF 架構，每一個時間點的輸入都是一個詞彙(Word)。
每一個時間點的輸入 w_i 會透過詞嵌入向量的 lookup table e^w，找到其對應的詞向量。
模型亦採用 bidirectional LSTM，並將隱藏層輸出作為 linear-chain CRF 的輸入以進行序列標註。
- Word + char LSTM
在 input representation 的部分，除了詞向量外，另外我們加入以字元透過 bidirectional LSTM 產生的向量，此作法可以讓輸入向量同時具有詞彙和字元兩種不同程度的語意資訊，且透過 bidirectional LSTM 產生的向量相較於預先分詞，並不會產生任何副作用。
南京市長 → 南京 / 市長
vector(南京)=[embedding_table(南京) ; bi_lstm(南,京)]
vector(市長)=[embedding_table(市長) ; bi_lstm(市,長)]
2. Word + char LSTM’
Word + char LSTM’ 則為上述方法的改良，有別於一般character based bilstm 僅利用單一詞彙內的資訊，此作法利用句子資訊，產生各詞彙的雙向輸出，再將其兩輸出合併(concatenate)起來，作為該詞彙的向量表示，此法能利用詞彙上下文的資訊，讓每個詞彙的向量表示，能同時考量詞彙前後的訊息。
3. Word + char CNN
Word + char CNN 除了詞向量外，也將詞會的每一個字元丟入 Convolutional Neural Network(CNN) 來抽取字元等級的向量。下式中，ke=3 表示 kernel size，捲積後通過 max pooling 來最終產生結果。
南京市長 → 南京 / 市長
vector(南京)=[embedding_table(南京) ; cnn(南,京)]
vector(市長)=[embedding_table(市長) ; cnn(市,長)]
3. Lattice Model
Lattice model 整體架構如上，可以將之視為改良版的 character-based model，整合了 word-based cells 和 additional gates 來控制整個資料流。
以下圖為例，模型的輸入為字元並加入所有連續字元的組合中在字典中成詞的候選詞彙，其中字典的產生透過分詞器將大量語料分詞後相異詞彙的聯集。
此架構中，共包含四種向量分別是 input vectors, output hidden vectors, cell vectors 和 gate vectors，其中字元的 input vectors 以下式作表示：
而下式為 LSTM 的基本操作，其中輸出i, f, o分別為 input, forget, output gates，c^~ 為通過線性轉換的input vector，σ() 為 sigmoid function。
與 character-based model 不同的是，現在多考量了所有候選詞彙的向量，如下式， w 的下標 b & e 分別代表字元的起始和結束 index，以上圖為例，「 大桥」的下標為 6 , 7，表示「 大」在 index 6 的位置，而「桥」在 index 7 的位置，我們透過 word_embedding_lookup_table 來找到每個候選詞彙所對應的詞向量。
word cell 的產生方式如下採用相同的操作，但拿掉了 output gate，如上圖，word cell 僅會在過程中被使用，沒有產生 output 的需求。
而 word cell 與 character cell 的連結方式如下圖，以詞彙「長江大橋」為例，「長江大橋」連結於起始字元「長」、結束於最後一個字元「橋」。我們將所有候選詞彙的起始字元與結束字元，分別連結於 character cell 所對應之相同字元。
我們加入了一個額外的 閘門（gate）來決定和控制每一個候選詞彙的貢獻程度。下面公式中，每個候選詞彙都有其各自的閘門 i，x 表示 index 為 e 的 character vector，c 表示所有結尾 index 為 e 的候選詞彙。閘門的計算就像 attention function 一樣，計算 character cell 和其對應的候選詞彙之注意力分數。
因此，cell 的計算變成：
其中 α 的計算如下，其總合為 1，代表針對某 character cell，所有候選詞彙連結於該 cell 以及本身 input 所對應的權重。α 權重就是控制所有 information flow的閘門，這意味著，訓練過程中，模型會去學習每一個 time step 所需注意的 information flow 有哪些，便提高其閘門權重，讓其 information flow 因為權重而獲得較大的影響力。
這裡值得注意的是，original LSTM cell 之值，是透過 previous character memory 和 current character input vector 計算而得；而 Lattice LSTM 如上式，仔細觀察式子發現，若該 time step 之 character cell 有被候選詞彙連結，則 previous character memory 就不納入計算，否則就照原 original LSTM 方法處理。至於為什麼不一併將 previous character memory 也加入考量，作者有了下面的解釋：
“Yes. Actually we tried both. Both of the structures have significant improvement but without the previous character memory gives a better result. Intuitively, we think this may be caused by the optimization problem, the previous character memory has a different weight set with the shortcut word memory, it will make the optimizer unstable because sometimes the shortcut word memory exists but sometimes it will not. This asymmetric situation will be a obstacle of the optimizer.”
Decoding and Training
最終我們將每一層的 hidden state output，通過 CRF 模型訓練，使用 viterbi algorithm 計算所有可能的標記組合中，其機率值最大者，即為最終的輸出。
我們將 L2 regularization 機制一併加入 sentence-level log-likelihood loss 進行訓練。
(這邊比較不解的是，前項為何不是negative log-likelihood ?)
2018/10/13補充：經寫信詢問，作者已回覆為筆誤，將於下一版更正此錯誤
Experiments
本篇針對四種不同資料集進行實驗，分別為 OntoNotes, MSRA, Weibo NER, Chinese resume，其中 OntoNotes 在訓練集、測試集、驗證集都有提供人工分詞，因此本實驗特別針對 OntoNotes 來比較使用人工分詞(word-based model) 和不使用，兩者之間的差距。
首先我們來看看 OntoNotes 驗證集，本實驗進行兩方法比較，一個是透過分詞器對驗證集作自動分詞(分詞器的訓練資料由訓練集的人工分詞而得)，另一方法則是以 character-based 不分詞的方法。
可以發現，分詞器因為分詞錯誤，會間接影響了 NER 的準確率，而不分詞的方法中，使用 softword & bichar 加入 character embedding 是相當有效的方法，但最終本論文提出 Lattice Model 還是優於其他方法，作者認為，使用 word information 來豐富 vector representation，相較於用 bichar 或 softword，是最直接、最有效的方式。
另一個實驗作在 OntoNotes 的測試集，這邊加入了人工分詞的結果一併加入比較，我們發現使用人工分詞的 word-based model 可拿到較佳的結果，但這其實也不意外，因為正確的分詞結果也意味著沒有 error propagation 的議題，因此不會有 trade-off，我們也從上面的結果看到幾個現象和結論：
- 不同的資料集中，character-based 都略勝於 word-based(auto seg)。
- Lattice model 在沒有人工分詞的情況下，為目前最優的方法。
- 即便使用人工分詞，Lattice model 仍優於部分的 gold seg 方法。
另外作者進行一個統計，由於 lattice model 中，那些候選詞彙都是由字典得來，發現字典所挑選的候選詞彙和實際 entity 的匹配率，會大大影響進步的幅度，以 MSRA 測試資料為例，候選詞彙和實際 entity 的匹配率有 73.76%，因此相較於 best character-based method的錯誤率減少了16.11% 之多，相反地，resume 資料由於訓練集和測試集詞彙涵蓋率僅有 28~29%，因此只見0.89% 微幅的進步。
當然如果一味著增加涵蓋率，那勢必 noise words 數量也會大大增加並影響模型的整體表現，因此作者也於 future work 提到候選詞彙涵蓋率和字典品質，將是下個階段要研究的議題。
作者也舉了一個例子，針對分詞錯誤會產生什麼後果，如上圖，可以發現當分詞器將「東莞台協會長」分成「東莞/台/協/會長」，則 NER 便無法標註出「東莞台協<org>」，此外使用 char+bichar+softword 由於沒有詞彙的資訊在裡面，因此模型將之分成「東莞台協會/長」，容易產生不符合文法的語言結構。
Conclusion
此篇針對無人工分詞的文本，提出了以 character-based model 為基底加上lattice word information，有效幫助模型判別出詞彙的命名實體，也免除傳統利用分詞器所帶來的 trade-off，為目前最好的中文 character-based NER 模型 。
在真實世界的應用中，存在著各式各樣不同領域的語料，我們很難一一進行人工分詞，因此透過此方法，我們能快速地搭建出一個準率度接近使用人工分詞的 NER 模型，這是十分貼近真實需求的應用，對於中文 NER 的發展有相當大的貢獻。
References
- Yue Zhang and Jie Yang. Chinese NER Using Lattice LSTM, Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (ACL), 2018.
- https://arxiv.org/pdf/1805.02023.pdf
