Introduction
Researchers from Saarland University have developed a language modeling approach that significantly outperforms complex syntactic models by simply looking further back—both within and across sentence boundaries. By combining "skip trigrams" (which look at non-adjacent words) with an "across sentence boundary" model (which uses context from previous sentences), they achieved a perplexity of 118.4 on the Penn Treebank, surpassing the previous state-of-the-art of 137.2.
The Problem: Short-Sighted Language Models
Standard statistical language models (n-grams) are inherently "short-sighted." Due to computational limits and data sparsity, they typically only consider the last two or three words to predict the next one. While this approach is effective for local grammar, it fails to capture long-range dependencies—such as how a word at the beginning of a long sentence might influence one at the end.
Previous attempts to address this involved "structured" language models that perform complex syntactic parsing (building grammar trees) during processing. While effective, these models are computationally expensive and still struggle to bridge the gap between sentences. This research investigates whether these long-range patterns can be captured using pure statistics without the heavy lifting of syntactic analysis.
Methodology
The authors propose a two-pronged strategy to capture broader context:
1. The Skip n-gram Model
Instead of only looking at immediate predecessors (e.g., words $n-1$ and $n-2$), this model uses a wider window of four words. It calculates probabilities based on various combinations of words within that window, effectively "skipping" intermediate words to find dependencies further back. Crucially, it maintains a similar memory footprint to a standard trigram model.
2. The Across Sentence Boundary (ASB) Model
Most models treat sentences as isolated units. The ASB model assumes that words in a previous sentence "trigger" or influence the distribution of words in the current one. It uses the word distribution of the preceding sentence to dynamically adjust the "unigram" probability (the general likelihood of a word appearing) for the current sentence.
These two approaches are combined into a single framework using log-linear interpolation, allowing the model to benefit from both local "skipping" context and broader "across-sentence" context.
Experimental Setup
The models were evaluated on the Penn Treebank (PTB), a gold-standard annotated corpus of American English. The training set consisted of sections 0-20 (~925k tokens), with sections 21-22 used for development and 23-24 for testing. The vocabulary included 10,000 word types clustered into 500 classes.
Key Results
The primary metric used is perplexity, where a lower score indicates a better-performing model. The combined model achieved a nearly 30% improvement over the standard trigram baseline.
| Model | Perplexity |
|---|---|
| Baseline (Standard Trigram) | 167.1 |
| Chelba & Jelinek (Structured LM) | 148.9 |
| Roark (Structured LM - Previous SOTA) | 137.2 |
| Proposed Skip n-gram (Interpolated) | 129.7 |
| Proposed ASB Model (Interpolated) | 126.5 |
| Proposed Combined Model | 118.4 |
Discussion and Insights
- Statistical Simplicity vs. Syntactic Complexity: A well-tuned statistical model can outperform models that attempt to "understand" grammar. By simply widening the context window and looking at the previous sentence, the authors outperformed models using deep syntactic parsing.
- Memory Efficiency: The skip trigram model provides a wider context without requiring significantly more memory than a standard trigram model.
- Contextual Connectivity: The success of the ASB model demonstrates that word probabilities are highly dependent on the immediate topical context provided by preceding sentences.
Limitations and Future Work
To maintain simplicity, the authors only utilized one preceding sentence for the ASB model; incorporating a longer history could yield further improvements. Additionally, while more efficient than syntactic parsers, the log-linear interpolation of multiple skip-gram combinations does introduce some computational overhead compared to a vanilla trigram model. Future work may also involve optimizing word clusters specifically for skip-gram or ASB architectures.
Summary updated