【大语言模型开发】BPE算法（Byte-Pair）

BPE算法（Byte-Pair）

1. 确定词表大小，并计算语料库中的单词集合和对应的词频；
2. 然后计算这个单词集合中的构成这些单词的所有符号；实际应用中，基本词汇至少包括ASCII字符；
3. 通过合并(merge)来添加新的tokens直到达到期望的词汇表大小；
4. 循环执行步骤3，直到达到某种要求后停止；

以这个句子为例："This is the Hugging Face Course."；
首先，计算语料库的单词集合（区分大小写），并且统计词频：

[("This", 1), ("is", 1), ("the", 1), ("Hugging", 1), ("Face", 1), ("Course", 1)]

（恰好没有一个词是重复的，如果语料库中存在重复词汇，也只会在单词集合中出现一次）
其次，计算单词集合中的构成这些单词的所有符号：

["T", "h", "i", "s", "t", "e", "H", "u", "g", "n", "F", "a", "c", "C", "o", "r", "."]

然后，我们开始合并过程；is这个组合在语料库中出现两次，出现频率比较高，因此，词表变化为：

["T", "h", "is", "t", "e", "H", "u", "g", "n", "F", "a", "c", "C", "o", "r", "."]

不断执行合并过程，最后满足某一条件停止。

如果我们 token化 不在训练语料库中的字符，则该字符将转换为未知 tokens，这就是为什么许多 NLP 模型在分析带有表情符号的内容的结果非常糟糕的原因之一。

GPT-2和RoBERTa的tokenizer设计一个巧妙地方法来处理这个问题；GPT-2和RoBERTa首先对输入的字符串使用utf-8进行编码Unicode代码点与编码，然后，将词汇看作是由字节编写的；尽管每个字符的字节数可能不同，但是一个字节都是8bit，这样，基本词汇表的大小就很小（$2^8=256$），但是能包含所有的字符（因为对应Unicode字符集），而不会产生未知token；这个技巧被称为字节级（byte-level） BPE.

BPE算法是一种贪婪算法：为了以最有效的方式表示语料库，BPE 在每次迭代时都会通过查看其频率来检查每个可能的合并选项，并且每次合并那些出现频率最高的合并对。因此，该算法的确是贪婪的。

正如上面所说的，BPE算法是一个基于统计的方法，因此，我重新思考，对这一个过程展开一个形式化的描述：

1. 统计：词频与共现
   BPE算法的每一步合并都依赖于字符对的共现频率。假设初始词汇表为所有单字符，语料库为$D$，定义一下符号：

• $c(x)$：字符或子词 $x$ 在 $D$ 中出现的次数。
• $c(xy)$：字符对 $xy$ 在 $D$ 中连续共现的次数。

什么是 $xy$ 共现？ $xy$是明确序偶关系的，假设$x=ab$，$y=c$，需要统计$abc$出现的次数。

合并规则：在每轮迭代中，选择共现频率最高的字符对$(x\ast ,y\ast )=\arg {\max }_{(x,y)}c(xy)$，将其合并为新子词$z=x\oplus y$。

2. 概率模型：条件概率
   如果将合并过程视为对字符的条件概率估计，那么可以这样假设：字符对 $(x,y)$ 的条件概率为：
   $$P(y|x)=\frac{c(xy)}{c(x)}$$
   但是BPE算法不是直接最大化条件概率$P(y|x)$，而是选择直接最大化$c(xy)$。