Efficient Sampling of Dependency Structure

Efficient Sampling of Dependency Structures Ran Zmigrod Tim Vieira Ryan Cotterell , University of Cambridge Johns Hopkins University ETH Zürich rz279@cam.ac.uk tim.f.vieira@gmail.com ryan.cotterell@inf.ethz.ch Abstract Probabilistic distributions over spanning trees in directed graphs are a fundamental model of dependency structure in natural language pro- cessing, 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 sample dependency trees from a graph sub- ject to the root constraint. Wilson (1996)’s sampling algorithm has a running time of O(H) where H is the mean hitting time of the graph. Colbourn et al. (1996)’s sampling al- gorithm 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’s algorithm and present a novel ex- tension that can sample K trees without re- placement in O(KN 3 + K2N) time. To the best of our knowledge, no algorithm has been given for sampling spanning trees without re- placement from a directed graph.1 1 Introduction Spanning trees in directed graphs2 are fundamental combinatorial structures in natural language pro- cessing where they are used to represent depen- dency structures—especially syntactic dependency structure (Kübler et al., 2009). Additionally, prob- abilistic models over spanning trees are common in the NLP literature with applications primarily in non-projective dependency parsing (Pei et al., 2015; Wang and Chang, 2016; Dozat and Manning, 2017; Ma and Hovy, 2017), but also in recovering phylogenic structures (Andrews et al., 2012), and event extraction (McClosky et al., 2011). 1Our implementation of these algorithms is publicly avail- able at https://github.com/rycolab/treesample. 2Directed spanning trees are known as arborescences in the graph theory literature (Williamson, 1985). However, we will simply refer to them as spanning trees. Given the prevalence of such probabilistic mod- els, efficient dependency tree sampling algorithms deserve study. Indeed, some work has been done in transition-based dependency parsing (Keith et al., 2018) as well as graph-based dependency parsing (Nakagawa, 2007; Mareˇcek and Žabokrtský, 2011). Sampling has also been utilized in an abundance of NLP tasks, such as text generation (Clark et al., 2018; Fedus et al., 2018), co-reference resolution (Singh et al., 2012), and language modeling (Mnih and Hinton, 2007; Logan IV et al., 2020). The theoretical computer science literature has several efficient algorithms for sampling directed spanning trees. These algorithms come in two fla- vors. First, random walks through Markov chains have been used to sample spanning trees from both undirected (Broder, 1989; Aldous, 1990) and di- rected graphs (Wilson, 1996). The algorithm of Wilson (1996) is linear in the mean hitting time of the graph and is currently the fastest sampling algo- rithm for directed spanning trees. It has been used in dependency parsing inference by Zhang et al. (2014a,b). Second, several algorithms have lever- aged the matrix–tree theorem (MTT; Kirchhoff, 1847; …

Content truncated to 500 words