type
status
password
date
slug
summary
category
URL
tags
icon
背景
在NLP任务中，神经网络模型的训练和预测都需要借助词表来对句子进行表示。传统构造词表的方法，是先对各个句子进行分词，然后再统计并选出频数最高的前N个词组成词表。通常训练集中包含了大量的词汇，以英语为例，总的单词数量在17万到100万左右。出于计算效率的考虑，通常N的选取无法包含训练集中的所有词。因而，这种方法构造的词表存在着如下的问题：
- 实际应用中，模型预测的词汇是开放的，对于未在词表中出现的词(
Out Of Vocabulary, OOV)，模型将无法处理及生成；
- 词表中的低频词/稀疏词在模型训练过程中无法得到充分训练，进而模型不能充分理解这些词的语义；
- 一个单词因为不同的形态会产生不同的词，如由"look"衍生出的"looks", "looking", "looked"，显然这些词具有相近的意思，但是在词表中这些词会被当作不同的词处理，一方面增加了训练冗余，另一方面也造成了大词汇量问题。
Subword
一种解决思路是使用字符粒度来表示词表（例如在英文中，字符的词表就是26个英文字母），虽然能够解决OOV问题，但单词被拆分成字符后，一方面丢失了词的语义信息，另一方面，模型输入会变得很长，这使得模型的训练更加复杂难以收敛。
针对上述问题，Subword(子词)模型方法横空出世。它的划分粒度介于词与字符之间，比如可以将
”looking”划分为”look”和”ing”两个子词，而划分出来的"look"，”ing”又能够用来构造其它词，如"look"和"ed"子词可组成单词"looked"，因而Subword方法能够大大降低词典的大小，同时对相近词能更好地处理。目前有三种主流的Subword算法，它们分别是：Byte Pair Encoding (BPE), WordPiece和Unigram Language Model。
Byte Pair Encoding (BPE)
BPE最早是一种数据压缩算法，由Sennrich等人于2015年引入到NLP领域并很快得到推广。该算法简单有效，因而目前它是最流行的方法。GPT-2和RoBERTa使用的Subword算法都是BPE。
算法原理-词汇表：
- 准备足够大的训练语料，并确定期望的Subword词表大小；
- 将单词拆分为成最小单元。比如英文中26个字母加上各种符号，这些作为初始词表；
- 在语料上统计单词内相邻单元对的频数，选取频数最高的单元对合并成新的Subword单元；
- 重复第3步直到达到第1步设定的Subword词表大小或下一个最高频数为1.
下面以一个例子来说明。
以这段话为例：
FloydHub is the fastest way to build, train and deploy deep learning models. Build deep learning models in the cloud. Train deep learning models. - 拆分，加后缀，统计词频：
WORD | FREQUENCY | WORD | FREQUENCY |
d e e p </w> | 3 | b u i l d </w> | 1 |
l e a r n i n g </w> | 3 | t r a i n </w> | 1 |
t h e </w> | 2 | a n d </w> | 1 |
m o d e l s </w> | 2 | d e p l o y </w> | 1 |
F l o y d h u b </w> | 1 | B u i l d </w> | 1 |
i s </w> | 1 | m o d e l s </w> | 1 |
f a s t e s t </w> | 1 | i n </w> | 1 |
w a y </w> | 1 | c l o u d </w> | 1 |
t o </w> | 1 | T r a i n </w> | 1 |
- 建立词表，统计字符频率（顺便排个序）：
NUMBER | TOKEN | FREQUENCY | NUMBER | TOKEN | FREQUENCY |
1 | </w> | 24 | 15 | g | 3 |
2 | e | 16 | 16 | m | 3 |
3 | d | 12 | 17 | . | 3 |
4 | l | 11 | 18 | b | 2 |
5 | n | 10 | 19 | h | 2 |
6 | i | 9 | 20 | F | 1 |
7 | a | 8 | 21 | H | 1 |
8 | o | 7 | 22 | f | 1 |
9 | s | 6 | 23 | w | 1 |
10 | t | 6 | 24 | 1 | |
11 | r | 5 | 25 | B | 1 |
12 | u | 4 | 26 | C | 1 |
13 | p | 4 | 27 | T | 1 |
14 | y | 3 | ㅤ | ㅤ | ㅤ |
- 以第一次迭代为例，将字符频率最高的
d和e替换为de(一共有7次)，后面依次迭代：
NUMBER | TOKEN | FREQUENCY | NUMBER | TOKEN | FREQUENCY |
1 | </w> | 24 | 15 | y | 3 |
2 | e | 16-7=9 | 16 | g | 3 |
3 | d | 12-7=5 | 17 | m | 3 |
4 | l | 11 | 18 | . | 3 |
5 | n | 10 | 19 | b | 2 |
6 | i | 9 | 20 | h | 2 |
7 | a | 8 | 21 | F | 1 |
8 | o | 7 | 22 | H | 1 |
9 | de | 7 | 23 | f | 1 |
10 | s | 6 | 24 | w | 1 |
11 | t | 6 | 25 | 1 | |
12 | r | 5 | 26 | B | 1 |
13 | u | 4 | 27 | C | 1 |
14 | p | 4 | 28 | T | 1 |
- 更新词表
WORD | FREQUENCY | WORD | FREQUENCY |
de e p </w> | 3 | b u i l d </w> | 1 |
l e a r n i n g </w> | 3 | t r a i n </w> | 1 |
t h e </w> | 2 | a n d </w> | 1 |
m o de l s </w> | 2 | de p l o y </w> | 1 |
F l o y d h u b </w> | 1 | B u i l d </w> | 1 |
i s </w> | 1 | m o de l s </w> | 1 |
f a s t e s t </w> | 1 | i n </w> | 1 |
w a y </w> | 1 | c l o u d </w> | 1 |
t o </w> | 1 | T r a i n </w> | 1 |
- 继续上述迭代直到达到预设的Subword词表大小或下一个最高频的字节对出现频率为1。
从上面的示例可以知道，每次合并后词表大小可能出现3种变化：
- +1，表明加入合并后的新子词，同时原来的2个子词还保留（2个字词分开出现在语料中）。
- +0，表明加入合并后的新子词，同时原来的2个子词中一个保留，一个被消解（一个子词完全随着另一个子词的出现而紧跟着出现）。
- 1，表明加入合并后的新子词，同时原来的2个子词都被消解（2个字词同时连续出现）。
实际上，随着合并的次数增加，词表大小通常先增加后减小。
编码-获取token
在得到Subword词表后，针对每一个单词，我们可以采用如下的方式来进行编码：
- 将词典中的所有子词按照长度由大到小进行排序；
- 对于单词w，依次遍历排好序的词典。查看当前子词是否是该单词的子字符串，如果是，则输出当前子词，并对剩余单词字符串继续匹配。
- 如果遍历完字典后，仍然有子字符串没有匹配，则将剩余字符串替换为特殊符号输出，如
”<unk>”。
- 单词的表示即为上述所有输出子词。
解码过程比较简单，如果相邻子词间没有中止符，则将两子词直接拼接，否则两子词之间添加分隔符。
BBPE
首先将文本按照UTF-8进行编码，每个字符在UTF-8的表示中占据1-4个byte。 在byte序列上再使用BPE算法，进行byte level的相邻合并。
WordPiece
WordPiece算法可以看作是BPE的变种。不同点在于，WordPiece基于概率生成新的subword而不是下一最高频字节对。即它每次合并的两个字符串A和B，应该具有最大的值。合并AB之后，所有原来切成A+B两个tokens的就只保留AB一个token，整个训练集上最大似然变化量与成正比。
WordPiece不一定会合并(“
un”，“##able”)，即使这对组合在词汇表中非常频繁地出现，因为“un”和“##able”这两对组合很可能会出现在很多其他单词中，而且频率很高。相比之下，像“hu”，“##gging”这样的组合可能会更快地合并(假设单词“hugging”经常出现在语料中)，因为“hu”和“##gging”单独出现的频率可能较低。算法原理-词汇表：
下面以一个例子来说明
- 语料：
("hug", 10),("pug", 5),("pun", 12),("bun", 4),("hugs", 5)
- 分词：
("h" "##u" "##g", 10),("p" "##u" "##g", 5),("p" "##u" "##n", 12),("b" "##u" "##n", 4), ("h" "##u" "##g" "##s", 5)
- 拆分，加后缀，统计词频：
WORD | Split | FREQUENCY |
hug | h ##u ##g | 10 |
pug | p ##u ##g | 5 |
pun | p ##u ##n | 12 |
bun | b ##u ##n | 4 |
hugs | h ##u ##g ##s | 5 |
- 建立词表，统计字符频率（顺便排个序）：
TOKEN | FREQUENCY |
h | 10+5=15 |
##u | 10+5+12+4+5=36 |
##g | 10+5+5=20 |
p | 5+12=17 |
##n | 12+4=16 |
b | 4 |
##s | 5 |
TOKEN | FREQUENCY |
##u | 36 |
##g | 20 |
p | 17 |
##n | 16 |
h | 15 |
##s | 5 |
b | 4 |
- 以第一次迭代为例，将score最高的
##g和##s替换为##gs()，后面依次迭代
TOKEN | FREQUENCY |
##u | 36 |
##g | 20-5=15 |
p | 17 |
##n | 16 |
h | 15 |
##gs | 5 |
b | 4 |
TOKEN | FREQUENCY |
##u | 36 |
p | 17 |
##n | 16 |
##g | 20-5=15 |
h | 15 |
##gs | 5 |
b | 4 |
- 继续上述迭代直到达到预设的Subword词表大小或概率增量低于某一阈值。
编码-获取token
在得到Subword词表后，针对每一个单词，我们可以采用如下的方式来进行编码：
- 将词典中的所有子词按照长度由大到小进行排序；
- 对于单词w，依次遍历排好序的词典。查看当前子词是否是该单词开头的子字符串，如果是，则输出当前子词，并对剩余单词字符串继续匹配。
- 重复步骤2，如果遍历完字典后，仍然有子字符串没有匹配，则输出
”<unk>”。
与BPE的区别
使用BPE进行编码的时候，从单词的任意位置匹配token
使用wordpiece进行编码的时候，从单词的开头匹配token
Unigram Language Model (ULM)
与BPE或者WordPiec不同之处在于，BPE和WordPiece算法的词表大小都是从小到大变化，属于增量法。而Unigram Language Model则是减量法,即先初始化一个大词表，根据评估准则不断丢弃词表，直到满足限定条件。ULM算法考虑了句子的不同分词可能，因而能够输出带概率的多个子词分段。
我们接下来看看ULM是如何操作的。
对于句子，为句子的一个分词结果，由m个子词组成。所以，当前分词下句子 的似然值可以表示为：
对于句子S，挑选似然值最大的作为分词结果，则可以表示为
这里包含了句子的所有分词结果。在实际应用中，词表大小有上万个，直接罗列所有可能的分词组合不具有操作性。针对这个问题，可通过维特比算法得到来解决。
那怎么求解每个子词的概率呢？ULM通过EM算法来估计。假设当前词表V, 则M步最大化的对象是如下似然函数：
其中， 是语料库中语料数量。上述公式的一个直观理解是，将语料库中所有句子的所有分词组合形成的概率相加。
但是，初始时，词表V并不存在。因而，ULM算法采用不断迭代的方法来构造词表以及求解分词概率：
- 初始时，建立一个足够大的词表。一般，可用语料中的所有字符加上常见的子字符串初始化词表，也可以通过BPE算法初始化。
- 针对当前词表，用EM算法求解每个子词在语料上的概率。
- 对于每个子词，计算当该子词被从词表中移除时，总的loss降低了多少，记为该子词的loss。
- 将子词按照loss大小进行排序，丢弃一定比例loss最小的子词(比如20%)，保留下来的子词生成新的词表。这里需要注意的是，单字符不能被丢弃，这是为了避免OOV情况。
- 重复步骤2到4，直到词表大小减少到设定范围。
可以看出，ULM会保留那些以较高频率出现在很多句子的分词结果中的子词，因为这些子词如果被丢弃，其损失会很大。
SentencePiece
如何使用上述子词算法？一种简便的方法是使用SentencePiece，它是谷歌推出的子词开源工具包，其中集成了BPE、ULM子词算法。除此之外，SentencePiece还能支持字符和词级别的分词。更进一步，为了能够处理多语言问题，sentencePiece将句子视为Unicode编码序列，从而子词算法不用依赖于语言的表示。
总结不易，如果觉得本文有所帮助请点个赞^_^，更多精彩内容欢迎关注公众号【IT民工boby】。