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:
- 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)
- PDF:
- https://preview.aclanthology.org/fix-volume-bibkeys/2024.findings-naacl.47.pdf