OOV问题和BPE算法

Posted on | In

OOV与BPE简述

自然语言处理（NLP）的许多相关任务如实体关系抽取、问答，机器翻译、阅读理解、文本摘要、实体链接等都需要对语言建模。近几年常用的语言模型有词向量，如Word2vec，Glove等。面向不同的领域和不同的任务，研究人员根据实际需要训练出来了各种各样的语言模型，如对实体链接训练了实体嵌入，对知识图谱的表示训练了知识图谱嵌入（实际上是一个三元组的向量化表示）。这些语言建模促使不同的NLP任务取得不同程度的进步。然而，词向量是一个词的有限集合的向量化表示，这些词都是常见词。故而由此而建成的语言模型（Language Mode，LM）总会存在不能满足实际应用的需求，即：目标任务中可能出现一些罕见词或是派生词，词的复数或者其他的一些组合词的规则而产生的词无法用现有词向量模型表示。所以这个问题就称之为OOV(Out-Of-Vocabulary)问题。为了解决这个问题，Rico Sennrich等人提出了BPE（Byte Pair Encoder）算法， 也叫做digram coding双字母组合编码，主要目的是为了数据压缩。算法描述为字符串里频率最常见的一对字符被一个没有在这个字符中出现的字符代替的层层迭代过程。利用BPE算法旨在发现各种介于word和character之间的词根，从而尽可能的覆盖各种各样的OOV。

BPE算法示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
比如我们想编码：
aaabdaaabac
我们会发现这里的aa出现的词数最高（我们这里只看两个字符的频率），那么用这里没有的字符Z来替代aa：
ZabdZabac
Z=aa
此时，又发现ab出现的频率最高，那么同样的，Y来代替ab：
ZYdZYac
Y=ab
Z=aa
同样的，ZY出现的频率大，我们用X来替代ZY：
XdXac
X=ZY
Y=ab
Z=aa
最后，连续两个字符的频率都为1了，也就结束了。
解码的时候，就按照相反的顺序更新替换即可。

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
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 = 10
for i in range(num_merges):
	pairs = get_stats(vocab)
	best = max(pairs, key=pairs.get)
	vocab = merge_vocab(best, vocab)
	print(best)

输出为：

1
2
3
4
5
6
7
8
9
10
('e', 's')
('es', 't')
('est', '</w>')
('l', 'o')
('lo', 'w')
('n', 'e')
('ne', 'w')
('new', 'est</w>')
('low', '</w>')
('w', 'i')