tokenizers：BPE算法_bpe tokenizer

我在之前介绍现代自然语言处理中的tokenizer的相关内容的文章中支出，那些流行的模型所用到的tokenizer大都是基于子词切分（subword tokenization）的。而Byte Pair Encoding的提出无疑可以说是开创了子词切分算法的先河。

本文结合算法论文，对BPE算法进行说明。

背景

BPE在论文Neural Machine Translation of Rare Words with Subword Units中被提出，它起初是被用来解决基于神经网络模型的机器翻译任务中的有限词表问题的。什么是有限词表问题呢？简而言之就是，如果翻译模型碰到了它没有见过的单词，那么它就会束手无策。显然，这会大大限制翻译模型。针对这个问题，传统的做法是，事先维护一个词典，遇到了陌生词，那么就通过查词典的方式来进行翻译。这种做法的弊端也是很明显的：首先，你需要维护一个相当规模的词典；其次，也是最致命的一点，并不是所有的词汇都在另外一种语言中有与之精准匹配的词汇。

因此，本文作者 重定义 了BPE算法。这种算法的核心就是将一个罕见的、模型未知的单词拆分成相对常见的子词，从而使模型能够处理未知新词。

之所以说是 重定义，是因为BPE最早指的是一种数据压缩算法，具体地，参看论文：A New Algorithm for Data Compression。

BPE是依赖这样一种直觉：许多复杂的词往往可以被拆分成一些简单的词，而这个复杂词汇的真实含义也可以由这些简单词汇组合得到。

这让我想起来中学时上英语课的场景：老师往往让我们去”猜“一个陌生单词的含义；而这种猜绝对不是漫无目的地瞎猜，而是根据它的拼写与哪些单词比较接近、它的词性与时态以及在句子中的位置等信息去推理出其可能含义。由此看来，我们当时用的就是BPE。

BPE算法

虽然沿用了BPE的名字，但在切分算法中，这里的B指的是字符。

在获取到语料库中的每个单词的词频后，就可以应用BPE算法了。其主要过程如下：

1. 初始化词表：将每个单词拆分成字母，这样就可以得到一个字符表（在初始时，每个字符都是单个字母），由于知道了每个单词的频数，因此也可以知道每个字母的频数；
2. 融合：计算字符表中任意两个字符拼接到一起组成新的字符时在语料中出现的频数，然后选择频数最大的组合，将其添加到字符表中；
3. 迭代：重复第2步，不断向字符表中添加新的组合的字符，直到字符表达到指定的大小。

在BPE算法中，字符表（词表）的大小等于初始化词表的大小加上融合的次数——融合次数是算法的一个超参数，需要提前指定。

应用实例

假设获取到的每个单词及其词频如下：

("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5)
1

一种toy implemention代码如下：

import re
import collections


def add_special_token(vocab):
    vocab_out = {}
    for key in vocab:
        vocab_out["<st>".join(list(key))] = vocab[key]
    return vocab_out


def get_stats(vocab):
    pairs = collections.defaultdict(int)
    for word, freq in vocab.items():
        symbols = word.split('<st>')
        for i in range(len(symbols) - 1):
            pairs[symbols[i], symbols[i+1]] += freq
    return pairs


def merge_vocab(pair, v_in):
    v_out = {}
    bigram = '<st>'.join(pair)
    p = re.compile(bigram)
    for word in v_in:
        w_out = p.sub("".join(pair), word)
        v_out[w_out] = v_in[word]
    return v_out


if __name__ == '__main__':
    num_merges = 3
    vocab = {"hug": 10, "pug": 5, "pun": 12, "bun": 5, "hugs": 5}
    init_vocab = collections.defaultdict(int)
    for i in vocab:
        for char in i:
            init_vocab[char] += vocab[i]

    vocab = add_special_token(vocab)
    for i in range(num_merges):
        pairs = get_stats(vocab)
        best = max(pairs, key=pairs.get)
        vocab = merge_vocab(best, vocab)
        init_vocab["".join(best)] = pairs[best]
        print(list(init_vocab.keys()))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

经过3次融合，得到的词表如下：

['h', 'u', 'g', 'p', 'n', 'b', 's', 'ug', 'un', 'hug']
1

对于一个新的单词，如"bug"，根据查词表，可以被分为"b"和"ug"；而对于单词"mug"，则会被分为"<UNK>“和"ug”——因为"m"并未在词表中，因此会被标记为"<UNK>"。