Efficient Computation of Expectations under Spanning Tree Distributions

Efficient Computation of Expectations under Spanning Tree Distributions Ran Zmigrod , Tim Vieira , Ryan Cotterell , University of Cambridge, United Kingdom Johns Hopkins University, United States ETH Z¨urich, United Kingdom rz279@cam.ac.uk tim.f.vieira@gmail.com ryan.cotterell@inf.ethz.ch Abstract We give a general framework for inference in spanning tree models. We propose unified al- gorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models. Our algorithms exploit a fundamental connection between gradients and expecta- tions, which allows us to derive efficient algorithms. These algorithms are easy to im- plement with or without automatic differentia- tion software. We motivate the development of our framework with several cautionary tales of previous research, which has developed numerous inefficient algorithms for comput- ing expectations and their gradients. We de- monstrate how our framework efficiently computes several quantities with known algo- rithms, including the expected attachment score, entropy, and generalized expectation criteria. As a bonus, we give algorithms for quantities that are missing in the literature, including the KL divergence. In all cases, our approach matches the efficiency of existing algorithms and, in several cases, reduces the runtime complexity by a factor of the sen- tence length. We validate the implementation of our framework through runtime experi- ments. We find our algorithms are up to 15 and 9 times faster than previous algorithms for computing the Shannon entropy and the gra- dient of the generalized expectation objective, respectively. 1 Introduction Dependency trees are a fundamental combinato- rial structure in natural language processing. It follows that probability models over dependency trees are an important object of study. In terms Equal contribution. of graph theory, one can view a (non-projective) dependency tree as an arborescence (commonly known as a spanning tree) of a graph. To build a dependency parser, we define a graph where the nodes are the tokens of the sentence, and the edges are possible dependency relations between the tokens. The edge weights are defined by a model, which is learned from data. In this paper, we focus on edge-factored models where the probability of a dependency tree is proportional to the product the weights of its edges. As there are exponen- tially many trees in the length of the sentence, we require clever algorithms for finding the normal- ization constant. Fortunately, the normalization constant for edge-factored models is efficient to compute via to the celebrated matrix–tree theorem. The matrix–tree theorem (Kirchhoff, 1847)— more specifically, its counterpart for directed graphs (Tutte, 1984)—appeared before the NLP community in an onslaught of contemporaneous papers (Koo et al., 2007; McDonald and Satta, 2007; Smith and Smith, 2007) that leverage the classic result to efficiently compute the normal- ization constant of a distribution over trees. The result is still used in more recent work (Ma and Hovy, 2017; Liu and Lapata, 2018). We build upon this tradition through a framework for computing expectations of a rich family of functions under a distribution over trees. Expectations appear in all aspects of the probabilistic modeling process: training, model validation, …

Content truncated to 500 words