Abstract
Weighted finite-state machines (WFSMs) are a fundamental building block of NLP systems, from early noisy channel models to modern neurally parameterized conditional random fields. This work examines the computation of higher-order derivatives with respect to the normalization constant for WFSMs. We provide a general algorithm for evaluating derivatives of all orders, which has not been previously described in the literature. In the case of second-order derivatives, our scheme runs in the optimal $\mathcal{O}(A^2 N^4)$ time where $A$ is the alphabet size and $N$ is the number of states. Our algorithm is significantly faster than prior algorithms and leads to a significantly faster algorithm for computing second-order expectations, such as covariance matrices and gradients of first-order expectations.
Introduction
Weighted Finite-state Machines (WFSMs) have remained a cornerstone of Natural Language Processing for decades. Whether they are powering speech recognition systems, morphological analyzers, or serving as the structured backbone for neural sequence models like Conditional Random Fields (CRFs), their utility is undeniable. A central challenge in utilizing these models is the calculation of the normalization constant ($Z$), which represents the sum of weights of all possible paths through the machine. While computing $Z$ is straightforward for acyclic machines, cyclic machines—which can contain infinite paths—require more sophisticated matrix-based approaches.
The Computational Bottleneck
Training and analyzing WFSM-based models often requires more than just the value of $Z$; it requires its derivatives. First-order derivatives are used for standard gradient-based training, while higher-order derivatives (such as the Hessian) are essential for calculating uncertainty, performing second-order optimization, and computing covariance matrices.
Historically, computing these higher-order derivatives has been a massive computational bottleneck. Previous methods, such as those described by Li and Eisner (2009), often reached complexities as high as $\mathcal{O}(N^7)$, where $N$ is the number of states. Even standard reverse-mode automatic differentiation (AD) typically results in $\mathcal{O}(AN^5 + A^2N^4)$ complexity. For large-scale NLP applications, these costs are often prohibitive.
A Linear-Algebraic Breakthrough
This research shifts the perspective on WFSMs from graph-based automata to a purely linear-algebraic framework. The authors leverage the fundamental identity that for a cyclic WFSM, the path sum $W^\star$ is equivalent to the matrix inverse $(I - W)^{-1}$.
By focusing on the differential properties of matrix inverses, the authors derived a novel theorem (Theorem 2) that expresses the $m^{th}$-order derivative of $Z$ as a sum over permutations of transitions. This theoretical foundation allows for the derivation of specific identities that bypass the overhead and inefficiencies of general-purpose automatic differentiation libraries.
Achieving Optimal Complexity
For the second-order derivative (the Hessian), the paper introduces an algorithm that is asymptotically optimal. Since the Hessian matrix itself contains $\mathcal{O}(A^2N^4)$ elements, any algorithm that materializes the full matrix cannot be faster than this bound. The proposed algorithm achieves exactly $\mathcal{O}(A^2N^4)$ time and space complexity by utilizing intermediate values from the matrix inversion process to compute each Hessian element in constant $\mathcal{O}(1)$ time.
This represents a significant leap over prior state-of-the-art methods, reducing the exponent of $N$ and making the computation of second-order information feasible for much larger state spaces than previously possible.
Applications: Second-Order Expectations
The implications of this work extend beyond the Hessian itself. The authors demonstrate how their approach leads to the fastest known algorithm for computing "second-order expectations." These expectations are critical for calculating the covariance between different features in a sequence model and for computing the gradients of first-order expectations. By exploiting the associativity of the underlying operations, the authors provide a method that outperforms the traditional "expectation semiring" approach.
Conclusion and Future Directions
By providing the first general algorithm for evaluating derivatives of all orders for cyclic WFSMs, this work fills a significant gap in the literature. The move to an optimal $\mathcal{O}(N^4)$ Hessian computation provides a powerful tool for researchers working with structured prediction and neuralized WFSMs.
While the current analysis assumes dense transition matrices, future work may integrate sparse matrix inversion techniques to further optimize performance for specific graph structures. Additionally, the development of "Hessian-vector product" versions of these algorithms could allow researchers to utilize second-order information without the memory overhead of fully materializing the $N^4$ matrix, opening the door to even larger-scale applications in modern NLP.
Summary updated