Tokenization方法总结

对各种tokenization方法进行总结。

词粒度

将输入句子进行分词，对英文来说，直接o通过空格分隔即可，中文则需要一些分词工具（如jieba）。

中文句子：我喜欢看电影和读书。
分词结果：我 | 喜欢 | 看 | 电影 | 和 | 读书。
英文句子：I enjoy watching movies and reading books.
分词结果：I | enjoy | watching | movies | and | reading | books.

词粒度优点:

• 语义明确：以词为单位进行分词可以更好的保留每个词的语义，使得文本在后续处理中能够更准确的表达含义。
• 上下文理解：以词为粒度进行分词有助于保留词语之间的关联性和上下文信息，从而在语义分析和理解时能够更好的捕捉句子的意图。

词粒度缺点：

• 长尾效应和稀有词问题：词表可能变得巨大，包含很多不常见的词汇，增加储存和训练成本。而且稀有词的训练数据有限，难以获得u准确的表示。
• OOV(Out-of-Vocabulary)问题：由于词汇过多，词表无法覆盖所有的词汇，所以会出现词汇不在词表中的问题。此时只能用特殊符号[UNK]表示未知词汇。
• 形态关系和词缀关系：无法捕捉同一词汇的不同形态，也无法学习词缀在不同词汇之间的共通性。比如love和loves是意思相同的词，但在词表中却用两个不同的id表示。并且fast、faster和fastest这种词缀之间的关系词粒度的分词也无法学习到。

字符粒度

以字符为单位进行分词，即将文本拆成单独的字符作为最小基本单元。这种字符粒度的分词方式适用于多种语言，无论是英文、中文还是其他不同语言，都能够一致地使用字符粒度进行处理。而且英文就26个字母以及其他的一些符号，中文常见字就6000个左右，所以可以用较小的词汇表表示所有字符。

中文句子：我喜欢看电影和读书。
分词结果：我 | 喜 | 欢 | 看 | 电 | 影 | 和 | 读 | 书 | 。

英文句子：I enjoy watching movies and reading books.
分词结果：I |   | e | n | j | o | y |   | w | a | t | c | h | i | n | g |   | m | o | v | i | e | s |   | a | n | d |   | r | e | a | d | i | n | g |   | b | o | o | k | s | .

字符粒度的优点：

• 统一处理方式：字符粒度分词方法适用于不同语言，无需针对每种语言设计不同的分词规则或工具，具有通用性。
• 由于字符粒度的词表可以覆盖所有字符，所以基本不会出现OOV的问题。

字符粒度缺点：

• 语义信息不明确：字符粒度分词无法直接表达词的语义。
• 效率问题：由于输入文本被拆分成字符粒度，导致tokens长度很长，增加了后续处理的计算成本。

子词粒度（subword）

在BERT时代，WordPiece 分词方法被广泛应用，比如 BERT、DistilBERT等。

在大语言模型时代，最常用的分词方法是BPE和Byte-level BPE。 * Byte-Pair Encoding (BPE)最初是一种文本压缩算法在15年被引入到NLP用于分词，在训练 GPT 时被 OpenAI 用于tokenization，后续如GPT，RoBERTa等都采用了这种分词方法。 * Byte-level BPE(BBPE)是于19年在BPE的基础上提出以Byte-level(字节)为粒度的分词方法，目前GPT2，BLOOM，Llama，Falcon等采用的是该分词方法。

WordPiece

WordPiece核心思想是将单词拆分成多个最小单元，再通过子词合并规则将最小单元合并为单词。例如对于单词"word"，拆分如下：

w ##o ##r ##d

下面是WordPiece的核心步骤：

1. 计算初始词表：通过预训练语料获得初始词表（26个英文字母+中文字符+符号）。
2. 计算合并分数，在WordPiece中合并分数是互信息，即选择互信息最大的两个相邻子词进行合并。而BPE中是选择频数最高的相邻子词合并。
   互信息计算公式：
   \[I=\frac{P(AB)}{P(A)P(B)}\]
   
3. 合并分数最高的子词对，并更新词表。
4. 重复合并步骤：不断重复步骤2和步骤3，直到达到预先设定的词表大小，或者无法获取有收益的合并。
5. 利用得到的词表进行分词。

WordPiece例子如下：

# 我们有以下的训练语料中的样例以及他们出现的频率
("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5)

# 将其进行拆分
("h" "##u" "##g", 10), ("p" "##u" "##g", 5), ("p" "##u" "##n", 12), ("b" "##u" "##n", 4), ("h" "##u" "##g" "##s", 5)

# 初始词表
["b", "h", "p", "##g", "##n", "##s", "##u"]

# 计算互信息，并取互信息最大的词对合并
# 这里互信息最大的为I("##g", "##s")=5/(20*5)
# 得到如下新的频率以及新的词表
("h" "##u" "##g", 10), ("p" "##u" "##g", 5), ("p" "##u" "##n", 12), ("b" "##u" "##n", 4), ("h" "##u" "##gs", 5)
["b", "h", "p", "##g", "##n", "##u", "##gs"]

# 重复上述操作，直到达到想要的词表大小
......

上面的步骤中，##g和##s合并之后##s已经没有单独出现了，可以选择将##s保留在词表中(此时词表是会一直增大的)，也可以将##s从词表中删去（词表一般会先增大后减小）。

BPE

BPE的详细解读可参考这篇文章：
https://fengyan-wby.github.io/2023/02/21/BPE%E7%AE%97%E6%B3%95%E8%AF%A6%E8%A7%A3

BPE的核心思想是逐步合并出现频率最高的子词对而不是像WordPiece合并最大互信息词对，下面是核心步骤：

1. 计算初始词表：通过预训练语料获得初始词表（26个英文字母+中文字符+符号）。
2. 频率统计：统计所有子词对在文本中出现的频率。
3. 合并频率最高的子词对。
4. 重复合并步骤：不断重复步骤2和步骤3，直到达到预先设定的词表大小，或者无法获取有收益的合并。
5. 利用得到的词表进行分词。

BPE理论上还是会出现OOV的，当词汇表的大小受限时，一些较少出现的子词和没有在训练过程中见过的子词，就会无法进入词汇表而出现OOV，但Byte-level BPE(BBPE)理论上是不会出现这个情况的。

Byte-level BPE

Byte-level BPE(BBPE)和Byte-Pair Encoding (BPE)区别就是BPE是最小词汇是字符级别，而BBPE是字节级别的，通过UTF-8的编码将输入转为字节形式，后续再进行BPE的步骤。

1. 计算初始词表：构建初始词表，包含一个字节的所有表示（共256个）。
2. 频率统计：统计所有子词对在文本中出现的频率。
3. 合并频率最高的子词对。
4. 重复合并步骤：不断重复步骤2和步骤3，直到达到预先设定的词表大小，或者无法获取有收益的合并。
5. 利用得到的词表进行分词。

Unigram

Unigram可参考https://arxiv.org/pdf/1804.10959.pdf。

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

我们来看看Unigram Language Model（ULM）是如何操作的。

对于句子\(S\)，\(\vec{x}=(x_1, x_2, ..., x_m)\)为句子的一个分词结果，由\(m\)个子词组成。所以，当前分词下句子\(S\)的似然值可以表示为：
\[P(\vec{x})=\prod_{i=1}^m P(x_i)\]

选取似然值最大的作为分词结果，即：
\[x^*=argmax_{x \in U(x)}P(\vec{x})\]

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

那么如何求解每个子词的概率\(P(x_i)\)呢？ULM通过EM算法来估计。

下面是Unigram算法的核心流程：

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