RNN-Based Sequence-Preserved Attention for Dependency Parsing

Yi Zhou, Junying Zhou, Lu Liu, Jiangtao Feng, Haoyuan Peng, Xiaoqing Zheng

Abstract

Dependency parsing is a fundamental task in natural language processing that identifies grammatical structures by linking head words to their modifiers. While attention mechanisms have significantly enhanced parsing performance, standard "vanilla" attention often fails to capture the essential sequential context between words, treating them as an unordered set. This paper introduces Sequence-Preserved Attention (SPA), an RNN-based mechanism that maintains word order during context processing. By employing a two-step SCAN and RESCAN approach, SPA enables models to "remember" the path between heads and modifiers. Experimental results on the English Penn Treebank and Chinese Treebank demonstrate that the Boundary-to-Target (BoT-SPA) variant consistently outperforms vanilla attention and achieves state-of-the-art performance, particularly in handling long-distance dependencies.

Introduction

In dependency parsing, the goal is to map out the grammatical relationships in a sentence, such as identifying that a verb is the "head" of its object. While Recurrent Neural Networks (RNNs) and standard attention mechanisms have pushed the boundaries of this field, they suffer from a significant limitation: vanilla attention mechanisms lose sequence information. By calculating a simple weighted sum of word representations, standard attention ignores the relative order of words between a potential head and its modifier—information that is often critical for determining correct syntactic links.

Methodology: SCAN and RESCAN

To address the loss of sequence information, the researchers proposed a two-stage process inspired by the human reading process: SCAN and RESCAN.

  1. The SCAN Step: A standard Bidirectional RNN (Bi-RNN) processes the sentence to generate initial word representations.
  2. The RESCAN Step (SPA): Instead of a parallel weighted sum, the model uses Sequence-Preserved Attention (SPA). This is implemented using a Gated Recurrent Unit (GRU) that "scans" the context. The attention score at each step is dependent on the previous step, ensuring the model maintains a sense of the path it has traversed through the sentence.
Comparison of Vanilla Attention (vanAtt), Target-to-Boundary SPA (ToB-SPA), and Boundary-to-Target SPA (BoT-SPA).

The authors explored two primary variants of this scanning behavior:

  • Target-to-Boundary (ToB-SPA): The model starts at the word of interest and scans outward toward the sentence boundaries.
  • Boundary-to-Target (BoT-SPA): The model starts at the sentence boundaries and scans inward toward the target word.

The Sequence-Preserved Mechanism

The core innovation of SPA is its ability to generate an attentional representation that is inherently sequence-aware. Unlike standard attention, which calculates weights independently for each word, SPA processes the input sequence to produce a hidden state that incorporates information from the preceding context. This recurrence allows the model to capture the structural "path" between words, which is critical for identifying complex syntactic relationships.

Detailed view of the sequence-preserved attention mechanism showing the flow from input sequence to attentional representation.

Key Results and Insights

The models were evaluated on the English Penn Treebank (PTB) and the Chinese Treebank (CTB) using Unlabeled Attachment Score (UAS) and Labeled Attachment Score (LAS).

  • Superiority of BoT-SPA: The BoT-SPA variant consistently outperformed ToB-SPA and vanilla attention. On the English PTB, BoT-SPA achieved a UAS of 94.72% in a transition-based parser, compared to 94.33% for vanilla attention. This success is attributed to the "recency bias" of RNNs; in BoT-SPA, the words closest to the target are processed last, ensuring the model has the clearest memory of the most relevant local context.
  • Handling Long-Distance Dependencies: Error analysis revealed that BoT-SPA is particularly effective at maintaining accuracy as sentence length increases. While other models' performance typically drops sharply when dealing with long-distance relationships, SPA's sequential memory mitigates this decay.
  • Versatility: The SPA mechanism proved effective across different parsing philosophies, providing significant accuracy boosts for both graph-based and transition-based systems.

Conclusion

Sequence-Preserved Attention represents a significant step forward in making attention mechanisms more suitable for syntax-heavy tasks like dependency parsing. By replacing the "bag of words" approach of vanilla attention with a sequential RNN-based scan, the researchers successfully integrated word-order information into the attentional representation. Future work may involve exploring the integration of SPA with more complex search strategies like beam search or comparing its performance against the parallel multi-head attention found in Transformer architectures.

Summary updated

Abstract

Recurrent neural networks (RNN) combined with attention mechanism has proved to be useful for various NLP tasks including machine translation, sequence labeling and syntactic parsing. The attention mechanism is usually applied by estimating the weights (or importance) of inputs and taking the weighted sum of inputs as derived features. Although such features have demonstrated their effectiveness, they may fail to capture the sequence information due to the simple weighted sum being used to produce them. The order of the words does matter to the meaning or the structure of the sentences, especially for syntactic parsing, which aims to recover the structure from a sequence of words. In this study, we propose an RNN-based attention to capture the relevant and sequence-preserved features from a sentence, and use the derived features to perform the dependency parsing. We evaluated the graph-based and transition-based parsing models enhanced with the RNN-based sequence-preserved attention on the both English PTB and Chinese CTB datasets. The experimental results show that the enhanced systems were improved with significant increase in parsing accuracy.
BibTeX
@inproceedings{zhou2018rnn,
  author = {Yi Zhou and Junying Zhou and Lu Liu and Jiangtao Feng and Haoyuan Peng and Xiaoqing Zheng},
  title = {{RNN-Based Sequence-Preserved Attention for Dependency Parsing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.12011},
}
Figure