Exploring beam-based shift-reduce dependency parsing with DyALog: Results from the SPMRL 2013 shared task

Éric Villemonte de la Clergerie

Abstract

This paper introduces DyALog-SR, a beam-based shift-reduce dependency parser implemented within a logic programming environment. The system was developed for the SPMRL 2013 shared task to address the unique challenges of Morphologically Rich Languages (MRLs). Our primary contribution is demonstrating that shift-reduce parsing, traditionally applied to linear text, can effectively process ambiguous word lattices with minimal loss in accuracy. DyALog-SR achieves performance on Hebrew lattices that is nearly identical to results on gold-segmented input, proving the viability of transition-based architectures for joint segmentation and parsing.

Introduction

Dependency parsing for Morphologically Rich Languages (MRLs) such as Arabic, Hebrew, and Basque faces a significant hurdle: word segmentation ambiguity. In these languages, a single character string can often be segmented into multiple word sequences, each carrying different grammatical functions.

While traditional dependency parsers assume pre-tokenized input, a more robust approach represents uncertain segmentation as a word lattice—a directed acyclic graph (DAG) where edges represent possible words. While chart-based parsers naturally handle such non-determinism, shift-reduce parsers are typically designed for linear sequences. DyALog-SR explores the adaptation of shift-reduce strategies to navigate these complex search spaces efficiently.

Example of a word lattice representing ambiguous segmentation paths and part-of-speech tags.

Methods

DyALog-SR is built upon DyALog, a tabular logic programming system. This environment is particularly suited for lattice parsing because its native support for tabulation (memoization) allows the parser to share computation across different paths that converge on the same suffix.

Technical Architecture

  • Transition Strategy: The system utilizes an arc-standard strategy for projective dependency parsing.
  • Efficiency Mechanisms: To manage memory and computational load, we implement Tree Structured Stacks (TSS), which allow different parsing hypotheses to share stack tails.
  • Statistical Model: We employ an averaged structured perceptron with "early updates" for training. A hybrid implementation is used, where the core logic resides in DyALog (~1500 lines) while a C module (~850 lines) handles the high-performance requirements of the statistical model.
  • Lattice Adaptation: To handle DAGs, the transition system was modified to include a length feature. This feature compensates for the inherent bias in shift-reduce systems toward shorter paths (fewer transitions) by accounting for the distance between nodes in the lattice.

Results

The system was evaluated across nine languages in the SPMRL 2013 Shared Task. DyALog-SR demonstrated competitive performance, particularly in scenarios with gold-annotated tags and full training sets.

Official results for DyALog-SR across nine languages, comparing gold and predicted tags with full and 5k training sets.

Lattice Parsing Performance

A key finding was the system's success on Hebrew lattices. DyALog-SR achieved a TED accuracy of 86.75 (using a beam size of 16), which is remarkably close to the 87.34 achieved on perfectly disambiguated gold input. This suggests that the search space volatility introduced by lattices can be managed effectively with a sufficiently large beam and appropriate feature engineering.

Discussion and Conclusion

DyALog-SR proves that logic programming and shift-reduce parsing are a potent combination for complex NLP tasks. The expressive power of DyALog allowed for a compact implementation (under 2000 lines) that handles non-determinism transparently.

However, limitations remain. The current arc-standard implementation is restricted to projective trees, requiring external projectivization for languages like German. Future work will focus on implementing a SWAP transition to handle non-projectivity natively and optimizing beam management within the C module to improve speed at high beam widths. Despite these areas for growth, DyALog-SR establishes a strong baseline for joint segmentation and dependency parsing in MRLs.

Summary updated

Abstract

The SPMRL 2013 shared task was the op-portunity to develop and test, with promising results, a simple beam-based shift-reduce de-pendency parser on top of the tabular logic programming system DYALOG. The parser was also extended to handle ambiguous word lattices, with almost no loss w.r.t. disam-biguated input, thanks to specific training, use of oracle segmentation, and large beams. We believe that this result is an interesting new one for shift-reduce parsing. 1
BibTeX
@inproceedings{clergerie2013exploring,
  author = {Éric Villemonte de la Clergerie},
  title = {{Exploring beam-based shift-reduce dependency parsing with DyALog: Results from the SPMRL 2013 shared task}},
  booktitle = {SPMRL @ EMNLP},
  year = {2013},
  doi = {10.18653/v1/w13-4906},
}
Figure