Efficient Sampling of Dependency Structure (2021)

Abstract: 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(’s sampling algorithm has a running time of O(H) where H is the mean hitting time of the graph. Colbourn (1996)’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’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.

## introduction spanning trees in directed graphs foot_1 are fundamental combinatorial structures in natural language processing where they are used to represent dependency structures-especially syntactic dependency structure @xcite . additionally, probabilistic models over spanning trees are common in the nlp literature with applications primarily in non-projective dependency parsing @xcite @xcite , but also in recovering phylogenic structures @xcite , and event extraction @xcite . given the prevalence of such probabilistic models, efficient dependency tree sampling algorithms deserve study. indeed, some work has been done in transition-based dependency parsing @xcite as well as graph-based dependency parsing @xcite . sampling has also been utilized in an abundance of nlp tasks, such as text generation @xcite , co-reference resolution @xcite , and language modeling @xcite . the theoretical computer science literature has several efficient algorithms for sampling directed spanning trees. these algorithms come in two flavors. first, random walks through markov chains have been used to sample spanning trees from both undirected @xcite and directed graphs @xcite . the algorithm of @xcite is linear in the mean hitting time of the graph and is currently the fastest sampling algorithm for directed spanning trees. it has been used in dependency parsing inference by @xcite . second, several algorithms have leveraged the matrix-tree theorem (mtt; @xcite . the mtt has been frequently used to perform inference on non-projective graphbased dependency parsers @xcite @xcite . this theorem was first used for sampling by @xcite who gave an o(n 5 ) algorithm which was then improved by @xcite and @xcite . @xcite give an o(n 3 ) algorithm to sample spanning trees from an unweighted directed graph. we generalize their algorithm to the weighted case. while directed spanning tree sampling algorithms exist, an important constraint of many dependency tree schemes, such as the universal dependency (ud) scheme @xcite , is that a dependency tree may only have one edge em-anating from the designated root symbol. algorithms exists for enforcing this constraint in decoding @xcite @xcite and inference @xcite . however, to the best of our knowledge, no sampling algorithm exists which enforces the root constraint. in this paper, we adapt the algorithms of @xcite and @xcite foot_2 to efficiently sample directed spanning trees subject to a root constraint while maintaining the runtime of the original algorithms. while our modification to @xcite 's algorithm faithfully samples trees subject to the root constraint, our extension to @xcite 's algorithm produces biased samples. additionally, we provide a further extension to @xcite 's algorithm that allows us to sample trees without replacement. sampling without replacement (swor) algorithms are useful when distributions are skewed, which is often the case in a trained system. to the best of our knowledge, no swor algorithm has been presented in the literature for directed spanning trees, though @xcite provides a general framework that enables a swor algorithm to be adapted for particular kinds of sampling algorithms. ## distributions over trees we consider distributions over spanning trees in rooted directed weighted graphs (graphs for short). a graph is denoted by @xmath0, n , e) where n is a set of n + 1 nodes including a designated root node ρ and e is a set of ordered pairs between two nodes (@xmath1. we note that the non-root nodes n {ρ} can be enumerated as [1, . . . , n ]. for each edge (@xmath2, we associate a non-negative weight w @xmath3. note that w @xmath4. a directed spanning tree, denoted by t, is a collection of edges in a graph g such that each node @xmath5. moreover, we specifically examine distributions over dependency trees, which are spanning trees with an additional constraint that exactly one edge must emanate from the root ρ. this additional constraint is common amongst most dependency tree annotation schemes, e.g., universal dependencies. 4 when the type of tree (spanning or dependency) is clear from context, we will simply use trees. the set of all spanning trees of a graph g is given by t (g) and the set of all dependency trees of a graph g is given by d(g). ## random walk sampling in this section, we present the spanning tree sampling algorithm of @xcite and adapt it to sample dependency trees. the algorithm is based on a random walk through the nodes of the graph until a tree is formed. in order to do this, we require a graph g to be stochastic. a stochastic graph is such that the weights of all incoming edges to a node sum to one. that is, for all non-root nodes @xmath6 wilson @xcite shows that any graph may be converted into a stochastic graph, by adjusting the edge weights to be locally normalized along all incoming edges. therefore, the edge (@xmath7 lemma 1. for any tree @xmath8, figure 1 : cycle erasure in a random walk of a graph. the associated graph of the above walk has six nodes (including the root node ρ ) and we start the walk at 1 with the tree only containing the root node. the random walk includes a cycle with nodes 2 , 3 , and 4 , this cycle is erased when we create the path from 1 back up to ρ . note that the arrows here mark the path upwards rather than the edges in the tree, the tree edges are reversed (e.g, ρ → 5 ). note that the left-hand term in (6c) is a constant since every non-root node has in incoming edge in the tree, and so the constant is equal to a stochastic graph then defines a markov chain that we can perform a random walk on. we begin with a tree that is just composed of the root ρ. then while there exists a node connect to the tree, we start a random walk where we add each edge used to the tree, until we encounter a node that is connected to the tree. when we have connected to the tree, we can proceed to start a new random walk from a node not in the tree. of course, during a random walk, we may go through a cycle. whenever we walk through a cycle, we simply forget the cycle as part of the walk. that is, if we find ourselves visiting node i in our walk for a second time, we erase the cyclic path formed at i and continue our walk. this can be seen visually in fig. 1 . this type of walk is known as a loop-erased random walk @xcite . given ## ancestral sampling in this section, we present an extension to the ancestral sampling algorithm of @xcite to the weighted graph case. this algorithm relies on the efficient computation of z using the mtt @xcite , allows us to compute z in o(n 3 ) by taking the determinant of the laplacian matrix, @xmath9. we use @xcite 's adaptation of the mtt to dependency trees. 6 theorem 3 (proposition 1, @xcite ). for any graph g, the normalization constant z over the distribution of dependency trees d is given by @xmath10 we present the algorithm using the above laplacian matrix to sample dependency trees rather than spanning trees. however, one can easily modify this algorithm to sample spanning trees. 7 the premise 6 koo et al. (2007)'s adaptation constructs the laplacian matrix without considering edges emanating from the root. they then arbitrarily replace the first row of the laplacian matrix with the root edge weights. one can see that the first row is chosen for convenience by examining the proof of proposition 1 in @xcite . indeed, the desired laplacian can be obtained by replacing any row by the root edge weights. 7 the laplacian matrix for spanning trees is given by note that @xmath11. we can then express the probability of a tree as we sample the first edge e 1 with probability p(e 1 ). we can find its marginal probability by taking the derivative of the log partition function log z in theorem 3 which @xcite show to be foot_5 figure 4 : consider sampling a tree from the fully connected graph g given in (a). we do this by sampling an incoming edge to each non-root node. we first sample an incoming edge to 1 , the possible edges are dashed in (a). suppose we sample e 1 with probability p(e 1 ), then we have @xmath12. if we include e 1 in our graph as in (b), and repeat the process, we will sample edge e 2 with probability p(e 2 | @xmath13. we now have @xmath14, e 2 }, and we can sample an incoming edge e 3 to 3 with probability p(e 3 | @xmath15. we can similarly find @xmath16. finally, in (e), we have @xmath17, e 2 , e 3 , e 4 }, which is a tree in t (g). note t (g t) = {t}. using ( 15 ), and then update graph to be g e and repeat. this algorithm will have to recompute b o(n ) times and so will have a runtime of o(n 4 ). we show a graphical example of the algorithm in fig. 4 . we give pseudocode for this as colbourn in fig. 5 . the function sample_edge samples from the distribution defined in (15) and the function condition updates b to contain the transpose of the laplacian inverse of the conditioned graph. we describe an efficient procedure for this conditioning step in the following section. @xcite show that we can update the marginals in o(n 2 ) rather than o(n 3 ) by using rank-one updates on l. namely, @xcite 's adds an outer-product uv to l for some column vectors u, @xmath18. we extend this to the weighted laplacian for dependency trees. ## conclusion we presented two efficient approaches to sample spanning trees subject to a root constraint, which were based on prior algorithms by @xcite and @xcite . while wilson (1996)'s o(h) algorithm was more rapid, @xcite 's o(n 3 ) algorithm is extendable to a novel sampling without replacement algorithm. to the best of our knowledge, not much work has been done in graph-based dependency parsing to sample dependency trees, and none has used sampling without replacement. we hope that this paper serves as a tutorial for how this can be done and encourages the use of sampling in future work.