Reproduce “Unbiased and Efficient Sampling of Dependency Trees” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Miloš Stanojević
The authors introduce unbiased samplers for dependency trees that enforce the Universal Dependencies requirement of exactly one edge from ROOT. They correct Wilson-RC’s root-edge choice using marginal probabilities and propose rejection sampling. For sampling k trees without replacement, trie-based sampling and stochastic beam search achieve worst-case O(kn³), versus O(kn³ + k²n). A JAX implementation reports up to 5× GPU speedup over CPU on 100-word sentences; performance varies by method.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.