Tokenizer基础篇

对于英语这种语言，虽然单词之间已经有了空格分隔符，但是如果只是用空格进行切分，会导致数据稀疏问题。英语的单词往往具有复杂的词形变换，传统的处理方法是根据语言学规则，引入词形还原（Lemmatization）或者词干提取（Stemming），提取出单词的词根，从而在一定程度上缓降数据稀疏问题。但是这种方法需要人工编写大量的规则，同时不易扩展到新领域，因此现在流行基于统计的无监督子词（Subword）切分。子词切分方法可以避免OOV（Out Of Vocabulary）问题。

子词切分算法基于这样一个原则：不应该将常用词拆分为更小的子词，应该将稀有词分解为有意义的子词。

子词切分技术分为以下几种：

分词方法	典型模型
BPE	GPT-1, GPT-2, GPT-3, BART, RoBERTa, LLaMA
WordPiece	BERT, DistilBERT, MobileBERT
UniLM	ALBERT, mBART, T5, XLNet

Tokenizer和模型一样，也包括训练和推理两个环节，从语料中训练得到一个分词器模型，推理阶段则给定一个句子，基于分词模型将该句子切分成子词序列。通常采用token代指子词subword。

Tokenizer的训练和Model的训练是分离的，同时Tokenizer的性能和Model的能力并不挂钩。Tokenizer负责将文本转成数字，它起到一个识字的作用；Model则将输入的One-hot向量转成Dense Vector，它起到一个理解的作用。

当然，我们一般讨论的LLM（Large Language Model，大型语言模型）是包括Tokenizer和Model在内的，LLM的实际表现和两者密切相关。就比如有些技术文章，我们认识那些字，但是连在一起就不理解了；有些生僻字不认识，更谈不上理解。因此Tokenizer和Model都是非常重要的。

BPE

BPE全称Byte Pair Encoding，目前的LLM大多采用了BPE作为Tokenizer，它的核心思想是：从一个基础小词表开始，通过不断合并最高频的连续token对来产生新的token。

BPE的步骤如下：

准备足够大的语料库
预分词，以空格为单位得到语料中的单词。每个单词拆分为字符序列，并在单词结尾添加一个</w>字符
用切分后的字符构成初始词表

在语料库中统计单词内相邻token对的频次

def get_stats(ids, counts=None):
    """
    Given a list of integers, return a dictionary of counts of consecutive pairs
    Example: [1, 2, 3, 1, 2] -> {(1, 2): 2, (2, 3): 1, (3, 1): 1}
    Optionally allows to update an existing dictionary of counts
    """
    counts = {} if counts is None else counts
    for pair in zip(ids, ids[1:]):
        counts[pair] = counts.get(pair, 0) + 1
    return counts

合并频次最高的token对，合并成新的token，并将新的token加入到词表中（还需要删除因为合并而消失的旧token）

def merge(ids, pair, idx):
    """
    In the list of integers (ids), replace all consecutive occurrences
    of pair with the new integer token idx
    Example: ids=[1, 2, 3, 1, 2], pair=(1, 2), idx=4 -> [4, 3, 4]
    """
    newids = []
    i = 0
    while i < len(ids):
        # if not at the very last position AND the pair matches, replace it
        if ids[i] == pair[0] and i < len(ids) - 1 and ids[i+1] == pair[1]:
            newids.append(idx)
            i += 2
        else:
            newids.append(ids[i])
            i += 1
    return newids

重复步骤4和5，直到进行了设定的合并次数或者达到了设定的子词词表大小

每次合并时，子词词汇表可能会发生3种变化：

+1，这表明合并后的新子词加入了词汇表，同时原来的两个子词仍然保留（两个子词不是完全同时连续出现）
+0，这表明合并后的新子词加入了词汇表，同时原来的两个子词一个保留，另一个被去除（一个子词完全随着另一个子词的出现而紧跟着出现）
-1，这表明合并后的新子词加入了词汇表，同时原来的两个子词都被去除（两个子词同时连续出现）

一般来说，随着合并次数的增加，词表大小会先增加后减小。

此外，GPT-2在实现BPE Tokenizer的时候，并不是直接对原始字符串进行处理，而是会强制执行一些规则，以确保文本的某些部分永远不会被合并。简单来说，它会先根据正则表达式对句子进行分词，然后对分词后的序列依次进行处理，最后再将处理结果拼接。其它的LLM Tokenizer也在BPE的基础上做出了一些改进。

BPE的优缺点：

优点：

编码句子所需要的token数量和词表大小以及子词粒度有关，所以BPE可以有效平衡词汇表大小和编码步数

缺点：

基于贪婪和确定的符号替换，不能提供带概率的多个分词结果（相对于UniLM而言）
同一个句子可能会有不同的subword序列，从而产生不同的id序列表示，这种歧义在解码阶段可能无法解决

