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
- Editors:
- Chengqing Zong, Fei Xia, Wenjie Li, Roberto Navigli
- 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
- 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)
- PDF:
- https://preview.aclanthology.org/landing_page/2021.acl-short.32.pdf
- Code
- rycolab/wfsm