Finite State Transducers Approximating Hidden Markov Models

Finite State Transducers Approximating Hidden Markov Models Andrd Kempe Rank Xerox Research Centre - Grenoble Laboratory 6, chemin de Maupertuis - 38240 Meylan - France andre, kempe©grenoble, rxrc. xerox, com http ://www. rxrc. xerox, com/research/mltt Abstract This paper describes the conversion of a Hidden Markov Model into a sequential transducer that closely approximates the behavior of the stochastic model. This transformation is especially advantageous for part-of-speech tagging because the re- sulting transducer can be composed with other transducers that encode correction rules for the most frequent tagging errors. The speed of tagging is also improved. The described methods have been implemented and successfully tested on six languages. 1 Introduction Finite-state automata have been successfully applied in many areas of computational linguistics. This paper describes two algorithms 1 which ap- proximate a Hidden Markov Model (HMM) used for part-of-speech tagging by a finite-state transducer (FST). These algorithms may be useful beyond the current description on any kind of analysis of written or spoken language based on both finite-state tech- nology and HMMs, such as corpus analysis, speech recognition, etc. Both algorithms have been fully implemented. An HMM used for tagging encodes, like a trans- ducer, a relation between two languages. One lan- guage contains sequences of ambiguity classes ob- tained by looking up in a lexicon all words of a sen- tence. The other language contains sequences of tags obtained by statistically disambiguating the class se- quences. From the outside, an HMM tagger behaves like a sequential transducer that deterministically 1There is a different (unpublished) algorithm by Julian M. Kupiec and John T. Maxwell (p.c.). maps every class sequence to a tag sequence, e.g.: [DET, PRO] [ADJ,NOUN] [ADJ,NOUN] ...... [END] (i) DET ADJ NOUN ...... END The aim of the conversion is not to generate FSTs that behave in the same way, or in as similar a way as possible like IIMMs, but rather FSTs that per- form tagging in as accurate a way as possible. The motivation to derive these FSTs from HMMs is that HMMs can be trained and converted with little man- ual effort. The tagging speed when using transducers is up to five times higher than when using the underly- ing HMMs. The main advantage of transforming an HMM is that the resulting transducer can be han- dled by finite state calculus. Among others, it can be composed with transducers that encode: • correction rules for the most frequent tagging errors which are automatically generated (Brill, 1992; Roche and Schabes, 1995) or manually written (Chanod and Tapanainen, 1995), in or- der to significantly improve tagging accuracy 2. These rules may include long-distance depen- dencies not handled by HMM taggers, and can conveniently be expressed by the replace oper- ator (Kaplan and Kay, 1994; Karttunen, 1995; Kempe and Karttunen, 1996). • further steps of text analysis, e.g. light parsing or extraction of noun phrases or other phrases (Ait-Mokhtar and Chanod, 1997). These compositions enable complex text analysis to be performed by a single transducer. An IIMM transducer builds …

Content truncated to 500 words