大家好，我是半虹，这篇文章来讲分词算法

---

1  概述

所谓分词就是将文本段落分解成基本语言单位，这里的基本单位也可以称为词元

在上篇文章，我们主要从分词过程的角度出发，介绍了一些不同类型的分词算法

而本篇文章，我们将要从分词结果的角度出发，来介绍一些不同粒度的分词算法

2  按粒度划分

分词算法按照粒度可以分为以下三类：词粒度、字粒度、子词粒度，下面会逐一进行讨论

2.1 词粒度

基于词粒度的分词是最为直观的分词，这与人类理解自然语言的过程是相似的

对于英文来说，句子中的空格是天然的分隔符；对于中文来说，情况则变得更困难

在上篇文章中所介绍的多种分词方法，都属于词粒度分词方法，一个例子如下

例句：he is likely to be unfriendly to me

分词：['he', 'is', 'likely', 'to', 'be', 'unfriendly', 'to', 'me']

基于词粒度的分词有着一些优点：

1. 词粒度的划分能够保留更多的语义信息

但是这种分词方法也有其他缺点：

1. 无论对于中文还是英文，词的数量都是庞大的，因此需要维护一张巨大的词表 ( $\text{vocabulary}$ )
2. 即使拥有着巨大的词表，还是难以避免地遇到在词表中从来没有出现过的生词 ( $\text{out of vocabulary}$ )
3. 而且特别对于英文来说，模型难以学习到同一个单词的不同形式和变化

2.2 字粒度

基于字粒度的分词是一种极端的分词，此类方法直接将文本分解为最小粒度

对于英文来说，就是将其分解为字母；对于中文来说，就是将其分解为汉字

由于操作简单，此类方法甚至无需建立模型，就按字符划分即可，一个例子如下

例句：he is likely to be unfriendly to me

分词：['h', 'e', 'i', 's', 'l', 'i', 'k', 'e', 'l', 'y', 't', 'o', 'b', 'e', 'u', 'n', 'f', 'r', 'i', 'e', 'n', 'd', 'l', 'y', 't', 'o', 'm', 'e']

基于字粒度的分词优点如下：

1. 词表规模大大较少，这是因为英文字母就只有  $26$  个，中文常用汉字也只有  $3500$  个
2. 极少出现未知词汇，很多常用词都可以由字母或者汉字组合得到

从另一方面来说其缺点如下：

1. 单个字母或者单个汉字并没有包含太多的语义信息
2. 同样的文本会切分更多的词元，使输入的长度增加，从而让模型变得难训练

2.3 子词粒度

不难发现，词粒度和字粒度的优劣是互补的，那会不会有一种折中的方案，能够综合二者的优点呢

答案自然是肯定的，这种方案就是子词粒度，这是目前很多大规模预训练模型所采用的分词方法，例子如下

例句：he is likely to be unfriendly to me

分词：['he', 'is', 'like', 'ly', 'to', 'be', 'un', 'friend', 'ly', 'to', 'me']

基于子词粒度分词，其核心为：用尽可能小的词表来覆盖尽可能多的词汇

这种方案介于词粒度和字粒度，能很好地平衡 $\text{out of vocabulary}$ 的问题

怎么达到此效果呢？关键就是：用词表中的小词元来组成句子中的大词汇，类似于英文中的词缀组合

例如现给定词汇 unfriendly，可将其拆分为以下的词元：un、friend、ly

这些词元本身也是带有语义的，如 un 表示否定、friend  表示友好、ly  表示品质

而且词元之间也能相互组合来构成新词汇，例如，like 和 ly 组合成 likely

这有利于模型学习词汇之间的形式和变化，同时还具有更好的泛化性

基于子词粒度分词的研究重点是如何划分子词，下面来介绍一些目前常用的基于子词的分词算法

1. $\text{Byte Pair Encoding}$ ( $\text{BPE}$ )
2. $\text{WordPiece}$
3. $\text{Unigram Language Model}$ ( $\text{ULM}$ )
4. $\text{SentencePiece}$

2.3.1 BPE

初次发表在：$\text{Neural Machine Translation of Rare Words with Subword Units}$

应用模型如：$\text{GPT-2}$、$\text{RoBERTa}$、…

