Does Your Language Model Have "Unpredictable Words"?

你的语言模型有没有“无法预测的词”？ 苏剑林 · 2022-04-20 · Machine Learning language model multi-task

As we all know, classification models typically work by first obtaining an encoded vector and then feeding it into a Dense layer to predict the probability of each class, with prediction outputting the class with the highest probability. But has anyone considered the following possibility: a trained classification model might have "unpredictable classes" — meaning that no matter what the input is, it's simply impossible for it to predict a certain class $k$; class $k$ can never be the one with the highest probability.

Of course, this situation generally only arises when the number of classes vastly exceeds the dimensionality of the encoding vector; ordinary classification problems are rarely this extreme. However, we know that a language model is fundamentally also a classification model, where the number of classes equals the total size of the vocabulary, which is often far larger than the vector dimension. So does our language model have "unpredictable words"? (Here we only consider greedy decoding.)

Does It Exist?

The ACL 2022 paper Low-Rank Softmax Can Have Unargmaxable Classes in Theory but Rarely in Practice was the first to explore this question. As its title suggests, the answer is "it exists in theory but rarely occurs in practice." more

Let's first look at "existing in theory." To prove existence, we only need to construct a concrete example. Let the class vectors be denoted $\boldsymbol{w}_1,\boldsymbol{w}_2,\cdots,\boldsymbol{w}_n\in\mathbb{R}^d$, with bias term $b_1,b_2,\cdots,b_n$. Suppose class $k$ is predictable; then there exists $\boldsymbol{z}\in\mathbb{R}^d$ that simultaneously satisfies

\begin{equation}\langle\boldsymbol{w}_k,\boldsymbol{z}\rangle + b_k > \langle\boldsymbol{w}_i,\boldsymbol{z}\rangle + b_i\quad (\forall i \neq k)\end{equation}

Conversely, if class $k$ is unpredictable, then for any $\boldsymbol{z}\in\mathbb{R}^d$, there must exist some $i\neq k$ satisfying

\begin{equation}\langle\boldsymbol{w}_k,\boldsymbol{z}\rangle + b_k \leq \langle\boldsymbol{w}_i,\boldsymbol{z}\rangle + b_i\end{equation}

Since here we only need to give an example, for simplicity let's first consider the case without a bias term, and set $k=n$. The condition then becomes $\langle \boldsymbol{w}_i - \boldsymbol{w}_n, \boldsymbol{z}\rangle \geq 0$, i.e., for any vector $\boldsymbol{z}$, we can always find some vector $\boldsymbol{w}_i - \boldsymbol{w}_n$ whose angle with it is at most 90 degrees. It's not hard to imagine that when the number of vectors exceeds the dimensionality of the space and the vectors are uniformly distributed in that space, this can indeed happen — for instance, in a 2D plane, any vector must form an angle of less than 90 degrees with at least one of $(0,1),(1,0),(0,-1),(-1,0)$. From this we can construct the example:

