大模型的分词算法

看了一些介绍tokenizer算法的文章，感觉大家介绍的时候并不是很系统，甚至有的文章还有一些错误，所以我在这篇文章做了一个汇总，没有个人原创的内容。

分词方法	典型模型
BPE	GPT,GPT-J, GPT-Neo, RoBERTa, BART, ChatGLM-6B, Baichuan
BBPE	GPT-2, LLaMA
UniLM	mBART, XLNet
WordPiece	BERT, DistilBERT，MobileBERT
SentencePiece	ALBERT, T5, Flan T5, XLM-RoBERTa

BPE

💡 输入：训练语料；词表大小V
1.准备足够大的训练语料，确定期望的subword词表大小；
2.准备基础词表：比如英文中26个字母加上各种符号；
3.基于基础词表将语料中的单词拆分为字符序列并在末尾添加后缀“ </ w>”；本阶段的subword的粒度是字符。例如单词“ low”的频率为5，那么我们将其改写为“ l o w </ w>”：5；
4.统计每一个连续字节对的出现频率，选择最高频的字符对合并成新的subword；
5.重复第4步直到达到第1步设定的subword词表大小或下一个最高频的字节对出现频率为1；

代码参考这篇文章，知乎几乎所有的代码都是来自于这里

https://leimao.github.io/blog/Byte-Pair-Encoding/

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
'''
https://leimao.github.io/blog/Byte-Pair-Encoding/
'''

import re, collections

def get_vocab(filename):
    vocab = collections.defaultdict(int)
    with open(filename, 'r', encoding='utf-8') as fhand:
        for line in fhand:
            words = line.strip().split()
            for word in words:
                vocab[' '.join(list(word)) + ' </w>'] += 1

    return vocab

def get_stats(vocab):
    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
    return pairs

def merge_vocab(pair, v_in):
    v_out = {}
    bigram = re.escape(' '.join(pair))
    p = re.compile(r'(?<!\S)' + bigram + r'(?!\S)')
    for word in v_in:
        w_out = p.sub(''.join(pair), word)
        v_out[w_out] = v_in[word]
    return v_out

def get_tokens_from_vocab(vocab):
    tokens_frequencies = collections.defaultdict(int)
    vocab_tokenization = {}
    for word, freq in vocab.items():
        word_tokens = word.split()
        for token in word_tokens:
            tokens_frequencies[token] += freq
        vocab_tokenization[''.join(word_tokens)] = word_tokens
    return tokens_frequencies, vocab_tokenization

def measure_token_length(token):
    if token[-4:] == '</w>':
        return len(token[:-4]) + 1
    else:
        return len(token)

def tokenize_word(string, sorted_tokens, unknown_token='</u>'):
    
    if string == '':
        return []
    if sorted_tokens == []:
        return [unknown_token]

    string_tokens = []
    for i in range(len(sorted_tokens)):
        token = sorted_tokens[i]
        token_reg = re.escape(token.replace('.', '[.]'))

        matched_positions = [(m.start(0), m.end(0)) for m in re.finditer(token_reg, string)]
        if len(matched_positions) == 0:
            continue
        substring_end_positions = [matched_position[0] for matched_position in matched_positions]

        substring_start_position = 0
        for substring_end_position in substring_end_positions:
            substring = string[substring_start_position:substring_end_position]
            string_tokens += tokenize_word(string=substring, sorted_tokens=sorted_tokens[i+1:], unknown_token=unknown_token)
            string_tokens += [token]
            substring_start_position = substring_end_position + len(token)
        remaining_substring = string[substring_start_position:]
        string_tokens += tokenize_word(string=remaining_substring, sorted_tokens=sorted_tokens[i+1:], unknown_token=unknown_token)
        break
    return string_tokens

# vocab = {'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}

vocab = get_vocab('../data/pg16457.txt')

print('==========')
print('Tokens Before BPE')
tokens_frequencies, vocab_tokenization = get_tokens_from_vocab(vocab)
print('All tokens: {}'.format(tokens_frequencies.keys()))
print('Number of tokens: {}'.format(len(tokens_frequencies.keys())))
print('==========')

num_merges = 10000
for i in range(num_merges):
    pairs = get_stats(vocab)
    if not pairs:
        break
    best = max(pairs, key=pairs.get)
    vocab = merge_vocab(best, vocab)
    print('Iter: {}'.format(i))
    print('Best pair: {}'.format(best))
    tokens_frequencies, vocab_tokenization = get_tokens_from_vocab(vocab)
    print('All tokens: {}'.format(tokens_frequencies.keys()))
    print('Number of tokens: {}'.format(len(tokens_frequencies.keys())))
    print('==========')

# Let's check how tokenization will be for a known word
word_given_known = 'mountains</w>'
word_given_unknown = 'Ilikeeatingapples!</w>'

sorted_tokens_tuple = sorted(tokens_frequencies.items(), key=lambda item: (measure_token_length(item[0]), item[1]), reverse=True)
sorted_tokens = [token for (token, freq) in sorted_tokens_tuple]

print(sorted_tokens)

word_given = word_given_known 

print('Tokenizing word: {}...'.format(word_given))
if word_given in vocab_tokenization:
    print('Tokenization of the known word:')
    print(vocab_tokenization[word_given])
    print('Tokenization treating the known word as unknown:')
    print(tokenize_word(string=word_given, sorted_tokens=sorted_tokens, unknown_token='</u>'))
