Abstract: Hao Peng, Roy Schwartz, Noah A. Smith. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP).
2019.
Introduction
Most modern language models (LMs) treat text as a flat sequence of tokens. However, human language is inherently hierarchical—words group into phrases (constituents), which group into larger phrases, forming a tree structure. While researchers know that incorporating this "syntactic" information helps NLP tasks, doing so is usually computationally expensive. Traditional methods often require complex algorithms like CKY or marginal inference, which do not scale well.
The authors of PaLM (Parser and Language Model) propose a hybrid architecture that adds a "span-based" attention layer to a standard RNN language model. This approach seeks a lightweight way to inject structural inductive bias into an LM without heavy computational overhead, allowing the model to learn which groups of words (spans) are most relevant for predicting what comes next.
The PaLM Architecture
PaLM builds on top of a standard Recurrent Neural Network (RNN) language model, specifically the AWD-LSTM. The core innovation is the Span Attention mechanism:
- Encoding: The model first processes tokens using a left-to-right RNN to obtain hidden states.
- Span Representations: To represent a "span" (a sequence of words like "the red apple"), the authors use Rational RNNs (RRNNs). RRNNs allow the model to compute representations for all possible spans ending at the current time step very efficiently ($O(n)$ function calls) using a mathematical trick involving forget gates and distributivity.
- Attention: Instead of attending to individual previous tokens, the LM attends to preceding spans. For example, when predicting the word after "The 2019 EMNLP conference will be held in...", the model might put high attention weight on the span "[EMNLP IJCNLP 2019]".
- Parsing: Because the model learns which spans are "important" via attention weights, a tree structure can be extracted. By greedily picking the highest-scored spans and recursively splitting the sentence, the model acts as an unsupervised constituency parser.
- Supervision (Optional): If a dataset with gold-standard trees (like the Penn Treebank) is available, the attention layer can be supervised to "look" at the correct syntactic constituents, further boosting performance.
Experimental Setup
The authors evaluated PaLM on two standard language modeling benchmarks:
- Penn Treebank (PTB): A classic dataset for both language modeling and syntactic parsing.
- WikiText-2 (WT2): A larger, more diverse dataset derived from Wikipedia articles.
- WSJ-40: A subset of the Wall Street Journal portion of the PTB (sentences up to 40 tokens) used specifically to evaluate the quality of the extracted parses.
Key Results
Language Modeling Performance
On the Penn Treebank, the baseline AWD-LSTM achieved a perplexity of 57.3. The unsupervised PaLM-U improved this to 56.4, and the supervised PaLM-S reached 55.5. Similar gains were observed on WikiText-2. These results suggest that "thinking in spans" is a naturally better way for models to process language, even without explicit syntactic labels.
Parsing and Branching Bias
In the unsupervised setting, PaLM achieved an $F_1$ score of 42.0 on the WSJ-40 dataset. While this outperformed a "Right Branching" baseline (40.7), it trailed behind specialized unsupervised parsers like DIORA (60.6). After training, the model showed a strong "right-skewness," meaning it preferred to group words into long prefixes. This suggests the model learned that long-range context is more useful for prediction than short-range local structure.
Discussion and Limitations
- Structure Helps Prediction: The unsupervised version of PaLM (PaLM-U) outperformed the baseline AWD-LSTM, indicating that structural bias is beneficial for language modeling.
- Efficiency via Rational RNNs: By using Rational RNNs, the authors made span-based attention nearly as fast as standard token-based attention, overcoming the $O(n^2)$ or $O(n^3)$ complexity typically associated with span representations.
- Parsing Accuracy: While PaLM is a strong language model, it is not a top-tier unsupervised parser. Its parses are heavily biased toward right-branching structures, which might not always reflect true linguistic hierarchy.
- Span Length: To maintain efficiency, the authors capped the maximum span length at 20 tokens, which might limit the model's ability to capture very long-range dependencies in complex sentences.
Summary updated