Weighted finite-state transducers in speech recognition

We survey the use of weighted nite state transducers WFSTs in speech recognition We show that WFSTs provide a common and natural rep resentation for HMM models context dependency pronunciation dictio naries grammars and alternative recognition outputs Furthermore gen eral transducer operations combine these representations exibly and e ciently Weighted determinization and minimization algorithms optimize their time and space requirements and a weight pushing algorithm dis tributes the weights along the paths of a weighted transducer optimally for speech recognition As an example we describe a North American Business News NAB recognition system built using these techniques that combines the HMMs full cross word triphones a lexicon of forty thousand words and a large trigram grammar into a single weighted transducer that is only somewhat larger than the trigram word grammar and that runs NAB in real time on a very simple decoder In another example we show that the same techniques can be used to optimize lattices for second pass recognition In a third example we show how general automata operations can be used to assemble lattices from di erent recognizers to improve recognition performance Introduction Much of current large vocabulary speech recognition is based on models such as HMMs tree lexicons or n gram language models that can be represented by weighted nite state transducers Even when richer models are used for instance context free grammars for spoken dialog applications they are often restricted for e ciency reasons to regular subsets either by design or by approximation Pereira and Wright Nederhof Mohri and Nederhof M Mohri Weighted FSTs in Speech Recognition A nite state transducer is a nite automaton whose state transitions are labeled with both input and output symbols Therefore a path through the transducer encodes a mapping from an input symbol sequence to an output symbol sequence A weighted transducer puts weights on transitions in addition to the input and output symbols Weights may encode probabilities durations penalties or any other quantity that accumulates along paths to compute the overall weight of mapping an input sequence to an output sequence Weighted transducers are thus a natural choice to represent the probabilistic nite state models prevalent in speech processing We present a survey of the recent work done on the use of weighted nite state transducers WFSTs in speech recognition Mohri et al Pereira and Riley Mohri Mohri et al Mohri and Riley Mohri et al Mohri and Riley We show that common methods for combin ing and optimizing probabilistic models in speech processing can be generalized and e ciently implemented by translation to mathematically well de ned op erations on weighted transducers Furthermore new optimization opportunities arise from viewing all symbolic levels of ASR modeling as weighted transducers Thus weighted nite state transducers de ne a common framework with shared algorithms for the representation and use of the models in speech recognition that has important algorithmic and software engineering bene ts We start by introducing the main de nitions and notation for weighted nite state acceptors and transducers used in this work We then present introductory speech related examples and describe the most important weighted transducer operations relevant to speech applications Finally we give examples of the ap plication of transducer representations and operations on transducers to large vocabulary speech recognition with results that meet certain optimality criteria Weighted Finite State Transducer De nitions and Al gorithms The de nitions that follow are based on the general algebraic notion of semiring Kuich and Salomaa The semiring abstraction permits the de nition of automata representations and algorithms over a broad class of weight sets and algebraic operations A semiring K consists of a set K equipped with an associative and com mutative operation and an associative operation with identities and respectively such that distributes over and a a In other words a semiring is similar to the more familiar ring algebraic structure such as the ring of polynomials over the reals except that the additive operation may not have an inverse For example N is a semiring The weights used in speech recognition often represent probabilities the cor responding semiring is then the probability semiring R For numerical stability implementations may replace probabilities with log probabilities The appropriate semiring is then the image by log of the semiring R M Mohri Weighted FSTs in Speech Recognition and is called the log semiring When using log probabilities with a Viterbi best path approximation the appropriate semiring is the tropical semiring R f g min In the following de nitions we assume an arbitrary semiring K We will give examples with di erent semirings to illustrate the variety of useful computations that can be carried out in this framework by a judicious choice of semiring