前言

Subword算法如今已經成為了一個重要的NLP模型性能提升方法。自從2018年BERT橫空出世橫掃NLP界各大排行榜之后，各路預訓練語言模型如同雨后春筍般涌現，其中Subword算法在其中已經成為標配。所以作為NLP界從業者，有必要了解下Subword算法的原理。

目錄

1. 與傳統空格分隔tokenization技術的對比
2. Byte Pair Encoding
3. WordPiece
4. Unigram Language Model
5. 總結

1. 與傳統空格分隔tokenization技術的對比

• 傳統詞表示方法無法很好的處理未知或罕見的詞匯（OOV問題）
• 傳統詞tokenization方法不利于模型學習詞綴之間的關系
  • E.g. 模型學到的“old”, “older”, and “oldest”之間的關系無法泛化到“smart”, “smarter”, and “smartest”。
• Character embedding作為OOV的解決方法粒度太細
• Subword粒度在詞與字符之間，能夠較好的平衡OOV問題

2. Byte Pair Encoding (Sennrich et al., 2015)

BPE(字節對)編碼或二元編碼是一種簡單的數據壓縮形式，其中最常見的一對連續字節數據被替換為該數據中不存在的字節。后期使用時需要一個替換表來重建原始數據。OpenAI GPT-2 與Facebook RoBERTa均采用此方法構建subword vector.

• 優點
  • 可以有效地平衡詞匯表大小和步數(編碼句子所需的token數量)。
• 缺點
  • 基于貪婪和確定的符號替換，不能提供帶概率的多個分片結果。

2.1 算法

1. 準備足夠大的訓練語料
2. 確定期望的subword詞表大小
3. 將單詞拆分為字符序列并在末尾添加后綴“ ”，統計單詞頻率。本階段的subword的粒度是字符。例如，“ low”的頻率為5，那么我們將其改寫為“ l o w ”：5
4. 統計每一個連續字節對的出現頻率，選擇最高頻者合并成新的subword
5. 重復第4步直到達到第2步設定的subword詞表大小或下一個最高頻的字節對出現頻率為1

停止符""的意義在于表示subword是詞后綴。舉例來說："st"字詞不加""可以出現在詞首如"st ar"，加了""表明改字詞位于詞尾，如"wide st"，二者意義截然不同。

每次合并后詞表可能出現3種變化：

• +1，表明加入合并后的新字詞，同時原來的2個子詞還保留（2個字詞不是完全同時連續出現）
• +0，表明加入合并后的新字詞，同時原來的2個子詞中一個保留，一個被消解（一個字詞完全隨著另一個字詞的出現而緊跟著出現）
• -1，表明加入合并后的新字詞，同時原來的2個子詞都被消解（2個字詞同時連續出現）

實際上，隨著合并的次數增加，詞表大小通常先增加后減小。

例子

輸入：

{'l o w ': 5, 'l o w e r ': 2, 'n e w e s t ': 6, 'w i d e s t ': 3}

Iter 1, 最高頻連續字節對"e"和"s"出現了6+3=9次，合并成"es"。輸出：

{'l o w ': 5, 'l o w e r ': 2, 'n e w es t ': 6, 'w i d es t ': 3}

Iter 2, 最高頻連續字節對"es"和"t"出現了6+3=9次, 合并成"est"。輸出：

{'l o w ': 5, 'l o w e r ': 2, 'n e w est ': 6, 'w i d est ': 3}

Iter 3, 以此類推，最高頻連續字節對為"est"和"" 輸出：

{'l o w ': 5, 'l o w e r ': 2, 'n e w est': 6, 'w i d est': 3}

……

Iter n, 繼續迭代直到達到預設的subword詞表大小或下一個最高頻的字節對出現頻率為1。

2.2 BPE實現

import re, collections

def get_stats(vocab):
    pairs = collections.defaultdict(int)
    for word, freq in vocab.items():
        symbols = word.split()
        for i in range(len(symbols)-1):
            pairs[symbols[i],symbols[i+1]] += freq
    return pairs

def merge_vocab(pair, v_in):
    v_out = {}
    bigram = re.escape(' '.join(pair))
    p = re.compile(r'(?\\S)''(?!\\S)')
    for word in v_in:
        w_out = p.sub(''.join(pair), word)
        v_out[w_out] = v_in[word]
    return v_out

