Dependency Link Embeddings: Continuous Representations of Syntactic Substructures

Mohit BansalNAACL 2015 · DOI

TL;DR

This paper introduces "dependency link embeddings," dense vector representations for syntactic relationships (like head-argument pairs) in dependency parsing. These embeddings offer a simpler, more efficient feature set for parsers, achieving comparable or better performance than complex, sparse features, and are also transferable to other NLP tasks.

What Problem Does This Paper Address?

Statistical dependency parsers traditionally rely on a vast number of sparse, hand-crafted features that combine words, their clusters, or embeddings. This leads to millions of features, increasing computational cost and memory usage. While recent work has explored denser representations, they often still depend on these complex feature combinations. The authors aim to address this by learning direct, dense representations for the fundamental syntactic substructures (dependency links) themselves, thereby simplifying feature engineering and improving efficiency without sacrificing accuracy.

Methods

The core of this work is learning "dependency link embeddings" using a modified skip-gram model (similar to word2vec). Instead of training on word sequences, they train on "context tuples" representing dependency links. A link's context is defined by its dependency relation label, its grandparent's relation label, and the signed, binned distance between the head and argument.

They explore two main feature types derived from these embeddings:

  • Bucket Features: For each dimension of the link embedding vector, an indicator feature is created based on the binned value. This results in a small set of unary features.
  • Bit-string Features: The link embeddings are hierarchically clustered to generate binary bit-strings. Features are then derived from prefixes of these bit-strings, along with the signed, binned distance.

These link embeddings are then integrated into a standard MSTParser framework as features.

Datasets

  • Training: The BLLIP corpus (excluding the PTB portion) was used for training the dependency link embeddings.
  • Evaluation:
    • WSJ (Wall Street Journal): Used for in-domain dependency parsing experiments.
  • Web treebank: Used for out-of-domain dependency parsing experiments.
  • Constituent parse reranking: The Berkeley parser's 50-best lists were used for evaluating the transferability of link embeddings to constituent parsing.

Key Insights and Ideas

  • Direct Representation of Structure: The paper demonstrates that it's possible and beneficial to learn dense, continuous representations directly for syntactic substructures (dependency links), rather than relying on sparse combinations of word-level features.
  • Feature Simplification: These link embeddings allow for a significantly smaller and simpler set of unary features, drastically reducing the complexity and computational cost associated with traditional dependency parsing feature engineering.
  • Portability: A key advantage is the "off-the-shelf" nature of these link embeddings. They can be easily imported as dense syntactic features into other NLP tasks, such as constituent parsing, without requiring task-specific re-engineering.
  • Complementary to Existing Features: The link embeddings not only match the performance of complex, template-based features but also stack over them, providing further improvements.

Key Results

  • Dependency Parsing:
    • Bucket and Bit-string link embedding features achieved UAS scores on WSJ that were statistically significant improvements over the baseline (92.3/92.6 vs. 91.9).
  • These features matched the performance of complex BROWN features (92.6 vs. 92.7 for Bit-string) and Bansal et al.'s (2014) SKIPDEP result (92.6 vs. 92.7).
  • When combined with BROWN features, they achieved even higher scores (93.0/93.1).
  • Out-of-domain performance on the Web treebank also showed improvements, with link embeddings stacking over BROWN.
  • Constituent Reranking:
    • Importing Bit-string link features into a constituent parse reranker matched and stacked over state-of-the-art, non-local reranking features.
  • Efficiency:
    • The feature generation process for Bucket features was 2-3 orders of magnitude faster than BROWN features.
  • The number of features was drastically reduced (e.g., 15K for Bucket vs. 30M for BROWN).

Limitations and Future Work

  • Out-of-Domain Training: While out-of-domain evaluation was performed using WSJ-trained models on Web treebanks, the authors suggest that training link embeddings directly on Web or Wikipedia data could yield even larger gains.
  • Representation Learning Tools: Future work could explore using newer representation learning tools like GloVe for potentially stronger parsing accuracies.
  • Intrinsic and Extrinsic Evaluation: The authors propose further intrinsic evaluation on syntactic datasets and extrinsic evaluation on a wider range of NLP tasks (e.g., sentence classification).
  • Direct Feature Integration: Investigating parsers or frameworks that can directly employ the embeddings as features, without bucketing or clustering, is another avenue for future research.

Summary updated

BibTeX
@inproceedings{bansal2015dependency,
  author = {Mohit Bansal},
  title = {{Dependency Link Embeddings: Continuous Representations of Syntactic Substructures}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2015},
  doi = {10.3115/v1/w15-1514},
}

Loading related content...

Figure