On Finding the K-best Non-projective Dependency Trees

Ran Zmigrod, Tim Vieira, Ryan Cotterell

TL;DR

This paper tackles the challenge of finding the top-K most likely dependency parse trees for sentences, a crucial task for robust natural language processing. The authors introduce a more efficient algorithm for finding K-best non-projective dependency trees, which are more common in real-world NLP tasks, and demonstrate a significant speedup over existing methods.

What Problem Does This Paper Address?

Dependency parsing aims to represent the grammatical structure of a sentence by identifying relationships between words. "Non-projective" dependency trees allow for more complex grammatical structures than "projective" ones, making them more suitable for many real-world languages and parsing scenarios. While finding the single "best" dependency tree is a well-studied problem, NLP systems often benefit from considering a set of the top-K most likely trees (K-best parsing). This is because the single best parse might not always be correct, and having a ranked list allows for better re-ranking or more robust downstream processing.

The core problem this paper addresses is the lack of efficient algorithms for finding the K-best non-projective dependency trees, especially when these trees must adhere to a "root constraint" (only one edge emanating from the sentence's root word). Existing methods for K-best spanning trees (a related but less constrained problem) are complex and have not been effectively adapted for the specific requirements of dependency parsing. The authors highlight that simply using K-best spanning tree algorithms can lead to a substantial increase in trees violating the root constraint, making them unsuitable for dependency parsing.

Methods

The paper builds upon the work of Camerini et al. (1980) for finding K-best spanning trees. Their key contributions are:

  • Simplified K-best Spanning Tree Algorithm: They present a reformulation of Camerini et al.'s algorithm that is simpler to understand and prove correct. This simplification leads to a constant-time speedup over the original algorithm. The core idea involves iteratively finding the second-best tree by considering edge exclusions and inclusions within subgraphs.
  • Novel Extension for Root-Constrained Dependency Trees: The main innovation is an extension of the K-best spanning tree algorithm to specifically handle the root constraint required for dependency trees. This new algorithm efficiently enumerates K-best dependency trees while ensuring the root constraint is met.

The algorithms rely on concepts like:

  • Graph Contraction: Collapsing cycles in a graph to simplify it.
  • Edge Inclusion/Exclusion Graphs: Creating subgraphs where specific edges are either forced to be included or excluded.
  • Greedy Graph: A graph formed by taking the highest-weighted incoming edge for each node.

Datasets

The authors use the Universal Dependency (UD) treebank for their experiments. They specifically mention using data from Qi et al. (2020) for evaluating the root constraint violation rates across 63 languages.

Key Insights and Ideas

  • Root Constraint Violation is a Major Issue: Simply decoding K-best spanning trees without considering the root constraint leads to a dramatic increase in invalid dependency trees, especially for larger values of K. This empirically justifies the need for a specialized algorithm.
  • K-best Spanning Trees as Building Blocks: The core insight is that finding the K-best dependency trees can be framed as finding the second-best trees of carefully constructed subgraphs. This recursive approach allows for efficient enumeration.
  • Algorithmic Simplification Matters: By simplifying the underlying K-best spanning tree algorithm, the authors not only achieve a speedup but also make the approach more accessible and easier to verify.

Key Results

  • Significant Speedup: The proposed K-best spanning tree algorithm achieves a constant-time speedup over the original Camerini et al. (1980) algorithm. Empirical results show an average speedup of 1.39x for parsing K-best spanning trees.
  • Reduced Root Constraint Violations: The new K-best dependency tree algorithm directly addresses the root constraint, preventing the high violation rates observed when using generic K-best spanning tree methods. For K=50, the violation rate can increase by an average of 13 times compared to K=1 when not using the specialized algorithm.
  • Practical Efficiency: The algorithm maintains an O(KN²) runtime complexity, which is efficient for practical K-best parsing scenarios.

Limitations and Future Work

  • Complexity of K-best Algorithms: While the paper simplifies the algorithm, K-best parsing algorithms are inherently more complex than finding the single best parse.
  • Potential for Multi-graphs: The authors note that their algorithms could be extended to handle multi-graphs, which might be beneficial for parsing with labeled dependency edges.
  • Broader Applications: The paper suggests that K-best algorithms can be useful for other NLP tasks like marginalization of latent variables and constructing parsers with global scoring functions.

The paper encourages further research into K-best non-projective dependency parsing, highlighting its importance for robust NLP systems.

Summary updated

BibTeX
@inproceedings{zmigrod2021finding,
  author = {Ran Zmigrod and Tim Vieira and Ryan Cotterell},
  title = {{On Finding the K-best Non-projective Dependency Trees}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
  url = {https://openreview.net/forum?id=HiVaoNaEOK4},
}
Figure