PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Miguel Ballesteros, Chris Dyer, Noah A. Smith

arXiv:1508.00657v2cs.CL

TL;DR

Dependency parsers need representations that handle morphology, especially where word forms encode grammatical information. This paper replaces lookup-based word vectors with LSTM character encodings within a continuous-state parser, and adds SWAP for nonprojective trees. Character-based representations improve results across languages, particularly morphologically rich ones, and can sometimes substitute for explicit POS features.

  • Problem

    Continuous-state dependency parsing needs word representations that capture morphology rather than treating each word type as opaque and independently modeled.

  • Method

    The parser constructs word embeddings from character sequences with LSTMs and augments its transition system with SWAP for nonprojective trees.

  • Results

    Character-based representations outperform Words across languages, are on par with Words + POS on average, and achieve their best average labeled attachment scores with Chars + POS.

  • Takeaways & Limitations

    Character encodings capture morphology useful for dependency parsing and can sometimes obviate explicit POS information, including in morphologically rich languages.

  • Takeaways & Limitations

    Chars requires more memory than Words, averaging 450 MB versus 300 MB for training and parsing.

Abstract

from arXiv · show

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.

1 Introduction

The paper extends continuous-state transition-based parsing by constructing morphology-sensitive word embeddings from character sequences. This improves parsing for morphologically rich languages, while adding SWAP enables nonprojective trees.

  • 1 Introduction: The parser represents words using orthographic character sequences, allowing its embeddings to capture morphological information without explicit morphological supervision.Character-based representations replace opaque, lookup-based word embeddings and use LSTMs to compose word vectors.
  • 1 Introduction: Character-based embeddings produce large gains on morphologically rich SPMRL languages, especially agglutinative languages and those with extensive case systems.The improvement occurs despite the model receiving no explicit morphological annotation.
  • 1 Introduction: Character-based word embeddings can sometimes replace explicit POS information, while retaining good performance in languages with little morphology.The results suggest the RNN composition strategy captures both morphological regularities and lexical arbitrariness.
  • 1 Introduction: The parser is extended with SWAP, allowing it to generate nonprojective dependency trees often found in morphologically rich languages.The base continuous-state parser used SHIFT and REDUCE; this work adds SWAP.

2 An LSTM Dependency Parser

The parser incrementally manipulates stack, buffer, and action structures while encoding their states with LSTMs. It composes partial parses recursively, predicts permitted transitions probabilistically, and adds SWAP for nonprojective trees.

  • 2 An LSTM Dependency Parser: The transition-based parser maintains a buffer, a stack of partial parses, and a list of previous actions, updating them one transition at a time.Its underlying algorithm is arc-standard parsing.
  • 2 An LSTM Dependency Parser: Each parser data structure receives a continuous vector representation, and the combined state determines the next transition.The state vectors for buffer, stack, and action history are combined with learned parameters.
  • 2.1 Stack LSTMs: LSTMs model sequential parser states, with stack LSTMs using pointers and pop operations to represent non-monotonic stack access.Stack LSTMs implement the buffer, stack, and action history separately.
  • 2.2 Composition Functions: REDUCE pops two tree fragments, composes them with a relation-specific recursive network, and pushes the resulting fragment back onto the stack.The composed vector occupies the same representation space as words and other tree fragments.
  • 2.3 Predicting Parser Decisions: At each step, the parser selects the most probable permitted action under a log-linear distribution and trains parameters by maximizing correct-decision likelihood.Allowed transitions are restricted by stack and buffer preconditions.
  • 2.4 Nonprojective Parsing: Adding SWAP breaks the stack’s linear order by moving non-top tokens back to the buffer, enabling nonprojective dependency trees.After swapping, the buffer may contain tree fragments as well as words.

3 Word Representations

The paper replaces opaque lookup-based word representations with character-based encodings designed to capture morphology. Bidirectional LSTMs process orthographic strings, including out-of-vocabulary words, before the resulting representation is used by the parser.

  • The main contribution is changing the word representations used by the continuous-state parser.
  • 3.1 Baseline: Standard Word Embeddings: The baseline concatenates a word-type vector with an optional POS-tag vector, then applies a linear map and component-wise ReLU.
  • 3.1 Baseline: Standard Word Embeddings: Out-of-vocabulary words receive a separate UNK representation in the baseline model.
  • 3.2 Character-Based Embeddings of Words: Character-based embeddings read each word from both directions with bidirectional LSTMs and concatenate the resulting vectors with a learned tag representation.
  • 3.2 Character-Based Embeddings of Words: The character-based representation treats out-of-vocabulary words as LSTM encodings that can be close to syntactically similar morphological relatives seen during training.

4 Experiments

The experiments apply the parsing model and several variations to parsing tasks, while Figure 3 illustrates a character-based embedding for the word party.

  • The authors applied the parsing model and several variations to several parsing tasks.
  • Figure 3 depicts the character-based word embedding of the word party.
  • The illustrated character-based representation is used for both in-vocabulary and out-of-vocabulary words.

4.1 Data

The evaluation covers morphologically rich-language treebanks from the SPMRL shared task, plus Turkish, Chinese, and English comparison setups.

  • The SPMRL evaluation includes Arabic, Basque, French, German, Hebrew, Hungarian, Korean, Polish, and Swedish treebanks.
  • The experiments also use the Turkish dependency treebank with gold POS tags.
  • Chinese experiments use the Penn Chinese Treebank 5.1 with gold POS tags.
  • English experiments use the Stanford Dependency representation of the Penn Treebank.
  • Results for Turkish, Chinese, and English use the CoNLL-X eval.pl script, which ignores punctuation symbols.

