前言

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

目錄

1. 與傳統(tǒng)空格分隔tokenization技術(shù)的對比
2. Byte Pair Encoding
3. WordPiece
4. Unigram Language Model
5. 總結(jié)

1. 與傳統(tǒng)空格分隔tokenization技術(shù)的對比

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

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

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

• 優(yōu)點(diǎn)
  • 可以有效地平衡詞匯表大小和步數(shù)(編碼句子所需的token數(shù)量)。
• 缺點(diǎn)
  • 基于貪婪和確定的符號(hào)替換，不能提供帶概率的多個(gè)分片結(jié)果。

2.1 算法

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

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

每次合并后詞表可能出現(xiàn)3種變化：

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

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

例子

輸入：

{'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, 最高頻連續(xù)字節(jié)對"e"和"s"出現(xiàn)了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, 最高頻連續(xù)字節(jié)對"es"和"t"出現(xiàn)了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, 以此類推，最高頻連續(xù)字節(jié)對為"est"和"" 輸出：

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

……

Iter n, 繼續(xù)迭代直到達(dá)到預(yù)設(shè)的subword詞表大小或下一個(gè)最高頻的字節(jié)對出現(xiàn)頻率為1。

2.2 BPE實(shí)現(xiàn)

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 編碼和解碼

• 編碼

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

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

例子

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

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

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

編碼的計(jì)算量很大。在實(shí)踐中，我們可以pre-tokenize所有單詞，并在詞典中保存單詞tokenize的結(jié)果。如果我們看到字典中不存在的未知單詞。我們應(yīng)用上述編碼方法對單詞進(jìn)行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的變種。不同點(diǎn)在于，WordPiece基于概率生成新的subword而不是下一最高頻字節(jié)對。

3.1 算法

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

4. Unigram Language Model (Kudo, 2012)

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

4.1 算法

1. 準(zhǔn)備足夠大的訓(xùn)練語料
2. 確定期望的subword詞表大小
3. 給定詞序列優(yōu)化下一個(gè)詞出現(xiàn)的概率
4. 計(jì)算每個(gè)subword的損失
5. 基于損失對subword排序并保留前X%。為了避免OOV，建議保留字符級的單元
6. 重復(fù)第3至第5步直到達(dá)到第2步設(shè)定的subword詞表大小或第5步的結(jié)果不再變化

5. 總結(jié)

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

參考資料

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