Đang chuẩn bị liên kết để tải về tài liệu:
Chapter 10: Hidden Markov Models

Chapter 10: Hidden Markov Models Introduction; Discrete Markov processes; Hidden Markov models; Three basic problems of HMMs; Evaluation problem; Finding the state sequence; Learning model parameters. | Chapter 10 Hidden Markov Models Assoc. Prof. Dr. Duong Tuan Anh Faculty of Computer Science and Engineering, HCMC Univ. of Technology 3/2015 Outline 1 Introduction 2. Discrete Markov processes 3. Hidden Markov models 4 Three basic problems of HMMs 5. Evaluation problem 6. Finding the state sequence 7. Learning model parameters 1. Introduction Hidden Markov models (HMMs) are important in pattern recognition because they are suited to classify patterns where each pattern is made up of a sequence of sub-patterns and these sub-patterns are dependent. HMMs can be used to characterize classes of patterns, where each pattern is viewed as a sequence of states. It is possible that the actual state is hidden and only probabilistic variations are observed. HMMs are popular in speech recognition. There are several other important applications including recognition of protein and DNA sequences/subsequences in bioinformatics. 2. Discrete Markov processes Consider a system that any time is . | Chapter 10 Hidden Markov Models Assoc. Prof. Dr. Duong Tuan Anh Faculty of Computer Science and Engineering, HCMC Univ. of Technology 3/2015 Outline 1 Introduction 2. Discrete Markov processes 3. Hidden Markov models 4 Three basic problems of HMMs 5. Evaluation problem 6. Finding the state sequence 7. Learning model parameters 1. Introduction Hidden Markov models (HMMs) are important in pattern recognition because they are suited to classify patterns where each pattern is made up of a sequence of sub-patterns and these sub-patterns are dependent. HMMs can be used to characterize classes of patterns, where each pattern is viewed as a sequence of states. It is possible that the actual state is hidden and only probabilistic variations are observed. HMMs are popular in speech recognition. There are several other important applications including recognition of protein and DNA sequences/subsequences in bioinformatics. 2. Discrete Markov processes Consider a system that any time is in one of a set of N distinct states: S1, S2, ,SN. The state at time t is denoted as qt, t = 1, 2, , so for example qt = Si means that at time t, the system is in state Si. At regularly spaced discrete times, the system moves to a state with a given probability, depending on the values of the previous states: P(qt+1 = Sj | qt = Si, qt-1 = Sk, ) For a special case of a first-order Markov model, the state at time t +1 depends only on state at time t, regardless of the states in the previous times: P(qt+1 = Sj | qt = Si, qt-1 = Sk, ) = P(qt+1 = Sj | qt = Si) (10.1) We further simplify the model by assuming that these transition probabilities are independent of time (stationary): aij P(qt+1 = Sj| qt = Si) (10.2) satisfying aij > 0 and So, going from Si to Sj has the same probability no matter when it happens, or where it happens in the observation sequence. A = [aij] is a N N matrix whose rows sum to 1. This can be seen as a stochastic automaton (see Fig. 10.1). From each state Si,