Efficient Dependency Tree Sampling Without Replacement (2024)

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.

## introduction dependency trees are one of the most popular structures used to represent syntactic relations between words @xcite . a popular formalisation for them is based on spanning trees in directed graphs, which is one of the core ways to represent dependency structures in natural language processing @xcite . a dependency graph for n words has n+1 nodes: one for each word and a special root node. it also has n 2 weighted edges between nodes: n(n-1) edges between any pair of distinct word nodes and n edges from the root to each node. a spanning tree of the graph is a subgraph that contains all the n+1 nodes, exactly n edges and no cycles. each node except for the root has exactly one incoming edge and is reachable from the root. probabilistic models over spanning trees have uses in non-projective dependency parsing @xcite @xcite , recovering phylogenic structures @xcite and event extraction @xcite . a typical dependency tree constraint that is also applied in the case of universal dependencies @xcite is that the tree must have exactly one edge coming out of the root node. in the rest of the paper we will refer to spanning trees that have exactly one edge coming out of the root node as "dependency trees". the need for algorithms that sample dependency trees comes from the fact that state-of-the-art parsers often predict invalid dependency trees as the most probable output @xcite . dependency tree sampling has uses in domains such as semi-supervised training of parsers @xcite , facilitating the approximate decoding of higher-order models @xcite and unsupervised grammar induction @xcite . there are 2 main sampling scenarios: sampling with replacement and sampling without replacement. in the case of sampling with replacement, the same tree can be sampled multiple times, while in the case of sampling without replacement, each tree can only be sampled once. some recent advances in dependency trees sampling can be found in @xcite , including algorithms for sampling dependency trees both with and without replacement, but in this paper we will focus on adapting the fastest algorithm in practice for sampling with replacement, wilson reject, to sampling without replacement, thus creating a new algorithm that we will call wilson reject swor that achieves superior performance compared to the other algorithms for graphs with random weights. the random weights setting usually occurs in the beginning of training of dependency parsers. ## distributions over tress in this section we will give formal definitions to distributions over spanning trees and dependency trees in rooted directed weighted graphs. a rooted directed graph can be denoted by @xmath0, e}, where v is a set of n+1 nodes (1 node for each of the n words and one special root node) and e is a set of directed weighted edges of the form {n 1 , n 2 , w} where n 1 is the starting node of the edge, n 2 is the end node of the edge and w is the nonnegative weight of an edge. a spanning tree is any subgraph of g that contains all the n+1 nodes, has exactly one incoming edge for each node except for the root and contains no cycles. a dependency tree is any subgraph of g that is a spanning tree and also has exactly one edge coming out of the root node. let d g be the set of all the dependency trees of g. let's denote the edge from node i to node j with @xmath1,j) . weight of a dependency tree can then be defined as: probability of a dependency tree can similarly be defined as: any unbiased dependency tree sampler must sample the trees according to their probabilities. ## previous work on sampling dependency trees for the problem of sampling with replacement (swir), the fastest algorithm in practice is the wilson reject algorithm (shown in algorithm 2), proposed here @xcite . wilson reject is based on rejection sampling, a strategy that we will also use in the algorithm we propose. rejection sampling is commonly used when we want to sample from a distribution d 1 (t) from which sampling is difficult, but there is a related distribution d 2 (t) from which sampling is easier. more details about rejection sampling can be found in @xcite . wilson reject uses wilson's sampling algorithm to sample spanning trees until a valid dependency tree is sampled. wilson's algorithm is a random walk based algorithm. the algorithm starts with the root node as the current selection. at each step, if there is a node that is not in the current selection, it starts a random walk from that node through its incoming edges until it reaches a node in the current selection. during the walk it samples a parent node of the current node randomly based on the weights of the incoming edges of the node. any cycles during the walk are implicitly deleted by the algorithm. the resulting chain is attached to the current selection. when all nodes are part of the selection, the selection will be a spanning tree and will be returned by the algorithm. it was proved in (stanojević, 2022) that wilson reject is an unbiased sampler, and that the expected number of samples it needs until it gets a valid dependency tree is euler's number. therefore, 3 runs of wilson's sampling algorithm are expected to be enough to sample a valid dependency tree. the total runtime complexity of wilson's algorithm depends on the graph edges and their weights, but can be as small as o(|v |) (wilson, 1996). therefore, the complexity of wilson reject is also often as small as o(|v |). the pseudocode of wilson's algorithm can be found in algorithm 1, and the pseudocode of wilson reject can be found in algorithm 2. algorithm 1 wilson 1: p ← ∅ ▷ p will keep the sampled tree edges 2: ▷ p[n 1 ] = n 2 stands for edge n 2 → n 1 3: visited ← {root } 4: for @xmath2: c ← i 6: while c / ∈ visited do 7: random sample node v with edge weight w @xmath3: p[c] ← v 9: c ← v 10: c ← i 11: while c / ∈ visited do 12: visited.add(c) 13: c ← p[c] 14: return p algorithm 2 wilson reject 1: t ← wilson(g) 2: while t has more than one root edge do 3: t ←wilson(g) 4: return t 4 wilson reject swor we will now analyze the scenario of sampling without replacement (swor), scenario in which it is not allowed to sample the same instance twice. for this scenario, 2 algorithms with complexity o(k * n 3 ) where k is the number of samples and n the number of words were proposed in (stanojević, 2022): trie-swor and sbs-swor. both use colbourn's algorithm @xcite , an ancestral sampling algorithm, as an auto-regressive form of dependency tree distribution and each of the 2 algorithms uses a different algorithm for sampling from sequential models: trie-swor is based on the trie algorithm @xcite and sbs-swor is based on stochastic beam search (sbs) @xcite . more details about these algorithms can be found in @xcite . we will focus on comparing our results with the sbs-swor algorithm, as it was found to be faster than trie-swor on cpu and, unlike trie-swor, its performance improves significantly when run on gpu. this is mainly caused by the fact that sbs-swor draws all the required samples in parallel instead of sequentially, so it can substantially benefit from the gpu's parallel computing. in order to ensure that no instance is sampled twice, swor algorithms need to constrain the current sample based on the previous samples @xcite . we create a new algorithm called wilson reject swor based on the wilson reject algorithm for the random weights setting. we do that by keeping a list of already sampled trees that are considered invalid samples for this step. at each sampling step we keep generating dependency trees with the wilson reject algorithm until we get a tree that wasn't already sampled. that tree is considered the valid sample for that step and added to the list of already sampled trees. theorem 1. wilson reject swor is unbiased. proof. we have to prove that at each step wilson reject swor samples dependency trees in an unbiased way. we consider that the trees sampled before the current step are invalid as they can't be sampled again in swor. it was already proved that wilson reject is an unbiased sampler of dependency trees @xcite . we can use rejection sampling concepts @xcite ) to prove that wilson reject swor which uses wilson reject is unbiased. let c be the current step, s c be the set of already sampled dependency trees, d 1 s c (t) be the distribution of valid dependency trees at step c and d 2 (t) be the distribution of all dependency trees that can be sampled. the condition for rejection sampling to work is that there must be a constant @xmath4, where d1 s c (t) is the unnormalized target distribution. after a sample is retrieved from d 2 (t), it is accepted with probability t) . in our case, since the trees in both distributions come from the same graph, they have the same weights, so we can have @xmath5. therefore, accepting any dependency tree sampled by wilson reject that wasn't already sampled is an unbiased swor sampling method. this means that wilson reject swor is unbiased. any node in a dependency tree except for the root can have exactly one incoming edge. therefore, if we have an edge from a node n 1 to a node n 2 , we will call n 1 the "parent" of node n 2 . to make the wilson reject swor algorithm more efficient, we can uniquely represent any dependency tree using a list of the parents of all the nodes. since the root has no parent in a dependency tree, we use a placeholder for its parent in the list. building a list of parents from a dependency tree and building a dependency tree from a list of parents are trivial operations that have o(|v |) time complexity. we can keep the parents list representations of the already sampled trees in a trie data structure. this allows us to check if a tree was already sampled by searching for its associated parents list in the trie in o(|v |) time. insertion of the parents list associated to a tree in the trie can also be done in o(|v |) time @xcite . wilson reject swor has no worst case complexity, but we can estimate the complexity for graphs with random weights. an important question is how often do we expect to sample a tree that was already sampled, which depends on the number of nodes, the configuration of edges and the number of samples. it is well known that there are n n-2 spanning trees for a complete graph of size n @xcite , and from each of them we can build a dependency tree for the graph with n+1 nodes corresponding to n words by adding the artificial root node and an edge from it to the root of the spanning tree. therefore, for the graph of size n+1 corresponding to n words, there are n n-2 dependency trees. since each dependency tree has the same number of edges, for graphs with random edge weights we can expect most dependency trees to most likely have their total weights close to their mean. this indicates that for graphs with a significant number of nodes and random weights, it is very unlikely the same tree would be sampled twice without a very big number of samples. as an experiment, we sampled 20000 dependency trees from a graph of size 100, and the same tree was never sampled twice. for cases when the same tree is only sampled once, we can consider that the complexity of wilson reject swor is the same as that of wilson reject, which as discussed previously depends on many factors but can be as small as o(|v |). therefore, the complexity of wilson reject swor can be as small as o(k * |v |), where k is the number of samples. the steps of the algorithm are shown in algorithm 3: algorithm 3 wilson reject swor 1: g ← original graph 2: t ← sample_with_wilson_reject(g) 3: t_parent_array ← get_prnt_array(t) 4: trie ← ∅ 5: while @xmath6: 6: t ← sample_with_wilson_reject(g) 7: t_parent_array ← get_prnt_array(t) 8: trie.insert(t_parent_array) 9: return t ## experiments we will now compare the results of wilson reject swor to those of sbs-swor for the case of sampling without replacement. unlike wilson reject swor, sbs-swor can be significantly improved by gpu acceleration due to the fact that it draws all samples in parallel, so it makes sense to compare the results with both those of sbs-swor on cpu and those of sbs-swor on gpu. the experiments were run on a 11th gen intel ® core(tm) i7-11800h @ 2.30ghz cpu and a nvidia ® geforce rtx 3050 gpu. the sbs-swor implementation that was used was from the synjax python library, version 2023.8.5, (stanojević and sartran, 2023) which is written in jax @xcite . we will present the results of the 2 algorithms for dependency graphs with random weights corresponding to 100 words. we found that wilson reject swor on cpu has better performance than both sbs-swor on cpu and sbs-swor on gpu, as it can be seen in figure 1 . it also has the advantage of being sequential unlike sbs-swor, allowing us to stop sampling if certain criteria were met, and the advantage of not relying on gpu. results for additional experiments with graphs with different numbers of words can be found in appendix a. ## conclusion in this paper we presented the wilson reject swor algorithm for sampling dependency trees without replacement which is based on random walks. we also showed that it is unbiased and has the best performance for graphs with random weights. it may have uses in tasks where dependency tree sampling is required such as semisupervised training of parsers @xcite , unsupervised grammar induction @xcite and approximate decoding of higher-order models @xcite .