Look-Back and Look-Ahead in the Conversion of Hidden Markov Models into Finite State Transducers

/ II II / / / / / / II / / / / II / Look-Back and Look-Ahead in the Conversion of Hidden Markov Models into Finite State Transducers Andrd Kempe Xerox Research Centre Europe - Grenoble Laboratory 6, chemin de Maupertuis - 38240 Meylan - France andre, kempe@xrce, xerox, tom http://www, xrce. xerox, com/research/mltt Abstract This paper describes the conversion of a Hid- den Markov Model into a finite state trans- ducer that closely approximates the behavior of the stochastic model. In some cases the transducer is equivalent to the HMM. This conversion is especially advantageous for part- of-speech tagging because the resulting trans- ducer can be composed with other transducers that encode correction rules for the most fre- quent tagging errors. The speed of tagging is also improved. The described methods have been implemented and successfully tested. 1 Introduction This paper presents an algorithm 1 which approxi- mates a Hidden Markov Model (HMM) by a finite- state transducer (FST). We describe one applica- tion, namely part-of-speech tagging. Other poten- tial applications may be found in areas where both HMMs and finite-state technology are applied, such as speech recognition, etc. The algorithm has 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 maps every class sequence to a tag sequence, e.g.: [DET, PRO] [ADJ,NOUN] [ADJ,NOUN] ...... [END] (i) DET ADJ NOUN ...... END aThere are other (dillerent) algorithms for HMM to FST conversion: An unpublished one by Julian M. Kupiec and John T. Maxwell (p.c.), and n-type and s- type approximation by Kempe (1997). The main advantage of transforming an HMM is that the resulting transducer can be handled by fi- nite state calculus. Among others, it can be com- posed 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 -9 . These rules may include long-distance depen- dencies not handled by ttMM 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. The speed of tagging by an FST is up to six times higher than with the original HMM. The motivation for deriving the FST from an HMM is that the tIMM can be trained and con- verted with little manual effort. An HMM transducer builds on the data (probabil- ity matrices) of …

Content truncated to 500 words