Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcs (2022)

Abstract: Weighted finite-state automata (WSFAs) arecommonly used in NLP. Failure transitions area useful extension for compactly representingbackoffs or interpolation in n-gram modelsand CRFs, which are special cases of WFSAs.Unfortunately, applying standard algorithmsfor computing the pathsum requires expand-ing these compact failure transitions. As aresult, na ̈ıve computation of the pathsum inacyclic WFSAs with failure transitions runs inO(|Q|2|Σ|) (O(|Q||Σ|) for deterministic WF-SAs) while the equivalent algorithm in normalWFSAs runs in O(|E|), where E representsthe set of transitions, Q the set of states, andΣ the alphabet. In this work, we present moreefficient algorithms for computing the pathsumin sparse acyclic WFSAs, i.e., WFSAs with av-erage out symbol fraction s ≪ 1. In those,backward runs in O(s|Q||Σ|). We proposean algorithm for semiring-weighted automatawhich runs in O(|E| + s|Σ||Q||Tmax| log |Σ|),where |Tmax| is the size of the largest con-nected component of failure transitions. Ad-ditionally, we propose faster algorithms fortwo specific cases. For ring-weighted WF-SAs we propose an algorithm with complex-ity O(|E| + s|Σ||Q||πmax|), where |πmax| de-notes the longest path length of failure transi-tions stemming from q and Σ(q) the set of sym-bols on the outgoing transitions from q. Forsemiring-weighted WFSAs whose failure tran-sition topology satisfies a condition exemplifiedby CRFs, we propose an algorithm with com-plexity O(|E| + s|Σ||Q| log |Σ|).

