Self-Organizing Markov Models and Their Application to Part-of-Speech Tagging

Self-Organizing Markov Models and Their Application to Part-of-Speech Tagging Jin-Dong Kim Dept. of Computer Science University of Tokyo jdkim@is.s.u-tokyo.ac.jp Hae-Chang Rim Dept. of Computer Science Korea University rim@nlp.korea.ac.kr Jun’ich Tsujii Dept. of Computer Science University of Tokyo, and CREST, JST tsujii@is.s.u-tokyo.ac.jp Abstract This paper presents a method to de- velop a class of variable memory Markov models that have higher memory capac- ity than traditional (uniform memory) Markov models. The structure of the vari- able memory models is induced from a manually annotated corpus through a de- cision tree learning algorithm. A series of comparative experiments show the result- ing models outperform uniform memory Markov models in a part-of-speech tag- ging task. 1 Introduction Many major NLP tasks can be regarded as prob- lems of finding an optimal valuation for random processes. For example, for a given word se- quence, part-of-speech (POS) tagging involves find- ing an optimal sequence of syntactic classes, and NP chunking involves finding IOB tag sequences (each of which represents the inside, outside and begin- ning of noun phrases respectively). Many machine learning techniques have been de- veloped to tackle such random process tasks, which include Hidden Markov Models (HMMs) (Rabiner, 1989), Maximum Entropy Models (MEs) (Rat- naparkhi, 1996), Support Vector Machines (SVMs) (Vapnik, 1998), etc. Among them, SVMs have high memory capacity and show high performance, especially when the target classifica- tion requires the consideration of various features. On the other hand, HMMs have low memory capacity but they work very well, especially when the target task involves a series of classifications that are tightly related to each other and requires global optimization of them. As for POS tagging, recent comparisons (Brants, 2000; Schr¨oder, 2001) show that HMMs work better than other models when they are combined with good smoothing techniques and with handling of unknown words. While global optimization is the strong point of HMMs, developers often complain that it is difficult to make HMMs incorporate various features and to improve them beyond given performances. For ex- ample, we often find that in some cases a certain lexical context can improve the performance of an HMM-based POS tagger, but incorporating such ad- ditional features is not easy and it may even degrade the overall performance. Because Markov models have the structure of tightly coupled states, an ar- bitrary change without elaborate consideration can spoil the overall structure. This paper presents a way of utilizing statistical decision trees to systematically raise the memory capacity of Markov models and effectively to make Markov models be able to accommodate various fea- tures. 2 Underlying Model The tagging model is probabilistically defined as finding the most probable tag sequence when a word sequence is given (equation (1)). T(w1,k) = arg max t1,k P(t1,k|w1,k) (1) = arg max t1,k P(t1,k)P(w1,k|t1,k) (2) ≈ arg max t1,k k � i=1 P(ti|ti−1)P(wi|ti) (3) By applying Bayes’ formula and eliminating a re- dundant term not affecting the argument maximiza- tion, we can obtain equation (2) which is a combi- nation of two separate …

Content truncated to 500 words