字节对编码算法最初用于数据压缩领域，该算法的编码过程会有点类似于哈夫曼树的构建过程，可描述如下

首先将词分为单个字符，这些字符作为初始子词，然后迭代合并频率最高的子词对，直至到达预设词表大小

学习 $\text{BPE}$ 词表的步骤及例子如下：

1. 准备语料库，定义词表大小和迭代次数，假设语料库中只有以下句子：

   a tidy tiger tied a tie tighter to tidy her tiny tail
   

2. 用预分词器将语料库的句子切分为单词，可以用空格或规则切分

   拆分单词为字符序列，并且在每个单词的末尾加停止符用以表示结尾，停止符可以是 </w>

   统计单词的出现频率，这些单词及其频率构成训练语料：

   {
       'a </w>': 2,
       't i d y </w>': 2,
       't i g e r </w>': 1,
       't i e d </w>': 1,
       't i e </w>': 1,
       't i g h t e r </w>': 1,
       't o </w>': 1,
       'h e r </w>': 1,
       't i n y </w>': 1,
       't a i l </w>': 1,
   }
   

   统计字符的出现频率，这些字符作为初始子词构成词典：

   {
       '</w>': 12,
       'a': 3,
       't': 10,
       'i': 8,
       'd': 3,
       'y': 3,
       'g': 2,
       'e': 5,
       'r': 3,
       'h': 2,
       'o': 1,
       'n': 1,
       'l': 1,
   }
   

3. 开始迭代，每次迭代完成以下操作，直至到达预设词表大小或到达迭代次数

   统计语料中相邻子词对的出现频率，选取频率最高的子词对合并成新的子词加入词表，并更新词典

   每次更新，词典可能出现三种变化：

   1. 词典的数量加一，这表明加入了合并后的子词，同时原来的两个子词被保留
   2. 词典的数量减一，这表明加入了合并后的子词，同时原来的两个子词被消解
   3. 词典的数量不变，这表明加入了合并后的子词，同时原来的两个子词一个被保留、一个被消解

   随着迭代的进行，词典大小通常先增后减

   
   

   第一次迭代如下：统计发现，子词 t 和 i 相邻出现的频率最高，将二者合并进词表，并更新词典

   { # 语料
       'a </w>': 2,
       'ti d y </w>': 2,
       'ti g e r </w>': 1,
       'ti e d </w>': 1,
       'ti e </w>': 1,
       'ti g h t e r </w>': 1,
       't o </w>': 1,
       'h e r </w>': 1,
       'ti n y </w>': 1,
       't a i l </w>': 1,
   }
   

   { # 词典
       '</w>': 12,
       'a': 3,
       't': 3, # [修改]
       'i': 1, # [修改]
       'd': 3,
       'y': 3,
       'g': 2,
       'e': 5,
       'r': 3,
       'h': 2,
       'o': 1,
       'n': 1,
       'l': 1,
       'ti': 7, # [增加]
   }
   

   { # 词表
       'ti',
   }
   

   第二次迭代如下：统计发现，子词 y 和 </w> 相邻出现的频率最高，将二者合并进词表，并更新词典

   { # 语料
       'a </w>': 2,
       'ti d y</w>': 2,
       'ti g e r </w>': 1,
       'ti e d </w>': 1,
       'ti e </w>': 1,
       'ti g h t e r </w>': 1,
       't o </w>': 1,
       'h e r </w>': 1,
       'ti n y</w>': 1,
       't a i l </w>': 1,
   }
   

   { # 词典
       '</w>': 9, # [修改]
       'a': 3,
       't': 3,
       'i': 1,
       'd': 3,
       # 'y': 0, # [删减]
       'g': 2,
       'e': 5,
       'r': 3,
       'h': 2,
       'o': 1,
       'n': 1,
       'l': 1,
       'ti': 7,
       'y</w>': 3, # [增加]
   }
   

   { # 词表
       'ti',
       'y</w>',
   }
   

   第三次迭代如下：统计发现，子词 e 和 r 相邻出现的频率最高，将二者合并进词表，并更新词典

   { # 语料
       'a </w>': 2,
       'ti d y</w>': 2,
       'ti g er </w>': 1,
       'ti e d </w>': 1,
       'ti e </w>': 1,
       'ti g h t er </w>': 1,
       't o </w>': 1,
       'h er </w>': 1,
       'ti n y</w>': 1,
       't a i l </w>': 1,
   }
   

   { # 词典
       '</w>': 9,
       'a': 3,
       't': 3,
       'i': 1,
       'd': 3,
       'g': 2,
       'e': 2, # [修改]
       # 'r': 0, # [删减]
       'h': 2,
       'o': 1,
       'n': 1,
       'l': 1,
       'ti': 7,
       'y</w>': 3,
       'er': 3, # [增加]
   }
   

   { # 词表
       'ti',
       'y</w>',
       'er',
   }
   

   第四次迭代如下：统计发现，子词 er 和 </w> 相邻出现的频率最高，将二者合并进词表，并更新词典

   { # 语料
       'a </w>': 2,
       'ti d y</w>': 2,
       'ti g er</w>': 1,
       'ti e d </w>': 1,
       'ti e </w>': 1,
       'ti g h t er</w>': 1,
       't o </w>': 1,
       'h er</w>': 1,
       'ti n y</w>': 1,
       't a i l </w>': 1,
   }
   

   { # 词典
       '</w>': 6, # [修改]
       'a': 3,
       't': 3,
       'i': 1,
       'd': 3,
       'g': 2,
       'e': 2,
       'h': 2,
       'o': 1,
       'n': 1,
       'l': 1,
       'ti': 7,
       'y</w>': 3,
       # 'er': 0, # [删减]
       'er</w>': 3, # [新增]
   }
   

   { # 词表
       'ti',
       'y</w>',
       'er',
       'er</w>',
   }
   

   …

