Question

1. 有三种常见的 subword tokenization 算法：Byte Pair Encoding: BPE 、WordPiece、Unigram。

1.1 BPE

1. Byte Pair Encoding: BPE 来自于论文 《Neural Machine Translation of Rare Words with Subword Units》（2015） 。

2. BPE 是一种简单的数据压缩技术，它迭代式地替换序列中最频繁的字节对。我们不是合并频繁的字节对，而是合并频繁的字符或字符序列。

   • 首先，我们用 character vocabulary 初始化 symbol vocabulary ，将每个单词表示为一个字符序列，加上一个特殊的单词结束符 </w>，这允许我们在 tokenization 后恢复原始的 tokenization 。

   • 然后，我们迭代地计算所有 symbol pair ，并用新的 symbol 'AB' 替换最频繁的 symbol pair ('A','B') 。每个merge 操作产生一个新的 symbol ，它代表一个 character n-gram 。

     同时，每个 merge 代表一个规则。

   最终的 symbol vocabulary 大小等于 initial vocabulary 的大小，加上 merge 操作的次数（这是算法唯一的超参数）。

3. 下面的显示了一个最小化的 Python 实现。在实践中，我们通过索引所有 pair 并增量更新数据结构来提高效率：

   ​x
   import re, collections
   
   
   def get_stats(vocab): # vocab : 存储 word -> freq 的 dict
       ''' 计算词表中，字符的 2-gram 及其出现频次
       '''
       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 # 计算字符的 2-gram 及其出现频次
       return pairs
   
   
   def merge_vocab(pair, v_in): # pair 为最高频的 2-gram，v_in 为已有的 vocab
       ''' 利用最高频的 2-gram 来更新已有的词表
       '''
       v_out = {}
       bigram = re.escape(' '.join(pair)) # 对字符串中可能被解释为正则运算符的字符进行转义
       p = re.compile(r'(?<!\S)' + bigram + r'(?!\S)') # 编译一个正则模式
       # \S 匹配任意非空字符
       # (?<! \S) 前向否定界定符。当 bigram 之前不是任意非空字符之时，匹配成功
       # (?! \S) 后向否定界定符。当 bigram 之后不是任意非空字符之时，匹配成功
       for word in v_in:
         w_out = p.sub(''.join(pair), word) # 将word中已有的pair替换为紧凑版本(移除中间的空格)
         # 注意这里有两个 join(pair), 一个是 ' '.join() 带空格, 另一个是 ''.join() 不带空格
         v_out[w_out] = v_in[word]
       return v_out

   示例：

   
   xxxxxxxxxx
   vocab = {'l o w </w>' : 5, 'l o w e r </w>' : 2, # initial vocabulary
            '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)
   # 最终 vocab: {'low</w>': 5, 'low e r </w>': 2, 'newest</w>': 6, 'wi d est</w>': 3}

   注意，初始的 vocab 已经将单词拆分为字符序列，并用 ' ' 分隔。这个步骤被称作 pre-tokenization 。

4. 在机器翻译任务上，有两种应用 BPE 的方法：

   • 学习两个独立的编码，一个用于 source vocabulary 、另一个用于 target vocabulary 。

     这种方法的优点是：在文本和词表规模方面更紧凑，并且更能保证在相应语言的训练文本中看到每个 subword 单元。

   • 学习两个 vocabulary 的并集上的编码，称之为 joint BPE 。

     这种方法的优点是：提高了 source tokenization 和 target tokenization 之间的一致性。如果我们独立地应用 BPE ，相同的 name 在两种语言中可能被不同地 tokenization ，这使得神经模型更难学习 subword 单元之间的映射。

5. Byte-level BPE：包含所有基础字符 base character 的 base vocabulary 可能非常大，例如，将所有 unicode 字符（一共 65536 个，即2 个字节的表示范围）作为基础字符。

   为了获得更小的 base vocabulary ，GPT-2 使用 byte 作为 base vocabulary 。这是一个聪明的技巧，它强制 base vocabulary 的大小为 256 （一个字节的表示范围），同时确保每个基本字符都包含在 vocabulary 中。GPT-2 具有 50257 的词表大小，其对应于 256 个 byte-base token 、一个特殊的文本结束 token 、以及通过 50000 次 merge 所学到的 symbol 。

   相比之下，使用传统 BPE 的GPT 的词表规模为 40478 ，其中包含 478 个基本字符，并在40000 次merge 后停止训练。

6. 来自 Hugging Face 上的例子：

   • 假设在 pre-tokenization 之后，我们得到了如下的单词及其频次的集合：

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

     将所有单词拆分到字符，则我们得到：

     
     xxxxxxxxxx
     ("h" "u" "g", 10), ("p" "u" "g", 5), ("p" "u" "n", 12), ("b" "u" "n", 4), ("h" "u" "g" "s", 5)

     此时 base vocabulary 为：

     
     xxxxxxxxxx
     ["b", "g", "h", "n", "p", "s", "u"]

   • 然后，BPE 计算每个可能的 symbol pair ，然后挑选出现频次最高的 symbol pair 。

     此时，频次最高的 symbol pair 是：将 "u" 后面跟着 "g" 的 symbol pair 合并为 "ug" 。

     此时单词及其频次的集合为：

     
     xxxxxxxxxx
     ("h" "ug", 10), ("p" "ug", 5), ("p" "u" "n", 12), ("b" "u" "n", 4), ("h" "ug" "s", 5)

     此时 base vocabulary 为：

     
     xxxxxxxxxx
     ["b", "g", "h", "n", "p", "s", "u", "ug"]

   • BPE 然后确定下一个最常见的 symbol pair，即 "u" 后面跟着 "n" 。因此，BPE 将 "u", "n" 合并为 "un" 。

     下一个最常见的 symbol pair，即 "h" 后面跟着 "ug" 。因此，BPE 将 "h", "ug" 合并为 "hug" 。

     此时单词及其频次的集合为：

     
     xxxxxxxxxx
     ("hug", 10), ("p" "ug", 5), ("p" "un", 12), ("b" "un", 4), ("hug" "s", 5)

     此时 base vocabulary 为：

     
     xxxxxxxxxx
     ["b", "g", "h", "n", "p", "s", "u", "ug", "un", "hug"]

   假设 BPE 的训练在这个时刻结束，那么所学习的所有 merge rule 将被应用于新的单词。例如：

   • 单词 "bug" 被 tokenized 为 ["b", "ug"] 。
   • 单词 "mug" 被 tokenized 为 ["<unk>", "ug"]，因为 symbol "m" 不在 base vocabulary 中。

1.2 WordPiece

1. 与 BPE 一样，WordPiece （《Japanese and korean voice search》(2012)）从一个小的词汇表开始，并学习 merge 规则。二者之间的区别在于 merge 的方式不同：WordPiece 不是选择最高频的 pair ，而是通过如下公式计算每个 pair 的得分：

   $$\begin{array}{}\text{(1)}& \text{score}(t_1,t_2)=\frac{\text{freq}(t_{1,2})}{\text{freq}(t_1)\times \text{freq}(t_2)}\end{array}$$

   其中：

   • $t_1$$ t_1 $ 和$t_2$$ t_2 $ 为两个 token，$t_{1,2}$$ t_{1,2} $ 为它们 merge 之后得到的新的 token 。
   • $\text{freq}(t)$$ \text{freq}(t) $ 为 token$t$$ t $ 在语料库中出现的频次。

   选择 score 最高的一对 token 等价于：

   $$\begin{array}{}\text{(2)}& \begin{array}{c}\underset{t_1,t_2}{max}\text{score}(t_1,t_2)=\underset{t_1,t_2}{max}\frac{\text{freq}(t_{1,2})/N}{\text{freq}(t_1)/N\times \text{freq}(t_2)/N}\\ =\underset{t_1,t_2}{max}\log p(t_{1,2})-[\log p(t_1)+\log p(t_2)]\end{array}\end{array}$$

   其中：$N$$ N $ 为语料库中的 token 总数。

   因此 WordPiece 的物理意义为：通过将$t_1,t_2$$ t_1,t_2 $ 合并为$t_{1,2}$$ t_{1,2} $ 之后，语料库的对数似然的增量最大化。

2. 来自 Hugging Face 上的例子：

   • 假设在 pre-tokenization 之后，我们得到了如下的单词及其频次的集合：

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

     将所有单词拆分到字符，则我们得到：

     
     xxxxxxxxxx
     ("h" "##u" "##g", 10), ("p" "##u" "##g", 5), ("p" "##u" "##n", 12), ("b" "##u" "##n", 4), ("h" "##u" "##g" "##s", 5)

     注意：WordPiece 通过添加前缀（在 BERT 中是 ##）来识别子词，这可以识别一个子词是否是单词的开始。这里通过将前缀添加到单词内的每个字符来拆分的，单词的首字符不添加前缀。

     此时的 base vocabulary 为：

     
     xxxxxxxxxx
     ["b", "h", "p", "##g", "##n", "##s", "##u"]

   • 然后，WordPiece 计算每个可能的 symbol pair ，然后挑选 score 最高的 symbol pair 。

     学到的第一个 merge 是 ("##g", "##s") -> ("##gs")。注意,当我们合并时,我们删除了两个 token 之间的 ##，所以我们添加 "##gs" 到词表中。

     此时单词及其频次的集合为：

     
     xxxxxxxxxx
     ("h" "##u" "##g", 10), ("p" "##u" "##g", 5), ("p" "##u" "##n", 12), ("b" "##u" "##n", 4), ("h" "##u" "##gs", 5)

     此时 base vocabulary 为：

     
     xxxxxxxxxx
     ["b", "h", "p", "##g", "##n", "##s", "##u", "##gs"]

   • 我们继续这样处理，直到达到我们所需的词汇量。

3. tokenization 算法：WordPiece 和 BPE 中的 tokenization 的不同在于：WordPiece 仅保存最终词表，而不保存学到的 merge rule 。

   在应用时，从待 tokenized 的单词开始，WordPiece 找到词表中能够匹配到的最长的子词，然后对单词进行拆分。例如，如果我们使用上面例子中学到的词表来 tokenize 单词 "hugs"：

   • 首先，单词从头开始能匹配到的词表中的最长子词是 "hug"，所以我们在那里拆分并得到 ["hug", "##s"]。
   • 然后，我们继续匹配剩下的 "##s"。刚好能够匹配到词表中的子词 "##s"。

   最终， "hugs" 的 tokenization 是 ["hug", "##s"]。

   如果使用 BPE , 我们将按顺序应用学习到的merge rule，并将其 tokenize 为 ["hu", "##gs"]，所以编码不同。

4. 当tokenization 无法在词表中找到子词时，整个单词被 tokenize 为 unknown 。 例如 "bum"，由于"##m" 不在词表中，由此产生的tokenization 将只是 ["[UNK]"], 不是 ["b", "##u", "[UNK]"]。

   这是与 BPE 的另一个区别：BPE 只会将不在词汇表中的单个字符 tokenize 为 unknown 。 例如 "bum"，由于"##m" 不在词表中，由此产生的tokenization 是 ["b", "##u", "[UNK]"]。

1.3 SentencePiece

1. SentencePiece （《Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates》(2018)）中经常使用 Unigram 算法。

2. Unigram 算法假设每个子词都是独立出现的，因此一个子词序列$\mathbf{x}=(x_1,\cdots ,x_M)$$ \mathbf x = (x_1,\cdots,x_M) $ 出现的概率是每个子词出现概率的乘积，即：

   $$\begin{array}{}\text{(3)}& \begin{array}{c}P(\mathbf{x})=\prod _{i=1}^{M}p(x_i)\\ \mathrm{\forall }i{x}_i\in \mathcal{V},\sum _{x\in \mathcal{V}}p(x)=1.0\end{array}\end{array}$$

   其中：$x$$ x $ 为子词，$p(x)$$ p(x) $ 为子词出现的概率，$\mathcal{V}$$ \mathcal V $ 为词表。

   对于给定的句子$X$$ X $ ，其最佳 tokenization 为：

   $$\begin{array}{}\text{(4)}& {\mathbf{x}}^{\ast }=\arg \underset{\mathbf{x}\in S(X)}{max}P(\mathbf{x})\end{array}$$

   其中：$S(X)$$ S(X) $ 为句子$X$$ X $ 的所有候选 tokenization 。

   如果我们已知词表$\mathcal{V}$$ \mathcal V $ 以及每个子词出现的概率$p(x)$$ p(x) $ ，则${\mathbf{x}}^{\ast }$$ \mathbf x^* $ 可以通过维特比算法求解得到。

3. 现在的问题是，给定一个训练语料库$D$$ D $ ，如何获得词表$\mathcal{V}$$ \mathcal V $ 以及每个子词出现的概率$p(x)$$ p(x) $ 。Unigram 利用 EM 算法来求解如下的边际似然 marginal likelihood$\mathcal{L}$$ \mathcal L $ ：

   $$\begin{array}{}\text{(5)}& \mathcal{L}=\sum _{s=1}^{|D|}\log P\left(X^{(s)}\right)=\sum _{s=1}^{|D|}\log (\sum _{\mathbf{x}\in S\left(X^{(s)}\right)}P(\mathbf{x}))\end{array}$$

   其中：$X^{(s)}$$ X^{(s)} $ 表示语料库$D$$ D $ 中的第$s$$ s $ 个句子。

   这里 Unigram 将$p(x)$$ p(x) $ 视作隐变量。

4. 为求解$\mathcal{L}$$ \mathcal L $ ，Unigram 采用了迭代式算法：

   • 首先，启发式地从训练语料库中获取一个足够大的 seed vocabulary 。

     一种选择方法是：使用所有字符、以及语料库中最高频的 substring 。

   • 重复以下步骤，直到词表规模$|\mathcal{V}|$$ |\mathcal V| $ 达到预期的值：

     • 固定词表，通过 EM 算法优化$p(x)$$ p(x) $ 。
     • 对每个子词$x_i$$ x_i $ 计算${\text{loss}}_i$$ \text{loss}_i $ ，其中${\text{loss}}_i$$ \text{loss}_i $ 表示当$x_i$$ x_i $ 从当前词表移除时，似然$\mathcal{L}$$ \mathcal L $ 降低的数值。
     • 根据${\text{loss}}_i$$ \text{loss}_i $ 进行降序排列，保留 top$\eta \mathrm{\%}$$ \eta\% $ 的子词（例如，80% ）。

     注意，我们总是在词表中保留单个 character 从而防止 out-of-vocabulary 。

   最终的词表$\mathcal{V}$$ \mathcal V $ 包含了语料库中的所有单个字符、也包括了一些 character-based tokenization 结果、甚至包括一些 word-based tokenization 结果。因此 Unigram 算法是这三者的混合体。

5. 来自 Hugging Face 上的例子：

   • 假设在 pre-tokenization 之后，我们得到了如下的单词及其频次的集合：

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

     seed vocabulary 采用初始词表的所有严格子字符串（即，不包含它自身）：

     
     xxxxxxxxxx
     ["h", "u", "g", "hu", "ug", "p", "pu", "n", "un", "b", "bu", "s", "hug", "gs", "ugs"]

   • 对于每个单词，考虑 tokenization 概率最高的。例如，对于 "pug"：

     • tokenization 为 ["p", "u", "g"] 的概率为：

       $$\begin{array}{}\text{(6)}& P([\text{"p","u","g"}])=P(\text{"p"})\times P(\text{"u"})\times P(\text{"g"})=\frac{5}{210}\times \frac{36}{210}\times \frac{20}{210}=0.000389\end{array}$$

       这里 210 为词表中所有 token 的频次之和。

     • tokenization 为 ["pu", "g"] 的概率为：

       $$\begin{array}{}\text{(7)}& P([\text{"pu","g"}])=P(\text{"pu"})\times P(\text{"g"})=\frac{5}{210}\times \frac{20}{210}=0.0022676\end{array}$$

     Unigram 选择对单词进行 tokenization 最高的那个：

     
     xxxxxxxxxx
     ["p", "u", "g"] : 0.000389
     ["p", "ug"] : 0.0022676
     ["pu", "g"] : 0.0022676

     所以, "pug" 将被标记为 ["p", "ug"] 或者 ["pu", "g"]，取决于首先遇到这些 中的哪一个。注意，在更大的语料库中这样的相等的情况很少见。

     通常在语料库中找到所有可能的 tokenization 并计算它们的概率，一般来说会有点困难。因此需要利用维特比算法。

     这里我们得到每个单词的最佳 tokenization：

     
     xxxxxxxxxx
     "hug": ["hug"] (score 0.071428)
     "pug": ["pu", "g"] (score 0.007710)
     "pun": ["pu", "n"] (score 0.006168)
     "bun": ["bu", "n"] (score 0.001451)
     "hugs": ["hug", "s"] (score 0.001701)

   • 现在我们需要计算从词表中删除每个 token 如何影响损失。然后我们根据这个损失对 token 进行排序，选择 top$\eta \mathrm{\%}$$ \eta\% $ 的 token 。