(air whooshing)
- In this video,
we will study together 'the Unigram Language Model
subword tokenization algorithm'.
The overall training strategy
of a Unigram Language Model tokenizer
is to start with a very large vocabulary
and then to remove tokens at each iteration
until we reach the desired size.
At each iteration,
we will calculate a loss on our training corpus
thanks to the Unigram model.
As the loss calculation depends on the available vocabulary,
we can use it to choose how to reduce the vocabulary.
So we look at the evolution of the loss
by removing in turn each token from the vocabulary.
We will choose to remove the p-percents
which increase the loss the less.
Before going further
in the explanation of the training algorithm,
I need to explain what is an Unigram model.
The Unigram Language Model
is a type of Statistical Language Modem.
A Statistical Language Model
will assign a probability to a text
considering that the text is in fact a sequence of tokens.
The simplest sequences of tokens to imagine
are the words that compose the sentence or the characters.
The particularity of Unigram Language Model
is that it assumes that the occurrence of each word
is independent of its previous word.
This assumption allows us to write
that the probability of a text
is equal to the product of the probabilities
of the tokens that compose it.
It should be noted here that it is a very simple model
which would not be adapted to the generation of text
since this model would always generate the same token,
the one which has the greatest probability.
Nevertheless, to do tokenization,
this model is very useful to us
because it can be used
to estimate the relative likelihood of different phrases.
We are now ready
to return to our explanation of the training algorithm.
Let's say that we have as a training corpus
with 10 times the word hug,
12 times the word pug,
5 times the word lug,
4 times bug
and 5 times dug.
As said earlier,
the training starts with a big vocabulary.
Obviously, as we are using a toy corpus,
this vocabulary will not be that big
but it should show you the principle.
A first method is to list all the possible strict substrings
and that's what we'll do here.
We could also have used the BPE algorithm
with a very large vocabulary size
but for now, the strict substrings are enough.
The training of the Unigram tokenizer
is based on the Expectation-Maximization method.
At each iteration,
we estimate the probabilities of the tokens
of the vocabulary
and then we remove the p-percent of tokens
that minimize the loss on the corpus
and which do not belong to the basic character
as we want to keep in our final vocabulary
the basic characters to be able to tokenize any word.
Let's go for it!
The probability of a token simply estimated
by the number of appearance of this token
in our training corpus
divided by the total number of appearance of all the tokens.
We could use this vocabulary to tokenize our words
according to the Unigram model.
We will do it together to understand two things:
how we tokenize a word with a Unigram model
and how the loss is calculated on our corpus.
The Unigram LM tokenization of our text 'Hug'
will be the one with the highest probability of occurrence
according to our Unigram model.
To find it, the simplest way to proceed
would be to list all the possible segmentations
of our text 'Hug',
calculate the probability of each of these segmentations
and then choose the one with the highest probability.
With the current vocabulary,
two tokenizations get exactly the same probability.
So we choose one of them
and keep in memory the associated probability.
To compute the loss on our training corpus,
we need to tokenize as we just did
all the remaining words in the corpus.
The loss is then the sum over all the words in the corpus
of the frequency of occurrence of the word
multiplied by the opposite of the log of the probability
associated with the tokenization of the word.
We obtain here a loss of 170.
Remember, our initial goal was to reduce the vocabulary.
To do this, we will remove a token from the vocabulary
and calculate the associated loss.
Let's remove for example, the token 'ug'.
We notice that the tokenization for 'hug'
with the letter 'h' and the tuple 'ug' is now impossible.
Nevertheless, as we saw earlier
that two tokenizations had the same probability,
we can still choose the remaining tokenization
with a probability of 1.10e-2.
The tokenizations of the other words of the vocabulary
also remain unchanged.
And finally, even if we remove the token 'ug'
from our vocabulary the loss remains equal to 170.
For this first iteration,
if we continue the calculation,
we would notice that we could remove any token
without it impacting the loss.
We will therefore choose at random to remove the token 'ug'
before starting a second iteration.
So we estimate again the probability of each token
before calculating the impact of each token on the loss.
For example, if we remove now
the token composed of the letters 'h' and 'u',
there is only one possible tokenization left for hug.
The tokenization of the other words of the vocabulary
is not changed.
In the end,
we obtain by removing the token
composed of the letters 'h' and 'u' from the vocabulary,
a loss of 168.
Finally, to choose which token to remove,
we will for each remaining token of the vocabulary,
which is not an elementary token,
calculate the associated loss.
Then, compare these losses between them.
The token which we will remove
is the token which impacts the least the loss,
here the token 'bu'.
We had mentioned at the beginning of the video
that at each iteration we could remove
p-percent of the tokens by iteration.
The second token that could be removed at this iteration
is the token 'du'.
And that's it.
We just have to repeat these steps
until we get the vocabulary of the desired size.
One last thing.
In practice, when we tokenize a word with a Unigram model,
we don't compute the set of probabilities of
all the possible splits of a word
before comparing them to keep the best one
but we use the Viterbi algorithm
which is much more efficient way to do it.
And that's it!
I hope that this example
has allowed you to better understand
the Unigram tokenization algorithm.
(air whooshing)