Weighted Rational Transductions and their Application to Human Language Processing

Weighted Rational Transductions and their Application to Human Language Processing Fernando Pereira Michael Riley Richard Sproat AT&T Bell Laboratories 600 Mountain Ave. Murray Hill, NJ 07974 ABSTRACT We present the concepts of weighted language, ~ansduction and au- tomaton from algebraic automata theory as a general framework for describing and implementing decoding cascades in speech and lan- guage processing. This generality allows us to represent uniformly such information sources as pronunciation dictionaries, language models artd lattices, and to use uniform algorithms for building de- coding stages and for optimizing and combining them. In particular, a single automata join algorithm can be used either to combine in- formation sources such as a pronunciation dictionary and a context- dependency model during the construction of a decoder, or dynam- ically during the operation of the decoder. Applications to speech recognition and to Chinese text segmentation will be discussed. 1. Introduction As is well known, many problems in human language process- ing can be usefully analyzed in terms of the "noisy channel" metaphor: given an observation sequence o, find which in- tended message w is most likely to generate that observation sequence by maximizing P(w, o) = P(olw)P(w), where P(olw ) characterizes the transduction between in- tended messages and observations, and P(w) characterizes the message generator. More generally, the transduction be- tween messages and observations may involve several inter- mediate stages P( so, sk )= P( sk Iso)P(so) P(sklso)=~,, ..... ,~_,P(sklsk-X)'"P(sllso) (1) where P(sk Iso) is the probability of transducing so to sk through the intermediate stages, assuming that each step in the cascade is conditionally independent from the previous ones. Each s t is a sequence of units in an appropriaterepresentation. For instance, in speech recognition some of the intermediate stages might correspond to sequences of units like phones or syllables. A stralghtforwardbut useful observation is that any such a cascade can be factored at any intermediate stage P(sils~) = ~ P(s~lsk)P(skls.i) (2) Sk For computational reasons, sums and products in (1) are often replaced by minirnizations and sums of negative log probabil- ities, yielding the approximation P(s0,sk) = P(sklso) + P(s0) (3) P(s ls0) rain,, ..... ,~_,El<j_<kP(s~lsj=l) where X = - log X. In this formulation, assuming the ap- proximation is reasonable, the most likely message so is the one minimizing P(s0, sk). Finally, each transduction in such a cascade is often modeled by some finite-state device, for example a hidden Markov model. Although the above approach is widely used in speech and language processing, usually the elements of the transduction cascade are built by "ad hoc" means, and commonalities be- tween them are not exploited. We will here outline how the theory of weighted rational languages and transductions can be used as a general framework for transduction cascades. This theoretical foundation provides a rich set of operators for combining cascade elements that generalizes the standard operations on regular languages, suggests novel ways of com- bining models of different parts of the decoding process, and supports uniform algorithms for transduction and search at …

Content truncated to 500 words