In this video, we will study together "the Unigram Language Model subword tokenization algorithm".

The overall training strategy of a Unigram LM 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 LM model is a type of statistical Language Modem. A statistical LM 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 LM 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 this 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 10 times the word hug, 12 times the word pug, 5 times the word lug, 4 times bug and 5 times dug. As said at the beginning of the video, 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 that's what we'll do here. We could also have used the BPE algorithm with a very large vocabulary size. So we have our initial vocabulary. 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. Then we remove the p percent of tokens that minimize the loss on the corpus and which do not belong to the basic characters 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 is 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, 2 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 one hundred and seventy. 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 and we can still choose the remaining tokenization with a probability of one point ten minus two. 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. 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 one hundred and sixty-eight. 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 % of the tokens by iteration. The second token that could be removed at this iteration is the "du" token. 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 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. And that's it! I hope that this example has allowed you to better understand the Unigram tokenization algorithm.