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