A Second-Order Hidden Markov Model for Part-of-Speech Tagging

A Second-Order Hidden Markov Model for Part-of-Speech Tagging Scott M. Thede and Mary P. Harper School of Electrical and Computer Engineering, Purdue University West Lafayette, IN 47907 { thede, harper} @ecn.purdue.edu Abstract This paper describes an extension to the hidden Markov model for part-of-speech tagging using second-order approximations for both contex- tual and lexical probabilities. This model in- creases the accuracy of the tagger to state of the art levels. These approximations make use of more contextual information than standard statistical systems. New methods of smoothing the estimated probabilities are also introduced to address the sparse data problem. 1 Introduction Part-of-speech tagging is the act of assigning each word in a sentence a tag that describes how that word is used in the sentence. Typ- ically, these tags indicate syntactic categories, such as noun or verb, and occasionally include additional feature information, such as number (singular or plural) and verb tense. The Penn Treebank documentation (Marcus et al., 1993) defines a commonly used set of tags. Part-of-speech tagging is an important re- search topic in Natural Language Processing (NLP). Taggers are often preprocessors in NLP systems, making accurate performance espe- cially important. Much research has been done to improve tagging accuracy using several dif- ferent models and methods, including: hidden Markov models (HMMs) (Kupiec, 1992), (Char- niak et al., 1993); rule-based systems (Brill, 1994), (Brill, 1995); memory-based systems (Daelemans et al., 1996); maximum-entropy systems (Ratnaparkhi, 1996); path voting con- straint systems (Tiir and Oflazer, 1998); linear separator systems (Roth and Zelenko, 1998); and majority voting systems (van Halteren et al., 1998). This paper describes various modifications to an HMM tagger that improve the perfor- mance to an accuracy comparable to or better than the best current single classifier taggers. 175 This improvement comes from using second- order approximations of the Markov assump- tions. Section 2 discusses a basic first-order hidden Markov model for part-of-speech tagging and extensions to that model to handle out-of- lexicon words. The new second-order HMM is described in Section 3, and Section 4 presents experimental results and conclusions. 2 Hidden Markov Models A hidden Markov model (HMM) is a statistical construct that can be used to solve classification problems that have an inherent state sequence representation. The model can be visualized as an interlocking set of states. These states are connected by a set of transition probabili- ties, which indicate the probability of traveling between two given states. A process begins in some state, then at discrete time intervals, the process "moves" to a new state as dictated by the transition probabilities. In an HMM, the exact sequence of states that the process gener- ates is unknown (i.e., hidden). As the process enters each state, one of a set of output symbols is emitted by the process. Exactly which symbol is emitted is determined by a probability distri- bution that is specific to each state. The output of the HMM is a sequence of output symbols. 2.1 Basic Definitions and Notation According to (Rabiner, 1989), there …

Content truncated to 500 words