光与影的个人博客

NEUCoder

0%

Subword分词:BPE&word-piece

发表于 更新于 分类于 ，

Subword分词:BPE&word-piece

在读transforme论文时，论文中在两个NMT任务中分别使用了两种编码算法byte pair encoding和word-piece，似乎子词嵌入模型是解决OOV问题不二选择，稍微了解一下

BPE

为了解决NMT中的OOV问题，基于子词模型（sub-word）以及Byte pair encoding思想提出了BPE算法，解决了词表大小压缩问题

Byte pair encoding

一种简单的数据压缩算法，寻找byte串中重复出现多次的byte对(pair of consecutive bytes)，使用串中未出现过的byte替代，直到byte串中不存在重复多次的byte串。

wekipedia的例子：

BPE算法与原Byte pair encoding算法完全一致，只是运行在character层级上，论文中思路主要为

  • 初始词表为所有单词拆分的字母+ 特殊的单词结束符（a special end-of word symbol ‘·’）
  • 重复遍历使用频率最高的pair替换
    • 如 (‘A’, ‘B’) 用 ‘AB’ 替换（一个词替代两个词）
    • replace each occurrence of the most frequent pair (‘A’, ‘B’) with a new symbol ‘AB’.
  • 重复迭代直到满足要求
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)
    //寻找出现次数最多的pair对
    best = max(pairs, key=pairs.get)
    vocab = merge_vocab(best, vocab)
    print(best)

joint BPE

NMT需要输入源语言、输出目标语言，因此需要构建两个分别包括两种语言的词表，论文中提出了两种类型的BPE

  • 源语言与目标语言分别运行BPE算法，构建子词词表
  • 源语言与目标语言合并在一起，共建一个BPE词表（joint BPE）

两种方法优略

  1. 第一种方法，确保两种语言词表中都只包含出现过的子词，不会存在另一种语言的子词干扰，保证了词表的大小
  2. 第二种方法，确保了基于统计切词在两种语言上运行的一致性，相同的词切分方式保持一致（比如说相同的人名）

没细看实验

wordpiece

方法来自于论文：Japanese and Korean voice search， 该方法的主要思路与BPE基本相同，只是每次不再按照频率的大小选取词对，而是选择能够使得语言模型最大似然增加（increases the likelihood），算法基本流程如下（贪心思路）：

  1. 首先以字符为单位在语料集上构建词表
  2. 使用词表+语料训练一个语言模型
  3. 遍历词表，选取字符对（word unit pair）,使用字符对替换的词表+语料再训练一个语言模型，最终选择使得语言模型最大似然最大的字符对作为此轮迭代选择的字符对，更新词表
  4. 重2，3直到词表大小满足预期要求

每次迭代都需要遍历整个词表，假设词表大小为k，能够找的 word unit pair 个数为 $k^2$, 也就需要训练 $k^2$ 个语言模型，计算复杂度多得离谱，因此原论文提出了几个加速方法

  1. 每次选择字符对，只选择训练语料中已经存在(字面意思理解就是 在语料中相邻的 word unit)

  2. 只选择那些很有可能成为最优字符对的进行比较（不太懂如何判断最有可能）

  3. c和d没太理解