Byte Pair Encoding（BPE）/WordPiece算法介绍

Subword算法如今已经成为了一个重要的NLP模型性能提升方法。自从2018年BERT横空出世横扫NLP界各大排行榜之后，各路预训练语言模型如同雨后春笋般涌现，其中Subword算法在其中已经成为标配。所以作为NLP界的小菜鸟，有必要了解下Subword算法的原理。

Intro

通常在英文NLP任务中，tokenization（分词）往往以空格为划分方式，但这种传统的分词方法还是存在一些问题，如：

• 传统词表示方法无法很好的处理未知或罕见的词汇（OOV问题）
• 传统词tokenization方法不利于模型学习词缀之间的关系
  • E.g. 模型学到的“old”, “older”, and “oldest”之间的关系无法泛化到“smart”, “smarter”, and “smartest”。
• Character embedding作为OOV的解决方法粒度太细
• Subword粒度在词与字符之间，能够较好的平衡OOV问题

针对这些缺点，越来越多人开始使用subword的相关tokenization方法，具体方法主要有BPE，WordPiece等。

1 BPE

BPE，（byte pair encoder）字节对编码，也可以叫做digram coding双字母组合编码，主要目的是为了数据压缩，算法描述为字符串里频率最常见的一对字符被一个没有在这个字符中出现的字符代替的层层迭代过程。具体在下面描述。该算法首先被提出是在Philip Gage的C Users Journal的 1994年2月的文章“A New Algorithm for Data Compression”。

第一次接触BPE算法是在Speech and Language Processing里看到的，具体可参考Introduction---Text Normalization中的BPE章节，那里面说的还是很详细的，推荐大家看看。

算法过程

输入：

{'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。

编码和解码

• 编码

在之前的算法中，我们已经得到了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>”

2 WordPiece

WordPiece算法可以看作是BPE的变种。不同点在于，WordPiece基于概率生成新的subword而不是下一最高频字节对。

算法

1. 准备足够大的训练语料
2. 确定期望的subword词表大小
3. 将单词拆分成字符序列
4. 基于第3步数据训练语言模型
5. 从所有可能的subword单元中选择加入语言模型后能最大程度地增加训练数据概率的单元作为新的单元
6. 重复第5步直到达到第2步设定的subword词表大小或概率增量低于某一阈值

Reference

一分钟搞懂的算法之BPE算法

深入理解NLP Subword算法：BPE、WordPiece、ULM