【NLP Subword】三大演算法原理：BPE、WordPiece、ULM

  • 2020 年 2 月 21 日
  • 筆記

編輯：夕小瑤的賣萌屋

正文作者：Luke

正文來源：https://zhuanlan.zhihu.com/p/86965595

前言

Subword演算法如今已經成為了一個重要的NLP模型性能提升方法。自從2018年BERT橫空出世橫掃NLP界各大排行榜之後，各路預訓練語言模型如同雨後春筍般湧現，其中Subword演算法在其中已經成為標配。且與傳統空格分隔tokenization技術的對比有很大的優勢~~

  • 傳統詞表示方法無法很好的處理未知或罕見的辭彙（OOV問題）
  • 傳統詞tokenization方法不利於模型學習詞綴之前的關係

E.g. 模型學到的「old」, 「older」, and 「oldest」之間的關係無法泛化到「smart」, 「smarter」, and 「smartest」。

  • Character embedding作為OOV的解決方法粒度太細
  • Subword粒度在詞與字元之間，能夠較好的平衡OOV問題

話不多說，和小夕一起來看一下當下最熱最火三個subword演算法叭o(*￣▽￣*)ブ

Byte Pair Encoding

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

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

演算法

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

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

每次合併後詞表可能出現3種變化：

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

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

例子

輸入：

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

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

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

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

{'l o w </w>': 5, 'l o w e r </w>': 2, 'n e w est </w>': 6, 'w i d est </w>': 3}
Iter 3, 以此類推，最高頻連續位元組對為"est"和"</w>" 輸出：
{'l o w </w>': 5, 'l o w e r </w>': 2, 'n e w est</w>': 6, 'w i d est</w>': 3}
Iter n, 繼續迭代直到達到預設的subword詞表大小或下一個最高頻的位元組對出現頻率為1。

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)' + bigram + r'(?!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 </w>': 5, 'l o w e r </w>': 2, 'n e w e s t </w>': 6, 'w i d e s t </w>': 3}  num_merges = 1000  for i in range(num_merges):      pairs = get_stats(vocab)      if not pairs:          break      best = max(pairs, key=pairs.get)      vocab = merge_vocab(best, vocab)      print(best)    # print output  # ('e', 's')  # ('es', 't')  # ('est', '</w>')  # ('l', 'o')  # ('lo', 'w')  # ('n', 'e')  # ('ne', 'w')  # ('new', 'est</w>')  # ('low', '</w>')  # ('w', 'i')  # ('wi', 'd')  # ('wid', 'est</w>')  # ('low', 'e')  # ('lowe', 'r')  # ('lower', '</w>')

編碼

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

我們從最長的token迭代到最短的token，嘗試將每個單詞中的子字元串替換為token。最終，我們將迭代所有tokens，並將所有子字元串替換為tokens。如果仍然有子字元串沒被替換但所有token都已迭代完畢，則將剩餘的子詞替換為特殊token，如<unk>。示例如下~~

# 給定單詞序列  [「the</w>」, 「highest</w>」, 「mountain</w>」]    # 假設已有排好序的subword詞表  [「errrr</w>」, 「tain</w>」, 「moun」, 「est</w>」, 「high」, 「the</w>」, 「a</w>」]    # 迭代結果  "the</w>" -> ["the</w>"]  "highest</w>" -> ["high", "est</w>"]  "mountain</w>" -> ["moun", "tain</w>"]

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

解碼

將所有的tokens拼在一起，示例如下：

# 編碼序列  [「the</w>」, 「high」, 「est</w>」, 「moun」, 「tain</w>」]    # 解碼序列  「the</w> highest</w> mountain</w>」

WordPiece

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

演算法

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

Unigram Language Model

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

演算法

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

總結

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

參考文獻

[1] https://en.wikipedia.org/wiki/Byte_pair_encoding

[2] https://leimao.github.io/blog/Byte-Pair-Encoding/

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

[4] Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates

VirMach 便宜 VPS

QNews

QNews