A* shortest string decoding for non-idempotent semirings (2024)

Abstract: Abstract: The single shortest path algorithm is undefined for weighted finite-state automata over non-idempotent semirings because such semirings do not guarantee the existence of a shortest path. However, in non-idempotent semirings admitting an order satisfying a monotonicity condition (such as the plus-times or log semirings), the shortest string is well-defined. We describe an algorithm which finds the shortest string for a weighted non-deterministic automaton over such semirings using the backwards shortest distance of an equivalent deterministic automaton (DFA) as a heuristic for A* search performed over a companion idempotent semiring, which is proven to return the shortest string. There may be exponentially more states in the DFA, but the proposed algorithm needs to visit only a small fraction of them if determinization is performed “on the fly”.

## introduction weighted finite-state automata provide a compact representation of hypotheses in various speech recognition and text processing applications (e.g., @xcite @xcite . under a wide range of assumptions, weighted finite-state lattices allow for efficient polynomial-time decoding via shortest-path algorithms @xcite . the shortest path-and the algorithms that compute it-are well-defined when the weights of a lattice are idempotent and exhibit the path property. these properties are formalized below, but informally they hold that the distance between any two states corresponds to a single path between those states, so that the shortest-path algorithm-having identified this path-does not need to consider the weights of competing paths between those states. however, when the weights of a lattice lack these two properties, there is no guarantee that a shortest path between any two states exists. this situation arises in many speech and language technologies. for instance, generative models for speech recognition and machine translation-and in many unsupervised settings-often use expectation maximization (em; @xcite or related algorithms for learning; such models generally lack these two key properties. under many conditions, efficient decoding of a lattice constructed using em is required; in this case, one can decode approximately by interpreting the lattice as if it were idempotent and had the path property, or one can train the model using the viterbi approximation to em, and then decode using an ordinary shortestpath algorithm. 1 in non-idempotent semirings admitting an order satisfying a monotonicity condition, the shortest path is undefined but the closely related notion of shortest string is well-defined. we show below that it is still possible to efficiently determine the shortest string for lattices defined over non-idempotent monotonic negative semirings such as the plustimes and log semirings, both used for expectation maximization. we propose a simple algorithm for decoding the shortest string over such semirings which combines shortest-path search with the a* queue discipline @xcite and "on the fly" determinization @xcite . after providing definitions and the algorithm, we describe an implementation and evaluate it using word lattices produced by a speech recognizer. the algorithmin contrast to a naïve algorithm-is shown to scale well as a function of lattice size. ## definitions before we introduce the proposed decoding algorithm we provide definitions of key notions. ## the algorithm consider an acyclic, ϵ-free wfsa over a monotonic negative semiring (k, ⊕, ⊗, 0, 1) with total order ⪯ for which we wish to find the shortest string. the same wfsa can also be viewed as a wfsa over the corresponding companion semiring (k, ⊕, ⊗, 0, 1), and we denote by β the backward shortest-distance over this companion semiring. we prove two theorems, and then introduce an algorithm for search. theorem 3.1. the backwards shortest distance of an wfsa over a monotonic negative semiring is an admissible heuristic for the a* search over its companion semiring. proof. in a monotonic negative semiring, the ⊕sum of any n terms is upper-bounded by each of the n terms and hence by the ⊕-sum of these n terms. it follows that theorem 3.2. the backwards shortest distance of an wfsa over a monotonic negative semiring is a consistent heuristic for the a* search over its companion semiring. proof. let (q, z, k, r) be a transition in δ. leveraging again the property that an ⊕-sum of any n terms is upper-bounded by any of these terms, we show that having established that this is an admissible and consistent heuristic for a* search over the companion semiring, a naïve algorithm then suggests itself, following lemma 2.2 and remark 2.12. given a non-deterministic wfsa over the monotonic negative semiring (k, ⊕, ⊗, 0, 1), apply determinization to obtain an equivalent dfa, compute β d , the backwards shortest distance over the resulting dfa over (k, ⊕, ⊗, 0, 1) and then perform a* search over the companion semiring using β d as the heuristic. however, as mentioned in remark 2.10, determinization has an exponential worse-case complexity in time and space and is often prohibitive in practice. yet determinization-and the computation of elements of β d -only need to be performed for states actually visited by a* search. let β denote the backwards shortest distance over a nondeterministic wfsa over the monotonic negative semiring (k, ⊕, ⊗, 0, 1). then, the algorithm is as follows: ## evaluation we evaluate the proposed algorithm using nonidempotent speech recognition lattices. ## related work several prior studies use a* search for decoding speech lattices over idempotent semirings. for example, @xcite describe a related algorithm for computing n-best lists over an idempotent wfsa. like the algorithm proposed here, they use a* search and on-the-fly determinization; however, they do not consider decoding over nonidempotent semirings. we note that the algorithm proposed here could be generalized to compute the n shortest strings over a non-idempotent wfsa. specifically, one would perform a* search over the companion semiring using β d as the heuristic as described in §3, but would then solve for the n shortest strings @xcite ). ## conclusions we propose an algorithm which allows for efficient shortest string decoding of weighted automata over non-idempotent semirings using a* search and onthe-fly determinization. we find that a* search results in a substantial reduction in the number of states visited during decoding, which in turn minimizes the amount of determinization required to find the shortest string. we envision several possible applications for the proposed algorithm. it could be used to exactly decode noisy channel "decipherment" models (e.g., @xcite of the form