Abstract: Ramón Fernandez Astudillo, Miguel Ballesteros, Tahira Naseem, Austin Blodgett, Radu Florian. Findings of the Association for Computational Linguistics: EMNLP 2020.
2020.
Introduction: The Challenge of State in Transformers
Transition-based parsing is a fundamental technique for converting natural language into structured representations, such as dependency trees or Abstract Meaning Representations (AMR). This process involves a sequence of actions—like shifting a word from a buffer to a stack or creating a directed edge between words—to incrementally build a graph.
The parser's state, defined by the contents of the stack (words currently being processed) and the buffer (words yet to be processed), is vital for determining the next action. While Recurrent Neural Networks (RNNs), such as Stack-LSTMs, are naturally suited to tracking this evolving state, standard Transformers are designed for global attention over the entire input. This global perspective often fails to capture the specific structural context required for transition-based systems. The Stack-Transformer was developed to bridge this gap, introducing state-awareness into the Transformer architecture without sacrificing its parallelization benefits.
The Stack-Transformer Architecture
The authors modify the standard sequence-to-sequence Transformer decoder to explicitly model the parser's state through three key innovations:
- Specialized Cross-Attention: Rather than having all attention heads look at the entire input sentence, specific heads are dedicated to the stack and the buffer.
- Dynamic Masking: As the parser progresses, the model dynamically updates masks. The "stack head" is restricted to words currently on the stack, while the "buffer head" only attends to words remaining in the buffer.
- Labeled SHIFT Multi-task: To encourage the model to represent state content more explicitly, the authors experimented with "decorating" the SHIFT action with the identity of the word being moved, creating a multi-task learning objective.
The model also explored stack- and buffer-specific position embeddings to help the model distinguish relative positions, such as the "top of the stack."
Key Results and Empirical Analysis
The Stack-Transformer was evaluated on Dependency Parsing (Penn Treebank) and Semantic Parsing (AMR 1.0 and 2.0). The results demonstrate that explicit state modeling provides a significant inductive bias, particularly when data is scarce or models are small.
As shown in the ablation study (Figure 3), the Stack-Transformer consistently outperforms vanilla Transformer baselines. Notably:
- Significant Performance Gains: The model achieved a 2-point absolute improvement in LAS for dependency parsing and Smatch for AMR parsing over the baseline.
- Small Data Efficiency: On the smaller AMR 1.0 dataset, the Stack-Transformer outperformed the vanilla model by 5.8 points.
- Architectural Smartness: A "small" 4-layer Stack-Transformer outperformed much larger vanilla Transformers, suggesting that structural awareness can compensate for raw parameter count.
Insights: Buffer vs. Stack
One of the most intriguing findings was that modeling the buffer (upcoming words) appeared more critical than modeling the stack (processed words). The authors hypothesize that the Transformer's action history already implicitly captures much of the information typically held in the stack. Furthermore, despite the lack of recursive composition (building phrase representations) found in Stack-LSTMs, the Stack-Transformer's attention mechanism proved to be a highly effective substitute for explicit structural recursion.
Limitations and Future Directions
While successful, the research highlighted some challenges:
- Position Embeddings: Explicit stack/buffer position embeddings were sometimes detrimental, likely because these positions change at every time step, making them difficult to learn.
- Recursive Composition: The current architecture does not "compress" sub-graphs into single vectors. Future work could explore integrating recursive representations into the Transformer's parallelizable framework.
- Action History Optimization: While the focus was on the stack and buffer, the sequence of previous actions remains a crucial component of the state that warrants further optimization.
Summary updated