SentencePiece and BPE¶
Introduction to Tokenization¶
In order to process text in neural network models it is first required to encode text as numbers with ids, since the tensor operations act on numbers. Finally, if the output of the network is to be words, it is required to decode the predicted tokens ids back to text.
To encode text, the first decision that has to be made is to what level of granularity are we going to consider the text? Because ultimately, from these tokens, features are going to be created about them. Many different experiments have been carried out using words, morphological units, phonemic units or characters as tokens. For example,
But how to identify these units, such as words, is largely determined by the language they come from. For example, in many European languages a space is used to separate words, while in some Asian languages there are no spaces between words. Compare English and Mandarin.
- Tokens are tricky. (original sentence)
- 标记很棘手 (Mandarin)
- Biāojì hěn jíshǒu (pinyin)
- 标记 很 棘手 (Mandarin with spaces)
So, the ability to tokenize, i.e. split text into meaningful fundamental units, is not always straight-forward.
Also, there are practical issues of how large our vocabulary of words, vocab_size, should be, considering memory limitations vs. coverage. A compromise may be need to be made between:
- the finest-grained models employing characters which can be memory intensive and
- more computationally efficient subword units such as n-grams or larger units.
In SentencePiece unicode characters are grouped together using either a unigram language model (used in this week's assignment) or BPE, byte-pair encoding. We will discuss BPE, since BERT and many of its variants use a modified version of BPE and its pseudocode is easy to implement and understand... hopefully!
Unsurprisingly, even using unicode to initially tokenize text can be ambiguous, e.g.,
eaccent = '\u00E9'
e_accent = '\u0065\u0301'
print(f'{eaccent} = {e_accent} : {eaccent == e_accent}')
é = é : False
SentencePiece uses the Unicode standard normalization form, NFKC, so this isn't an issue. Looking at the example from above but with normalization:
from unicodedata import normalize
norm_eaccent = normalize('NFKC', '\u00E9')
norm_e_accent = normalize('NFKC', '\u0065\u0301')
print(f'{norm_eaccent} = {norm_e_accent} : {norm_eaccent == norm_e_accent}')
é = é : True
Normalization has actually changed the unicode code point (unicode unique id) for one of these two characters.
def get_hex_encoding(s):
return ' '.join(hex(ord(c)) for c in s)
def print_string_and_encoding(s):
print(f'{s} : {get_hex_encoding(s)}')
for s in [eaccent, e_accent, norm_eaccent, norm_e_accent]:
print_string_and_encoding(s)
é : 0xe9 é : 0x65 0x301 é : 0xe9 é : 0xe9
This normalization has other side effects which may be considered useful such as converting curly quotes “ to " their ASCII equivalent. (Although we *now lose directionality of the quote...)
Lossless Tokenization¶
SentencePiece also ensures that when you tokenize your data and detokenize your data the original position of white space is preserved. However, tabs and newlines are converted to spaces, please try this experiment yourself later below.
To ensure this lossless tokenization, SentencePiece replaces white space with _ (U+2581). So that a simple join of the tokens by replacing underscores with spaces can restore the white space, even if there are consecutive symbols. But remember first to normalize and then replace spaces with _ (U+2581). As the following example shows.
s = 'Tokenization is hard.'
s_ = s.replace(' ', '\u2581')
s_n = normalize('NFKC', 'Tokenization is hard.')
print(get_hex_encoding(s))
print(get_hex_encoding(s_))
print(get_hex_encoding(s_n))
0x54 0x6f 0x6b 0x65 0x6e 0x69 0x7a 0x61 0x74 0x69 0x6f 0x6e 0x20 0x69 0x73 0x20 0x68 0x61 0x72 0x64 0x2e 0x54 0x6f 0x6b 0x65 0x6e 0x69 0x7a 0x61 0x74 0x69 0x6f 0x6e 0x2581 0x69 0x73 0x2581 0x68 0x61 0x72 0x64 0x2e 0x54 0x6f 0x6b 0x65 0x6e 0x69 0x7a 0x61 0x74 0x69 0x6f 0x6e 0x20 0x69 0x73 0x20 0x68 0x61 0x72 0x64 0x2e
So the special unicode underscore was replaced by the ASCII unicode. Reversing the order of the second and third operations, you see that the special unicode underscore was retained.
s = 'Tokenization is hard.'
sn = normalize('NFKC', 'Tokenization is hard.')
sn_ = s.replace(' ', '\u2581')
print(get_hex_encoding(s))
print(get_hex_encoding(sn))
print(get_hex_encoding(sn_))
0x54 0x6f 0x6b 0x65 0x6e 0x69 0x7a 0x61 0x74 0x69 0x6f 0x6e 0x20 0x69 0x73 0x20 0x68 0x61 0x72 0x64 0x2e 0x54 0x6f 0x6b 0x65 0x6e 0x69 0x7a 0x61 0x74 0x69 0x6f 0x6e 0x20 0x69 0x73 0x20 0x68 0x61 0x72 0x64 0x2e 0x54 0x6f 0x6b 0x65 0x6e 0x69 0x7a 0x61 0x74 0x69 0x6f 0x6e 0x2581 0x69 0x73 0x2581 0x68 0x61 0x72 0x64 0x2e
BPE Algorithm¶
After discussing the preprocessing that SentencePiece performs, you will get the data, preprocess it, and apply the BPE algorithm. You will see how this reproduces the tokenization produced by training SentencePiece on the example dataset (from this week's assignment).
Preparing our Data¶
First, you get the Squad data and process it as above.
import ast
def convert_json_examples_to_text(filepath):
example_jsons = list(map(ast.literal_eval, open(filepath))) # Read in the json from the example file
texts = [example_json['text'].decode('utf-8') for example_json in example_jsons] # Decode the byte sequences
text = '\n\n'.join(texts) # Separate different articles by two newlines
text = normalize('NFKC', text) # Normalize the text
with open('example.txt', 'w') as fw:
fw.write(text)
return text
text = convert_json_examples_to_text('./data/data.txt')
print(text[:900])
Beginners BBQ Class Taking Place in Missoula! Do you want to get better at making delicious BBQ? You will have the opportunity, put this on your calendar now. Thursday, September 22nd join World Class BBQ Champion, Tony Balay from Lonestar Smoke Rangers. He will be teaching a beginner level class for everyone who wants to get better with their culinary skills. He will teach you everything you need to know to compete in a KCBS BBQ competition, including techniques, recipes, timelines, meat selection and trimming, plus smoker and fire information. The cost to be in the class is $35 per person, and for spectators it is free. Included in the cost will be either a t-shirt or apron and you will be tasting samples of each meat that is prepared. Discussion in 'Mac OS X Lion (10.7)' started by axboi87, Jan 20, 2012. I've got a 500gb internal drive and a 240gb SSD. When trying to restore using di
In the algorithm the vocab variable is actually a frequency dictionary of the words. Those words have been prepended with an underscore to indicate that they are the beginning of a word. Finally, the characters have been delimited by spaces so that the BPE algorithm can group the most common characters together in the dictionary in a greedy fashion. You will see how that is done shortly.
from collections import Counter
vocab = Counter(['\u2581' + word for word in text.split()])
vocab = {' '.join([l for l in word]): freq for word, freq in vocab.items()}
def show_vocab(vocab, end='\n', limit=20):
"""Show word frequencys in vocab up to the limit number of words"""
shown = 0
for word, freq in vocab.items():
print(f'{word}: {freq}', end=end)
shown +=1
if shown > limit:
break
show_vocab(vocab)
▁ B e g i n n e r s: 1 ▁ B B Q: 3 ▁ C l a s s: 2 ▁ T a k i n g: 1 ▁ P l a c e: 1 ▁ i n: 15 ▁ M i s s o u l a !: 1 ▁ D o: 1 ▁ y o u: 13 ▁ w a n t: 1 ▁ t o: 33 ▁ g e t: 2 ▁ b e t t e r: 2 ▁ a t: 1 ▁ m a k i n g: 2 ▁ d e l i c i o u s: 1 ▁ B B Q ?: 1 ▁ Y o u: 1 ▁ w i l l: 6 ▁ h a v e: 4 ▁ t h e: 31
You check the size of the vocabulary (frequency dictionary) because this is the one hyperparameter that BPE depends on crucially on how far it breaks up a word into SentencePieces. It turns out that for your trained model on the small dataset that 60% of 455 merges of the most frequent characters need to be done to reproduce the upperlimit of a 32K vocab_size over the entire corpus of examples.
print(f'Total number of unique words: {len(vocab)}')
print(f'Number of merges required to reproduce SentencePiece training on the whole corpus: {int(0.60*len(vocab))}')
Total number of unique words: 455 Number of merges required to reproduce SentencePiece training on the whole corpus: 273
BPE Algorithm¶
Directly from the BPE paper you have the following algorithm.
import re, collections
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_sentence_piece_vocab(vocab, frac_merges=0.60):
sp_vocab = vocab.copy()
num_merges = int(len(sp_vocab)*frac_merges)
for i in range(num_merges):
pairs = get_stats(sp_vocab)
best = max(pairs, key=pairs.get)
sp_vocab = merge_vocab(best, sp_vocab)
return sp_vocab
To understand what's going on first take a look at the third function get_sentence_piece_vocab. It takes in the current vocab word-frequency dictionary and the fraction, frac_merges, of the total vocab_size to merge characters in the words of the dictionary, num_merges times. Then for each merge operation it get_stats on how many of each pair of character sequences there are. It gets the most frequent pair of symbols as the best pair. Then it merges that pair of symbols (removes the space between them) in each word in the vocab that contains this best (= pair). Consequently, merge_vocab creates a new vocab, v_out. This process is repeated num_merges times and the result is the set of SentencePieces (keys of the final sp_vocab).
Additional Discussion of BPE Algorithm¶
Please feel free to skip the below if the above description was enough.
In a little more detail you can see in get_stats you initially create a list of bigram (two character sequence) frequencies from the vocabulary. Later, this may include trigrams, quadgrams, etc. Note that the key of the pairs frequency dictionary is actually a 2-tuple, which is just shorthand notation for a pair.
In merge_vocab you take in an individual pair (of character sequences, note this is the most frequency best pair) and the current vocab as v_in. You create a new vocab, v_out, from the old by joining together the characters in the pair (removing the space), if they are present in a word of the dictionary.
Warning: the expression (?<!\S) means that either a whitespace character follows before the bigram or there is nothing before the bigram (it is the beginning of the word), similarly for (?!\S) for preceding whitespace or the end of the word.
sp_vocab = get_sentence_piece_vocab(vocab)
show_vocab(sp_vocab)
▁B e g in n ers: 1 ▁BBQ: 3 ▁Cl ass: 2 ▁T ak ing: 1 ▁P la ce: 1 ▁in: 15 ▁M is s ou la !: 1 ▁D o: 1 ▁you: 13 ▁w an t: 1 ▁to: 33 ▁g et: 2 ▁be t ter: 2 ▁a t: 1 ▁mak ing: 2 ▁d e l ic i ou s: 1 ▁BBQ ?: 1 ▁ Y ou: 1 ▁will: 6 ▁have: 4 ▁the: 31
import sentencepiece as spm
sp = spm.SentencePieceProcessor(model_file='./data/sentencepiece.model')
# help(sp)
Try it out on the first sentence of the example text.
s0 = 'Beginners BBQ Class Taking Place in Missoula!'
# encode: text => id
print(sp.encode_as_pieces(s0))
print(sp.encode_as_ids(s0))
# decode: id => text
print(sp.decode_pieces(sp.encode_as_pieces(s0)))
print(sp.decode_ids([12847, 277]))
['▁Beginn', 'ers', '▁BBQ', '▁Class', '▁', 'Taking', '▁Place', '▁in', '▁Miss', 'oul', 'a', '!'] [12847, 277, 15068, 4501, 3, 12297, 3399, 16, 5964, 7115, 9, 55] Beginners BBQ Class Taking Place in Missoula! Beginners
Notice how SentencePiece breaks the words into seemingly odd parts, but you have seen something similar with BPE. But how close was the model trained on the whole corpus of examples with a vocab_size of 32,000 instead of 455? Here you can also test what happens to white space, like '\n'.
But first note that SentencePiece encodes the SentencePieces, the tokens, and has reserved some of the ids as can be seen in this week's assignment.
uid = 15068
spiece = "\u2581BBQ"
unknown = "__MUST_BE_UNKNOWN__"
# id <=> piece conversion
print(f'SentencePiece for ID {uid}: {sp.id_to_piece(uid)}')
print(f'ID for Sentence Piece {spiece}: {sp.piece_to_id(spiece)}')
# returns 0 for unknown tokens (we can change the id for UNK)
print(f'ID for unknown text {unknown}: {sp.piece_to_id(unknown)}')
SentencePiece for ID 15068: ▁BBQ ID for Sentence Piece ▁BBQ: 15068 ID for unknown text __MUST_BE_UNKNOWN__: 2
print(f'Beginning of sentence id: {sp.bos_id()}')
print(f'Pad id: {sp.pad_id()}')
print(f'End of sentence id: {sp.eos_id()}')
print(f'Unknown id: {sp.unk_id()}')
print(f'Vocab size: {sp.vocab_size()}')
Beginning of sentence id: -1 Pad id: 0 End of sentence id: 1 Unknown id: 2 Vocab size: 32000
You can also check what are the ids for the first part and last part of the vocabulary.
print('\nId\tSentP\tControl?')
print('------------------------')
# <unk>, <s>, </s> are defined by default. Their ids are (0, 1, 2)
# <s> and </s> are defined as 'control' symbol.
for uid in range(10):
print(uid, sp.id_to_piece(uid), sp.is_control(uid), sep='\t')
# for uid in range(sp.vocab_size()-10,sp.vocab_size()):
# print(uid, sp.id_to_piece(uid), sp.is_control(uid), sep='\t')
Id SentP Control? ------------------------ 0 <pad> True 1 </s> True 2 <unk> False 3 ▁ False 4 X False 5 . False 6 , False 7 s False 8 ▁the False 9 a False
Train SentencePiece BPE model with our example.txt¶
Finally, train your own BPE model directly from the SentencePiece library and compare it to the results of the implemention of the algorithm from the BPE paper itself.
spm.SentencePieceTrainer.train('--input=example.txt --model_prefix=example_bpe --vocab_size=450 --model_type=bpe')
sp_bpe = spm.SentencePieceProcessor()
sp_bpe.load('example_bpe.model')
print('*** BPE ***')
print(sp_bpe.encode_as_pieces(s0))
*** BPE *** ['▁B', 'e', 'ginn', 'ers', '▁BBQ', '▁Cl', 'ass', '▁T', 'ak', 'ing', '▁P', 'la', 'ce', '▁in', '▁M', 'is', 's', 'ou', 'la', '!']
sentencepiece_trainer.cc(177) LOG(INFO) Running command: --input=example.txt --model_prefix=example_bpe --vocab_size=450 --model_type=bpe
sentencepiece_trainer.cc(77) LOG(INFO) Starts training with :
trainer_spec {
input: example.txt
input_format:
model_prefix: example_bpe
model_type: BPE
vocab_size: 450
self_test_sample_size: 0
character_coverage: 0.9995
input_sentence_size: 0
shuffle_input_sentence: 1
seed_sentencepiece_size: 1000000
shrinking_factor: 0.75
max_sentence_length: 4192
num_threads: 16
num_sub_iterations: 2
max_sentencepiece_length: 16
split_by_unicode_script: 1
split_by_number: 1
split_by_whitespace: 1
split_digits: 0
pretokenization_delimiter:
treat_whitespace_as_suffix: 0
allow_whitespace_only_pieces: 0
required_chars:
byte_fallback: 0
vocabulary_output_piece_score: 1
train_extremely_large_corpus: 0
hard_vocab_limit: 1
use_all_vocab: 0
unk_id: 0
bos_id: 1
eos_id: 2
pad_id: -1
unk_piece: <unk>
bos_piece: <s>
eos_piece: </s>
pad_piece: <pad>
unk_surface: ⁇
enable_differential_privacy: 0
differential_privacy_noise_level: 0
differential_privacy_clipping_threshold: 0
}
normalizer_spec {
name: nmt_nfkc
add_dummy_prefix: 1
remove_extra_whitespaces: 1
escape_whitespaces: 1
normalization_rule_tsv:
}
denormalizer_spec {}
trainer_interface.cc(351) LOG(INFO) SentenceIterator is not specified. Using MultiFileSentenceIterator.
trainer_interface.cc(183) LOG(INFO) Loading corpus: example.txt
trainer_interface.cc(407) LOG(INFO) Loaded all 26 sentences
trainer_interface.cc(423) LOG(INFO) Adding meta_piece: <unk>
trainer_interface.cc(423) LOG(INFO) Adding meta_piece: <s>
trainer_interface.cc(423) LOG(INFO) Adding meta_piece: </s>
trainer_interface.cc(428) LOG(INFO) Normalizing sentences...
trainer_interface.cc(537) LOG(INFO) all chars count=4533
trainer_interface.cc(548) LOG(INFO) Done: 99.9559% characters are covered.
trainer_interface.cc(558) LOG(INFO) Alphabet size=73
trainer_interface.cc(559) LOG(INFO) Final character coverage=0.999559
trainer_interface.cc(591) LOG(INFO) Done! preprocessed 26 sentences.
trainer_interface.cc(597) LOG(INFO) Tokenizing input sentences with whitespace: 26
trainer_interface.cc(608) LOG(INFO) Done! 455
bpe_model_trainer.cc(159) LOG(INFO) Updating active symbols. max_freq=99 min_freq=1
bpe_model_trainer.cc(268) LOG(INFO) Added: freq=31 size=20 all=732 active=658 piece=▁w
bpe_model_trainer.cc(268) LOG(INFO) Added: freq=16 size=40 all=937 active=863 piece=ch
bpe_model_trainer.cc(268) LOG(INFO) Added: freq=11 size=60 all=1014 active=940 piece=▁u
bpe_model_trainer.cc(268) LOG(INFO) Added: freq=8 size=80 all=1110 active=1036 piece=me
bpe_model_trainer.cc(268) LOG(INFO) Added: freq=6 size=100 all=1166 active=1092 piece=la
bpe_model_trainer.cc(159) LOG(INFO) Updating active symbols. max_freq=6 min_freq=0
bpe_model_trainer.cc(268) LOG(INFO) Added: freq=5 size=120 all=1217 active=1042 piece=SD
bpe_model_trainer.cc(268) LOG(INFO) Added: freq=5 size=140 all=1272 active=1097 piece=▁bu
bpe_model_trainer.cc(268) LOG(INFO) Added: freq=5 size=160 all=1288 active=1113 piece=▁site
bpe_model_trainer.cc(268) LOG(INFO) Added: freq=4 size=180 all=1315 active=1140 piece=ter
bpe_model_trainer.cc(268) LOG(INFO) Added: freq=4 size=200 all=1330 active=1155 piece=asure
bpe_model_trainer.cc(159) LOG(INFO) Updating active symbols. max_freq=4 min_freq=0
bpe_model_trainer.cc(268) LOG(INFO) Added: freq=3 size=220 all=1339 active=1008 piece=ge
bpe_model_trainer.cc(268) LOG(INFO) Added: freq=3 size=240 all=1371 active=1040 piece=▁sh
bpe_model_trainer.cc(268) LOG(INFO) Added: freq=3 size=260 all=1384 active=1053 piece=▁cost
bpe_model_trainer.cc(268) LOG(INFO) Added: freq=2 size=280 all=1391 active=1060 piece=de
bpe_model_trainer.cc(268) LOG(INFO) Added: freq=2 size=300 all=1405 active=1074 piece=000
bpe_model_trainer.cc(159) LOG(INFO) Updating active symbols. max_freq=2 min_freq=0
bpe_model_trainer.cc(268) LOG(INFO) Added: freq=2 size=320 all=1427 active=1021 piece=▁GB
bpe_model_trainer.cc(268) LOG(INFO) Added: freq=2 size=340 all=1438 active=1032 piece=last
bpe_model_trainer.cc(268) LOG(INFO) Added: freq=2 size=360 all=1441 active=1035 piece=▁let
trainer_interface.cc(686) LOG(INFO) Saving model: example_bpe.model
trainer_interface.cc(698) LOG(INFO) Saving vocabs: example_bpe.vocab
show_vocab(sp_vocab, end = ', ')
▁B e g in n ers: 1, ▁BBQ: 3, ▁Cl ass: 2, ▁T ak ing: 1, ▁P la ce: 1, ▁in: 15, ▁M is s ou la !: 1, ▁D o: 1, ▁you: 13, ▁w an t: 1, ▁to: 33, ▁g et: 2, ▁be t ter: 2, ▁a t: 1, ▁mak ing: 2, ▁d e l ic i ou s: 1, ▁BBQ ?: 1, ▁ Y ou: 1, ▁will: 6, ▁have: 4, ▁the: 31,
The implementation of BPE's code from the paper matches up pretty well with the library itself! The differences are probably accounted for by the vocab_size. There is also another technical difference in that in the SentencePiece implementation of BPE a priority queue is used to more efficiently keep track of the best pairs. Actually, there is a priority queue in the Python standard library called heapq if you would like to give that a try below!
Optionally try to implement BPE using a priority queue below¶
from heapq import heappush, heappop
def heapsort(iterable):
h = []
for value in iterable:
heappush(h, value)
return [heappop(h) for i in range(len(h))]
a = [1,4,3,1,3,2,1,4,2]
heapsort(a)
[1, 1, 1, 2, 2, 3, 3, 4, 4]
For a more extensive example consider looking at the SentencePiece repo. The last few sections of this code were repurposed from that tutorial. Thanks for your participation! Next stop BERT and T5!