Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcs
Anej Svete, Benjamin Dayan, Ryan Cotterell, Tim Vieira, Jason M. Eisner · 2022
Weighted finite-state automata (WSFAs) are commonly used in NLP.Failure transitions are a useful extension for compactly representing backoffs or interpolation in n-gram models and CRFs, which are special cases of WFSAs.The pathsum in ordinary acyclic WFSAs is efficiently computed by the backward algorithm in time O(|E|), where E is the set of transitions.However, this does not allow failure transitions, and preprocessing the WFSA to eliminate failure transitions could greatly increase |E|.We extend the backward algorithm to handle failure transitions directly.Our approach is efficient when the average state has outgoing arcs for only a small fraction s ≪ 1 of the alphabet Σ.We propose an algorithm for general acyclic WFSAs which runs in O(|E| + s|Σ||Q||T max | log |Σ|), where Q is the set of states and |T max | is the size of the largest connected component of failure transitions.When the failure transition topology satisfies a condition exemplified by CRFs, the |T max | factor can be dropped, and when the weight semiring is a ring, the log |Σ| factor can be dropped.In the latter case (ring-weighted acyclic WFSAs), we also give an alternative algorithm with complexity O(|E| + |Σ||Q| min(1, s|π max |)), where |π max | is the size of the longest failure path.https://github.com/rycolab/ failure-backward