一個好的自然語言模型，需要維持一個好的 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。
想在訓練期間，減少執行期間 OOV 產生的方法，若 vocabulary set 仍是維持 word-level 的精度，最直覺的方法，便是使用字彙量㥛多的巨量 corpus 來訓練語言模型。 然而，這麼做有以下下列問題：
- 參數量的暴增：字彙的頻率分佈通常呈長尾的指數衰退，也就是在尾端充滿著出現頻率接近零的少見字。如果我們都把這些少見字都放進我們的 word-level vocabulary，我們就有 embedding 參數量暴增的問題，如果你不認識 embedding，建議你先從延伸閱讀讀起。
- 無法模擬非標準字和錯字：面對社群網絡中常用的非標準字（如，Goooooood Vibesssssss），領域相關的技術字或錯字，如果沒有特別手工前置處理，word-level vocabulary 會將這些 tokens 都當作一個非相同且獨特的 vocabulary 。這樣的處理方式等同於將同樣語義的 token 分別用不同的表示法表示。這不僅不符合最簡表示，更進而削弱了統計能力。
- 語詞形態（morphemes）豐富的字詞：對於像芬蘭語等語詞形態豐富的語言，word-level vocabulary 不能捕捉在不同字詞中同型態的字首或字尾的語義，更無法對拼音相似的字詞產生關聯。如，對英語而言，副詞通常在字尾帶有 “ly” 。
上述的問題們，可以藉由建立一個 character-level 的模型來緩和。Character-level 的模型，尤其在翻譯系統，可以採取直接拷貝的方法來進行，如人名等。對於同源的語言對，則可以藉由 character-level 的直接翻譯達成。 然而 character-level 的模型，雖然在解決前述問題相當有效率，但他們無法像 word-level vocabulary 的語言模型，能夠捕捉字詞間的長依賴關係。關於幾個使用不同字詞特徵建立語言模型的方法，請見延伸閱讀中的連結文章。
所以就有了第三種方法，那就是利用產生 subwords 的方式來自動建立 vocabulary。Subwords 其實就是 substring，也就是一個字詞中可擷取出來部分或全部在字詞中連續的字母序列。對於語詞形態，使用 subwords 的方法可以保留字詞的字尾或字首。對於沒有固定分割字元，（如，英文使用空白當作字詞間的分割字元）的語言，如中文等，則可以使用 subwords 在 byte-level 進行字詞分割。
目前依照如何納入 subwords 在模型中，主要有兩種方式，一種是直接豐富vocabulary set，另外一種則是豐富單詞的連續表現方法。前者的代表是 Byte Pair Encoding（BPE）和他的繼承者（WordPiece 和 SentencePiece 等）。後者的代表則是由 Facebook 提出的 Fasttext。
BPE 最早是應用在 data compression ，也是最早應用到單字分割（subwords segmentation）的演算法。它的本質是 greedy 意思就是說它不能提供最佳解。該演算法被 Open AI 的 GPT2 和 Facebook 的 XLM 使用「註一」。而該演算法的步驟簡述如下：
- Segment Criterion：將 vocabulary set 裡的單詞都分割為字母大小的長度（byte 長度）。並使用 </W> token 來表示單詞結尾。
- 建立一個記錄「字母對」與出現頻率的 dictionary。這個 dictionary 的鍵值是在步驟一產生在同一個單詞內相鄰的「字母對」，而值的部分則是該鍵值的出現頻率。
- Merge Criterion：合併出現頻率最高的「字母對」將會被優先合併成一個新的 subword，並以該 subword 取代原來的字母對。
- 重複步驟 2 和 3，直到達到所設下的 vocabulary size。
上圖來自延伸閱讀 [2]。主要是呈現兩個 merge 步驟的 BPE 演算法。
這個簡單演算法，Google 在他們的 Neural Machine Translation (NMT) 經過修改後也使用上了。 Google NMT 更改成兩個版本，一個是 WordPiece，用在 BERT pre-train 模型上，另一個則是 SentencePiece。
WordPiece 和 BPE 最主要的不同在於 Merge Criterion。WordPiece 與 BPE 不同，它並不使用出現頻率來作為合併的條件，相反地它使用 maximizing the likelihood 的方式來最佳化合併的過程。
至於 SentencePiece 則延伸 WordPiece ，並採取與 BPE 不相同的 Segment Criterion，也就是使用 UTF-8 encode 方式來做分割。針對 UTF-8 來做為最小分割單元，而非 byte，是因為使用 UTF-8 切割字元為最小單位有助於學習缺乏自然字詞界限，無法 pre-tokenized 的東方語言，如中文。此外，不像 WordPiece 演算法會先從已被 pre-tokenized Word-level 的字彙開始，SentencePience 會從全句開始分割，並保留空白字元作為特殊 token。 SententcePiece 的作者之一，另外使用 Unigram model 來建立多重 subwords 模型。作者認為使用多個 subword segmentation 方式，有助於調節模型。
最後，要提到的是 FastText。這個方法也是利用 subwords 的方式解決 OOV。和之前的 subword algorithms 不同的是，FastText 並不為 subword 創造出一個新的 vocabulary entry。相對地， FastText 會計算每一個單詞的 back-off ，並與原單詞一併相加計算貢獻， 用來作 w2v word-level embedding 的最後計算結果。
註釋：
- 嚴格說來 XLM 是使用 fastBPE，這是一個使用 C++ 重新優化 BPE 的演算法。
參考資料：
- 3 subword algorithms help to improve your NLP model performance（英）
- Stanford 2019 CS224N #12 subword（英）