4. 最终，上述词表加上基础字符得到最终词表如下

   {
       # 上述词表
       'ti',
       'y</w>',
       'er',
       'er</w>',
       # 基础字符
       '</w>',
       'a',
       't',
       'i',
       'd',
       'y',
       'g',
       'e',
       'r',
       'h',
       'o',
       'n',
       'l',
   }
   

应用 $\text{BPE}$ 词表分词的步骤及例子如下：

0. 设子词词表如下：

   {
       'ti',
       'y</w>',
       'er',
       'er</w>',
       '</w>',
       'a',
       't',
       'i',
       'd',
       'y',
       'g',
       'e',
       'r',
       'h',
       'o',
       'n',
       'l',
   }
   

   且输入句子如下：

   tiger is tidy
   

1. 将子词词表中的子词按照长度从大到小进行排序（若长度相同，则按照上述词典对应词频排序）

   {
       'er</w>',
       'ti',
       'y</w>',
       'er',
       '</w>',
       'a',
       't',
       'd',
       'g',
       'e',
       'h',
       'i',
       'o',
       'n',
       'l',
       'r',
       'y',
   }
   

   将输入句子预分词，并在每个单词后添加停止符 </w>

   ['tiger</w>', 'is</w>', 'tidy</w>']
   

2. 对输入句子的每个单词，遍历排序的词典

   若当前子词是这个单词的子字符串，则将其切分并对剩余部分继续匹配

   若遍历完词典仍有子字符串无匹配，则将这些子字符串替换成未知标志，例如 <unk>

   最终结果如下：

   ['ti', 'g', 'er</w>', 'i', '<unk>', '</w>', 'ti', 'd', 'y</w>']
   

   上述过程亦可称为编码过程，通常发生在模型的输入部分，旨在将文本分解成词元输入到模型

   另外与之对应的是解码过程，通常发生在模型的输出部分，旨在将模型输出的词元还原成文本

   具体就是将上述的词元序列直接拼接起来即可，但要注意将 </w> 替换回空格

   对应结果如下：

   tiger i<unk> tidy
   

2.3.2 WordPiece

初次发表在：$\text{Japanese And Korean Voice Search}$

应用模型如：$\text{BERT}$、$\text{DistilBERT}$

$\text{WordPiece}$ 和 $\text{BPE}$ 很像，唯一的不同在于子词合并的方法

$\text{BPE}$ 选择频次最高的相邻子词合并，而 $\text{WordPiece}$ 选择能最大程度增加语料概率的相邻子词合并