## 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 models (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 higherorder 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 that word. the pathsum computes the total weight of all the paths in a wfsa graph, where the weights may fall in any semiring. @xcite examples include finding the highest-weighted path for viterbi decoding, computing the posterior marginals (inference) in hidden markov models, and computing the normalizing constant in crfs. the pathsum is particularly efficient to compute in acyclic wfsas with the backward algorithm, whose runtime is o(|e|). however, the special semantics of failure transitions mean that the ordinary backward algorithm cannot be applied (nor can the forward algorithm). failure transitions must first be replaced by normal ones (alg. 2 below), resulting in the failure-expanded transition set e, which can contain up to |q| 2 |σ| transitions. replacing failure transitions, therefore, undoes the compaction afforded by them. this is especially expensive (|e| ≫ |e|) for backoff language models, for example, where each of the many 4-gram states only has explicit transitions in e for symbols a that were observed in training data to follow that 4-gram, but has transitions in e for every @xmath0. for example, penn treebank tagging has |σ| = 36 and czech morphological tagging has |σ| > 1000 (hajič and hladká, 1998). while allauzen et al. (2003) present an o(n 2 |σ||q|) method to preprocess a (possibly cyclic) n-gram language model wfsa with failure transitions such that the pathsum remains identical, their method only applies to the case of the tropical semiring. in this paper, we study the problem of efficiently computing the pathsum in wfsas with failure transitions over general semirings. we specifically focus on acyclic wfsas, 2 introducing several algorithms, all based on the backward algorithm, that take advantage of the compact structure induced by the failure transitions. our improvements are strongest for wfsas that are sparse in a sense to be defined shortly. we summarise our contributions as follows: ## preliminaries this section defines wfsas, the pathsum problem, the backward algorithm, and failure transitions. definition 1. a semiring is a 5-tuple @xmath1, ⊕, ⊗, 0, 1) where k is a set equipped with operations ⊕ and ⊗, s.t. (k, ⊕, 0) is a commutative @xcite we have also worked out several novel algorithms for cyclic wfsas with failure transitions. however, the 9-page format of emnlp submissions meant that we had to save these for a future manuscript. moreover, we view the split into acyclic and cyclic cases as natural, as our algorithms for cyclic automata are based on the more complex algorithm of lehmann (1977). while the acyclic algorithms cannot be run on a backoff language model (one of our examples), they can be used, for example, to compute the total language model probability of all paths in an acyclic lattice that may have wildcard arcs and/or failure arcs. even though the language model is cyclic, its intersection with the lattice becomes acyclic. monoid, (k, ⊗, 1) is a monoid, ⊕ distributes over ⊗, and 0 annihilates ⊗. definition 2. a weighted finite-state automaton (wfsa) is a 5-tuple @xmath2, q, e, λ, ρ⟩, where σ is a finite alphabet, q a finite set of states, e a collection of transitions in q×σ×k×q, λ ∶ @xmath3, and ρ ∶ @xmath4. to improve readability, we render a transition (q, a, w, q ′ ) as q a/@xmath5. we further define importantly, we will assume that the graph (q, e) is acyclic (see footnote 2). less importantly, our definition of wfsas does not allow ε-transitions, assuming that they have been eliminated in advance (mohri, 2002a), which is easy in the acyclic case. our runtime analyses assume for simplicity that (i) the graph is connected (implying |e| ≥ |q| -1) and (ii) that for each q, q ′ ∈ q, e contains at most one transition q a/@xmath6. definition 5. the pathsum of a is defined as the problem of computing the pathsum is sometimes also referred to as the generalized shortestdistance problem (mohri, 2002b). definition 6. the backward value β(q) of a state @xmath7, i.e., the value β(q, a) can be seen as the result of restricting the paths contributing to β(q) to those starting with @xmath8. notice that β(q) = ρ (q) ⊕ β(q, σ(q)). naïvely computing the pathsum by enumerating all π ∈ π(a) in an acyclic wfsa would result in an exponential runtime. however, algebraic properties of semirings allow for faster algorithms (mohri, 2002b). an example is the backward algorithm, a dynamic program which computes backward values and the pathsum in acyclic wfsas in time o (|e|). it exploits the fact that, in acyclic wfsas, q can always be topologically sorted and the backward values can be computed in reverse topological order. this guarantees that the backward values of q's children will have been computed by the time we expand q, meaning that β(q) can be computed as the pseudocode is given in alg. 1. all our algorithms are based on the backward algorithm. ## expanding failure transitions the pathsum of a wfsa-ϕ can be naïvely computed by replacing the ϕ-transitions with normal ones according to the semantics of the ϕ-transitions and running the backward algorithm on the expanded wfsa. before introducing our contributions, we present this method for pedagogical purposes. while this solution is near-optimal for non-σ-sparse wfsas, it can be improved for certain σ-sparse wfsas. ## incrementally modified aggregator the point of alg. 4 line 9 is to replace some summands of β(q ϕ , σ) to get β(q, σ). when no subtraction operator ⊖ is available (e.g., if ⊕ = max), we can use an aggregation data structure that is designed to efficiently replace individual summands in a sum without using subtraction. for example, a fenwick tree (fenwick, 1994) can replace a summand and recompute the sum in o(log n ) called in alg. 4, the memo (for that particular a) may not yet exist and will have to be filled in on demand. @xcite clearly we will represent each sum β(q, σ) in alg. 4 as the total value of an aggregator that stores summands β(q, a) for @xmath9. in principle, this aggregator could be obtained by copying the aggregator for β(q ϕ , σ) and then modifying some summands (see line 9). however, aggregators are not constantsize data structures, so creating all of these slightly different aggregators would be expensive. instead, our strategy will be to use just a single aggregator, for the "current" state q, and make small modifications as we visit different states q ′ . more precisely, we have one aggregator γ per failure tree, first created at the tree's root. when we step backwards in the failure tree, say from q ϕ to q, we modify "just a few" summands in γ so that β(q, a) replaces β(q ϕ , a) for @xmath10. this is fast if σ(q) is small. we can now obtain β(q, σ) as the aggregator's new total value. to visit other ancestors of q ϕ , we must first move forward to q ϕ again, which we do by reverting the modifications. @xcite definition 11. aggregator γ represents @xmath11, a), ∀@xmath12. when γ represents q, it holds that β(q) = ρ(q) ⊕ γ.value(), by (10). updates are carried out by the methods in alg. 5, which move backward and forward in a failure tree. when γ represents q ϕ , we can call visit(γ, q) to update γ so that it represents q. at any later time when γ again represents q, we can call leave(γ, q) to undo this update, so that γ again represents q ϕ . like alg. 3, this computes β(q) at all states in reverse topological order. however, it attempts to share work among states q in the same failure tree t , by having them share an aggregator γ t that currently represents some state q @xmath13. the algorithm updates the aggregator to represent q, by descending in the failure tree until it reaches a common descendant, and then ascending again until it reaches q. to make line 8 efficient, we preprocess each failure tree by visiting its states in depth-first order and annotating each state with the time interval during which it is on the stack. @xcite the loop at line 8 continues until the q t interval contains the q interval. ## comparison of algorithms this work proposed multiple algorithms for computing the pathsum of an acyclic wfsa-ϕ. they are all alternatives to running the backward algorithm (alg. 1)-or its simple improvement by aggregation (alg. 3)-after explicitly expanding failure transitions (alg. 2). this section summarizes the improvements. as mentioned in §3.2, we never change the way the local component of the backward values is computed. all algorithms we consider therefore retain the o(|e|) complexity term from expanding the non-ϕ transitions. what differs is the method for computing the failure term β(q, σ ∖ σ(q))-the contribution of the paths starting at q that take q's failure transition. maintaining perspective, the benefits of our more sophisticated pathsum algorithms over the basic alg. 3 only make an actual impact if alg. 3's failure component complexity o((ss)|σ||q|) is dominant over the local component o(|e|), where |e| ≥ s|σ||q|. in particular, reducing the failure component is only helpful if s ≫ s, so that expanding failure transitions would make the graph denser. ## conclusion we presented two new algorithms for more efficiently computing the backward values and pathsum of a sparse acyclic semiring-weighted fsa with ϕ-transitions, using the observation that a ϕtransition from q to q ϕ means that β(q) is a sparsely modified version of β(q ϕ ). we characterized when the new algorithms are asymptotically faster.