BPE 算法原理及使用指南【深入浅出】

Suprit

退役ACMer NLP方向硕士在读

193 人赞同了该文章

本文力争通俗易懂，但由于牵扯的知识较多，我也是参考了很多文章才弄清楚 BPE、Subword（子词）、WordPiece、Tokenize、Vocabulary（词表）这些词之间的关系（吐槽一句全是英文真不友好），请耐心按顺序往下看，一定不会让你失望：

1. 从分词说起

只要您稍微学过一点 NLP，对于分词这个概念肯定不陌生。机器无法直接理解自然语言的文本，我们需要进行文本预处理 ，而最重要的一步就是分词（Tokenize） 。

一些概念

一个完整的分词流程如下：

其中，执行分词的算法模型称为分词器（Tokenizer） ，划分好的一个个词称为 Token （为啥不直接叫 Word？接着往后看），这个过程称为 Tokenization 。

我们将一个个的 token（可以理解为小片段）表示向量，我们分词的目的就是尽可能的让这些向量蕴含更多有用的信息，然后把这些向量输入到算法模型中。

由于一篇文本的词往往太多了，为了方便算法模型训练，我们会选取出频率 （也可能是其它的权重）最高的若干个词组成一个词表（Vocabulary） 。

古典分词方法

分词，顾名思义，就是把一句话分词一个个词，这还不简单？直接把词与词直接加一个空格不就行了？那如果真这么简单我们也不用讨论了，还有什么办法呢，再想一想？或许还能按标点符号分词 ，或者按语法规则分词 。

上面提到的这些方法，统称为古典分词方法 ，区别不是很大。

‼️ 古典分词方法的缺点

可见，一个句子，使用不同的规则，将有许多种不同的分词结果。古典分词方法的缺点非常明显：

• 对于未在词表中出现的词（Out Of Vocabulary, OOV ），模型将无法处理（未知符号标记为 [UNK]）。
• 词表中的低频词/稀疏词在模型训无法得到训练（因为词表大小有限，太大的话会影响效率）。
• ⭐️ 很多语言难以用空格进行分词，例如英语单词的多形态，"look"衍生出的"looks", "looking", "looked"，其实都是一个意思，但是在词表中却被当作不同的词处理，模型也无法通过 old, older, oldest 之间的关系学到 smart, smarter, smartest 之间的关系。这一方面增加了训练冗余，另一方面也造成了大词汇量问题。

拆分为单个字符

这种方法称为 Character embedding，是一种更为极端的分词方法，直接把一个词分成一个一个的字母和特殊符号。虽然能解决 OOV 问题，也避免了大词汇量问题，但缺点也太明显了，粒度太细，训练花费的成本太高，但这种思想或许我们后面会用到。

其中最重要的就是最后一个问题，那么怎么解决这些问题呢？我们接着往下看。

2. BERT 的出现

我们都知道，随着 BERT 算法的横空出世，NLP 中的很多领域都被颠覆性的改变了，BERT 也称为了一个非常主流的 NLP 算法。由于 BERT 的特性（具体请移步学习 BERT），要求分词方法也必须作出改变。这就对应提出了 Subword 算法 （或成为 WordPiece），该算法已经成为一种标配。

3. 基于子词的分词方法（Subword Tokenization）

可见不论是传统分词算法的局限性，还是 BERT 的横空出世，都要求我们提出新的分词算法，下面就轮到本文的主角登场：基于子词的分词方法（Subword Tokenization） ，简称为 Subword 算法，意思就是把一个词切成更小的一块一块的子词。如果我们能使用将一个 token 分成多个 subtokens，上面的问题就能很好的解决。

这种方法的目的是通过一个有限的词表 来解决所有单词的分词问题，同时尽可能将结果中 token 的数目降到最低。例如，可以用更小的词片段来组成更大的词，例如：

“unfortunately ” = “un ” + “for ” + “tun ” + “ate ” + “ly ”。

可以看到，有点类似英语中的词根词缀拼词法，其中的这些小片段又可以用来构造其他词。可见这样做，既可以降低词表的大小，同时对相近词也能更好地处理。

Subword 与传统分词方法的比较

• 传统词表示方法无法很好的处理未知或罕见的词汇（OOV 问题）。
• 传统词 tokenization 方法不利于模型学习词缀之间的关系，例如模型学到的“old”, “older”, and “oldest”之间的关系无法泛化到“smart”, “smarter”, and “smartest”。
• Character embedding 作为 OOV 的解决方法粒度太细。
• Subword 粒度在词与字符之间，能够较好的平衡 OOV 问题。

