Efficient Dependency Tree Sampling Without Replacement

Bogdan Dobre


Abstract
In the context of computational models of dependency syntax, most dependency treebanks have the restriction that any valid dependency tree must have exactly one edge coming out of the root node in addition to respecting the spanning tree constraints. Many algorithms for dependency tree sampling were recently proposed, both for sampling with and without replacement.In this paper we propose a new algorithm called Wilson Reject SWOR for the case of sampling without replacement by adapting the Wilson Reject algorithm originally created for sampling with replacement and combining it with a Trie data structure. Experimental results indicate the efficiency of our approach in the scenario of sampling without replacement from dependency graphs with random weights.
Anthology ID:
2024.findings-naacl.47
Volume:
Findings of the Association for Computational Linguistics: NAACL 2024
Month:
June
Year:
2024
Address:
Mexico City, Mexico
Editors:
Kevin Duh, Helena Gomez, Steven Bethard
Venue:
Findings
SIG:
Publisher:
Association for Computational Linguistics
Note:
Pages:
736–741
Language:
URL:
https://aclanthology.org/2024.findings-naacl.47
DOI:
Bibkey:
Cite (ACL):
Bogdan Dobre. 2024. Efficient Dependency Tree Sampling Without Replacement. In Findings of the Association for Computational Linguistics: NAACL 2024, pages 736–741, Mexico City, Mexico. Association for Computational Linguistics.
Cite (Informal):
Efficient Dependency Tree Sampling Without Replacement (Dobre, Findings 2024)
Copy Citation:
PDF:
https://aclanthology.org/2024.findings-naacl.47.pdf
Copyright:
 2024.findings-naacl.47.copyright.pdf