BPE算法
- BPE
- 示例
- 参考文章
BPE
BPE (Byte Pair Encoding)全称为字节对编码，本质是一种数据压缩方法，来自于一篇发表于1994年的论文：“A new algorithm for data compression”。它在数据压缩中原始的核心思路非常简单：每一步都将最常见的一对_相邻数据单位_替换为该数据中没有出现过的一个_新单位_，反复迭代直到满足停止条件 。比如有一段数据是“abbabyabya”，其中相邻字母对的组合中"ab"出现3次是出现最多，即可以使用一个字母Z去代替"ab"，数据形式压缩成：“ZbZyZya”。以此类推，下一个’Zy’继续被替换成Y，数据形式变成：“ZbYYa”。
在NLP 中，2015年Sennrich 通过论文Neural Machine Translation of Rare Words with Subword Units将这个算法使用在生成Tokenizer的词表上，做法是先将每个文本词（Word）拆分成 Char粒度的字母序列，然后通过迭代地合并最频繁出现的字符或字符序列来实现生成Tokenizer最终词表的过程。 之后OpenAI GPT-2 与Facebook RoBERTa均采用此方法进阶版BBPE构建 Subword 向量，也是目前最常用的Tokenizer方法之一。
BPE算法步骤:
输入：训练语料； 词表大小V
1.准备足够大的训练语料，确定期望的subword词表大小；
2.准备基础词表：比如英文中26个字母加上各种符号；
3.基于基础词表将语料中的单词拆分为字符序列并在末尾添加后缀“ </ w>”；本阶段的subword的粒度是字符。例如单词“ low”的频率为5，那么我们将其改写为“ l o w </ w>”：5；
4.统计每一个连续字节对的出现频率，选择最高频的字符对合并成新的subword；
5.重复第4步直到达到第1步设定的subword词表大小或下一个最高频的字节对出现频率为1；
示例
回到我们之前的例子，让我们假设单词有以下频率：
("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5)
“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)
然后我们看成对的。这对（“h”，“u”）出现在单词“hug”和“hugs”中，所以在语料库中总共出现了15次。不过，这并不是最常见的一对组合：“u”、“g”在“hug”、“pug”和“hugs”中出现的次数最多，总共出现了20次。
因此，标记器学习的第一个合并规则是（“u”，“g”）->“ug”，这意味着“ug”将被添加到词汇表中，并且应该在语料库的所有单词中合并对。在这个阶段结束时，词汇和语料库看起来是这样的：
Vocabulary: ["b", "g", "h", "n", "p", "s", "u", "ug"]
Corpus: ("h" "ug", 10), ("p" "ug", 5), ("p" "u" "n", 12), ("b" "u" "n", 4), ("h" "ug" "s", 5)
现在我们有一些对，它们会产生一个超过两个字符的标记：例如，对（“h”，“ug”）（在语料库中出现15次）。在这个阶段最常见的一对是（“u”，“n”），然而，在语料库中出现了16次，因此学习的第二个合并规则是（“u”，“n”）->“un”。将其添加到词汇表中并合并所有现有的出现导致我们：
Vocabulary: ["b", "g", "h", "n", "p", "s", "u", "ug", "un"]
Corpus: ("h" "ug", 10), ("p" "ug", 5), ("p" "un", 12), ("b" "un", 4), ("h" "ug" "s", 5)
Now the most frequent pair is (“h”, “ug”), so we learn the merge rule (“h”, “ug”) -> “hug”, which gives us our first three-letter token. After the merge, the corpus looks like this:
Vocabulary: ["b", "g", "h", "n", "p", "s", "u", "ug", "un", "hug"]
Corpus: ("hug", 10), ("p" "ug", 5), ("p" "un", 12), ("b" "un", 4), ("hug" "s", 5)
参考文章
NLP 中的Tokenizer：BPE、BBPE、WordPiece、UniLM 理论
Byte-Pair Encoding tokenization
