Principles of Non-stationary Hidden Markov Model and Its Applications to Sequence Labeling Task

R. Dale et al. (Eds.): IJCNLP 2005, LNAI 3651, pp. 827 – 837, 2005. © Springer-Verlag Berlin Heidelberg 2005 Principles of Non-stationary Hidden Markov Model and Its Applications to Sequence Labeling Task Xiao JingHui, Liu BingQuan, and Wang XiaoLong School of Computer Science and Techniques, Harbin Institute of Technology, Harbin, 150001, China {xiaojinghui, liubq, wangxl}@insun.hit.edu.cn Abstract. Hidden Markov Model (Hmm) is one of the most popular language models. To improve its predictive power, one of Hmm hypotheses, named limited history hypothesis, is usually relaxed. Then Higher-order Hmm is built up. But there are several severe problems hampering the applications of high- order Hmm, such as the problem of parameter space explosion, data sparseness problem and system resource exhaustion problem. From another point of view, this paper relaxes the other Hmm hypothesis, named stationary (time invariant) hypothesis, makes use of time information and proposes a non-stationary Hmm (NSHmm). This paper describes NSHmm in detail, including its definition, the representation of time information, the algorithms and the parameter space and so on. Moreover, to further reduce the parameter space for mobile applications, this paper proposes a variant form of NSHmm (VNSHmm). Then NSHmm and VNSHmm are applied to two sequence labeling tasks: pos tagging and pinyin-to- character conversion. Experiment results show that compared with Hmm, NSHmm and VNSHmm can greatly reduce the error rate in both of the two tasks, which proves that they have much more predictive power than Hmm does. 1 Introduction Statistical language model plays an important role in natural language processing and great efforts are devoted to the research of language modeling. Hidden Markov Model (Hmm) is one of the most popular language models. It was first proposed by IBM in speech recognition [1] and achieved great success. Then Hmm has a wide range of applications in many domains, such as OCR [2], handwriting recognition [3], machine translation [4], Chinese pinyin-to-character conversion [5] and so on. To improve Hmm’s predictive power, one of Hmm hypotheses [6] named limited history hypothesis, is usually relaxed and higher-order Hmm is proposed. But as the order of Hmm increases, its parameter space explodes at an exponential rate, which may result in several severe problems, such as data sparseness problem [7], system resource exhaustion problem and so on. From another point of view, this paper relaxes the other Hmm hypothesis, named stationary hypothesis, makes use of time information and proposes non-stationary Hmm (NSHmm). This paper first defines NSHmm in a formalized form, and then discusses how to represent time information in NSHmm. After that, the algorithms of NSHmm are provided and the parameter space complexity is calculated. Moreover, to further reduce the parameter space, a 828 J. Xiao, B. Liu, and X. Wang variant form of NSHmm (VNSHmm) is proposed later. At last, NSHmm and VNSHmm are applied to two sequence labeling tasks: pos tagging and pinyin-to- character conversion. As the experiment results show, compared with Hmm, NSHmm and VNSHmm can greatly reduce the error rate in the both two tasks. The rest …

Content truncated to 500 words