BPE编码 Byte Pair Encoding 字节对编码

Posted on | In | | 阅读数

BPE编码 Byte Pair Encoding 字节对编码

Neural Machine Translation of Rare Words with Subword Units

github: https://github.com/sebastien-j/LV_groundhog

github：https://github.com/rsennrich/subword-nmt

知乎：https://zhuanlan.zhihu.com/p/86965595

知乎：https://zhuanlan.zhihu.com/p/164520154

解决了什么问题
  • 神经机器翻译（neural machine translation (NMT) ）里存在OOV的问题，就是没见过的词没法翻译，本文提出了对罕见和没见过的词进行编码成子词序列，从而解决了OOV问题；该模型成为子词模型subword model
用了什么方法

  • 将分词算法用于机器翻译任务中，这是来源于称职的译者可以根据已知的子词单位(如语素或音素)进行翻译，即使这些词对他或她来说是新颖的。因此分词算法用于翻译任务是有道理的；

    即不同的词类可以通过比单词更小的单位进行翻译，例如名称(通过字符复制或音译)，化合物(通过组合翻译)，以及同源词和外来词(通过语音和形态的转换)。

  • 分词算法包括n-gram和BPE；

效果如何
  • 在WMT 15 translation tasks English→German and English→Russian 任务上，比back-off dictionary baseline 好1.1和1.3 BLEU

思路

  • 将BPE(byte pair encoding (BPE) (Gage, 1994))算法用到机器翻译任务上，用作分词算法，以解决OOV问题；

  • BPE允许通过固定大小的词汇表（词汇表里构成词的字符序列不一样长的）来表示开放词汇表open vocabulary ；

  • NMT模型：encoder-decoder结构，encoder：biGRU

  • 提出假设：将罕见词切分为适当的子词单元足以让神经翻译网络学习透明翻译，并将这一知识推广到翻译和产生不可见的词

  • BPE编码：迭代地用一个未使用的字节替换序列中最频繁的一对字节；本文合并字符或字符序列，而不是合并频繁的字节对。

    首先，我们用字符词汇表初始化符号词汇表，并将每个单词表示为一个字符序列，加上一个特殊的词尾符号’·’，这使我们能够在翻译后恢复原来的标记化。我们迭代计算所有符号对，并将出现频率最高的符号对(‘ A ‘， ‘ B ‘)替换为新的符号’ AB ‘。每个合并操作产生一个表示字符n-gram的新符号。频繁的字符n-grams(或整个单词)最终会合并成一个符号，因此BPE不需要候选列表。最后的符号词汇表大小等于初始词汇表的大小加上合并操作的次数（超参）；

image-20220604163527055

流程

  1. 确定subword词表大小
  2. 统计每一个连续字节对的出现频率，并保存为code_file。这个是git中learn-bpe完成
  3. 将单词拆分为字符序列并在末尾添加后缀“ ”，而后按照code_file合并新的subword，首先合并频率出现最高的字节对。例如单词birthday，分割为[‘b’, ‘i’, ‘r’, ‘t’, ‘h’, ‘d’, ‘a’, ‘y‘]，查code_file，发现’th’出现的最多，那么合并为[‘b’, ‘i’, ‘r’, ‘th’, ‘d’, ‘a’, ‘y‘]，最后，字符序列合并为[‘birth’, ‘day‘]。然后去除’‘,变为[‘birth’, ‘day’]，将这两个词添加到词表。这个是apply-bpe完成。
  4. 重复第3步直到达到第2步设定的subword词表大小或下一个最高频的字节对出现频率为1

或者：

  1. 准备足够大的训练语料
  2. 确定期望的subword词表大小
  3. 将单词拆分为字符序列并在末尾添加后缀“ </ w>”，统计单词频率。 本阶段的subword的粒度是字符。 例如，“ low”的频率为5，那么我们将其改写为“ l o w </ w>”：5
  4. 统计每一个连续字节对的出现频率，选择最高频者合并成新的subword
  5. 重复第4步直到达到第2步设定的subword词表大小或下一个最高频的字节对出现频率为1

例子

输入：

1
{'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}

Iter 1, 最高频连续字节对”e”和”s”出现了6+3=9次，合并成”es”。输出：

1
{'l o w </w>': 5, 'l o w e r </w>': 2, 'n e w es t </w>': 6, 'w i d es t </w>': 3}

Iter 2, 最高频连续字节对”es”和”t”出现了6+3=9次, 合并成”est”。输出：

1
{'l o w </w>': 5, 'l o w e r </w>': 2, 'n e w est </w>': 6, 'w i d est </w>': 3}

Iter 3, 以此类推，最高频连续字节对为”est”和”“ 输出：

1
{'l o w </w>': 5, 'l o w e r </w>': 2, 'n e w est</w>': 6, 'w i d est</w>': 3}

……

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

BPE包

https://github.com/google/sentencepiece

▁表示空格，也表示文本开头，detoken时，▁换成空格，把空格连起来；

把比如token后的文本“▁A L V IN ▁AND ▁THE ▁C H AP TER”其实是“Alvin and the chapter”

grep “只能在线不能离线” text_token_eng

1
import sentencepiece as spm

BPE实现

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
import re, collections

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

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}
num_merges = 1000
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(best)

# print output
# ('e', 's')
# ('es', 't')
# ('est', '</w>')
# ('l', 'o')
# ('lo', 'w')
# ('n', 'e')
# ('ne', 'w')
# ('new', 'est</w>')
# ('low', '</w>')
# ('w', 'i')
# ('wi', 'd')
# ('wid', 'est</w>')
# ('low', 'e')
# ('lowe', 'r')
# ('lower', '</w>')

编码和解码

  • 编码

在之前的算法中，我们已经得到了subword的词表，对该词表按照子词长度由大到小排序。编码时，对于每个单词，遍历排好序的子词词表寻找是否有token是当前单词的子字符串，如果有，则该token是表示单词的tokens之一。

我们从最长的token迭代到最短的token，尝试将每个单词中的子字符串替换为token。 最终，我们将迭代所有tokens，并将所有子字符串替换为tokens。 如果仍然有子字符串没被替换但所有token都已迭代完毕，则将剩余的子词替换为特殊token，如。

例子

1
2
3
4
5
6
7
8
9
10
# 给定单词序列
[“the</w>”, “highest</w>”, “mountain</w>”]

# 假设已有排好序的subword词表
[“errrr</w>”, “tain</w>”, “moun”, “est</w>”, “high”, “the</w>”, “a</w>”]

# 迭代结果
"the</w>" -> ["the</w>"]
"highest</w>" -> ["high", "est</w>"]
"mountain</w>" -> ["moun", "tain</w>"]

编码的计算量很大。 在实践中，我们可以pre-tokenize所有单词，并在词典中保存单词tokenize的结果。 如果我们看到字典中不存在的未知单词。 我们应用上述编码方法对单词进行tokenize，然后将新单词的tokenization添加到字典中备用。

  • 解码

将所有的tokens拼在一起。

例子：

1
2
3
4
5
# 编码序列
[“the</w>”, “high”, “est</w>”, “moun”, “tain</w>”]

# 解码序列
“the</w> highest</w> mountain</w>”

tr ‘▁’ ‘ ‘