Efficient Computation of Expectations under Spanning Tree Distributions

Ran Zmigrod, Tim Vieira, Ryan Cotterell

TL;DR

This paper introduces a unified, high-performance framework for computing expectations in spanning tree models (commonly used in dependency parsing). By exploiting a deep mathematical connection between gradients and expectations, the authors provide $O(N^3)$ algorithms for complex quantities like entropy and KL divergence, offering up to a 15x practical speedup over previous methods.

What Problem Does This Paper Address?

In Natural Language Processing, dependency parsing often involves finding the most likely "tree" structure that connects words in a sentence. Because the number of possible trees grows exponentially with the sentence length ($N$), we use probabilistic models over spanning trees.

A major bottleneck in training and evaluating these models is computing expectations. Whether you are calculating the "Risk" (expected error), the "Entropy" (uncertainty), or the "KL Divergence" (difference between two models), you technically need to sum over every possible tree. While the celebrated Matrix-Tree Theorem (MTT) allows us to find the normalization constant ($Z$) in $O(N^3)$ time, calculating expectations of more complex functions has historically led to "cautionary tales" in the literature—researchers frequently published inefficient $O(N^4)$ or even $O(N^5)$ algorithms because a unified approach was missing.

Methods

The authors bridge this gap by leveraging the relationship between gradients and expectations.

  1. First-Order Expectations: They show that the total weight of a function that decomposes over edges (like the number of correct attachments) can be computed using the gradient of the normalization constant ($\nabla Z$). Thanks to the "cheap gradient principle" from automatic differentiation, if $Z$ is $O(N^3)$, its gradient is also $O(N^3)$.
  2. Second-Order Expectations: Quantities like the gradient of entropy or the Generalized Expectation (GE) objective involve second-order interactions. Naively, these require the Hessian ($\nabla^2 Z$), which is usually too slow to compute.
  3. The $T_2$ Algorithm: The paper’s crown jewel is a novel algorithm that refactors the bottleneck of the Hessian computation. By applying the distributive property to the Laplacian matrix's inverse, they avoid materializing dense matrices, bringing the complexity of many second-order expectations down to $O(N^3)$.

Crucially, these algorithms are designed to "piggyback" on modern automatic differentiation (AD) libraries like PyTorch or JAX, making them easy to implement in just a few lines of code.

Datasets

The authors validated their framework using the Universal Dependencies (UD) corpora, specifically testing on five languages with varying average sentence lengths:

  • Finnish, English, German, French, and Arabic.
  • They also used the English UD Treebank specifically for experiments involving the Generalized Expectation (GE) objective.

Key Insights and Ideas

  • The "Cheap Gradient" Advantage: The authors remind the community that if you have an efficient algorithm for a partition function, you essentially get the first-order expectations "for free" (in the same complexity class) via backpropagation.
  • Refactoring the Hessian: The realization that the second derivative of the determinant (via Jacobi’s formula) can be decomposed into sparse operations is what allows the jump from $O(N^4)$ to $O(N^3)$.
  • Agnostic Parameterization: The framework works regardless of whether your edge weights come from a simple log-linear model or a complex deep neural network.
  • Filling the Literature Gaps: The paper provides the first known algorithm for computing the KL divergence between two graph-based parsers.

Key Results

  • Entropy Speedup: The proposed $O(N^3)$ algorithm was compared against the standard $O(N^4)$ approach. On Finnish (short sentences), it was 4.1x faster; on Arabic (longer sentences), it was 15.1x faster.
  • GE Objective: For the Generalized Expectation objective, the framework achieved a 9x speedup over the previous state-of-the-art strategy.
  • Numerical Stability: Despite concerns in older literature that automatic differentiation might be numerically unstable for these tasks, the authors found that their AD-based gradients matched traditional methods with an absolute tolerance of $10^{-16}$.

Limitations and Future Work

  • Edge-Factored Constraint: The framework is specifically designed for "edge-factored" models, where the score of a tree is the product of the scores of its individual edges. It does not directly extend to higher-order models (e.g., those considering sibling or grandparent relationships) without significant changes to the underlying graph structure.
  • Future Directions: The authors suggest that this "differentiation-as-inference" approach could be extended to other structured prediction models beyond spanning trees, potentially unifying inference for a wider variety of combinatorial structures 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 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},
}

Loading related content...

Figure