目前有三种主流的 Subword 算法，它们分别是：Byte Pair Encoding (BPE)、WordPiece 和 Unigram Language Model。

字节对编码（BPE, Byte Pair Encoding）

字节对编码（BPE, Byte Pair Encoder），又称 digram coding 双字母组合编码，是一种数据压缩 算法，用来在固定大小的词表中实现可变⻓度的子词。该算法简单有效，因而目前它是最流行的方法。

BPE 首先将词分成单个字符，然后依次用另一个字符替换频率最高的一对字符 ，直到循环次数结束。

接下来详细介绍 BPE 在分词中的算法过程：

算法过程

1. 准备语料库，确定期望的 subword 词表大小等参数
2. 通常在每个单词末尾添加后缀 </w>，统计每个单词出现的频率，例如，low 的频率为 5，那么我们将其改写为 "l o w </ w>”：5
   注：停止符 </w> 的意义在于标明 subword 是词后缀。举例来说：st 不加 </w> 可以出现在词首，如 st ar；加了 </w> 表明该子词位于词尾，如 we st</w>，二者意义截然不同
3. 将语料库中所有单词拆分为单个字符，用所有单个字符建立最初的词典，并统计每个字符的频率，本阶段的 subword 的粒度是字符
4. 挑出频次最高的符号对 ，比如说 t 和 h 组成的 th，将新字符加入词表，然后将语料中所有该字符对融合（merge），即所有 t 和 h 都变为 th。
   注：新字符依然可以参与后续的 merge，有点类似哈夫曼树，BPE 实际上就是一种贪心算法 。
5. 重复遍历 2 和 3 操作，直到词表中单词数达到设定量 或下一个最高频数为 1 ，如果已经打到设定量，其余的词汇直接丢弃

注：看似我们要维护两张表，一个词表，一个字符表，实际上只有一张，词表只是为了我们方便理解。

一个完整的例子

我们举一个完整的例子，来直观地看一下这个过程：

1. 获取语料库，这样一段话为例：“FloydHub is the fastest way to build, train and deploy deep learning models. Build deep learning models in the cloud. Train deep learning models.”
2. 拆分，加后缀，统计词频：

1. 建立词表，统计字符频率（顺便排个序）：

1. 以第一次迭代为例，将字符频率最高的 d 和 e 替换为 de，后面依次迭代：

1. 更新词表

继续迭代直到达到预设的 subwords 词表大小或下一个最高频的字节对出现频率为 1。

如果将词表大小设置为 10，最终的结果为：

d e
r n
rn i
rni n
rnin g</w>
o de
ode l
m odel
l o
l e

这样我们就得到了更加合适的词表，这个词表可能会出现一些不是单词的组合，但是其本身有意义的一种形式

BPE 的优点

上面例子中的语料库很小，知识为了方便我们理解 BPE 的过程，但实际中语料库往往非常非常大，无法给每个词(token)都放在词表中。BPE 的优点就在于，可以很有效地平衡词典大小和编码步骤数（将语料编码所需要的 token 数量）。

随着合并的次数增加，词表大小通常先增加后减小。迭代次数太小，大部分还是字母，没什么意义；迭代次数多，又重新变回了原来那几个词。所以词表大小要取一个中间值。

BPE 的缺点

• 对于同一个句子, 例如 Hello world，如图所示，可能会有不同的 Subword 序列。不同的 Subword 序列会产生完全不同的 id 序列表示，这种歧义可能在解码阶段无法解决。在翻译任务中，不同的 id 序列可能翻译出不同的句子，这显然是错误的。

• 在训练任务中，如果能对不同的 Subword 进行训练的话，将增加模型的健壮性，能够容忍更多的噪声，而 BPE 的贪心算法无法对随机分布进行学习。

个人理解：我感觉缺点直接可以忽略

BPE 的适用范围

BPE 一般适用在欧美语言拉丁语系中，因为欧美语言大多是字符形式，涉及前缀、后缀的单词比较多。而中文的汉字一般不用 BPE 进行编码，因为中文是字无法进行拆分。对中文的处理通常只有分词和分字两种。理论上分词效果更好，更好的区别语义。分字效率高、简洁，因为常用的字不过 3000 字，词表更加简短。

BPE 的实现

实现代码如下：

import re, collections
 
def get_vocab(filename):
    vocab = collections.defaultdict(int)
    with open(filename, 'r', encoding='utf-8') as fhand:
        for line in fhand:
            words = line.strip().split()
            for word in words:
                vocab[' '.join(list(word)) + ' </w>'] += 1
    return vocab
 
