大模型中的Tokenizer

在使用GPT 、BERT模型输入词语常常会先进行tokenize 。

tokenize的目标是把输入的文本流，切分成一个个子串，每个子串相对有完整的语义，便于学习embedding表达和后续模型的使用。

一、粒度

三种粒度：word/subword/char

word词，是最自然的语言单元。对于英文等自然语言来说，存在着天然的分隔符，比如说空格，或者是一些标点符号，对词的切分相对容易。但是对于一些东亚文字包括中文来说，就需要某种分词算法才行。顺便说一下，Tokenizers库中，基于规则切分部分，采用了spaCy和Moses两个库。如果基于词来做词汇表，由于长尾现象的存在，这个词汇表可能会超大。像Transformer XL库就用到了一个26.7万个单词的词汇表。这需要极大的embedding matrix才能存得下。embedding matrix是用于查找取用token的embedding vector的。这对于内存或者显存都是极大的挑战。常规的词汇表，一般大小不超过5万。
char/字符, 也就是说，我们的词汇表里只有最基本的字符。而一般来讲，字符的数量是少量有限的。这样做的问题是，由于字符数量太小，我们在为每个字符学习嵌入向量的时候，每个向量就容纳了太多的语义在内，学习起来非常困难。
subword子词级，它介于字符和单词之间。比如说Transformers可能会被分成Transform和ers两个部分。这个方案平衡了词汇量和语义独立性，是相对较优的方案。它的处理原则是，常用词应该保持原状，生僻词应该拆分成子词以共享token压缩空间

二、不同tokenize的策略比较

1、word-level

这些分词的方法都是将句子拆分为词，即word-level，这么做的优缺点是：

优点：能够保存较为完整的语义信息

缺点：

1、词汇表会非常大，大的词汇表对应模型需要使用很大的embedding层，这既增加了内存，又增加了时间复杂度。

2、 word-level级别的分词略显粗糙，无法发现更加细节的语义信息，例如模型学到的“old”, “older”, and “oldest”之间的关系无法泛化到“smart”, “smarter”, and “smartest”。

3、word-level级别的分词对于拼写错误等情况的鲁棒性不好；

4、 oov问题不好解决

2、char-level

一个简单的方法就是将word-level的分词方法改成 char-level的分词方法，对于英文来说，就是字母界别的，比如 "China"拆分为"C","h","i","n","a"，对于中文来说，"中国"拆分为"中"，"国"，

优点：

1、这可以大大降低embedding部分计算的内存和时间复杂度，以英文为例，英文字母总共就26个，中文常用字也就几千个。

2、char-level的文本中蕴含了一些word-level的文本所难以描述的模式，因此一方面出现了可以学习到char-level特征的词向量FastText，另一方面在有监督任务中开始通过浅层CNN、HIghwayNet、RNN等网络引入char-level文本的表示；

缺点：

1、但是这样使得任务的难度大大增加了，毕竟使用字符大大扭曲了词的意义，一个字母或者一个单中文字实际上并没有任何语义意义，单纯使用char-level往往伴随着模型性能的下降；

2、增加了输入的计算压力，原本”I love you“是3个embedding进入后面的cnn、rnn之类的网络结构，而进行char-level拆分之后则变成 8个embedding进入后面的cnn或者rnn之类的网络结构，这样计算起来非常慢；

3、subword-level

subword-level的分词方式遵循的原则是：尽量不分解常用词，而是将不常用词分解为常用的子词，

例如，"annoyingly"可能被认为是一个罕见的单词，并且可以分解为"annoying"和"ly"。"annoying"并"ly"作为独立的子词会更频繁地出现，同时，"annoyingly"是由"annoying"和"ly"这两个子词的复合含义构成的复杂含义，这在诸如土耳其语之类的凝集性语言中特别有用，在该语言中，可以通过将子词串在一起来形成（几乎）任意长的复杂词。

subword-level的分词方式使模型相对合理的词汇量（不会太多也不会太少），同时能够学习有意义的与上下文无关的表示形式（另外，subword-level的分词方式通过将模型分解成已知的子词，使模型能够处理以前从未见过的词（oov问题得到了很大程度上的缓解）。

三. 常用tokenize算法

最常用的三种tokenize算法：BPE（Byte-Pair Encoding），WordPiece和SentencePiece

3.1 Byte-Pair Encoding (BPE) / Byte-level BPE

BPE

首先，它依赖于一种预分词器pretokenizer来完成初步的切分。pretokenizer可以是简单基于空格的，也可以是基于规则的；
分词之后，统计每个词出现的频次供后续计算使用。例如，我们统计到了5个词的词频

