Improved Transition-Based Parsing by Modeling Characters instead of Words with LSTMs

Miguel Ballesteros, Chris Dyer, Noah A. Smith

Abstract

We present extensions to a continuous-state dependency parsing method that makes it applicable to morphologically rich languages. Starting with a high-performance transition-based parser that uses long short-term memory (LSTM) recurrent neural networks to learn representations of the parser state, we replace lookup-based word representations with representations constructed from the orthographic representations of the words, also using LSTMs. This allows statistical sharing across word forms that are similar on the surface. Experiments for morphologically rich languages show that the parsing model benefits from incorporating the character-based encodings of words.

Introduction

In dependency parsing, the objective is to determine the grammatical structure of a sentence by establishing directed links (arcs) between words, such as identifying subjects and objects. Traditional parsers typically treat words as atomic units—discrete identifiers in a large lookup table. While this approach is effective for languages with relatively simple morphology like English, it struggles with Morphologically Rich Languages (MRLs) such as Turkish, Basque, or Hungarian. In these languages, a single root can generate hundreds of distinct word forms through extensive affixation.

Treating every variant (e.g., "walk," "walks," "walking") as an unrelated entity leads to two primary issues: data sparsity, where the model must learn each form independently, and the Out-of-Vocabulary (OOV) problem, where unseen word forms are mapped to a generic UNK token, stripping away vital syntactic information.

Methodology: Character-Based Word Representations

To address these challenges, we extend the Stack LSTM parser architecture. The core innovation is the replacement of traditional word-lookup embeddings with Character-Based Word Embeddings generated via Bidirectional LSTMs.

The architecture of the character-based word representation. A word like "party" is processed character-by-character in both forward and backward directions, with the final hidden states concatenated to form the word vector.

As shown in the architecture above, the model reads a word character-by-character from left-to-right and right-to-left. The final hidden states of these two passes are concatenated to form the word's representation. This allows the model to naturally capture internal word structures (prefixes and suffixes) and share statistical information across morphologically similar words. Additionally, a SWAP operation was added to the transition system to handle non-projective trees, which are common in languages with flexible word orders.

Experimental Results

The model was evaluated across a diverse set of languages, including the SPMRL datasets (Arabic, Basque, French, German, Hebrew, Hungarian, Korean, Polish, and Swedish) and Turkish (CoNLL-X). The results demonstrate that character-level modeling provides significant advantages, particularly as the complexity of the language increases.

Correlation between the Out-of-Vocabulary (OOV) rate and the performance gap (LAS difference) between word-based and character-based models. As OOV rates increase in morphologically rich languages, the character-based model shows increasingly superior performance.

The most dramatic improvements were observed in Basque and Hungarian, where the character-based model improved Unlabeled Attachment Scores (UAS) by approximately 8% over the word-based baseline. As illustrated in the figure above, there is a strong correlation between a language's OOV rate and the benefit derived from character-level modeling. When the model is forced to treat unknown words as a single UNK token, performance drops significantly, confirming that the character-level internal structure is essential for generalization.

Key Insights and Discussion

  • Morphology for Free: The character-level LSTM learns to recognize morphological patterns, such as tense or case endings, without requiring explicit linguistic rules or external morphological analyzers.
  • POS Tag Redundancy: The character-based embeddings are sufficiently rich that they often make explicit Part-of-Speech (POS) tags redundant. In several tests, the character-based model without POS tags outperformed the word-based model that did use POS tags.
  • Robustness to Unknowns: By analyzing characters, the model can infer the likely grammatical role of unseen words (e.g., identifying a word ending in "-ing" as a gerund), allowing for more robust parsing of real-world text.

Conclusion

By shifting from word-level to character-level representations, we significantly improve the performance of transition-based dependency parsers on morphologically rich languages. While this approach introduces a higher computational cost—taking approximately 130ms per sentence compared to 44ms for word-based models—the gains in accuracy and the ability to handle OOV words make it a superior choice for complex linguistic environments.

Summary updated

Abstract

We present extensions to a continuous-state dependency parsing method that makes it applicable to morphologically rich languages. Starting with a high-performance transition-based parser that uses long short-term memory (LSTM) recurrent neural networks to learn representations of the parser state, we replace lookup-based word representations with representations constructed from the orthographic representations of the words, also using LSTMs. This allows statistical sharing across word forms that are similar on the surface. Experiments for morphologically rich languages show that the parsing model benefits from incorporating the character-based encodings of words.
BibTeX
@inproceedings{ballesteros2015improved,
  author = {Miguel Ballesteros and Chris Dyer and Noah A. Smith},
  title = {{Improved Transition-Based Parsing by Modeling Characters instead of Words with LSTMs}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2015},
  url = {https://openreview.net/forum?id=By4MSffOZH},
}
Figure