Language Processing with Weighted Transducers

TALN 2001, Tours, 2-5 juillet 2001 Language Processing with Weighted Transducers Mehryar Mohri AT&T Labs - Research 180 Park Avenue Florham Park, NJ 07932-0971, USA mohri@research.att.com R´esum´e - Abstract Les automates et transducteurs pond´er´es sont utilis´es dans un ´eventail d’applications allant de la reconnaissance et synth`ese automatiques de la langue `a la biologie informatique. Ils four- nissent un cadre commun pour la repr´esentation des composants d’un syst`eme complexe, ce qui rend possible l’application d’algorithmes d’optimisation g´en´eraux tels que la d´eterminisation, l’´elimination des mots vides, et la minimisation des transducteurs pond´er´es. Nous donnerons un bref aperc¸u des progr`es r´ecents dans le traitement de la langue `a l’aide d’automates et transducteurs pond´er´es, y compris une vue d’ensemble de la reconnaissance de la parole avec des transducteurs pond´er´es et des r´esultats algorithmiques r´ecents dans ce domaine. Nous pr´esenterons ´egalement de nouveaux r´esultats li´es `a l’approximation des gram- maires context-free pond´er´ees et `a la reconnaissance `a l’aide d’automates pond´er´es. Weighted automata and transducers are used in a variety of applications ranging from automatic speech recognition and synthesis to computational biology. They give a unifying framework for the representation of the components of complex systems. This provides opportunities for the application of general optimization algorithms such as determinization, � -removal and mini- mization of weighted transducers. We give a brief survey of recent advances in language processing with weighted automata and transducers, including an overview of speech recognition with weighted transducers and recent algorithmic results in that field. We also present new results related to the approximation of weighted context-free grammars and language recognition with weighted automata. Keywords: automatic speech recognition, weighted finite-state transducers, weighted automata, context-free grammars, regular approximation of CFGs, rational power series. 1 Introduction It is a common observation that massive quantities of digitized data are widely available for various information sources such as text, speech, biological sequences, images, and handwritten Mehryar Mohri characters or patterns. But much needs to be done to fully exploit these resources since they are all highly variable or noisy sources of information. Natural language texts are extremely ambiguous, speech and handwritten texts highly variable and hard to detect in presence of noise, biological sequences often altered. To cope with this variability, sophisticated machine learning techniques have been used to de- sign statistical models for these information sources (Vapnik1995). The theory of weighted finite-state transducers combining the classical automata theory and statistical models provides a general framework for processing such sources of information. Weighted transducers are in fact used in a variety of applications ranging from automatic speech recognition and synthesis to computational biology (Baldi and Brunak1998; Culik II and Kari1997; Mohri1997). They give a common representation for the components of complex language processing sys- tems. This provides opportunities for the application of general optimization algorithms such as determinization, � -removal, and minimization of weighted transducers. In what follows, we give a brief survey of some recent advances in language processing with weighted automata and transducers, including an overview of speech recognition with weighted transducers and recent …

Content truncated to 500 words