BPE、WordPiece和SentencePiece

2022-04-25 本文已影响0人 Jarkata

1. 背景与基础

在使用GPT BERT模型输入词语常常会先进行tokenize ，tokenize具体目标与粒度是什么呢？tokenize也有许多类别及优缺点，这篇文章总结一下各个方法及实际案例。

tokenize的目标是把输入的文本流，切分成一个个子串，每个子串相对有完整的语义，便于学习embedding表达和后续模型的使用。

tokenize有三种粒度：word/subword/char

word/词，词，是最自然的语言单元。对于英文等自然语言来说，存在着天然的分隔符，如空格或一些标点符号等，对词的切分相对容易。但是对于一些东亚文字包括中文来说，就需要某种分词算法才行。顺便说一下，Tokenizers库中，基于规则切分部分，采用了spaCy和Moses两个库。如果基于词来做词汇表，由于长尾现象的存在，这个词汇表可能会超大。像Transformer XL库就用到了一个26.7万个单词的词汇表。这需要极大的embedding matrix才能存得下。embedding matrix是用于查找取用token的embedding vector的。这对于内存或者显存都是极大的挑战。常规的词汇表，一般大小不超过5万。
char/字符，即最基本的字符，如英语中的'a','b','c'或中文中的'你'，'我'，'他'等。而一般来讲，字符的数量是少量有限的。这样做的问题是，由于字符数量太小，我们在为每个字符学习嵌入向量的时候，每个向量就容纳了太多的语义在内，学习起来非常困难。
subword/子词级，它介于字符和单词之间。比如说'Transformers'可能会被分成'Transform'和'ers'两个部分。这个方案平衡了词汇量和语义独立性，是相对较优的方案。它的处理原则是，常用词应该保持原状，生僻词应该拆分成子词以共享token压缩空间。

2. 常用tokenize算法

最常用的三种tokenize算法：BPE（Byte-Pair Encoding)，WordPiece和SentencePiece

2.1 Byte-Pair Encoding (BPE) / Byte-level BPE

2.1.1 BPE

BPE，即字节对编码。其核心思想在于将最常出现的子词对合并，直到词汇表达到预定的大小时停止。

首先，它依赖于一种预分词器pretokenizer来完成初步的切分。pretokenizer可以是简单基于空格的，也可以是基于规则的；
分词之后，统计每个词出现的频次，供后续计算使用。例如，我们统计到了5个词的词频

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

建立基础词汇表，包括所有的字符，即：

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

根据规则，我们分别考察2-gram，3-gram的基本字符组合，把高频的ngram组合依次加入到词汇表中，直到词汇表达到预定大小停止。比如，我们计算出ug/un/hug三种组合出现频次分别为20，16和15，加入到词汇表中。
最终词汇表的大小= 基础字符词汇表大小 + 合并串的数量，比如像GPT，它的词汇表大小 40478 = 478(基础字符) + 40000（merges）。添加完后，我们词汇表变成：

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

实际使用中，如果遇到未知字符用<unk>代表。

2.1.2 Byte-level BPE

BPE的一个问题是，如果遇到了unicode，基本字符集可能会很大。一种处理方法是我们以一个字节为一种“字符”，不管实际字符集用了几个字节来表示一个字符。这样的话，基础字符集的大小就锁定在了256。

例如，像GPT-2的词汇表大小为50257 = 256 + <EOS> + 50000 mergers，<EOS>是句子结尾的特殊标记。

2.2 WordPiece

WordPiece，从名字好理解，它是一种子词粒度的tokenize算法subword tokenization algorithm，很多著名的Transformers模型，比如BERT/DistilBERT/Electra都使用了它。

它的原理非常接近BPE，不同之处在于它做合并时，并不是直接找最高频的组合，而是找能够最大化训练数据似然的merge。即它每次合并的两个字符串A和B，应该具有最大的 $\frac{P(AB)}{P(A)P(B)}$ 值。合并AB之后，所有原来切成A+B两个tokens的就只保留AB一个token，整个训练集上最大似然变化量与 $\frac{P(AB)}{P(A)P(B)}$ 成正比。

2.3 Unigram

与BPE或者WordPiece不同，Unigram的算法思想是从一个巨大的词汇表出发，再逐渐删除trim down其中的词汇，直到size满足预定义。

初始的词汇表可以采用所有预分词器分出来的词，再加上所有高频的子串。
每次从词汇表中删除词汇的原则是使预定义的损失最小。训练时，计算loss的公式为：
$Loss = - \sum^{N}_{i=1}log \left( \sum_{x \in S(x_i)} p(x) \right )$
假设训练文档中的所有词分别为 $x_1;x_2,...,x_N$ ，而每个词tokenize的方法是一个集合 $S(x_i)$ 。
当一个词汇表确定时，每个词tokenize的方法集合 $S(x_i)$ 就是确定的，而每种方法对应着一个概率 $p(x)$ 。
如果从词汇表中删除部分词，则某些词的tokenize的种类集合就会变少，log(*)中的求和项就会减少，从而增加整体loss。

