[探索] 語言模型基礎：Subword algorithms

一個好的自然語言模型，需要維持一個好的 vocabulary set。一旦我們向語言模型提問，出現了語言模型的 vocabulary set 未曾收錄的單字，語言模型就會產生 Out-of-Vocabulary 或 OOV 的問題。而 OOV 處理的情況，大致上分為兩種，一種就是直白的說了「我不知道」，另一種則是委婉地說了「我再查查看」。

前者語言模型會產生 UNK token，意思就是 Unknown（我不知道）。後者則被需使用 back-off 機制去處理。配有 back-off 的語言模型，需要維持數個不同精度的語言模型，當單詞不在最大精度的模型中，就「退到」次等精度模型查詢。以 n-gram 模型為例，若有一 n-gram 的 token 發生 OOV 的情況，back-off 機制就會「退到」 n-1 gram 的模型去查詢該 token，若仍舊在 unigram model 找不到該單詞，模型就會發出 UNK token。

1. 參數量的暴增：字彙的頻率分佈通常呈長尾的指數衰退，也就是在尾端充滿著出現頻率接近零的少見字。如果我們都把這些少見字都放進我們的 word-level vocabulary，我們就有 embedding 參數量的暴增問題，如果你不認識 embedding，建議你先從延伸閱讀讀起。
2. 無法模擬非標準字和錯字：面對社群網絡中常用的非標準字（如，Goooooood Vibesssssss），領域相關的技術字或錯字，如果沒有特別手工處理，word-level vocabulary 會將這些 tokens 都當作一個非相同且獨特的 vocabulary 。這樣的處理方式等同於將同樣語義的 token 分別用不同的表示法表示。這不僅不符合最簡表示，更進而削弱了統計能力。
3. 語詞形態（morphemes）豐富的字詞：對於像芬蘭語等語詞形態豐富字詞，word-level vocabulary 不能捕捉在不同字詞中同型態字首或字尾的語義，更無法對拼音相同的字詞產生關聯。如，對英語而言，副詞通常在字尾帶有 “ly” 。

上述的問題們，可以藉由建立一個 character-level 的模型來緩和。character-level 的模型，尤其在翻譯系統，可以採取直接拷貝的方法來進行，如人名等。對於同源的語言對，則可以藉由 character-level 的直接翻譯達成。 然而 character-level 的模型，雖然在解決前述問題相當有效率，但他們無法像 word-level vocabulary 的語言模型，能夠捕捉字詞間的長依賴關係。關於幾個使用不同字詞特徵建立語言模型的方法，可見延伸閱讀連結。

所以就有了第三種方法，那就是利用產生 subwords 的方式來自動建立 vocabulary。Subwords 是一個字詞中可擷取出來部分或全部連續序列。對於語詞形態，使用 subwords 的方法可以保留字詞的字尾或字首。對於沒有固定分割字元，（如，英文使用空白當作字詞間的分割字元）的語言，如中文等，則可以使用 subwords 在 byte-level 進行字詞分割。

目前依照如何納入 subwords 在模型中，主要有兩種方式，一種是當作字彙，另外一種則是將所有可能 subwords 列出，一併併入 word embedding 的計算中。前者，我們會介紹一種 greedy algorithm 來做 subwords segmentation。後者，我們將簡略提到修改 word2vec 模型，引入 subwords counts 的 FastText。

一個典型 subwords segmentation 演算法，名為 Byte Pair Encoding（BPE），最早是應用在 data compression ，除了是最早應用到單字分割的演算法，該演算法也被 Open AI 的 GPT2 使用。而該演算法的步驟如下：

1. Segment Criterion：將單詞字典裡的單詞都分割為字母大小的長度（byte 長度）。並使用 </W> token 來表示單詞結尾。
2. 建立一個記錄「字母對」與出現頻率的 dictionary。這個 dictionary 的鍵值是在步驟一產生在同一個單詞內相鄰的「字母對」，而值的部分則是該鍵值的出現頻率。
3. Merge Criterion：合併出現頻率最高的「字母對」將會被優先合併成一個新的 subword，並以該 subword 取代原來的字母對。
4. 重複步驟 2 和 3，直到達到所設下的 vocabulary size。

圖片來源：參考資料 [2]

BPE 可以不分割高頻率的字詞，但對於少見字彙分割比字詞還小的 subword，所以大幅減少 OOV 的問題。

