NLP

理解NLP SubWord算法

Byte Pair Encoding

Posted by Wwt on September 20, 2021

本文参考自深入理解NLP Subword算法:BPE、WordPiece、ULM

介绍

Subword算法如今已经成为一个重要的NLP模型性能提升方法。自2018年BERT出现后,各路预训练模型如同雨后春笋般涌现,其中subword算法在其中已经成为标配。作为NLP从业者,有必要了解下subword算法的原理。

分词器是做什么的

机器无法理解文本。当我们将句子序列送入模型时,模型仅仅能看到一串字节,它无法知道一个词从哪里开始,到哪里结束,所以也不知道一个词是怎么组成的。所以为了帮助机器理解文本,我们需要

  1. 将文本分成一个个小片段
  2. 然后将这些片段表示为一个向量作为模型的输入
  3. 同时,我们需要将一个个小片段(token)表示为向量,作为词嵌入矩阵,通过在语料上训练来优化token的表示,使其蕴含更多有用的信息,用于之后的任务。

与传统空格分词技术对比

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

Byte Pair Encoding

BPE(字节对)编码或二元编码是一种简单的数据压缩形式,其中最常见的一对连续字节数据被替换为该数据中不存在的字节。后期使用时需要一个替换词表来重建原始数据。

  • 优点
    • 可以有效的平衡词汇表大小和步数(编码句子所需的token数量)。
  • 缺点
    • 基于贪婪和确定的符号替换,不能提供带概率的多个分片结果。

算法

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

停止符”</w>“的意义在于表示subword是词后缀。举例来说,”st”字词不加”</w>“可以出现在词首如”st ar”,加了”</w>“表明该字词位于词尾,如”wide st</w>“,二者意义截然不同。

每次合并后词表肯能出现3种变化:

  • +1,表明加入合并后的新字词,同时原来的2个子词还保留(2个字词不是完全同时连续出现)
  • +0,表明加入合并后的新字词,同时原来的2个子词中一个保留,一个被消解(一个字词完全随着另一个字词的出现而紧跟着出现)
  • -1,表明加入合并后的新字词,同时原来的2个子词都被消解(2个字词同时连续出现)

实际上,随着合并次数增加,词表大小通常先增加后减小。

例子

输入:

{‘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}

第一次迭代,最高频连续字节对”e”和”s”出现了6+3=9次,合并成”es”。输出:

{‘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}

第二次迭代,最高频连续字节对’es’和“t”出现了6+3=9次,合并成“est”。输出“

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

第三次迭代,以此类推,最高频连续字节对为”est”和“</w>”输出。

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

……

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

编码和解码

  • 编码

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

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

例子

# 给定单词序列
[“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-tokenizer 所有单词。并在词典中保存单词tokenizer的结果。如果我们看到字典中不存在的未知单词。我们应用上述编码方法对单词进行tokenize,然后将新单词的tokenization添加到字典中备用。

  • 解码

将所有tokens拼接在一起。

例子:

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

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

WordPiece

WordPiece算法可以看作是BPE的变种。不同点在于,WordPiece基于概率生成新的subword而不是下一个最高频字节对。

算法

  1. 准备足够大的训练语料
  2. 确定期望的subword词表大小
  3. 将单词拆分成字符序列
  4. 基于第3步数据训练语言模型
  5. 从所有可能的subword单元中选择加入语言模型后能最大程度地增加训练数据概率的单元作为新的单元
  6. 重复第5步直到达到第2步设定的subword词表大小或概率增量低于某一个阈值

Unigram Language Model

ULM 是另外一种subword分割算法,它能够输出带概率的多个子词片段。它引入一个假设:所有subword的出现都是独立的,并且subword序列由subword出现概率的乘积产生。WordPiece和ULM都利用语言模型建立subword词表。

算法

  1. 准备足够大的训练语料
  2. 确定期望的subword词表大小
  3. 给定词序列优化下一个词出现的概率
  4. 计算每个subword的损失
  5. 基于损失对subword排序保留前X%,为了避免OOV,建议保留字符级的单元
  6. 重复3至5步直到达到第2步设定的subword词表大小或第5步的结果不再变化

可以看出,ULM会保留那些以较高频率出现在很多句子的分词结果中的子词,因为这些子词如果被丢弃,其损失会很大。

总结

  1. subword可以平衡词汇量对未知词的覆盖。极端情况下,我们只能使用26个token(即字符)来表示所有英语单词。一般情况,建议使用16k或32k子词足以取得良好的效果,
  2. 对于包括中文在内的许多的亚洲语言,单词不能用空格分隔。因此,初始词汇量需要比英语大很多。