Simpler and More General Minimization for Weighted Finite-State Automata

Simpler and More General Minimization for Weighted Finite-State Automata Jason Eisner Department of Computer Science Johns Hopkins University Baltimore, MD, USA 21218-2691 jason@cs.jhu.edu Abstract Previous work on minimizing weighted finite-state automata (including transducers) is limited to particular types of weights. We present efficient new minimization algorithms that apply much more generally, while being simpler and about as fast. We also point out theoretical limits on minimization algo- rithms. We characterize the kind of “well-behaved” weight semirings where our methods work. Outside these semirings, minimization is not well-defined (in the sense of producing a unique minimal automaton), and even finding the minimum number of states is in general NP-complete and inapproximable. 1 Introduction It is well known how to efficiently minimize a determin- istic finite-state automaton (DFA), in the sense of con- structing another DFA that recognizes the same language as the original but with as few states as possible (Aho et al., 1974). This DFA also has as few arcs as possible. Minimization is useful for saving memory, as when building very large automata or deploying NLP systems on small hand-held devices. When automata are built up through complex regular expressions, the savings from minimization can be considerable, especially when ap- plied at intermediate stages of the construction, since (for example) smaller automata can be intersected faster. Recently the computational linguistics community has turned its attention to weighted automata that compute interesting functions of their input strings. A traditional automaton only returns an boolean from the set K = {true, false}, which indicates whether it has accepted the input. But a probabilistic automaton returns a prob- ability in K = [0, 1], or equivalently, a negated log- probability in K = [0, ∞]. A transducer returns an output string from K = ∆∗ (for some alphabet ∆). Celebrated algorithms by Mohri (1997; 2000) have recently made it possible to minimize deterministic au- tomata whose weights (outputs) are log-probabilities or strings. These cases are of central interest in language and speech processing. However, automata with other kinds of weights can also be defined. The general formulation of weighted automata (Berstel and Reutenauer, 1988) permits any weight set K, if appropriate operations ⊕ and ⊗ are pro- vided for combining weights from the different arcs of the automaton. The triple (K, ⊕, ⊗) is called a weight semiring and will be explained below. K-valued func- tions that can be computed by finite-state automata are called rational functions. How does minimization generalize to arbitrary weight semirings? The question is of practical as well as theoret- ical interest. Some NLP automata use the real semiring (R, +, ×), or its log equivalent, to compute unnormalized probabilities or other scores outside the range [0, 1] (Laf- ferty et al., 2001; Cortes et al., 2002). Expectation semir- ings (Eisner, 2002) are used to handle bookkeeping when training the parameters of a probabilistic transducer. A byproduct of this paper is a minimization algorithm that works fully with those semirings, a new result permitting more efficient automaton processing …

Content truncated to 500 words