5
$\begingroup$

I have been trying to understand how the unigram tokenizer works since it is used in the sentencePiece tokenizer that I am planning on using, but I cannot wrap my head around it.

I tried to read the original paper, which contains so little details that it feels like it's been written explicitely not to be understood. I also read several blog posts about it but none really clarified it (one straight up admitted not undertanding it completely).

Can somebody explain it to me? I am familiar with the EM algorithm but I cannot see how it related to the loss function in order to find the subwords probabilities...

$\endgroup$

1 Answer 1

5
$\begingroup$

The explanation in the documentation of the Huggingface Transformers library seems more approachable:

Unigram is a subword tokenization algorithm introduced in Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (Kudo, 2018). In contrast to BPE or WordPiece, Unigram initializes its base vocabulary to a large number of symbols and progressively trims down each symbol to obtain a smaller vocabulary. The base vocabulary could for instance correspond to all pre-tokenized words and the most common substrings. Unigram is not used directly for any of the models in the transformers, but itโ€™s used in conjunction with SentencePiece.

At each training step, the Unigram algorithm defines a loss (often defined as the log-likelihood) over the training data given the current vocabulary and a unigram language model. Then, for each symbol in the vocabulary, the algorithm computes how much the overall loss would increase if the symbol was to be removed from the vocabulary. Unigram then removes p (with p usually being 10% or 20%) percent of the symbols whose loss increase is the lowest, i.e. those symbols that least affect the overall loss over the training data. This process is repeated until the vocabulary has reached the desired size. The Unigram algorithm always keeps the base characters so that any word can be tokenized.

Because Unigram is not based on merge rules (in contrast to BPE and WordPiece), the algorithm has several ways of tokenizing new text after training. As an example, if a trained Unigram tokenizer exhibits the vocabulary:

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

"hugs" could be tokenized both as ["hug", "s"], ["h", "ug", "s"] or ["h", "u", "g", "s"]. So which one to choose? Unigram saves the probability of each token in the training corpus on top of saving the vocabulary so that the probability of each possible tokenization can be computed after training. The algorithm simply picks the most likely tokenization in practice, but also offers the possibility to sample a possible tokenization according to their probabilities.

Those probabilities are defined by the loss the tokenizer is trained on. Assuming that the training data consists of the words ๐‘ฅ1,โ€ฆ,๐‘ฅ๐‘ and that the set of all possible tokenizations for a word ๐‘ฅ๐‘– is defined as ๐‘†(๐‘ฅ๐‘–), then the overall loss is defined as

$\mathcal{L} = -\sum_{i=1}^{N} \log \left ( \sum_{x \in S(x_{i})} p(x) \right )$

There are some parts that are not very detailed, though, for instance, how it initializes the base (seed) vocabulary to a large number of symbols". This part is more clearly explained in the original article by the end of section 3.2:

There are several ways to prepare the seed vocabulary. The natural choice is to use the union of all characters and the most frequent substrings in the corpus. Frequent substrings can be enumerated in $O(T)$ time and $O(20T)$ space with the Enhanced Suffix Array algorithm (Nong et al., 2009), where T is the size of the corpus.

About the details of the expectation maximization algorithm used to compute probabilities, this is what happens:

  1. [Expectation] Estimate each subword probability by the corresponding frequency counts in the vocabulary
  2. [Maximization] Use the Viterbi algorithm to segment the corpus, returning the optimal segments.

You can check the details, together with practical examples, in this tutorial.

$\endgroup$
6
  • $\begingroup$ Yeah I've read that already, it's nicely layed out but doesn't explain two things: - How are the possible tokenizations generated at the beginning (since we start with all possible tokenizations and progressively reduce the set) ? - How are the probabilities of the possible tokens computed? I guess this one could be trivially done by frequency count but the original paper indicates that they use the EM algorithm (without explaining how. classic google paper) and I don't understand why or how. $\endgroup$
    – Johncowk
    Feb 3, 2021 at 13:23
  • $\begingroup$ I updated my answer to address the points to indicated. $\endgroup$
    – noe
    Feb 3, 2021 at 14:53
  • $\begingroup$ Thank you very much. $\endgroup$
    – Johncowk
    Feb 3, 2021 at 15:36
  • $\begingroup$ The HuggingFace documentation describes a tokeniser that doesn't exist. It should not be relied on as an explanation for ULM, because it doesn't even come close. $\endgroup$
    – Mew
    Feb 26 at 12:43
  • $\begingroup$ @Mew could you provide some sources? $\endgroup$
    – noe
    Feb 26 at 20:53

Your Answer

By clicking โ€œPost Your Answerโ€, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.