Higher-order Derivatives of Weighted Finite-state Machines

Ran Zmigrod, Tim Vieira, Ryan Cotterell


Abstract
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(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. Additionally, our approach leads to a significantly faster algorithm for computing second-order expectations, such as covariance matrices and gradients of first-order expectations.
Anthology ID:
2021.acl-short.32
Volume:
Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 2: Short Papers)
Month:
August
Year:
2021
Address:
Online
Venues:
ACL | IJCNLP
SIG:
Publisher:
Association for Computational Linguistics
Note:
Pages:
240–248
Language:
URL:
https://aclanthology.org/2021.acl-short.32
DOI:
10.18653/v1/2021.acl-short.32
Bibkey:
Cite (ACL):
Ran Zmigrod, Tim Vieira, and Ryan Cotterell. 2021. Higher-order Derivatives of Weighted Finite-state Machines. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 2: Short Papers), pages 240–248, Online. Association for Computational Linguistics.
Cite (Informal):
Higher-order Derivatives of Weighted Finite-state Machines (Zmigrod et al., ACL-IJCNLP 2021)
Copy Citation:
PDF:
https://aclanthology.org/2021.acl-short.32.pdf
Video:
 https://aclanthology.org/2021.acl-short.32.mp4