NLP中Tokenizers总结（BPE、WordPiece、Unigram和SentencePiece）

1. 介绍

        在NLP中，模型如Bert、GPT）的输入通常需要先进行tokenize，其目的是将输入的文本流，切分为一个个子串，每个子串都有完整的语义，便于学习embedding表达和后续模型的使用。tokenize有三种粒度：word/subword/char。

• word/词：词是最自然的语言单元，对于英文来说其天然存在空格进行，切分相对容易，常用的分词器有spaCy和Moses 。中文不具备这样的分割符，所以相对困难一些，不过目前也有Jieba、HanLP、LTP等分词器，这些分词器基于规则与模型，可以取得良好的分词效果。使用词时会有2个问题：1.词表通常是基于语料进行分词获得，但遇到新的语料时可能会出现OOV的情况；2.词表过于庞大，对于模型来说大部分参数都集中在输入输出层，不利于模型学习，且容易爆内存（显存）。通常情况下词表大小不超过5w。
• char/字符：字符是一种语言最基本的组成单元，如英文中的'a','b','c'或中文中的‘你’,‘我’,‘他’等。使用字符有如下问题：1.字符数量是有限的通常数量较少，这样在学习每个字符的embedding向量时，每个字符中包含非常多的语义，学习起来比较困难；2.以字符分割，会造成序列长度过长，对后续应用造成较大限制。
• subword/子词：它介于char和word之间，可以很好的平衡词汇量和语义独立性。它的切分准则是常用的词不被切分，而不常见的词切分为子词。

2. 子词算法

2.1. Byte Pair Encoding (BPE)

        BPE最早是一种数据压缩算法，由Sennrich等人于2015年引入到NLP领域并很快得到推广，可参考Neural Machine Translation of Rare Words with Subword Units (Sennrich et al., 2015) 。该算法简单有效，因而目前它是最流行的方法。GPT-2和RoBERTa使用的Subword算法都是BPE。

算法

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。

2.2 WordPiece

        WordPiece与BPE非常相似，也是每次从词表中选出两个子词合并成新的子词，可参考Japanese and Korean Voice Search (Schuster et al., 2012)。区别在于，BPE选择频数最高的相邻子词合并，而WordPiece选择能够提升语言模型概率最大的相邻子词加入词表。

        也许你还不清楚WordPiece是如何选取子词的，接下来详细说明下WordPiece在合并这一步是如何做的。假设句子$S= \left ( t_{1},t_{2}, ...,t_{n}\right )$是由n个子词组成，$t_{i}$表示子词，且假设各个子词之间是独立存在的，则句子S的语言模型似然值等价与所有子词概率的乘积：

$\large logP(S)=\sum_{i=1}^{n}logP(t_{i})$

 假设把相邻位置的x和y两个子词进行合并，合并后产生的子词为z，此时句子S似然值的变化可表示为：

可以看见似然值的变化就是两个子词之间的互信息。简而言之，WordPiece每次选择合并的两个子词，他们具有最大的互信息，也就是两个子词在语言模型上具有较强的关联性，它们经常在语料中以相邻的方式同时出现。

2.3 Unigram Language Model(ULM)

        ULM的介绍可参考 Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (Kudo, 2018)。Unigram与BPE和WordPiece的区别在于，BPE和Worpiece算法的词表都是一点一点增加，由小到大的。而Unigram则是先初始化一个非常巨大的词表，然后根据标准不断的丢弃，知道词表大小满足限定条件。Unigram算法考虑了句子的不同分词可能，因而能够出输出带概率的子词分段。

接下来，我们看看ULM是如何操作的。

对于句子S，为句子的一个分词结果，由m个子词组成。所以，当前分词下句子S的似然值可以表示为：

对于句子S，挑选似然值最大的作为分词结果，则可以表示为

这里U(x)包含了句子的所有分词结果。在实际应用中，词表大小有上万个，直接罗列所有可能的分词组合不具有操作性。针对这个问题，可通过维特比算法得到来解决。

那怎么求解每个子词的概率P(xi)呢？ULM通过EM算法来估计。假设当前词表V, 则M步最大化的对象是如下似然函数：

其中，|D|是语料库中语料数量。上述公式的一个直观理解是，将语料库中所有句子的所有分词组合形成的概率相加。

但是，初始时，词表V并不存在。因而，ULM算法采用不断迭代的方法来构造词表以及求解分词概率：

1. 初始时，建立一个足够大的词表。一般，可用语料中的所有字符加上常见的子字符串初始化词表，也可以通过BPE算法初始化。
2. 针对当前词表，用EM算法求解每个子词在语料上的概率。
3. 对于每个子词，计算当该子词被从词表中移除时，总的loss降低了多少，记为该子词的loss。
4. 将子词按照loss大小进行排序，丢弃一定比例loss最小的子词(比如20%)，保留下来的子词生成新的词表。这里需要注意的是，单字符不能被丢弃，这是为了避免OOV情况。
5. 重复步骤2到4，直到词表大小减少到设定范围。

可以看出，ULM会保留那些以较高频率出现在很多句子的分词结果中的子词，因为这些子词如果被丢弃，其损失会很大。

3.  SentencePiece

       上述的所有算法都有一个前提：输入以空格来进行区分。然而并不是所有语言的词语都是使用空格来进行分割（比如中文、日文），一种比较常见的做法是使用预分词。为了更加一般化的解决这个问题，谷歌推出了开源工具包SentencePiece 。SentencePiece是把一个句子看做一个整体，再拆成片段，而没有保留天然的词语的概念。一般地，它把space也当做一种特殊的字符来处理，再用BPE或者Unigram算法来构造词汇表。比如，XLNetTokenizer就采用了_来代替空格，解码的时候会再用空格替换回来。目前，Tokenizers库中，所有使用了SentencePiece的都是与Unigram算法联合使用的，比如ALBERT、XLNet、Marian和T5.

4. 举例

4.1 BertTokenizer/WordPiece

from transformers import BertTokenizer
tokenizer = BertTokenizer.from_pretrained("bert-base-uncased")

        Text:  I have a new GPU!