Unbiased and Efficient Sampling of Dependency Trees (2022)

Abstract: Most computational models of dependency syntax consist of distributions over spanning trees. However, the majority of dependency treebanks require that every valid dependency tree has a single edge coming out of the ROOT node, a constraint that is not part of the definition of spanning trees. For this reason all standard inference algorithms for spanning trees are sub-optimal for inference over dependency trees.Zmigrod et al (2021) proposed algorithms for sampling with and without replacement from the dependency tree distribution that incorporate the single-root constraint. In this paper we show that their fastest algorithm for sampling with replacement, Wilson-RC, is in fact producing biased samples and we provide two alternatives that are unbiased. Additionally, we propose two algorithms (one incremental, one parallel) that reduce the asymptotic runtime of algorithm for sampling k trees without replacement to O(kn^3). These algorithms are both asymptotically and practically more efficient.

## introduction dependency trees are one of the core structures for representing syntactic relations between words @xcite . there are multiple ways that these trees can be formally defined which has computational, linguistic and modeling consequences. until recently, the most common formalisation of dependency structures used in computational linguistics was a spanning tree formalisation. a spanning tree is a directed graph that contains n + 1 nodes (n words and one artificial root token), n directed edges (each word has one incoming edge except for the root node that has only outgoing edges) and there are no cycles. this simple formalisation allows for the usage of efficient algorithms for finding optimal spanning trees @xcite . unfortunately, spanning trees are too loose of a formalisation to represent the constraints linguists would expect from dependency trees. one of the main linguistic constraints is that there is only one word that represents the main head of the sentence. this is a standard in universal dependencies treebanks @xcite where the constraint is incorporated by stating that every valid dependency tree should have exactly one edge coming out of the artificial root node (ud, 2022). 1 in the rest of the article we will use the term spanning tree to refer to the unconstrained trees and term dependency tree to refer to the trees that have a single-root constraint as in universal dependencies. the distinction between spanning and dependency trees at first may appear unimportant because all dependency trees are a subset of the set of spanning trees and maybe a strong neural model would learn distributions that ignore spanning trees which are not valid dependency trees. however, @xcite have shown that that is not the case-state-of-the-art trained parsers often predict an invalid dependency tree as the mode and the situation is even worse with k-best trees @xcite . this motivates the creation of specialized algorithms that do inference only over valid dependency structures. the most important algorithms needed for inference are: (1) finding the most probable tree, (2) finding marginals over edges, and (3) generating tree samples. finding the most probable dependency tree is a solved problem since the algorithm by @xcite is optimal for that task. marginals can be computed efficiently using the adaptation of matrix-tree theorem to singleroot dependency trees by @xcite . in this paper we focus on the last of these problems-generation of samples of dependency trees. the sampling of dependency trees is often used as a key component of unsupervised grammar induction @xcite , semi-supervised training of parsers @xcite , or for enabling the approximate decoding of higher-order models @xcite . the only previous work that deals specifically with sampling from distributions of constrained dependency trees is by @xcite . they adapt algorithms for sampling spanning trees to include the single-root constraint and provide algorithms for sampling with and without replacement. our main contributions are in: (i) showing that the most efficient sampling algorithm by @xcite in fact producing biased samples, (ii) proposing two new algorithms that address this issue, and (iii) providing two more algorithms (one incremental and one parallel) that improve the worst-case complexity of sampling without replacement (swor). all these algorithms are shown to be both asymptotically and practically efficient. ## distributions over dependency trees here we define more formally the distributions over dependency and spanning trees. we will consider only unlabelled trees, but extending this to the labelled case is trivial. dependency graph g of a sentence with n words is an unlabelled directed weighted rooted graph that consists of: n+1 nodes where each word of the sentence is a node, and in addition to those n nodes there is a special root node, n foot_2 edges out of which n(n -1) are directed edges between every pair of word nodes (excluding self-loops) and n edges that go from the special root node to each of the word nodes, n 2 weights , sometimes also called potentials, are non-negative real numbers associated with each of the edges using a function ϕ(•). 2 we can represent any graph of this type with an adjacency matrix w of shape (n+1, n+1) where all elements are non-negative weights with a constraint that diagonal entries are 0 (self-loops are not allowed) and first column entries are 0 (no edges can enter the root node which is at position 0 by convention). spanning tree is any subgraph of g for which it holds that (i) every word node has exactly one incoming edge and (ii) there are no cycles. dependency tree is spanning tree that in addition to the above mentioned properties also contains the constraint that there can be only one edge coming out of the special root node. we will refer to the set of all spanning trees as t and set of all dependency trees as d. the following definitions are presented for dependency trees but their analogs for spanning trees are trivial to define by just replacing every occurrence of d with t . weight of a dependency tree t is a product of the weights of all its edges: probability of a dependency tree t is a normalized weight of a tree t with respect to all other dependency trees: here z d stands for the partition function of dependency trees that must be positive i.e. z @xmath0. marginal probability of an edge e in the distribution over dependency trees is a sum of probabilities of all dependency trees d e that contain edge e: ## previous work on sampling spanning trees here we present the main two algorithms for sampling from the distributions of unconstrained spanning trees. both of these algorithms have different advantages. the first one, by @xcite , is oftentimes faster in practice and we will use it to design a fast sampler of dependency trees in section 4. the second algorithm is a type of ancestral sampling by @xcite and has a convenient form for extension to sampling without replacement, that will be used in section 5. ## extensions of wilson's algorithm to valid dependency trees in this section we will describe novel contributions with regards to sampling dependency trees with replacement. in §4.1 we show that the previous fastest sampling algorithm is in fact biased. in §4.2 and §4.3 we present two new unbiased algorithms. 2. construct graph g ′ by deleting all edges coming out of root and set the target of the edge e to be the new root, 3. apply original wilson's algorithm to graph g ′ . ## sampling without replacement (swor) sampling without replacement (swor) is a sampling procedure where after some instance is sampled it cannot be sampled again. that is useful in cases of low-entropy distributions where standard sampling is likely to provide many repetitions of the same set of samples and be inefficient in estimating the target value. samples are not independently drawn and therefore require specialized estimators @xcite . @xcite propose a swor algorithm that is based on modification of colbourn's ancestral sampling algorithm. they follow the general pattern for constructing swor algorithms by @xcite where after one tree is sampled, its probability mass is removed from the distribution so it cannot be sampled again. zmigrod et al. maintain an unstructured list of sampled trees that is always queried whenever a new sample is drawn. this makes the algorithm have quadratic complexity in terms of the number of drawn samples. concretely, for a sentence of length n the swor algorithm of zmigrod et al. draws k samples in o(kn 3 + k 2 n). this is inefficient if we want to draw a large number of samples. we provide two solutions that reduce complexity to o(kn 3 ) which is linearly dependent on the number of samples k. the main idea for both algorithms is to represent distributions over dependency trees as sequential auto-regressive models. after that is done we can apply any algorithm for sampling without replacement from sequential models. ## experiments we test the empirical performance of the algorithms presented here. we implemented all of them in python and numpy in order to comparable to previous work on @xcite for swor sampling. we do not compare performance against their adaptation of wilson's algorithm for single-7 1697 root trees since that adaptation is not correct, as we have shown in section 4.1. sampling with replacement experiments were conducted in two settings: random weights and trained weights. for random weights we used graphs with weights sampled from the uniform distribution. to get the trained weights we applied stanza's english model @xcite on english sentences of the news commentary corpus. for each graph we sample 100 trees with replacement. we compared colbourn with single-root constraint from @xcite against our wilsonmarginal and wilsonreject from section 4. the results are shown in figure 2 . both of our algorithms significantly improve upon the version of @xcite . among the two of our algorithms, wilsonmarginal performs better in random weights setting, while in trained weights setting their performance is almost identical. this is expected result from the analysis in section 4.3.1. in trained weights there are almost no rejected samples so the difference between wilsonre-ject and wilsonmarginal comes down to wilsonmarginal having matrix-inversion operation which does not seem to cause any slowdown. sampling without replacement tests were conducted in a similar way except that we vary the number of swor samples instead of the sentence length. we use sentence length of 14 words because that is the longest sequence that we could run zmigrod et al. algorithm without encountering issues with numerical instability. in appendix c we show results with running our algorithm on the longer sentences. we test only on random weights since the runtime of these algorithms does not depend on the weights value. as visible from figure 3 both of our algorithms outperform the algorithm of @xcite . of our two algorithms, the trie algorithm is slightly slower due to the constant factors needed to maintain the trie data structure. we also reimplemented a version of sbs-swor in jax so that we can see the benefits of having a parallel algorithm executed with parallel hardware and got up to ×5 speedup on gpu over cpu with sentences of length 100 (figure 4 ). see appendix c for tests on other lengths. the main takeaway is that sbs-swor allows for a vectorized implementation that can exploit modern hardware accelerators, unlike other swor algorithms. ## conclusion we have presented multiple contributions to the techniques for sampling dependency trees that (1) correct errors in the previously published algorithms, (2) propose new algorithms for sampling with replacement, (3) propose new algorithms for sampling without replacement and (4) show that these algorithms have both asymptotically and practically good performance. we hope the proposed algorithms will lead to advancements in all problems where sampling is crucial such as unsupervised grammar induction @xcite , syntax marginalization in syntactic language models @xcite and approximate decoding of higher-order models @xcite .