else:
    print('Tokenizating of the unknown word:')
    print(tokenize_word(string=word_given, sorted_tokens=sorted_tokens, unknown_token='</u>'))

word_given = word_given_unknown 

print('Tokenizing word: {}...'.format(word_given))
if word_given in vocab_tokenization:
    print('Tokenization of the known word:')
    print(vocab_tokenization[word_given])
    print('Tokenization treating the known word as unknown:')
    print(tokenize_word(string=word_given, sorted_tokens=sorted_tokens, unknown_token='</u>'))
else:
    print('Tokenizating of the unknown word:')
    print(tokenize_word(string=word_given, sorted_tokens=sorted_tokens, unknown_token='</u>'))

'''
Tokenizing word: mountains</w>...
Tokenization of the known word:
['mountains</w>']
Tokenization treating the known word as unknown:
['mountains</w>']
Tokenizing word: Ilikeeatingapples!</w>...
Tokenizating of the unknown word:
['I', 'like', 'ea', 'ting', 'app', 'l', 'es!</w>']
'''

BBPE

对于英文来说，使用BPE能够在词表可控的前提下解决OOV的问题，但是对于中文、日文等语言时，稀有文字可能会不必要的占用词表大小。所以BBPE方法是将一本文本的UTF-8编码中的一个字节256位不同编码作为词表的初始化Subword。

相比ASCII只能覆盖英文中字符，UTF-8编码创建的本身就是为了通用的将世界上不同的语言字符尽可能全部用一套编码进行编号，同时相比UTF-32对于每个字符都采用4位字节（byte）过于冗长。改进的UTF-8编码是一个变长的编码，有1～4个范围的字节(bytes)长度。对于不同语言中字符采用不同长度的字节编码，例如英文字符基本都是1个字节（byte），中文汉字通常需要2～3个字节。

核心思想是用byte来构建最基础的词表而不是字符。首先将文本按照UTF-8进行编码，每个字符在UTF-8的表示中占据1-4个byte。在byte序列上再使用BPE算法，进行byte level的相邻合并。编码形式如下。

在解码阶段，一个byte序列可能解码后不是一个合法的字符序列，这里需要动态规划进行解码，使其能解码出尽可能多的合法字符。所以BBPE虽然解决了中文、日文词表过大的问题，但是解码上还是有一些问题。

WordPiece

💡 输入：训练语料；词表大小V
1.准备足够大的训练语料，确定期望的subword词表大小；
2.准备基础词表：比如英文中26个字母加上各种符号；
3.基于基础词表将语料中的单词拆分为最小单元;
4.基于第3步数据训练语言模型，可以是最简单的unigram语言模型，通过极大似然进行估计即可;
5.从所有可能的subword单元中选择加入语言模型后能最大程度地增加训练数据概率的单元作为新的单元;
6.重复第5步直到达到第2步设定的subword词表大小或概率增量低于某一阈值;

WordPiece算法跟BPE算法流程基本一致，BPE是基于最高词频来生成Subword，而WordPiece是基于概率来生成Subword。具体来说，有一个词为z，z由x和y组成，对比P(Z)的概率和P(X)+P(Y)的概率，如果 $P(Z)>P(X)+P(Y)$ ，则合并x和y，因为他们具有最的互信息，也就是在语言模型上具有较强的关联性。

我们假设句子 $S=(t_1,t_2,…,t_n)$ ，其中 $t_i$ 代表一个子词，且假设各个子词之间是相互独立存在的，那么句子的语言模型似然值等价于所有子词概率的乘积。

$logP(S) = \sum_{i}^nlogP(t_i)$

假设把相邻位置的x和y两个子词进行合并，合并后产生的新的字词为z，此时句子S的似然值变化可以表示为：

$logP(t_z)-(logP(t_x)+logP(t_y))=log(\frac{P(t_z)}{P(t_x)P(t_y)})$

从上面的公式可以发现，似然值的变化就是两个子词的互信息。简而言之，WordPiece每次选择合并的两个子词，他们具有最大的互信息值，也就是相关字词在语言模型上具有较强的关联性，他们经常在语料中以相邻的方式同时出现。

UniLM

💡 输入：训练语料；词表大小V；保留阈值X；
1.准备基础词表：初始化一个很大的词表，比如所有字符+高频Ngram，也可以通过BPE算法初始化；
2.针对当前词表，用语言模型（unigram lm)估计每个子词在语料上的概率；
3.计算删除每个Subword后对总loss的影响及Score得分，作为该Subword排序的Score得分；
4.将子词按照Score大小进行排序，保留前X%的Subword；注意，建议单字符的Subword不能被丢弃，以免OOV；
5.重复步骤2到4，直到词表大小减少到设定值；

UniLM可以看成是WordPiece算法在执行过程中进行反向操作。相比WordPiece借助语言模型选择合并计算概率最大的相邻字符对加入词表中作为新的Subword，UniLM是开始时先构建足够大的词表，之后每一步选择一定比例的计算概率低的Subword从词表中删除。因此过程中比较显著差别是WordPiece算法的词表在生成过程中是从小到大的变化，而UniLM的词表则是从大到小的变化，整个过程根据评估不断删除排序靠后的Subword直到词表大小减少到设定值。