Word perplexity on a subword language model

Question

Let's have corpora

$X = x_1...x_N$

in which every word can be represented using subwords (from a fixed size vocabulary of subwords)

$x_i = x_{i,0}...x_{i,M(x_i)}$

where $M(x_i)$ is number of subwords to which the word is divided.

For a word language model we would calculate perplexity using formula:

$\exp\left(\frac{{\sum_{i=1}^N \log \left(\dfrac{1}{q(x_i)}\right)}}{N}\right)$

where $q(x_i)$ is probability of a word from language model.

My questions are:

1. Is it valid to calculate word perplexity on a subword language model, where $q'(x_i) $ would equal to $\prod_{j=1}^{M(x_i)}r(x_{i,j})$ and $r(x_{i,j})$ is probability from subword language model. The whole formula would look like this:

$\exp\left(\frac{{\sum_{i=1}^N \log \left(\dfrac{1}{\prod_{j=1}^{M(x_i)}r(x_{i,j})}\right)}}{N}\right) = \exp\left(\frac{{\sum_{i=1}^N \sum_{j=1}^{M(x_i)}\log \left(\dfrac{1}{r(x_{i,j})}\right)}}{N}\right)$

2. If not is there other way to calculate word perplexity on subword model and do two language models with different vocabulary can be even compared?

3. The probability is actually conditional probability $q(x_i|x_{0...i-1})$, does it change something in that manner?

Answer 1

I disagree with the other response, because you cannot compare perplexities across different tokenizations; the denominator is different. The same amount of log-likelihood is distributed across different numbers of units (e.g., 13 words vs 30 subwords). In that sense, your approach is correct because you're dividing by the number of words in both cases.

(In natural language processing, when we say 'perplexity', we implicitly mean 'perplexity per word'. Being explicit about those last two words would make things a lot clearer.)

---

There's a more subtle problem that prevents you from simply comparing in the way you describe. The naive approach to computing a string's probability in a subword model underestimates its probability. This is because multiple tokenizations will give you the same text.

Example. If a subword vocabulary includes the tokens $\{\mathrm{t}, \mathrm{h},\mathrm{e},\mathrm{th},\mathrm{the}\}$, then the string $\mathrm{the}$ can be generated in three ways: $\{\mathrm{t+h+e}, \mathrm{th+e},\mathrm{the}\}$. You need to marginalize over all three.

So the correct way to compute the probability of string $\boldsymbol{x}$ in the language model $r$ is to marginalize over all segmentations $\boldsymbol{s}$ which yield the string $\boldsymbol{x}$: $$ p(\boldsymbol{x}) = \sum_{\boldsymbol{s} \in \operatorname{segmentations}(\boldsymbol{x})} \prod_{{i=1}}^{|\boldsymbol{s}|} r\left(s_{i} \mid \boldsymbol{s}_{<i}\right) \text{.} $$

Each subword $s_i$ is conditioned the tokens generated before it in the sequence, $\boldsymbol{s}_{<i}$.

---

These issues are discussed at length in Cao and Rimell (2021 at EMNLP).

Answer 2

No, I thought you don't need to multiply the probabilities of the subwords of a word, and all you need to do is just treat each subword as a word, and hence the formula is OK if you change the $x_i$ in your first formula to $x_i\in \{generated\_subwords\}$.

References:

1. https://twitter.com/lmthang/status/1222398272427347968
2. https://arxiv.org/pdf/2001.09977.pdf