Arc-Standard Spinal Parsing with Stack-LSTMs

Miguel Ballesteros, Xavier Carreras

Introduction: Bridging Dependency and Constituency

Natural language processing traditionally relies on two distinct structural representations: dependency parsing and constituency parsing. Dependency parsing focuses on word-to-word relationships, offering computational efficiency but lacking hierarchical phrase structure. Conversely, constituency parsing captures nested groupings (e.g., Noun Phrases, Verb Phrases) but is often more complex to compute. This paper introduces a neural transition-based parser that utilizes spinal trees—a hybrid representation designed to provide the hierarchical richness of constituency parsing with the efficiency of dependency-based methods.

The Spinal Tree Representation

In a spinal tree, every word is associated with a "spine"—a vertical sequence of non-terminal labels representing the phrases to which the word belongs. This allows the parser to represent both the functional relationships between words and the phrase-level structure of the sentence.

A spinal tree representation combining word-to-word dependencies with hierarchical phrase labels.

Methodology: Arc-Standard Spinal Parsing

The authors extend the Arc-Standard transition system, commonly used for dependency parsing, to accommodate spinal structures. The system employs a Stack-LSTM to maintain a continuous vector representation of the parsing state, including the buffer of incoming words and the stack of partially constructed trees.

A key innovation is the introduction of the node(n) operation, which adds a non-terminal node (such as "NP" or "VP") to the top of a word's current spine. Furthermore, the model uses a recursive composition function. When a new branch is created or a node is added, the neural network combines the vector of the head word with the vector of the dependent or the new phrase label. This mechanism ensures that the model "remembers" the context of entire phrases as it processes the sentence.

Empirical Evaluation and the Impact of Head Rules

The model was evaluated on the Penn Treebank (PTB). To convert standard constituent trees into spinal trees, the authors tested various "head-finding" rules, ranging from simple structural heuristics (Leftmost/Rightmost) to linguistically-informed rules (Stanford Dependencies, Yamada and Matsumoto).

Performance metrics across different head-finding rules, demonstrating the robustness of the Stack-LSTM approach.

As shown in the results table, the parser's performance remained remarkably consistent regardless of the head-finding rule used. This suggests that Stack-LSTMs are sufficiently powerful to induce effective internal syntactic states without requiring precise linguistic definitions of "heads." The model achieved a competitive F1 score of 91.11 (using rightmost heads) and an Unlabeled Attachment Score (UAS) of 93.49, demonstrating its robustness in both constituency and dependency evaluation frameworks.

Conclusion and Future Directions

The transition-based spinal parser successfully bridges the gap between two major parsing paradigms. While highly effective for projective languages like English, future work is needed to adapt the system for non-projective structures found in languages with more flexible word orders. Additionally, while this study focused on structural accuracy, extending the model to include functional dependency labels (e.g., subject, object) remains a promising avenue for further research.

Summary updated

BibTeX
@inproceedings{ballesteros2017arc,
  author = {Miguel Ballesteros and Xavier Carreras},
  title = {{Arc-Standard Spinal Parsing with Stack-LSTMs}},
  booktitle = {IWPT},
  year = {2017},
}
Figure