设句子 $S$ 由若干个相互独立的子词 $(t_1,t_2,...,t_n)$ 组成，则句子的概率似然值如下：
$$\log P(S)=\sum _{i=1}^{n}P(t_i)$$
设子词 $x$ 和子词 $y$ 合并后得到子词 $z$，那么句子的似然变化量如下：
$$\begin{array}{rl}\Delta \log P(S)& =\log P(z)-(\log P(x)+\log P(y))\\ & \\ & =\log \frac{P(z)}{P(x)\cdot P(y)}\\ & \\ & =\log \frac{P(x,y)}{P(x)\cdot P(y)}\end{array}$$
可以看到，句子的似然变化量实际上就是子词 $x$ 和子词 $y$ 的互信息量

选择能最大程度增加语料概率的相邻子词合并 ，实际上就是选择具有最大互信息量的相邻子词合并

互信息量越大，说明子词之间的相互关联越强 ，说明它们在语料中经常相邻出现

2.3.3 ULM

初次发表在：Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates

应用模型如：…

$\text{ULM}$ 与 $\text{WordPiece}$ 一样，都是根据概率来选择子词，而 $\text{BPE}$  则是根据频次来选择子词

但是，$\text{BPE}$ 和 $\text{WordPiece}$  的词表是从小到大扩增的，而 $\text{ULM}$ 的词表是从大到小缩减的

具体来说，$\text{ULM}$ 从一个大词表开始，每次迭代去除对语料概率增益较小的子词，直至到达预设词表大小

需要注意，$\text{ULM}$ 假设所有子词独立，因此句子的概率似然值会等于其组成子词的概率乘积

学习 $\text{ULM}$ 词表的步骤如下：

1. 准备语料库，定义词表大小和迭代次数

2. 初始化词表，通常就是语料中所有字符加上所有高频子字符串，或者也可以用 $\text{BPE}$ 来初始化

3. 现开始迭代，每次迭代完成以下操作，直至到达预设词表大小或到达迭代次数

   对当前词表，用期望最大算法计算每个子词的出现概率

   为每个子词计算损失，这个损失表示当该子词被丢弃时，语料的概率似然值的减少程度

   基于损失对子词排序，丢弃损失较小的 $20\%$ 子词，保留剩余的 $80\%$ 子词构成新的词表

   为了避免 $\text{OOV}$，单字符不能被丢弃

给定子词序列 $\chi =(x_1,...,x_M)$，假设子词间相互独立，则出现概率 $P(\chi )={\prod }_{i=1}^{M}p(x_i)$

对于输入句子 $X$，其最大概率切分 ${\chi }^{\ast }=\underset{\chi \in S(X)}{\mathrm{argmax}}P(\chi )$，其中 $S(X)$ 是 $X$ 的所有切分集合

那么如何求解每个子词的出现概率 $p(x_i)$ 呢？可以通过 $\text{EM}$ 算法最大化以下的似然函数估算
$$\mathcal{L}=\sum _{s=1}^{|D|}\log (P(X^{(s)}))=\sum _{s=1}^{|D|}\log (\sum _{\chi \in S(X^{(s)})}P(\chi ))$$
其中 $|D|$ 为语料大小，该公式的直观理解是将语料库中所有句子的所有切分组合的概率相加

每个子词的损失表示为当子词被移除时 $\mathcal{L}$ 的下降程度

2.3.4 SentencePiece

初次发表在：SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing

应用模型如：$\text{ALBERT}$、$\text{XLNet}$、$\text{T5}$、…

$\text{SentencePiece}$ 是 $\text{Google}$ 开源的子词切分工具，集成 $\text{BPE}$ 、$\text{ULM}$ 算法，并对这些算法进行改进

$\text{SentencePiece}$ 的改进就是将所有输入都转换成 $\text{Unicode}$ 字符，包括空格，这样处理会有以下好处

1. 可以统一处理多种语言
2. 可以统一处理空格字符，无需预先切分单词

---

好啦，本文到此结束，感谢您的阅读！

如果你觉得这篇文章有需要修改完善的地方，欢迎在评论区留下你宝贵的意见或者建议

如果你觉得这篇文章还不错的话，欢迎点赞、收藏、关注，你的支持是对我最大的鼓励 (/ω＼)