Some Researches On The Algorithms Of High-order Hidden Markov Model

Hidden Markov model as a statistical model with a doubly stochastic process hasbeen widely applied to speech recognition, character recognition, biological sequenceanalysis, financial data analysis, image processing and computer vision, etc. not onlybecause of its reliable theoretical basis of probability and statistics but also because ofits powerful mathematical structure. These applications, however, are mainly based onthe first-order hidden Markov model in which there exists an assumption that the statetransition probability and output observation probability depend only on the current stateand have nothing with the previous states and output observations. While it can simplifythe algorithms of the first-order hidden Markov model and is also valid to some extentin some applications, this assumption causes some shortages for the first-order hiddenMarkov model and can not provide more accurate description for some real processessuch as speech process and DNA bases sorting process etc.To overcome the shortages of the first-order hidden Markov model, some re-searchers have proposed several refinements from diferent perspectives. One of these re-finements is to extend the first-order hidden Markov model to high-order hidden Markovmodel that takes into consideration the dependency of state transition probability or out-put observation probability on more long-distance states. By contrast with the first-orderhidden Markov model, high-order hidden Markov model has better temporal structureand can contain more statistical characteristics, so that it can partly compensate for theshortages of the first-order hidden Markov model and more exactly match some real pro-cesses. In spite of its potential, high-order hidden Markov model has been found littleapplication in the existing literatures. One of the reasons for little application is the lackof efective algorithms of high-order hidden Markov model due to its imperfect theory.To obtain more wide applications of high-order hidden Markov model, the algorithms ofhigh-order hidden Markov model must be further developed and improved.There are two basic approaches to study the algorithms of high-order hiddenMarkov model. The first one is called the extended approach, which is to extend directlythe existing algorithms of the first-order hidden Markov model to high-order hiddenMarkov model by using the principles and techniques of the algorithms of the first-orderhidden Markov models. The second one is called the model reduction method, which isto transform high-order hidden Markov to an equivalent first-order hidden Markov modelby some means and then to establish the algorithms of high-order hidden Markov modelby using standard techniques applicable to the first-order hidden Markov model. Thisdissertation uses the extended approach and the model reduction method respectively to discuss several important problems on the algorithms of high-order hidden Markovmodel, and then further develops and improves the algorithms of high-order hiddenMarkov model. This dissertation lays a theory foundation for the application of high-order hidden Markov model. The main findings of this dissertation are listed as follows:(1) A class of third-order hidden Markov model is proposed. In this proposedmodel, both state transition probability and output observation probability depend onthe current state and on the two preceding states as well. With reference of the prin-ciples and techniques of the algorithms of the first-order hidden Markov models andby using the extended method, three variables for third-order hidden Markov model aredefined, including the forward variable, the backward variable and the Viterbi variable,and then three algorithms of third-order hidden Markov model are developed and de-rived, including the forward-backward algorithm for observation sequence evaluation,the Viterbi algorithm for determining the optimal state sequence, the Baum-Welch al-gorithm for training third-order hidden Markov model with single observation sequenceand the Baum-Welch algorithm for training third-order hidden Markov model with mul-tiple observation sequences. In this treatment, multiple observation sequences are eitherindependent of each other or statistically correlated, and the dependence-independenceproperty of multiple observation sequences is characterized by combinational weights,so that the Baum-Welch algorithm for training third-order hidden Markov model withmultiple observation sequences can be suitable for a more general training set. To showthis generality, two special cases of the Baum-Welch algorithm are given when multipleobservation sequences are independent of each other and uniformly dependent on oneanother respectively. In addition, a first-order hidden Markov model equivalent to thethird-order hidden Markov model is constructed, and then a theorem of their equivalenceis proposed and proved.(2) Aiming at a class of any high-order hidden Markov model, based on Hadar’sequivalent transformation method and Li’s combinatorial method, the Baum-Welch algo-rithm for training high-order hidden Markov model with multiple observation sequencesis developed and derived by using the model reduction method, and then the correspond-ing parameter reestimation formula can be expressed by using standard techniques ap-plicable to the first-order hidden Markov model. In this treatment, multiple observa-tion sequences are either independent of each other or statistically correlated, and thedependence-independence property of multiple observation sequences is characterizedby combinational weights, so that the Baum-Welch algorithm for training high-orderhidden Markov model with multiple observation sequences can be suitable for a moregeneral training set. To show this generality, two special cases of the parameter reesti- mation formula are given when multiple observation sequences are independent of eachother and uniformly dependent on one another respectively.(3) With reference of the definition of mixture model, a class of mixture high-orderhidden Markov model is proposed. Based on the model reduction method, mixture high-order hidden Markov model is transformed into two equivalent mixture first-order hid-den Markov models respectively by using Hadar’s equivalent transformation method,and then the Baum-Welch algorithm of mixture high-order hidden Markov model is de-veloped and derived by means of the Baum-Welch algorithm of an equivalent mixturefirst-order hidden Markov model. Also, the parameter reestimation formula of mixturehigh-order hidden Markov model can be expressed by using standard techniques appli-cable to the first-order hidden Markov model.(4) Aiming at a class of any high-order hidden Markov model, the extended ap-proach and the model reduction method are used respectively to decode high-order hid-den Markov model. As for the extended approach, the Viterbi variable of high-orderhidden Markov model is firstly defined, and then the extended Viterbi algorithm of high-order hidden Markov model is established according to the dynamic programming princi-ple. The extended Viterbi algorithm can determine directly the optimal state sequence ofhigh-order hidden Markov model. As for the model reduction method, high-order hid-den Markov model is transformed into an equivalent first-order hidden Markov modelby Hadar’s equivalent transformation method, and then the optimal state sequence of theequivalent first-order hidden Markov model is determined by the existing Viterbi algo-rithm of the first-order hidden Markov model. Based on their equivalence, the optimalstate sequence of high-order hidden Markov model is inferred from the optimal statesequence of the equivalent first-order hidden Markov model.