原址：http://www.shokhirev.com/nikolai/abc/alg/hmm/hmm.html
慢慢学习更新中。。。
定义：The Hidden Markov Model (HMM) is a variant of a finite state machine having a set of hidden states, Q, an output alphabet (observations), O, transition probabilities, A, output (emission) probabilities, B, and initial state probabilities, Π. The current state is not observable. Instead, each state produces an output with a certain probability (B). Usually the states, Q, and outputs, O, are understood, so an HMM is said to be a triple, ( A, B, Π ).
Formal Definition:
Hidden states Q = { qi }, i = 1, . . . , N .
Transition probabilities A = {aij = P(qj at t +1 | qi at t)}, where P(a | b) is the conditional probability of a given b, t = 1, . . . , T is time, and qi in Q. Informally, A is the probability that the next state is qj given that the current state is qi.
Observations (symbols) O = { ok }, k = 1, . . . , M .
Emission probabilities B = { bik = bi(ok) = P(ok | qi) }, where ok in O. Informally, B is the probability that the output is ok given that the current state is qi.
Initial state probabilities Π = {pi = P(qi at t = 1)}.
Canonical problems
There are 3 canonical problems to solve with HMMs:
Given the model parameters, compute the probability of a particular output sequence. This problem is solved by the Forward and Backward algorithms (described below).
Given the model parameters, find the most likely sequence of (hidden) states which could have generated a given output sequence. Solved by the Viterbi algorithm and Posterior decoding.
Given an output sequence, find the most likely set of state transition and output probabilities. Solved by the Baum-Welch algorithm
Forward Algorithm
Let αt(i) be the probability of the partial observation sequence Ot = {o(1), o(2), ... , o(t)} to be produced by all possible state sequences that end at the i-th state.
αt(i) = P(o(1), o(2), ... , o(t) | q(t) = qi ).
Then the unconditional probability of the partial observation sequence is the sum of αt(i) over all N states.
The Forward Algorithm is a recursive algorithm for calculating αt(i) for the observation sequence of increasing length t . First, the probabilities for the single-symbol sequence are calculated as a product of initial i-th state probability and emission probability of the given symbol o(1) in the i-th state. Then the recursive formula is applied. Assume we have calculated αt(i) for some t. To calculate αt+1(j), we multiply every αt(i) by the corresponding transition probability from the i-th state to the j-th state, sum the products over all states, and then multiply the result by the emission probability of the symbol o(t+1). Iterating the process, we can eventually calculate αT(i), and then summing them over all states, we can obtain the required probability.
Formal Definition
Initialization:
α1(i) = pi bi(o(1)) , i =1, ... , N
Recursion:
here i =1, ... , N , t =1, ... , T - 1
Termination:
参考：
- Hidden Markov model, http://www.nist.gov/dads/HTML/hiddenMarkovModel.html
- Hidden Markov model, http://en.wikipedia.org/wiki/Hidden_Markov_model
- Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE, 77 (2), p. 257286, February 1989.
- V. Petrushin. Hidden Markov Models: Fundamentals and Applications. Part 2: Discrete and Continuous Hidden Markov Models, Online Symposium for Electronics Engineers. 2000
- Narada Warakagoda, Baum-Welch Algorithm. http://jedlik.phy.bme.hu/~gerjanos/HMM/node11.html
网友评论