WordPiece

WordPiece和BPE有点类似，只不过WordPiece是基于概率生成新的subword而不是最高频的token对合并得到新子词。它的核心思想是：从一个基础小词表出发，通过不断合并互信息最大的连续token来产生新的token。

WordPiece的步骤如下：

准备足够大的语料库
将语料中的每个单词拆分为字符序列，字符构成初始子词词表
基于上一步得到的数据训练语言模型，可以是Unigram语言模型，通过极大似然进行估计即可
从所有可能的子词单元中，选择能最大程度得增加语言模型概率的相邻子词作为新的子词加入词表
重复第4步直到子词词表达到一定数量或概率增量低于某一阈值

何为增加语言模型概率？
假设句子$S=(t_1,…,t_n)$由$n$个子词组成，$t_i$表示第$i$个子词。如果各子词之间是独立存在的，则句子$S$的语言模型似然值为：

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

假设把相邻位置的子词$x$和子词$y$进行合并，合并之后产生新的子词$z$，此时句子$S$的似然值变化是：

$logP(t_z)-(logP(t_x)+logP(t_y))=log\frac{P(t_z)}{P(t_x)P(t_y)}$

似然值的变化就是两个子词之间的互信息。

总之，WordPiece每次选择合并的两个子词，它们具有最大的互信息，即两个子词在语言模型上具有较强的关联性，它们经常在语料中以相邻的方式同时出现。

WordPiece的优缺点：

优点：

可以较好地平衡词表大小和OOV问题

缺点：

可能会产生一些不太合理的子词或者说错误的切分
对拼写错误非常敏感
对前缀的支持不够好

UniLM

UniLM全称是Unigram Language Model，和WordPiece一样，UniLM也利用语言模型来建立子词词表。该算法考虑了句子的不同分词可能，因而能够输出带概率的子词。

不过BPE和WordPiece算法的词表都是一点点增加，由小到大，而UniLM则先初始化一个非常大的词表，然后根据标准不断丢弃，直到词表大小满足限定条件。

UniLM核心思想是：初始化一个大词表，然后通过Unigram Language Model计算删除不同subword造成的损失，以此代表subword的重要性，保留loss较大或者说重要性较高的subword。

对于句子$S$，如果$(t_1,…,t_n)$是句子的一种分词结果，那么当前分词结果下句子$S$的似然值可以表示为：

$P(S)=\prod_{i=1}^{n}P(t_i)$

挑选似然值最大的分词结果作为最终分词结果，那么优化目标可以表示为：

$argmax_{t\in U(t)}P(t)$

其中$U(t)$包含了句子的所有分词结果。在实际应用中，词表大小有几万，直接罗列所有可能的分词组合不具有操作性，可以通过维特比算法解决。此处不展开。

那么如何求解每个子词的概率$P(t_i)$呢？UniLM通过EM算法来估计。假设当前语料是$D$，那么第$M$步最大化的对象如下：

$L=\sum_{s=1}^{|D|}log(\sum_{t\in U(t)}P(t))$

UniLM算法采用不断迭代的方法构造词表并求解分词概率，该算法的步骤如下：

初始化一个很大的基础词表，可以通过BPE得到该初始词表
针对当前词表，用EM算法求解每个子词在语料上的概率
针对每个子词，计算当该子词被从词表中移除时，总损失降低了多少，并记住该子词对应的损失
将子词按照损失大小排序，丢弃一定比例损失最小的子词，保留下来的子词生成新的词表。为避免OOV问题，单字符不能被丢弃。
重复步骤2到4，直到词表大小减少到设定范围

UniLM会倾向于保留那些以较高频率出现在很多句子的分词结果中的子词，因为这些子词如果被删除，损失会很大。

UniLM的优缺点：

优点：

使用的训练算法可以利用所有可能的分词结果，这是通过data sampling算法实现
提出基于语言模型的分词算法，这种语言模型可以给多种分词结果赋予概率，从而学习到其中的噪声
使用时可以给出带概率的多个分词结果

缺点：

效果和初始词表息息相关，初始的大词表要足够好，比如可以通过BPE来初始化
略显复杂

三种subword算法比较

模型	BPE	WordPiece	UniLM
词表大小	小词表到大词表	小词表到大词表	大词表到小词表
词表筛选	合并最高频的子词对	合并互信息最大的子词对	丢弃一定比例损失最小的子词
学习	合并规则和词汇表	词汇表	带有概率的词汇表
编码	将一个单词分割成字符序列，然后利用训练得到的合并规则合并这些序列	从词汇表中找开始位置能匹配到的最长子词，然后依次匹配单词的剩余部分	利用训练得到的概率分数，找到最有可能的划分子词序列

【参考资料】