Dependency Parsing by Belief Propagation

David A. Smith, Jason EisnerEMNLP 2008 · OpenReview

Abstract: We formulate dependency parsing as a graphical model with the novel ingredient of global constraints. We show how to apply loopy belief propagation (BP), a simple and effective tool for approximate learning and inference. As a parsing algorithm, BP is both asymptotically and empirically efficient. Even with second-order features or latent variables, which would make exact parsing considerably slower or NP-hard, BP needs only $O(n^3)$ time with a small constant factor. Furthermore, such features significantly improve parse accuracy over exact first-order methods. Incorporating additional features would increase the runtime additively rather than multiplicatively.

Breaking the Complexity Wall

In dependency parsing, the goal is to determine the grammatical structure of a sentence by linking words—for instance, identifying a verb as the "parent" of a specific noun. Historically, researchers faced a fundamental trade-off. First-order models, which look at single edges in isolation, are computationally efficient ($O(n^3)$) but lack linguistic nuance. Higher-order models, which consider grandparent-child or sibling relations, offer greater accuracy but at a steep cost: for projective parsing, complexity jumps to $O(n^4)$ or $O(n^5)$, and for non-projective parsing, the problem becomes NP-hard.

This paper presents a framework to achieve the accuracy of higher-order features without the prohibitive computational overhead of exact search.

Parsing as a Graphical Model

The authors reformulate parsing as a Markov Random Field (MRF) where each potential link between words is a boolean variable. To navigate this complex space, they employ two key innovations:

  1. Loopy Belief Propagation (BP): Instead of exact dynamic programming, the system uses BP, an iterative message-passing algorithm. Variables and "factors" (representing features) pass messages to negotiate the most likely edges.
  2. Global Constraints as Propagators: A valid parse must be a tree, which is a global property. The authors introduced a global TREE factor that connects to every edge variable. They demonstrated that messages for this global factor can be calculated efficiently by using a standard first-order parser as a subroutine.
Factor graph representation of dependency parsing with a global TREE constraint and higher-order factors like GRAND.

In this setup, higher-order features suggest adjustments to edge weights, and the first-order parser "cleans up" these suggestions to ensure the result remains a coherent tree.

Additive vs. Multiplicative Cost

A major insight of this work is the shift from multiplicative to additive complexity. In traditional dynamic programming, adding a new feature type typically multiplies the state space. In the BP framework, adding a new feature is additive to the runtime per iteration.

Complexity analysis of various factor families, demonstrating the additive nature of runtime in the BP framework.

As shown in the complexity analysis, even complex factors like CHILDSEQ or GRAND maintain manageable runtimes. By treating the "tree-ness" requirement as a hard global constraint, the authors leverage existing $O(n^3)$ algorithms (like the Matrix-Tree Theorem) to perform the heavy lifting within the BP loop.

Empirical Results

The model was evaluated on English (mostly projective), Danish (slightly non-projective), and Dutch (highly non-projective) datasets from the CoNLL 2007 Shared Task.

  • Accuracy: On non-projective languages, adding higher-order features via BP significantly outperformed first-order baselines.
  • Efficiency: Models that would normally require $O(n^5)$ for exact inference stayed at $O(n^3)$ per iteration. In practice, the parser averaged 1.5 to 1.8 seconds per sentence.
  • Low Search Error: Despite being an approximation, the search error was remarkably low—only about 0.4% after 10 iterations.

Conclusion

By reframing dependency parsing through the lens of graphical models and global constraints, this work provides a scalable path for incorporating complex linguistic features. While BP does not guarantee convergence on graphs with loops, it proved highly stable in practice. This framework opens the door for joint tasks, such as simultaneous parsing and Part-of-Speech tagging, where the additive nature of BP complexity is particularly advantageous.

Summary updated

Abstract

We formulate dependency parsing as a graphical model with the novel ingredient of global constraints. We show how to apply loopy belief propagation (BP), a simple and effective tool for approximate learning and inference. As a parsing algorithm, BP is both asymptotically and empirically efficient. Even with second-order features or latent variables, which would make exact parsing considerably slower or NP-hard, BP needs only O(n3) time with a small constant factor. Furthermore, such features significantly improve parse accuracy over exact first-order methods. Incorporating additional features would increase the runtime additively rather than multiplicatively.
BibTeX
@inproceedings{smith2008dependency,
  author = {David A. Smith and Jason Eisner},
  title = {{Dependency Parsing by Belief Propagation}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2008},
  url = {https://openreview.net/forum?id=HyVEqMMObr},
}
Figure