Efficient Computation of Expectations under Spanning Tree Distributions

Ran Zmigrod, Tim Vieira, Ryan Cotterell

Abstract

Probabilistic models over spanning trees are fundamental to dependency parsing in Natural Language Processing. However, computing expectations of complex functions—such as entropy, KL divergence, and risk—has historically been computationally expensive, often requiring $O(N^4)$ or $O(N^5)$ algorithms. We introduce a unified framework that reduces the complexity of these computations to $O(N^3)$. By exploiting the mathematical connection between gradients and expectations and introducing a novel $T_2$ algorithm for refactoring Hessian-based bottlenecks, our approach achieves up to a 15x practical speedup over previous methods.

Introduction

In dependency parsing, the goal is to identify the most probable tree structure connecting words in a sentence of length $N$. Given the exponential growth of possible trees, researchers rely on the Matrix-Tree Theorem (MTT) to compute the partition function $Z$ in $O(N^3)$ time. Despite this, calculating expectations for training objectives like Generalized Expectation (GE) or evaluation metrics like KL divergence has remained a significant bottleneck. Previous literature often resorted to inefficient higher-order algorithms due to the lack of a unified computational framework. This paper addresses this gap by leveraging the relationship between gradients and expectations.

Methodology: From Gradients to Expectations

Our framework bridges the gap between automatic differentiation (AD) and probabilistic inference by leveraging the relationship between gradients and expectations.

First-Order Expectations

We demonstrate that the total weight of functions decomposing over edges (e.g., the expected number of correct attachments) can be computed using the gradient of the normalization constant ($\nabla Z$). Following the "cheap gradient principle" from automatic differentiation, since $Z$ is computable in $O(N^3)$, its gradient is also $O(N^3)$. This allows first-order expectations to be computed with the same complexity as the partition function itself.

Second-Order Expectations and the $T_2$ Algorithm

Quantities such as the gradient of entropy or the Generalized Expectation (GE) objective involve second-order interactions, typically requiring the Hessian ($\nabla^2 Z$). To avoid the prohibitive cost of dense Hessian computation, we propose the $T_2$ Algorithm. This method refactors the Laplacian matrix's inverse using the distributive property, avoiding dense matrix materialization and maintaining $O(N^3)$ complexity for second-order expectations. These algorithms are designed to integrate seamlessly with modern AD libraries like PyTorch or JAX.

Experimental Evaluation

We validated the framework using the Universal Dependencies (UD) corpora across five languages: Finnish, English, German, French, and Arabic.

Performance and Speedup

The proposed $O(N^3)$ entropy algorithm significantly outperformed the standard $O(N^4)$ baseline. Speedups ranged from 4.1x for shorter sentences (Finnish) to 15.1x for longer sentences (Arabic). For the Generalized Expectation (GE) objective on the English UD Treebank, the framework achieved a 9x speedup over previous state-of-the-art strategies.

Numerical Stability

Contrary to historical concerns regarding the stability of automatic differentiation for these tasks, our implementation maintained high precision. AD-based gradients matched traditional methods with an absolute tolerance of $10^{-16}$, confirming the robustness of modern AD libraries for structured inference.

Conclusion and Future Work

While currently constrained to edge-factored models, this "differentiation-as-inference" approach provides a powerful tool for structured prediction. The paper provides the first known algorithm for computing the KL divergence between two graph-based parsers. Future work will explore extending these techniques to higher-order models and other combinatorial structures beyond spanning trees, potentially unifying inference for a wider variety of models in NLP.

Summary updated

Abstract

We give a general framework for inference in spanning tree models. We propose unified algorithms 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 expectations, which allows us to derive efficient algorithms. These algorithms are easy to implement with or without automatic differentiation software. We motivate the development of our framework with several \emph{cautionary tales} of previous research, which has developed numerous inefficient algorithms for computing expectations and their gradients. We demonstrate how our framework efficiently computes several quantities with known algorithms, 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 sentence length. We validate the implementation of our framework through runtime experiments. We find our algorithms are up to 15 and 9 times faster than previous algorithms for computing the Shannon entropy and the gradient of the generalized expectation objective, respectively.
BibTeX
@article{zmigrod2021efficient,
  author = {Ran Zmigrod and Tim Vieira and Ryan Cotterell},
  title = {{Efficient Computation of Expectations under Spanning Tree Distributions}},
  journal = {Trans. Assoc. Comput. Linguistics},
  year = {2021},
  url = {https://openreview.net/forum?id=4L_zWatV7rj},
}
Figure