vocab = {'l o w ': 5, 'l o w e r ': 2, 'n e w e s t ': 6, 'w i d e s t ': 3}
num_merges = 1000
for i in range(num_merges):
    pairs = get_stats(vocab)
    ifnot pairs:
        break
    best = max(pairs, key=pairs.get)
    vocab = merge_vocab(best, vocab)
    print(best)

# print output
# ('e', 's')
# ('es', 't')
# ('est', '')
# ('l', 'o')
# ('lo', 'w')
# ('n', 'e')
# ('ne', 'w')
# ('new', 'est')
# ('low', '')
# ('w', 'i')
# ('wi', 'd')
# ('wid', 'est')
# ('low', 'e')
# ('lowe', 'r')
# ('lower', '')

2.3 編碼和解碼

• 編碼

在之前的算法中，我們已經得到了subword的詞表，對該詞表按照子詞長度由大到小排序。編碼時，對于每個單詞，遍歷排好序的子詞詞表尋找是否有token是當前單詞的子字符串，如果有，則該token是表示單詞的tokens之一。

我們從最長的token迭代到最短的token，嘗試將每個單詞中的子字符串替換為token。最終，我們將迭代所有tokens，并將所有子字符串替換為tokens。如果仍然有子字符串沒被替換但所有token都已迭代完畢，則將剩余的子詞替換為特殊token，如。

例子

# 給定單詞序列
[“the</w>”, “highestspanw>”, “mountain”]

# 假設已有排好序的subword詞表
[“errrr</w>”, “tainspanw>”, “moun”, “est</w>”, “high”, “thespanw>”, “a”]

# 迭代結果
"the" -> ["the"]
"highest" -> ["high", "est"]
"mountain" -> ["moun", "tain"]

編碼的計算量很大。在實踐中，我們可以pre-tokenize所有單詞，并在詞典中保存單詞tokenize的結果。如果我們看到字典中不存在的未知單詞。我們應用上述編碼方法對單詞進行tokenize，然后將新單詞的tokenization添加到字典中備用。

• 解碼

將所有的tokens拼在一起。

例子：

# 編碼序列
[“theclass="hljs-name"w>”, “high”, “estclass="hljs-name"w>”, “moun”, “tainclass="hljs-name"w>”]

# 解碼序列
“theclass="hljs-name"w> highestclass="hljs-name"w> mountainclass="hljs-name"w>”

3. WordPiece (Schuster et al., 2012)

WordPiece算法可以看作是BPE的變種。不同點在于，WordPiece基于概率生成新的subword而不是下一最高頻字節對。

3.1 算法

1. 準備足夠大的訓練語料
2. 確定期望的subword詞表大小
3. 將單詞拆分成字符序列
4. 基于第3步數據訓練語言模型
5. 從所有可能的subword單元中選擇加入語言模型后能最大程度地增加訓練數據概率的單元作為新的單元
6. 重復第5步直到達到第2步設定的subword詞表大小或概率增量低于某一閾值

4. Unigram Language Model (Kudo, 2012)

ULM是另外一種subword分隔算法，它能夠輸出帶概率的多個子詞分段。它引入了一個假設：所有subword的出現都是獨立的，并且subword序列由subword出現概率的乘積產生。WordPiece和ULM都利用語言模型建立subword詞表。

4.1 算法

1. 準備足夠大的訓練語料
2. 確定期望的subword詞表大小
3. 給定詞序列優化下一個詞出現的概率
4. 計算每個subword的損失
5. 基于損失對subword排序并保留前X%。為了避免OOV，建議保留字符級的單元
6. 重復第3至第5步直到達到第2步設定的subword詞表大小或第5步的結果不再變化

5. 總結

1. subword可以平衡詞匯量和對未知詞的覆蓋。極端的情況下，我們只能使用26個token（即字符）來表示所有英語單詞。一般情況，建議使用16k或32k子詞足以取得良好的效果，Facebook RoBERTa甚至建立的多達50k的詞表。
2. 對于包括中文在內的許多亞洲語言，單詞不能用空格分隔。因此，初始詞匯量需要比英語大很多。

參考資料

https://en.wikipedia.org/wiki/Byte_pair_encoding

https://leimao.github.io/blog/Byte-Pair-Encoding/https://link.zhihu.com/?target=https%3A//arxiv.org/abs/1804.10959)

https://medium.com/@makcedward/how-subword-helps-on-your-nlp-model-83dd1b836f46

https://arxiv.org/abs/1804.10959