TL;DR
Standard neural language models suffer from a fundamental geometric flaw called the stolen probability effect, which prevents words located on the interior of the embedding space's convex hull from ever receiving high probability scores. This structural weakness means these models mathematically cannot predict certain infrequent words with high confidence, even in highly predictable contexts.
What Problem Does This Paper Address?
Most Neural Network Language Models (NNLMs) predict the next word by taking the dot product of a context-driven prediction vector ($h_t$) and all word embedding vectors ($x_i$), passing the results through a softmax function.
The authors reveal a hidden limitation in this ubiquitous setup: the geometry of the dot-product softmax strictly bounds the maximum probability of any word whose embedding vector falls inside the convex hull of the vocabulary. Even if a sequence perfectly points to an interior word (for example, the word "America" completing the phrase "the United States of America"), the model is structurally incapable of assigning it a high probability. Instead, that probability is effectively "stolen" by the words located on the outer hull of the embedding space.
Methods
- Theoretical Proof: The authors mathematically demonstrate that for any interior word vector, as the magnitude of the prediction vector grows to maximize confidence, its probability under a dot-product softmax asymptotically approaches zero.
- Approximate Detection Algorithm: Finding an exact convex hull in high-dimensional spaces (e.g., over 10 dimensions) is computationally intractable using standard methods like Quickhull. The authors developed a high-precision, low-recall approximation algorithm that discretizes the angular space of an $n$-sphere to systematically identify and classify interior words.
- Model Evaluation: The authors evaluated the effect on two popular architectures—AWD-LSTM and the Mixture of Softmaxes (MoS) model—across various dimensionalities ($d \in \{50, 100, 200\}$).
- Targeted Ensembling: To mitigate the effect, they built a hybrid model that combines an NNLM with a traditional smoothed trigram model. Because $n$-gram models rely on count statistics rather than dot-product geometry, they do not suffer from the stolen probability limitation.
Datasets
The models were trained and evaluated on the standard Wikitext-2 corpus. While no new datasets were introduced, the authors used their detection algorithm to partition the Wikitext-2 vocabulary into distinct "interior" and "non-interior" word sets for analysis.
Key Insights and Ideas
- Geometry Binds Expressiveness: The stolen probability effect is a consequence of the spatial arrangement of word embeddings rather than the dimensionality of the space or matrix rank. This makes it distinct from the well-known "softmax bottleneck."
- Infrequent Words Suffer Most: Words that appear infrequently in the training data naturally tend to have smaller embedding norms. This pulls them toward the center of the embedding space, inadvertently trapping them inside the convex hull.
- Bias Terms Are Not a Cure: Word-specific bias terms only shift logits by a constant factor. They can adjust the severity of the effect but cannot alter the underlying geometric boundaries that cause probability bounding.
Key Results
- The Probability Gap: As shown in the maximum probability rankings, NNLMs severely struggle to assign high probabilities to interior words, whereas traditional trigram models easily capture their true statistical likelihood.
- Ensemble Rescue: Incorporating a trigram model dramatically improved performance for interior words. For an MoS model ($d=100$), the targeted ensemble dropped the training perplexity of interior words from 700.0 to 157.2 and test perplexity from 645.6 to 306.7.
- Geometric vs. Norm-Based Effects: While interior words generally have smaller embedding norms, the scatter plot of maximum probability vs. embedding norm confirms that the limitation is strictly geometric: non-interior words with similarly small norms face no such probability ceiling.
Limitations and Future Work
- Approximate Detection: The proposed detection algorithm favors precision over recall (achieving ~100% precision but only 68% recall in low-dimensional tests). This means many interior words likely went undetected in higher dimensions.
- Vocabulary Scale: Wikitext-2 has a relatively small vocabulary. The authors note that larger vocabularies might introduce more interior words, potentially shifting or worsening the impact of the stolen probability effect.
- Architectural Alternatives: While ensembling with $n$-grams mitigates the issue, the ultimate solution requires designing alternative neural network output layers that completely bypass the structural limitations of the dot-product softmax.
Summary updated