Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcs

Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcs Anej Svete1 Benjamin Dayan1 Tim Vieira2 Ryan Cotterell1 Jason Eisner2 1ETH Z¨urich 2Johns Hopkins University {asvete, bdayan}@ethz.ch ryan.cotterell@inf.ethz.ch {timv, jason}@cs.jhu.edu Abstract Weighted finite-state automata (WSFAs) are commonly used in NLP. Failure transitions are a useful extension for compactly repre- senting 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 back- ward algorithm in time O(∣E∣), where E is the set of transitions. However, this does not al- low failure transitions, and preprocessing the WFSA to eliminate failure transitions could greatly increase ∣E∣. We extend the back- ward 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 pro- pose an algorithm for general acyclic WFSAs which runs in O(∣E∣ + s∣Σ∣∣Q∣∣Tmax∣log ∣Σ∣), where Q is the set of states and ∣Tmax∣ is the size of the largest connected component of failure transitions. When the failure transi- tion topology satisfies a condition exemplified by CRFs, the ∣Tmax∣ 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 complex- ity O(∣E∣ + ∣Σ∣∣Q∣min(1,s∣πmax∣)), where ∣πmax∣ is the size of the longest failure path. https://github.com/rycolab/ failure-backward 1 Introduction Weighted finite-state automata (WFSAs) are a common formalism in NLP. Many popular models are special cases, e.g., n-gram language models (Brown et al., 1992), conditional random fields (CRFs: Lafferty et al., 2001), maximum-entropy Markov models (McCallum et al., 2000), and semi-Markov models (Sarawagi and Cohen, 2004). In current practice, the weights in the WFSAs are often derived from a neural network, and neuralized WFSAs constitute the state of the art on a variety of common tasks in NLP (Rastogi et al., 2016; Schwartz et al., 2018; Lin et al., 2019; Jiang et al., 2021; Rijhwani et al., 2021; Alon et al., 2022). WFSAs are also increasingly being used for the design (Shen et al., 2019; Schwartz et al., 2018) and analysis (Peng et al., 2018; Hewitt et al., 2020; Hahn, 2020; Chiang and Cholak, 2022) of neural architectures. Failure transitions are a useful augmentation of standard WFSAs. First introduced in the context of string matching (Aho and Corasick, 1975), they can be used to represent backoff n-gram language mod- els (Allauzen et al., 2003), higher-order CRFs, and variable-order CRFs (VoCRFs; Vieira et al., 2016) in a more compact way. They represent “default” transitions out of states when no other transition is possible. For example, in backoff n-gram language models, a weighted failure transition from a higher- order history to a lower-order history (e.g., from a 4-gram to a 3-gram) is used to back off before reading a word that was rarely observed with the higher-order history, so that it was not worth including a dedicated transition for …

Content truncated to 500 words