Efficient Sampling of Dependency Structure

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10442260" target="_blank" >RIV/00216208:11320/21:10442260 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Efficient Sampling of Dependency Structure

Original language description

Probabilistic distributions over spanning trees in directed graphs are a fundamental model of dependency structure in natural language processing, syntactic dependency trees. In NLP, dependency trees often have an additional root constraint: only one edge may emanate from the root. However, no sampling algorithm has been presented in the literature to account for this additional constraint. In this paper, we adapt two spanning tree sampling algorithms to faithfully sample dependency trees from a graph subject to the root constraint. Wilson (1996(&apos;s sampling algorithm has a running time of O(H) where H is the mean hitting time of the graph. Colbourn (1996)&apos;s sampling algorithm has a running time of O(N^3), which is often greater than the mean hitting time of a directed graph. Additionally, we build upon Colbourn&apos;s algorithm and present a novel extension that can sample K trees without replacement in O(K N^3 + K^2 N) time. To the best of our knowledge, no algorithm has been given for sampling spanning trees without replacement from a directed graph.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

—

Publication year

2021

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing

ISBN

978-1-955917-09-4

ISSN

—

e-ISSN

—

Number of pages

12

Pages from-to

10558-10569

Publisher name

Association for Computational Linguistics

Place of publication

Stroudsburg

Event location

Punta Cana

Event date

Nov 7, 2021

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—