Unbiased and Efficient Sampling of Dependency Trees

Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 1691 - 1706 December 7-11, 2022 ©2022 Association for Computational Linguistics Unbiased and Efficient Sampling of Dependency Trees Miloš Stanojevi´c DeepMind stanojevic@deepmind.com Abstract Most computational models of dependency syn- tax 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. (2021b) proposed algorithms for sampling with and without replacement from the dependency tree distribution that incorpo- rate the single-root constraint. In this paper we show that their fastest algorithm for sam- pling 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 replace- ment to O(kn3). These algorithms are both asymptotically and practically more efficient. 1 Introduction Dependency trees are one of the core structures for representing syntactic relations between words (Kübler et al., 2009; Osborne, 2019). There are multiple ways that these trees can be formally de- fined which has computational, linguistic and mod- eling consequences. Until recently, the most com- mon 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 artifi- cial 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 (Tarjan, 1977; McDonald et al., 2005). 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 tree- banks (Nivre et al., 2020) 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 re- fer 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 depen- dency trees at first may appear unimportant be- cause 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, Zmigrod et al. (2020) have shown that that is not the case—state-of-the-art trained parsers often pre- dict an invalid dependency tree as …

Content truncated to 500 words