Unbiased and Efficient Sampling of Dependency Trees

Milos StanojevicEMNLP 2022 · DOI

Introduction

Dependency trees are fundamental to representing syntactic structure in natural language processing. In frameworks like Universal Dependencies, a valid dependency tree must satisfy a "single-root" constraint: exactly one edge must originate from an artificial ROOT node.

Example of dependency trees and the single-root constraint.

While Wilson’s algorithm is a standard for sampling spanning trees, adapting it to this constraint is non-trivial. Previous attempts, such as the Wilson-RC algorithm (Zmigrod et al., 2021b), introduced mathematical bias by failing to sample trees in true proportion to their weights. This paper identifies this bias and proposes two unbiased alternatives: WilsonMarginal and WilsonReject.

Unbiased Sampling Methods

The authors introduce two primary algorithms to ensure unbiased sampling:

  1. WilsonMarginal: This method uses the Matrix-Tree Theorem to compute the marginal probability of each root edge—the sum of weights of all trees containing that edge. By sampling the root edge from this distribution first, the algorithm ensures the resulting tree is drawn correctly.
  2. WilsonReject: A simpler rejection sampling approach. It uses the standard Wilson’s algorithm to sample spanning trees and rejects those that violate the single-root constraint.

Efficient Sampling Without Replacement (SWOR)

Beyond sampling with replacement, the paper addresses the computational bottleneck of sampling $k$ unique trees (SWOR). Existing methods scaled poorly, often $O(k^2)$. The authors reformulate tree generation as an auto-regressive sequence and introduce:

  • Trie-SWOR: Utilizes a trie data structure to track previously sampled trees, improving complexity to $O(kn^3)$.
  • SBS-SWOR (Stochastic Beam Search): A parallelizable variant using the Gumbel-top-k trick, designed for modern hardware like GPUs.

Experimental Results

The algorithms were evaluated on synthetic data and real-world corpora (News Commentary v16) using weights from a Stanza parser.

Runtime comparison of unbiased samplers on random vs. trained weights.

A key finding is the surprising efficiency of WilsonReject. In random graphs, it requires only ~2.7 attempts on average. In trained models, where the distribution naturally favors single-root structures, the success rate is ~95%, making it highly competitive with more complex methods. Furthermore, the JAX implementation of SBS-SWOR achieved a 5x speedup on GPUs for 100-word sentences, demonstrating the benefits of parallelization.

Conclusion

By providing unbiased and efficient sampling algorithms, this work enables more accurate unsupervised grammar induction and faster training for neural dependency parsers. The shift from $O(k^2)$ to $O(k)$ scaling for SWOR and the exploitation of GPU parallelism represent significant practical advancements for the field.

Summary updated

BibTeX
@inproceedings{stanojevic2022unbiased,
  author = {Milos Stanojevic},
  title = {{Unbiased and Efficient Sampling of Dependency Trees}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2022},
  doi = {10.18653/v1/2022.emnlp-main.110},
}
Figure