4.2 Experimental Configurations

The experiments isolate word, character, and POS-tag representations without pretrained embeddings or additional data, while allowing nonprojective trees through SWAP.

  • The ablation compares Words, Chars, Words + POS, and Chars + POS configurations.
  • Words uses word inputs without POS tags, whereas Chars uses bidirectional-LSTM character representations without POS tags.
  • Words + POS and Chars + POS add POS tags to the corresponding word-based and character-based configurations.
  • None of the configurations uses pretrained word embeddings or additional data resources.
  • All experiments include the SWAP transition, allowing nonprojective trees to be produced in any language.
  • The full model uses 100-dimensional LSTM hidden states, 32-dimensional learned word representations, 100-dimensional character representations, and 12-dimensional POS embeddings.

4.3 Training Procedure

The model is trained from random initialization with stochastic gradient descent, using backpropagation through the sequence of parsing actions and development-set UAS for stopping.

  • Parameters are initialized randomly, with no parameter pretraining.
  • Stochastic gradient descent without minibatches optimizes derivatives of the negative log likelihood for parsing-action sequences.
  • Training stops when the learned model’s UAS stops improving on the development set, after which the model parses the test set.

4.4 Results and Discussion

Character-based representations improve parsing across morphologically rich languages, especially agglutinative and case-marking languages, while also helping with out-of-vocabulary words. The approach captures syntactic and morphological regularities without explicit morphological features, but increases computational requirements.

  • Overall results: Chars consistently outperform Words across languages, while Chars + POS achieves the best average labeled attachment score.Chars is on par with Words + POS on average; improvements are especially notable for Basque, Hungarian, Korean, and Turkish.
  • Morphology and POS tags: Morphological information encoded in treebank POS tags appears insufficient for morphologically rich languages, unlike the high-accuracy setting for English.The paper contrasts English tags encoding number and tense with the apparent insufficiency of POS tags in morphologically rich languages.
  • Learned representations: Character-based representations form visible clusters of past-tense verbs, gerunds, and other syntactic classes in a t-SNE visualization.The visualization uses representations learned by character-based bidirectional LSTMs, with colors indicating the most common POS tag.
  • Out-of-vocabulary words: Replacing every OOV word with UNK lowers performance by an average of −4.5 LAS and −2.8 UAS, with Korean dropping 15.5 LAS.The drop varies with development-set OOV rate across treebanks, and a similar but smaller pattern occurs when POS tags are included.
  • Out-of-vocabulary words: Even the UNK-based model remains better than Words for every language, including a 4 LAS advantage for Korean, indicating benefits beyond OOV handling.The paper attributes this pattern to statistical sharing across orthographically close words.
  • Computational requirements: Chars parses sentences in 130 ms versus 44 ms for Words and requires 450 MB of memory versus 300 MB.Character composition also affects training time, although test-time representations could be cached.

5 Related Work

The paper builds on character-based neural representations and morphological approaches in NLP, applying character-based embeddings to dependency parsing without an external morphological analyzer. It positions this as a novel use of character-based embeddings for improving dependency parsers.

  • Character-based representations: Character-level neural representations had already improved POS tagging and named entity recognition, motivating their use in parsing.Prior work learned character-level representations directly for these tasks and reported large error reductions.
  • Morphology-aware modeling: Morphological analyzers can provide stems, prefixes, and suffixes, whereas this paper learns word representations without requiring an external analyzer.The contrast is between additive morpheme-meaning modeling and learning directly from orthographic strings.
  • Morphology-aware modeling: Prior work jointly modeled morphological disambiguation and dependency parsing for richly inflected languages.Examples include transition-based parsing with joint morphological tagging for Czech, Finnish, German, Hungarian, and Russian.
  • Character-based representations: Character-level processing has also been explored for Chinese parsing, where word segmentation helps predict correct POS tags.These studies show that character information can contribute directly to parsing and tagging decisions.
  • Contribution: The authors state that previous work had not used character-based embeddings to improve dependency parsers in this way.This identifies the paper’s claimed novelty within the cited dependency-parsing literature.

6 Conclusion

The paper finds that character-based representations improve transition-based dependency parsing, especially for agglutinative and morphologically rich languages. They also help with out-of-vocabulary words without additional resources, while morphological information can be learned implicitly from strings.

  • Conclusion: Character-based representations improve transition-based dependency parsing by capturing morphological information relevant to syntax.The conclusion presents this as evidence that character-based representations are useful beyond tagging and recognition tasks.
  • Conclusion: Strong improvements occur for agglutinative languages, including Basque, Hungarian, Korean, and Turkish, comparing favorably with POS tags.The comparison uses POS tags encoded in the languages’ available treebanks.
  • Conclusion: The authors suggest prioritizing dependency annotation while allowing morphological features to be learned implicitly from strings.They motivate this suggestion by noting that annotating morphological information for a treebank is expensive.
  • Conclusion: Character-based representations can overcome the out-of-vocabulary problem and substantially improve performance when OOV rates are high.The paper states this benefit occurs without additional resources.
Loading 1508.00657v2…