Why is the WordPiece algorithm implemented according to the maximum mutual information?

Question

WordPiece is a subword segmentation algorithm in the field of natural language processing. Different from BPE, WordPiece will select a pair with the largest mutual information to merge each time, and the pair here is defined as adjacent subwords.

Most of the tutorials are given like this: The WordPiece algorithm assumes that each subword is independent of each other, so for a subword sequence $S=(t_1,\cdots,t_n)$, its probability can be written as

$$ \log P(S)=\sum_{i=1}^n \log P(t_i)\tag{1} $$

If we choose subwords $t_i$ and $t_j$ to merge, and record the merged subword as $t_k$, then the change value of $\log P(S)$ is

$$ \log P(t_k)-\bigl(\log P(t_i)+\log P(t_j)\bigr)=\log\frac{P(t_k)}{P(t_i)P(t_j)}\tag{2} $$

Many tutorials define $\log\frac{P(t_k)}{P(t_i)P(t_j)}$ as the mutual information between two subwords, but I think this approach is a bit inappropriate. In fact, according to Wikipedia, the mutual information between two subwords should be

$$ \log\frac{P(t_i,t_j)}{P(t_i)P(t_j)}\tag{3} $$

But before that, it has been assumed that the subwords are independent of each other, so $P(t_i,t_j)=P(t_i)P(t_j)$, thus the value of formula $(3)$ is $0$, which seems a bit contradictory.

Which step went wrong?

Answer 1

This is about a modeling assumption differing from reality. Let me respond point-by-point.

it has been assumed that the subwords are independent of each other

The modeling assumption that subwords are independently generated is not a fact about reality. It is a choice that Kudo made in defining the SentencePiece segmentation model; in fact, it is quite common in segmentation. As they say, "All models are wrong, but some are useful."

$P(t_i, t_j) = P(t_i)P(t_j)$, thus the value of formula (3) is 0

That's not quite true. The mutual information calculation compares the empirical distributions of the subwords on a corpus. Acknowledging that the modeling assumption is not true, the mutual information asks how frequently the two subwords co-occur, compared to our prior belief according to the model about their co-occurrence. This divergence between the true and predicted values is what makes the mutual information nonzero.

Many tutorials define $\log \frac{P(t_k)}{P(t_i)P(t_j)}$ as the mutual information between two subwords, but I think this approach is a bit inappropriate.

To call the quantity $\frac{P(t_k)}{P(t_i)P(t_j)}$ (point wise) mutual information is completely correct and in line with the standard usage of MI applied to bigrams in NLP for at least 40 years. This is because the subword $t_k$ yields exactly the same string as $t_it_j$, so the numerator is equal to $P(t_i, t_j)$.