\begin{equation}\left\{\begin{aligned} &\boldsymbol{w}_5 = (1, 1) \quad(\boldsymbol{w}_5\text{can be chosen freely})\\ &\boldsymbol{w}_1 = (1, 1) + (0, 1) = (1, 2)\\ &\boldsymbol{w}_2 = (1, 1) + (1, 0) = (2, 1)\\ &\boldsymbol{w}_3 = (1, 1) + (0, -1) = (1, 0)\\ &\boldsymbol{w}_4 = (1, 1) + (-1, 0) = (0, 1)\\ \end{aligned}\right.\end{equation}

In this example, class 5 is unpredictable — if you don't believe it, feel free to substitute some values of $\boldsymbol{z}$ and check.

How to Determine This

Now that we've confirmed "unpredictable classes" can indeed exist, a natural question arises: given a trained model, i.e., given $\boldsymbol{w}_1,\boldsymbol{w}_2,\cdots,\boldsymbol{w}_n\in\mathbb{R}^d$ and $b_1,b_2,\cdots,b_n$, how do we determine whether an unpredictable class exists among them?

Based on the description in the previous section, from the perspective of solving inequalities, if class $k$ is predictable, then the solution set of the following system of inequalities must be non-empty:

\begin{equation}\langle\boldsymbol{w}_k - \boldsymbol{w}_i,\boldsymbol{z}\rangle + (b_k - b_i) > 0\quad (\forall i \neq k)\end{equation}

Without loss of generality, let's again set $k=n$, and denote $\Delta\boldsymbol{w}_i = \boldsymbol{w}_n - \boldsymbol{w}_i, \Delta b_i = b_n - b_i$. Notice that

\begin{equation}\langle\Delta\boldsymbol{w}_i,\boldsymbol{z}\rangle + \Delta b_i > 0\,(i = 1,2,\cdots,n-1)\quad\Leftrightarrow\quad \min_i \langle\Delta\boldsymbol{w}_i,\boldsymbol{z}\rangle + \Delta b_i > 0\end{equation}

So, as long as we try to maximize $\min\limits_i \langle\Delta\boldsymbol{w}_i,\boldsymbol{z}\rangle + \Delta b_i$, if the final result is positive, then class $n$ is predictable; otherwise it is unpredictable. Readers who have previously read Musings on Multi-Task Learning (II): Doing Row-Space Gradient Business will find this problem "déjà vu" — especially in the case without a bias term, where it is almost identical to the process of finding the "Pareto optimum" in multi-task learning.

Now the problem becomes

\begin{equation}\max_{\boldsymbol{z}} \min_i \langle\Delta\boldsymbol{w}_i,\boldsymbol{z}\rangle + \Delta b_i\end{equation}

To avoid divergence to infinity, we can add a constraint $\Vert \boldsymbol{z}\Vert\leq r$:

\begin{equation}\max_{\Vert \boldsymbol{z}\Vert\leq r} \min_i \langle\Delta\boldsymbol{w}_i,\boldsymbol{z}\rangle + \Delta b_i \end{equation}

where $r$ is a constant. As long as $r$ is taken sufficiently large, it will match reality closely enough, since the outputs of neural networks are typically bounded anyway. The subsequent process is almost identical to that in Musings on Multi-Task Learning (II): Doing Row-Space Gradient Business. First, we introduce

\begin{equation}\mathbb{P}^{n-1} = \left\{(\alpha_1,\alpha_2,\cdots,\alpha_{n-1})\left|\alpha_1,\alpha_2,\cdots,\alpha_{n-1}\geq 0, \sum_i \alpha_i = 1\right.\right\}\end{equation}

so the problem becomes

\begin{equation}\max_{\Vert \boldsymbol{z}\Vert\leq r} \min_{\alpha\in\mathbb{P}^{n-1}} \left\langle\sum_i \alpha_i \Delta\boldsymbol{w}_i,\boldsymbol{z}\right\rangle + \sum_i \alpha_i \Delta b_i\end{equation}

By von Neumann's minimax theorem, we can swap the order of $\max$ and $\min$:

\begin{equation}\min_{\alpha\in\mathbb{P}^{n-1}} \max_{\Vert \boldsymbol{z}\Vert\leq r}\left\langle\sum_i \alpha_i \Delta\boldsymbol{w}_i,\boldsymbol{z}\right\rangle + \sum_i \alpha_i \Delta b_i\end{equation}

Clearly, the step involving $\max$ is achieved when $\Vert\boldsymbol{z}\Vert=r$ and $\boldsymbol{z}$ points in the same direction as $\sum\limits_i \alpha_i \Delta\boldsymbol{w}_i$, giving the result

\begin{equation}\min_{\alpha\in\mathbb{P}^{n-1}} r\left\Vert\sum_i \alpha_i \Delta\boldsymbol{w}_i\right\Vert + \sum_i \alpha_i \Delta b_i\end{equation}

When $r$ is sufficiently large, the influence of the bias term becomes negligible, so this is almost equivalent to the case without a bias term:

\begin{equation}\min_{\alpha\in\mathbb{P}^{n-1}} \left\Vert\sum_i \alpha_i \Delta\boldsymbol{w}_i\right\Vert\end{equation}

The process of solving the final $\min$ has already been discussed in Musings on Multi-Task Learning (II): Doing Row-Space Gradient Business, which mainly relies on the Frank–Wolfe algorithm, so we won't repeat it here.

(Note: The above derivation of the discriminative procedure is my own; it differs from the method used in the paper Low-Rank Softmax Can Have Unargmaxable Classes in Theory but Rarely in Practice.)

What About in Practice?

The discussion so far has been purely theoretical — so how likely is it, in practice, for actual language models to have "unpredictable words"? The original paper examined this on a number of trained language models and generative models, and found that in practice the probability of this occurring is quite small. For example, here are the test results on a machine translation model:

Test results of the machine translation model

This actually isn't hard to understand. From our earlier discussion, we know that "unpredictable words" generally only appear when the number of classes is far greater than the vector dimension — this is exactly the "low-rank" in the paper's title. But due to the "curse of dimensionality," the notion of "far greater than" isn't quite as intuitive as we might think. For example, in a 2D space, having 4 classes could already be considered "far greater," but in a 200-dimensional space, even 40,000 classes wouldn't count as "far greater." The vector dimension of common language models is typically several hundred, while the vocabulary size is at most on the order of hundreds of thousands — so this actually doesn't qualify as "far greater than" either. Hence the probability of "unpredictable words" occurring is quite small.

Additionally, we can also prove that if all the $\boldsymbol{w}_i$ are distinct from each other but have equal norms, then "unpredictable words" absolutely cannot occur. This unpredictable situation therefore only arises when the norms of $\boldsymbol{w}_i$ vary substantially. In the mainstream deep models used today, thanks to the widespread application of various normalization techniques, cases where the norms of $\boldsymbol{w}_i$ vary substantially are quite rare — which further reduces the likelihood of "unpredictable words" occurring.

Of course, as mentioned at the beginning of the article, the "unpredictable words" discussed here specifically refer to maximization-based prediction, i.e., greedy search. If beam search or random sampling is used instead, then even "unpredictable words" could still potentially be generated. So this notion of "unpredictable words" is more of a fun theoretical curiosity than something of much practical value.

Summary

In this post, I've introduced a phenomenon that has little practical value but is quite interesting: your language model may harbor certain "unpredictable words" that can never be the one with the highest probability.