def get_stats(vocab):
    pairs = collections.defaultdict(int)
    for word, freq in vocab.items():
        symbols = word.split()
        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 = re.escape(' '.join(pair))
    p = re.compile(r'(?<!\S)' + bigram + r'(?!\S)')
    for word in v_in:
        w_out = p.sub(''.join(pair), word)
        v_out[w_out] = v_in[word]
    return v_out
 
def get_tokens(vocab):
    tokens = collections.defaultdict(int)
    for word, freq in vocab.items():
        word_tokens = word.split()
        for token in word_tokens:
            tokens[token] += freq
    return tokens

跑一个例子试一下，这里已经对原句子进行了预处理：

vocab = {'l o w </w>': 5, 'l o w e r </w>': 2, 'n e w e s t </w>': 6, 'w i d e s t </w>': 3}
print('==========')
print('Tokens Before BPE')
tokens = get_tokens(vocab)
print('Tokens: {}'.format(tokens))
print('Number of tokens: {}'.format(len(tokens)))
print('==========')
 
num_merges = 5
for i in range(num_merges):
    pairs = get_stats(vocab)
    if not pairs:
        break
    best = max(pairs, key=pairs.get)
    vocab = merge_vocab(best, vocab)
    print('Iter: {}'.format(i))
    print('Best pair: {}'.format(best))
    tokens = get_tokens(vocab)
    print('Tokens: {}'.format(tokens))
    print('Number of tokens: {}'.format(len(token

结果：

==========
Tokens Before BPE
Tokens: defaultdict(<class 'int'>, {'l': 7, 'o': 7, 'w': 16, '</w>': 16, 'e': 17, 'r': 2, 'n': 6, 's': 9, 't': 9, 'i': 3, 'd': 3})
Number of tokens: 11
==========
Iter: 0
Best pair: ('e', 's')
Tokens: defaultdict(<class 'int'>, {'l': 7, 'o': 7, 'w': 16, '</w>': 16, 'e': 8, 'r': 2, 'n': 6, 'es': 9, 't': 9, 'i': 3, 'd': 3})
Number of tokens: 11
==========
Iter: 1
Best pair: ('es', 't')
Tokens: defaultdict(<class 'int'>, {'l': 7, 'o': 7, 'w': 16, '</w>': 16, 'e': 8, 'r': 2, 'n': 6, 'est': 9, 'i': 3, 'd': 3})
Number of tokens: 10
==========
Iter: 2
Best pair: ('est', '</w>')
Tokens: defaultdict(<class 'int'>, {'l': 7, 'o': 7, 'w': 16, '</w>': 7, 'e': 8, 'r': 2, 'n': 6, 'est</w>': 9, 'i': 3, 'd': 3})
Number of tokens: 10
==========
Iter: 3
Best pair: ('l', 'o')
Tokens: defaultdict(<class 'int'>, {'lo': 7, 'w': 16, '</w>': 7, 'e': 8, 'r': 2, 'n': 6, 'est</w>': 9, 'i': 3, 'd': 3})
Number of tokens: 9
==========
Iter: 4
Best pair: ('lo', 'w')
Tokens: defaultdict(<class 'int'>, {'low': 7, '</w>': 7, 'e': 8, 'r': 2, 'n': 6, 'w': 9, 'est</w>': 9, 'i': 3, 'd': 3})
Number of tokens: 9
==========

编码与解码

上面的过程称为编码。解码过程比较简单，如果相邻子词间没有中止符，则将两子词直接拼接，否则两子词之间添加分隔符。 如果仍然有子字符串没被替换但所有 token 都已迭代完毕，则将剩余的子词替换为特殊 token，如 <unk>。例如：

# 编码序列
["the</w>", "high", "est</w>", "moun", "tain</w>"]
 
# 解码序列
"the</w> highest</w> mountain</w>"

如何调包使用 BPE

BPE 可以直接用最经典的 subword-nmt 包，不需要自己实现

其他方法

其他 Subword 的分词方法比较重要的还有 Unigram Based Tokenization 和 WordPiece。

参考

WordPiece、BPE 详解及代码

Bert 系列伴生的_新分词器_

NLP 三大 Subword 模型详解：BPE、WordPiece、ULM

BPE 算法详解

Tokenizers: How machines read

子词技巧：The Tricks of Subword

深入理解 NLP Subword 算法：BPE、WordPiece、ULM

发布于 2021-12-21 16:48

自然语言处理

机器学习