BPE 中貪心合併的方法屬於 deterministic 執行，一個 stochastic 版本被稱為 BPE-dropout。在 dropout 版本中，是否進行合併是由一個極小的機率（p=0.1）所決定。使用 stochastic 的版本，主要是在訓練時提供調節的功能，預防 BPE 演算法陷入局部最佳解，而只產生一種 segmentation 結果。在 inference 的時候，仍是以原本的 BPE 演算法為實踐方法。透過應用 BPE-dropout 方法，能建立一個對拼錯字不敏感的強健語言模型。除此之外，BPE-dropout 證明能夠有效訓練低資源的語言模型。

這個簡單演算法，Google 在他們的 Neural Machine Translation (NMT) 經過修改後也使用上了。 Google NMT 更改成兩個版本，一個是 WordPiece，用在 BERT pre-train 模型上，另一個則是 SentencePiece。

WordPiece 和 BPE 最主要的不同在於 Merge Criterion。WordPiece 與 BPE 不同，它並不使用出現頻率來作為合併的條件，相反地它使用 maximizing the likelihood 的方式來最佳化合併的過程。除此之外，WordPiece 原本是應用在日文及韓文的語音系統，所以在演算法步驟一中所使用的 character 數目較多。此外 WordPiece 增加了一些特別的 token。使用 ‘_’ 來表示單字的開始（BPE 使用 </W> 表示字詞的結束’）。以及利用 <B> <M> <E> 分別代表少用單字的開始，中間和結束。使用這些 token prefix 是希望在翻譯系統中可以還原該單字，能以直接拷貝的方式處理。

至於 SentencePiece 則延伸 WordPiece 都是針對 UTF-8 來做為字母的最小單元，而非在 byte-level。使用 UTF-8 切割字元為最小單位有助於學習缺乏自然字詞界限，無法 pre-tokenized 的東方語言，如中文。此外，不像 WordPiece 演算法會先從已被 pre-tokenized Word-level 的字彙開始，SentencePiece 會從全句開始分割，並保留空白字元作為特殊 token。

左為 DPE 機械翻譯流程，右為 DPE transformer 架構圖片來源：參考資料 [4]

Dynamic Programming Encoding （DPE）則是架構在機械翻譯之上的一個 subword segmentation 演算法。這個方法是基於一個觀察，那就是對於翻譯的輸出而言，如何做 segmentation 方式不是很重要，只要輸出的位置正確即可。所以，使用 dynamic programming 將可能 segmentation 的方法都併入後驗機率的計算中。然而這樣的觀察，是對目標語言來說，來源語言仍需要準確的 segmentation 方式，所以在 DPE 構成的機械翻譯系統中，DPE 只獨立於 preprocessing 的架構中，而來源語言的 subword segmentation 演算法，仍使用 BPE 或 BPE-dropout（見上圖左）。DPE 的學習架構是利用一個混合字元與 subword 的 transformer decoder，負責輸出 subword 的 softmax 層，會在事先以 BPE 方法建立的 subword vocabulary 選出最有可能的 subword 輸出（見上圖右）。DPE 的 segmentation 結果，比起使用 BPE 更符合語言學（見下圖）。如保留單詞複數或副詞字尾的型態。

給定德文輸入，比較 BPE （BPE target）和 DPE （DPE target）兩個方法的輸出。圖片來源：參考資料 [3]

最後，要提到的是 FastText。這個方法也是利用 subword 的方式解決 OOV。和之前的 subword algorithm 不同的是，FastText 並不為 subword 創造出一個新的 vocabulary entry。相對地， FastText 仍舊使用 word2vec word-level 學習 word embedding 的模型，不一樣的是 FastText 會計算每一個單詞的 n-gram 表示，與原單詞一併相加計算貢獻。

參考資料：

1. 3 subword algorithms help to improve your NLP model performance（英）
2. Stanford 2019 CS224N #12 subword（英）
3. Complete Guide to Subword Tokenization Methods in the Neural Era（英）
4. Dynamic Programming Encoding for Subword Segmentation in Neural Machine Translation（英，DPE 論文）

延伸閱讀：

1. 深度學習甜點系列：以字頻為主的語言模型
2. 深度學習甜點系列：以單字為基礎的語言模型
3. 深度學習甜點系列：以字母為基礎的語言模型