[BTTB] BPE：从 Byte 到 Byte，到 No BPE
作者： AINLP 来源： [AINLP](https://mp.weixin.qq.com/s/AnZQII7ACp-ACtuFHaGNVg)
考古文，最新东西卷不过几个大号，而且本人也比较喜欢在小小的角落，挖呀挖呀挖~
因为早期搞 NMT（机器翻译），所以 BPE 挺早就知道了，但也没太深究名字。最近突然想起挖了挖，原来还有这样一段故事，颇为有趣，给大家增加点冷知识作为谈资，也分享一些自己见解。
Byte Begins
虽然该算法现在是以 Tokenizer 被大家知道，但从一个 Tokenizer 的角度来看名字却很奇怪：Byte Pair Encoding（BPE） ，不太像是一个 Tokenizer 的名字。横向对比来看，其他常用 subword Tokenizer 都叫：Unigram、WordPiece，一看就和语言相关，突然就蹦出来一个 BPE。
硕士做机器翻译相关，开始还挺疑惑，翻 Sennrich 那篇论文才知道最早是压缩算法，借鉴过来用于 Tokenizer，所以名字也没改，当时也没深究了，忙着玩呢。
最近给提出 BPE 那篇 A New Algorithm for Data Compression 给看了，还是有收获的，角度不同。
首先，自然生成数据大都有规律可循，所以大多压缩算法 idea 就是给常见模式用更短表征来替换，就是贪心算法。BPE 也基于相同思想：找到相邻最高频的 byte 对，然后用另外一个没用过的 byte 来替换 。
论文中原话是：
The algorithm compresses data by finding the most frequently occurring pairs of adjacent bytes in the data and replacing all instances of the pair with a byte that was not in the original data. The algorithm repeats this process until no further compression is possible, either because there are no more frequently occurring pairs or there are no more unused bytes to represent pairs. The algorithm writes out the table of pair substitutions before the packed data.
算法压缩数据时，会先找到数据中最常出现的相邻 byte 对 ，然后将这个 byte 对用没出现过在原数据中的 byte 来表示 。该算法不断重复此过程，直到不能进一步压缩 ，比如说没有更多高频 byte 对，或是没有没用过的 byte 来进行替换表示了。最后算法会在写出压缩数据前，写出替换 byte 对的替换表。
熟悉 BPE Tokenizer 训练流程的同学，应该会感觉到有那味儿了。
现在再看 Byte Pair Encoding 这个名字，毫无违和感。至于为什么用 byte，因为作为一个 lossless 的通用压缩算法，自然要用 byte 这个通用最小表示单元，为什么不用 bit 呢，嗯，总共才两位。
此时的 BPE 算法具体过程是，将需压缩文件转成 Byte 流，将一部分存入 buffer，接着对这部分进行 BPE 算法压缩，不断找高频 byte pair 用没用上的 byte 替换掉。最后输出压缩过的文件 ，还有一个有序的替换表 用于还原。因为会按 buffer 大小切成很多部分，所以输入一个文件，获得很多段被压缩的byte段，以及每段对应的替换表。
输入：文件
输出：多个压缩文件段 + 多个替换查询表
解压时，只需要对每段用替换表，反向替换一遍就能获得原始文件。
Bye Bye~ Byte
然而作为压缩算法而提出的 BPE，可能因为在压缩速度和压缩率上并没啥优势，所以也没在压缩领域获得太大关注。看早期引用它的论文，也大多是模式匹配还有手机终端通讯的少量文章。直到 Sennrich 那篇给 BPE 算法用在 Tokenizer 训练，才开始逐渐受到关注。
这就来到了 Sennrich 15 年那篇 Neural Machine Translation of Rare Words with Subword Units，给 BPE 引入 NLP 领域。
思想是类似的，也就是找到最高频相邻 pair，然后替换掉。不同之处在于：
-
不再是对 byte 维度进行操作了，而是在 character 层面上进行操作；
-
原算法只能在已有 byte 个数上进行 merge 替换，比如一个终止条件就是未使用 byte 没了，但 BPE Tokenizer 算法，则只需要给新 merge 出来的片段一个新 词表 id，就可以无限扩充。
于是 BPE 就完成了一次从 Byte 到 Character 的跳跃，算法名字中的 Byte 也就失去了意义，更多变成了指融合相邻 pair，不断替换成新词的 Tokenizer 算法。
因为 Subword Tokenizer 能比较有效解决 OOV 问题，而且效果也还不错，所以也就从机器翻译慢慢推广开了。但到 BERT 时期最流行的也都还是 WordPiece，因为 Bert 用 WordPiece. 所以直到 GPT2 随着 GPT 受到关注，BPE 也就获得更多关注。
Sennrich 这一步是最有开创性的一步，给一个其他领域算法用在一个全新领域 ，而且赋予新的意义 ，包括用法上的思路也不一样了 。
BPE 算法过程变成了，先拿到训练数据集（也可采样部分），做一些前处理，切分，拆成英文 char 级别，接着统计相邻 char 频率，将最高频的用 merge 后 pair 替换掉，同时词表加一.
下面是原论文中实现：
和 BPE 压缩算法的不同在于，输入训练文本文件，没 buffer 切分，在整个文件层面上进行 char 级别 pair 统计，不断将最高频 pair 合并起来，重新统计，合并。直到满足设一个合并次数限制，或其他限制（如频率都低于某个阈值）。整个过程记录不断加入的新词，即词表文件 （vocab.json），而记录下来的 merge 操作，就是 merge 文件 （merge.txt）。
输入：训练文本
输出：词表文件 + merge 文件
之后使用时，用词表文件+merge文件将输入的文本转成对应 id，从压缩算法角度来看，可以理解为每次都对输入文本进行压缩，而模型在压缩后的文本上进行训练。
为什么要压缩，而不在原始文件 char 级别，或词级别直接训呢。
这就涉及到效率的权衡，直接词级别，各种各样词太多了，词表会特别大，稀疏，要对词表中每个 id 都进行充分训练，训练效率不高，而如果限制词表大小，还会出现很多 OOV（Out-of-Vocabulary，词表中没有的词）；而如果是 char 级别，又会出现每个输入特别长，这个也带来效率问题，如果是 LSTM 的话 timestep 会特别长，训练费时，还要担心梯度传播问题，如果是 Transformer 又因为计算复杂度 的问题，效率也不高。
所以 BPE 子词 Tokenizer 算法，只是效率上权衡下采用的一种 Tokenizer 算法。
到这一步 Byte Pair Encoding 里的 Byte 已失去了意义，主要是 Pair Encoding，大家说 BPE 也都指这个意思。
Back to the Byte (BTTB)
最开始看到 ByteLevelBPE 思路时，还挺疑惑，为什么要这么做，也没觉得 ByteLevelBPE 有多好，反而因为和大多 Bert 类（除 Roberta） Tokenizer 相差较大，中间 byte 组成的 token，可解释性也不太好，而且当时在 benchmark 上也没体现太多优势。
一些早期看不懂东西，可能和传统做法不同，且刚开始效果一般，导致大家也都没在意。直到各种条件满足了，如硬件调节，接着突然拿到一个很好效果，说服了大家，然后整个范式就从旧的换到新的范式上来。
chatGPT 的技术22年年初就基本都告诉大家了，GPT3 也很久前东西，RLHF 这个 OpenAI 也搞挺久了，再久远 Deep Learning 又何尝不是。
言归正传，ByteLevelBPE 思路，就是给之前 BPE 的 char 思路推回 byte，ByteLevelBPE 则是先给所有 char 都先转成 byte，接着在 byte 级别上训练词表。
比 char 的优势体现在什么地方，下面几点：
-
OOV 问题基本上不存在了 ，之前的 NLP 在词表这块一直存在一个 OOV 问题（所以会有个类似 [UNK] 的token）；
-
也和 OOV 问题相关，之前主要做英文相关 NLP，而一旦做多语言 用英文词表就全是 OOV，而到 Byte 级别就能处理所有字符，颜文字都能处理；
-
Byte级别，就不需要管一些前处理步骤 了，比如 lower case 啥的，直接输入转 byte，然后直接输出 byte，再转成 unicode 文本
有意思的是，明明 BPE 里已经有 byte 这个词，但因为大家之前都基本给 BPE 当成 PE（Pair Encoding）来用了，为强调 byte 这一点，又刻意再加上 ByteLevel 来说明，于是从 byte 出发，到跟 byte 没关系，结果又回到 byte .
随着不断 Scaling，加上处理多语言， ByteLevelBPE 已经成为默认 Tokenizer 算法了，无论是效率还是使用方面。
ByteLevelBPE 训练和 BPE 算法一样，输入训练文本，获得词表文件和 merge 文件。但这块 OpenAI 的 tiktoken 库较新词表都只有一个文件了，开始还以为搞出了什么新技术，后来发现就是 merge 词表。想了一下确实，因为 vocab 是隐含在 merge 中的 ，本质上只用 merge 就可以。
输入：训练文本
输出：byte 级别的 merge 表
未来：No BPE
现在再看训 ByteLevelBPE Tokenizer 到模型训练，本质上就是先在训练语料上进行 BPE 训练统计，获得一个压缩词表，训练时先对训练数据进行转换，转成对应的 id，这一步相当于一个压缩过程，之后语言模型再在压缩数据上进行训练。
从压缩角度来看，压缩相关之前张俊林有篇《世界的参数倒影》，我自己很久之前（你有几篇不是很久之前？）也写过篇相关《信息论，语言模型，压缩闲谈》，相当于我们先对整个训练数据进行压缩，然后通过训练模型，进行进一步压缩学习。
我一直是大力出奇迹的推崇者，相信之后走向如《苦痛的教训》中说的，随着算力成本越来越低，那么肯定会干掉所有辅助先验。现在基本已经干掉了语言学先验，一些中间任务。那在 BPE 算法角度，能看到现在还相当于 BPE 先验压缩一遍 ，然后模型训练再压缩一遍 的做法，那干掉步骤，就应该干掉 BPE，也就是 No BPE 直接在最基础单元上进行训练 。
什么是最基础单元，比如byte、像素等等，这些也有些相关论文。但这些算法现在还处在一个早期没明显优势阶段，其实可以类比成 GPT2 刚放出来，大家也没觉得 ByteLevelBPE 有多好，但是我相信随着算力的进一步发展，同时大家对各种模态输入的需求，这个方向是必然的，到时候也就不需要 BPE 这个中间过程，直接从最原始的输入开始。
而且回归到这种基础单元，有些现在解决不了的问题直接就能解决了，如常举例子，现在 GPT Tokenizer 对于单词 char 级别反转类就不好做，而如果换成更底层单元的话就能直接做了。
Reference
-
A New Algorithm for Data Compression
-
Neural Machine Translation of Rare Words with Subword Units
-
Language Models are Unsupervised Multitask Learners
-
MEGABYTE: Predicting Million-byte Sequences with Multiscale Transformers
**进技术交流群请添加AINLP小助手微信（id: ainlp2)**
**请备注具体方向+所用到的相关技术点**
**关于AINLP**
AINLP 是一个有趣有AI的自然语言处理社区，专注于 AI、NLP、机器学习、深度学习、推荐算法等相关技术的分享，主题包括文本摘要、智能问答、聊天机器人、机器翻译、自动生成、知识图谱、预训练模型、推荐系统、计算广告、招聘信息、求职经验分享等，欢迎关注！加技术交流群请添加AINLP小助手微信(id：ainlp2)，备注工作/研究方向+加群目的。
**阅读至此了，分享、点赞、在看三选一吧🙏**
