在自然語言的文字處理步驟中，第一步就是將文字轉為某種數字表達式。舉例詞向量(word embedding)來說，我們就以一個字典將每個詞對應到一個詞向量上。然而常常在真實世界中總是會出現不在你字典中的新詞彙，這時候只能以一個表達未知的符號來代替該字。另外語言的詞彙太多，如果將所有詞彙對應到一個詞向量模型將會變得太大無法在一般的電腦上運行(3百萬詞彙的 FastText 就需要6GB 的記憶體)。

為了解決這種資訊缺失問題，過去研究員提出字元向量(character embedding)、將字元用類神經網路轉為詞向量1、用n-gram表達詞以生成詞向量(FastText)。以上三個方法都有其優缺點，字元向量( character embedding )能表達的資訊並不多且容易導入雜訊, 但能解決OOV問題、用類神經將一串字元對應到詞向量加重訓練負擔、FastText的超參數n是固定的對於很容易受到錯字影響。今天我想說說是我認為在2019年中權衡了未知詞問題(Out-of-vocabulary OOV) 問題與控制降低詞典大小的方法： Byte Pair Encoding。在講BPE 前請容許我筆記一下，sub word encoding (子字元表達)的方法。

[1] Improved Graph-Based Dependency Parsing via Hierarchical LSTM Networks

FastText

Sub-word encoding

為了權衡使用字元表達的向量所帶來的靈活與詞向量的資訊豐富性，過去的論文嘗試將詞做有效的拆解成子詞彙的方式。例如 2017年的 FastText 提出將詞以字元的 n-gram 向量的總和來表達、與2016 年提出用 Byte Pair Encoding 來做語言翻譯、還有與BPE 很相似的WordPiece。

相比FastText, BPE 可以精確的控制字典的大小且它沒有像FastText因為將子詞做加總而導致資訊丟失。舉例 FastText 在 3-gram 下，會將 where 由 { wh, whe, her, ere, re } 的子詞向量表達，而where 的向量就是這些向量的總和。而BPE 則是將 where 由 { _wh, er, e } 這三個向量表達。

而WordPiece 與 BPE 的概念非常類似，其中WordPiece是從既有的詞彙中做拆分而BPE則是從既有的字元做結合，WordPiece 是 top down approach 而 BPE 則是 bottom up approach。兩者都可以控制詞典大小，但我認為 BPE 應該不會有面對 OOV 的問題，因為語言一定是由既有的字元組成（即一種編碼組成一連串的資訊）。而面對新的詞彙、只要其子組合非常特殊、且不存在先前的訓練資料中WordPiece 且 vocabulary數目不大，還是會OOV 的問題。

What is Byte Pair Encoding

BPE 最早由Philip Gage 提出，用來做數據壓縮上。它的原理是將常見連續的兩個符號以另一個符號表達。例如 ababab 中 a 後面很常接著 b 我們就用 c 表達 ab，並得到一個新的序列 ccc，c=ab 。

那BPE的字典在NLP中又是如何生成的呢？為了可以控制詞典的大小，我們就首先預設一個我們電腦記憶體可以容得下的詞典大小K。這個大小範圍在該語言的所有字元總數( N )與所有詞彙總數( M )之間( \(N << M, N < K < M\) )。從所字元的詞典開始，我們根據訓練資料中統計最常出現的字元

根據每個符號的前後對的頻率 (a,b)，我們將出現頻率最高的一對以一個新的符號表示，舉例 (a,b) 對出現頻率最高，那麼新的符號就是 “ab”, 將這個新的符號加入現有的所有符號中，再統計一次並找出新的符號。這動作一直重複到符號的數量等於我們定義的 K。而這些符號的集合就是我們的字典，而字典中就可會混合常見的詞（例如英文的話就會有 is, are, we, us…）。

2017 年提出的 BPEmb: Tokenization-free Pre-trained Subword Embeddings in 275 Languages，就是用BPE來tokenize語料，並用 Glove 來訓練word embedding。從論文中可以看到不同的字典大小，句子的表達形式也不一樣。

\(字典大小^{*}\)	用 BPE 處理後的句子(符號間以空格隔開)
-（原本句子）	toyoda station is a railway station on the chu ̄o ̄ main line
小	to y od a _station _is _a _r ail way _station _on _the _ch u ̄ o ̄ _main _l ine
中	toy oda _station _is _a _rail way _station _on _the _ch u ̄ o ̄ _main _line
大	toy oda _station _is _a _railway _station _on _the _chu ̄o ̄ _main_line

\(^{*}\) 字典大小的意思是指做配對次數，大：做10萬次配對、中：1萬次配對、小：做1千次配對

以上的表格可以看出，不同的字典大小，每個詞的表達也不太一樣。例如配對次數很少的時候， chu ̄o ̄ 被切分成 {chu,u, o} 三個符號，隨著字典越來越大，最後被合成了它最終表達的詞。底線的意思是為了表達一個詞的開始。

2015 年最先使用 BPE 在自然語言翻譯上的論文：Neural Machine Translation of Rare Words with Subword Units 的pseudo code 如下：

Conclusion

看完BPE 以後我的感想是：BPE 的詞典大小象徵了我們小時候認識語言的方法。3歲時，我們先學會英文的26個字母，接著學習一些簡單簡短的單詞，從這些單詞中的字音我們學習如何正確拼出其他更複雜的單字。例如 daddy 可以從 {dad, dy} 拼成。另外如果將單字先以簡單的子詞拼出，在訓練中階段性的換成更長的字詞( 第一階段先用 { da, d, d, dy } 來表示 daddy, 第二階段再替換更長的字詞 { dad, dy } )，也許會有意料之外的效果。