Unigram算法每次会从词汇表中挑出使得loss增长最小的10%~20%的词汇来删除。
一般Unigram算法会与SentencePiece算法连用。

2.4 SentencePiece

SentencePiece，顾名思义，它是把一个句子看作一个整体，再拆成片段，而没有保留天然的词语的概念。一般地，它把空格space也当作一种特殊字符来处理，再用BPE或者Unigram算法来构造词汇表。

比如，XLNetTokenizer就采用了_来代替空格，解码的时候会再用空格替换回来。

目前，Tokenizers库中，所有使用了SentencePiece的都是与Unigram算法联合使用的，比如ALBERT、XLNet、Marian和T5.

3. 切分实例与代码分析

3.1 BertTokenizer/ WordPiece

先试一个BertTokenizer，它基于WordPiece算法，base版本的词汇表大小为21128

from transformers import BertTokenizer
tokenizer = BertTokenizer.from_pretrained('bert-base-chinese')
tokens = t.encode(...).tokens

切分效果为：

Tokenizer: <class 'transformers.models.bert.tokenization_bert.BertTokenizer'>
Text: The problems of your past are your business. The problems of your future are my privilege.
Tokens: [UNK],pro,##ble,##ms,of,your,pa,##st,are,your,business,.,[UNK],pro,##ble,##ms,of,your,future,are,my,pr,##i,##vi,##le,##ge,.

Text: 你的过去我不愿过问，那是你的事情。你的未来我希望参与，这是我的荣幸。
Tokens: 你,的,过,去,我,不,愿,过,问,，,那,是,你,的,事,情,。,你,的,未,来,我,希,望,参,与,，,这,是,我,的,荣,幸,。

Text: Don’t make the user feel stupid.
Tokens: [UNK],[UNK],t,make,the,user,feel,st,##up,##id,.

Text: 中国语言研究院正式宣布，“笔画最多的汉字”的桂冠属于“龖（dá）”字！
Tokens: 中,国,语,言,研,究,院,正,式,宣,布,，,[UNK],笔,画,最,多,的,汉,字,[UNK],的,桂,冠,属,于,[UNK],[UNK],（,[UNK],）,[UNK],字,！

其中，

BertTokenizer中，用##符号表示非开头的子词，比如第1句中的problems被拆分成了三部分，pro/##ble/##ms；
标点符号、生僻字等未出现的token被[UNK]代替
中文基本拆分成了字的形式，并没有看到多字词的形式

分词流程与代码分析如下：
BertTokenizer类关系如下

在代码中查看

主要做了两件事情：

根据参数控制来对输入文本做基础分词 (basic_tokenizer)
对于切分出来的单个词，再切分(wordpiece_tokenizer)

basic_tokenizer是把句子切分成词，仍然可以对着代码看一下：

特别要注意的在 401 行：如果 tokenize_chinese_chars 参数为 True，那么所有的中文词都会被切成字符级别！！！参数传来的 never_split 并不会让这些中文词不被切分。

wordpiece_tokenizer则是将词切成字符级别，例如 doing->['do', '###ing']。

这里的做法就是把一个词送入 BERT 中做最大匹配（类似于 Jieba 分词的正向最大匹配算法），如果前面已经有匹配，则后面的词都会加 ’##‘。

而中文，因为已经在上一步被切分成字符级别，所以不会有任何改变。

3.2 T5Tokenizer / SentencePiece

T5模型是基于SentencePiece的，我们看看它的切分效果。我用的这个版本词汇表大小是250112。

Tokenizer: <class 'transformers.models.t5.tokenization_t5.T5Tokenizer'>
Text: The problems of your past are your business. The problems of your future are my privilege.
Tokens: ▁The,▁problems,▁of,▁your,▁past,▁are,▁your,▁business,.,▁The,▁problems,▁of,▁your,▁future,▁are,▁my,▁,privilege,.

Text: 你的过去我不愿过问，那是你的事情。你的未来我希望参与，这是我的荣幸。
Tokens: ▁,你的,过去,我不,愿,过,问,,,那是,你,的事情,。,你的,未来,我,希望,参与,,,这是,我的,荣,幸,。

Text: Don’t make the user feel stupid.
Tokens: ▁Don,’,t,▁make,▁the,▁user,▁feel,▁stupid,.

Text: 中国语言研究院正式宣布，“笔画最多的汉字”的桂冠属于“龖（dá）”字！
Tokens: ▁,中国,语言,研究院,正式,宣布,,“,笔,画,最多,的,汉,字,”,的,桂,冠,属于,“,<0xE9>,<0xBE>,<0x96>,(,dá,),”,字,!

其中，

最明显的，可以看到下划线被引入，代替了空格和句子开头特殊符号
中文可以看到一些多字词，比如“未来”，“研究院”等，但有些词其实不符合一般的分词习惯，比如“的事情”、“我不”等等
生僻字龖被拆成了三个基础字节形式的token