("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5)

建立基础词汇表，包括所有的字符，即：

["b", "g", "h", "n", "p", "s", "u"]

根据规则，我们分别考察2-gram，3-gram的基本字符组合，把高频的ngram组合依次加入到词汇表当中，直到词汇表达到预定大小停止。比如，我们计算出ug/un/hug三种组合出现频次分别为20，16和15，加入到词汇表中。
最终词汇表的大小 = 基础字符词汇表大小 + 合并串的数量，比如像GPT，它的词汇表大小 40478 = 478(基础字符) + 40000（merges）。添加完后，我们词汇表变成：

["b", "g", "h", "n", "p", "s", "u", "ug", "un", "hug"]

实际使用中，如果遇到未知字符用<unk>代表。

以语料：

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

为例，假设我们对原始的文本进行分词之后只有上面4个词，则：

1、对每个词进行词频统计，并且对每个词末尾的字符转化为末尾字符和</w>两个字符，停止符"</w>"的意义在于表示subword是词后缀。举例来说："st"字词不加"</w>"可以出现在词首如"st ar"，加了"</w>"表明改字词位于词尾，如"wide st</w>"，二者意义截然不同。

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

此时我们的词表为

{"l","o",'w',"e","r","</w>","n","s","t","i"}

2、统计每一个连续字节对的出现频率，选择最高频者合并成新的subword

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

最高频连续字节对"e"和"s"出现了6+3=9次，合并成"es"

需要注意的是，"es"生成后会消除"s"，因为上述语料中 "s"总和"es"共同出现，但是s除了"es"外就没有其它的字符组合出现了，所以"s"被消除，但是"e"在"lower"中出现过有"er"或"we"这样的组合，所以"e"没有被消除，此时词表变化为：

{"l","o",'w',"e","r","</w>","n","es","t","i"}

（补充另外两种情况：

如果es中的e和s都是和es一起出现，除此之外没有单独再出现其它的字符组合，则es一起消除；如果es中的e和s都各自有和其它字符的组合，则e和s都不会被消除，但是多了个新词es）

3、继续上述过程：

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

此时最高频连续字节对"es"和"t"出现了6+3=9次, 合并成"est"。输出：

同理，上一步的词表中"t"被消除，"est"加入此表

......

继续迭代直到达到人工预设的subword词表大小或下一个最高频的字节对出现频率为1。

上述就完成了编码过程，得到了词表，然后要把原始的word-level的分词结果进行相应转化：

1、将此表按照其中token的长度，从长到短排列；

例如排序好之后的词表为：

[“errrr</w>”, “tain</w>”, “moun”, “est</w>”, “high”, “the</w>”, “a</w>”]

2、对原始的word-level的分词结果进行转化，例如原始的语料为：

[“the</w>”, “highest</w>”, “mountain</w>”]

则转化为：

"the</w>" -> ["the</w>"]
"highest</w>" -> ["high", "est</w>"]
"mountain</w>" -> ["moun", "tain</w>"]

这样就完成了BPE的分词了；

Byte-level BPE

BPE的一个问题是，如果遇到了unicode，基本字符集可能会很大。一种处理方法是我们以一个字节为一种“字符”，不管实际字符集用了几个字节来表示一个字符。这样的话，基础字符集的大小就锁定在了256。

例如，像GPT-2的词汇表大小为50257 = 256 + <EOS> + 50000 mergers，<EOS>是句子结尾的特殊标记。

3.2 WordPiece

WordPiece，从名字好理解，它是一种子词粒度的tokenize算法subword tokenization algorithm，很多著名的Transformers模型，比如BERT/DistilBERT/Electra都使用了它。

它的原理非常接近BPE，不同之处在于，它在做合并的时候，并不是每次找最高频的组合，而是找能够最大化训练集数据似然的merge，即它每次合并的两个字符串A和B，应该具有最大的 P(AB)P(A)P(B) 值。合并AB之后，所有原来切成A+B两个tokens的就只保留AB一个token，整个训练集上最大似然变化量与 P(AB)P(A)P(B) 成正比。

3.3 Unigram

与BPE或者WordPiece不同，Unigram的算法思想是从一个巨大的词汇表出发，再逐渐删除trim down其中的词汇，直到size满足预定义。

初始的词汇表可以采用所有预分词器分出来的词，再加上所有高频的子串。

每次从词汇表中删除词汇的原则是使预定义的损失最小。训练时，计算loss的公式为：

假设训练文档中的所有词分别为 x1;x2...xN ，而每个词tokenize的方法是一个集合 S(xi) 。当一个词汇表确定时，每个词tokenize的方法集合 S(xi) 就是确定的，而每种方法对应着一个概率p(x)。如果从词汇表中删除部分词，则某些词的tokenize的种类集合就会变少，log(*)中的求和项就会减少，从而增加整体loss。

Unigram算法每次会从词汇表中挑出使得loss增长最小的10%~20%的词汇来删除。

一般Unigram算法会与SentencePiece算法连用。