Part-of-Speech Tagging Using a Variable Memory Markov Model

PART-OF-SPEECH TAGGING USING A VARIABLE MEMORY MARKOV MODEL Hinrich Schiitze Center for the Study of Language and Information Stanford, CA 94305-4115 Internet: schuetze~csli.stanford.edu Yoram Singer Institute of Computer Science and Center for Neural Computation Hebrew University, Jerusalem 91904 Internet: singer@cs.huji.ac.il Abstract We present a new approach to disambiguating syn- tactically ambiguous words in context, based on Variable Memory Markov (VMM) models. In con- trast to fixed-length Markov models, which predict based on fixed-length histories, variable memory Markov models dynamically adapt their history length based on the training data, and hence may use fewer parameters. In a test of a VMM based tagger on the Brown corpus, 95.81% of tokens are correctly classified. INTRODUCTION Many words in English have several parts of speech (POS). For example "book" is used as a noun in "She read a book." and as a verb in "She didn't book a trip." Part-of-speech tagging is the prob- lem of determining the syntactic part of speech of an occurrence of a word in context. In any given English text, most tokens are syntactically am- biguous since most of the high-frequency English words have several parts of speech. Therefore, a correct syntactic classification of words in context is important for most syntactic and other higher- level processing of natural language text. Two stochastic methods have been widely used for POS tagging: fixed order Markov models and Bidden Markov models. Fixed order Markov models are used in (Church, 1989) and (Charniak et al., 1993). Since the order of the model is as- sumed to be fixed, a short memory (small order) is typically used, since the number of possible combi- nations grows exponentially. For example, assum- ing there are 184 different tags, as in the Brown corpus, there are 1843 = 6,229,504 different or- der 3 combinations of tags (of course not all of these will actually occur, see (Weischedel et al., 1993)). Because of the large number of param- eters higher-order fixed length models are hard to estimate. (See (Brill, 1993) for a rule-based approach to incorporating higher-order informa- tion.) In a Hidden iarkov Model (HMM) (Jelinek, 1985; Kupiec, 1992), a different state is defined for each POS tag and the transition probabilities and the output probabilities are estimated using the EM (Dempster et al., 1977) algorithm, which guarantees convergence to.a local minimum (Wu, 1983). The advantage of an HMM is that it can be trained using untagged text. On the other hand, the training procedure is time consuming, and a fixed model (topology) is assumed. Another dis- advantage is due to the local convergence proper- ties of the EM algorithm. The solution obtained depends on the initial setting of the model's pa- rameters, and different solutions are obtained for different parameter initialization schemes. This phenomenon discourages linguistic analysis based on the output of the model. We present a new method based on vari- able memory Markov models (VMM) (Ron et al., 1993; Ron et al., 1994). The VMM is an approx- imation of an unlimited order Markov …

Content truncated to 500 words