# Higher-order Derivatives of Weighted Finite-state Machines

arXiv: https://arxiv.org/abs/2106.00749 · HTML: https://mlsanity.com/paper/2106.00749/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 25 references that are in the map.
- First posted on arXiv 1 Jun 2021.

## Builds on (most cited first, 3 of 3)

- [Differentiable Weighted Finite-State Transducers](https://mlsanity.com/paper/2010.01003/) (2020)
- [Efficient Computation of Expectations under Spanning Tree Distributions](https://mlsanity.com/paper/2008.12988/) (2020)
- [SoPa: Bridging CNNs, RNNs, and Weighted Finite-State Machines](https://mlsanity.com/paper/1805.06061/) (2018)

## Abstract (arXiv)

Weighted finite-state machines are a fundamental building block of NLP systems. They have withstood the test of time -- from their early use in noisy channel models in the 1990s up to modern-day neurally parameterized conditional random fields. This work examines the computation of higher-order derivatives with respect to the normalization constant for weighted finite-state machines. 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 O(A2 N4) time where A is the alphabet size and N is the number of states. Our algorithm is significantly faster than prior algorithms. Additionally, our approach leads to a significantly faster algorithm for computing second-order expectations, such as covariance matrices and gradients of first-order expectations.