Baum–Welch algorithm
In electrical engineering, computer science, statistical computing and bioinformatics, the Baum–Welch algorithm is a special case of the EM algorithm used to find the unknown parameters of a hidden Markov model. It makes use of the forward-backward algorithm to compute the statistics for the expectation step.
History
The Baum–Welch algorithm was named after its inventors Leonard E. Baum and Lloyd R. Welch. The algorithm and the Hidden Markov models were first described in a series of articles by Baum and his peers at the Institute for Defense Analyses in the late 1960s and early 1970s. One of the first major applications of HMMs was to the field of speech processing. In the 1980s, HMMs were emerging as a useful tool in the analysis of biological systems and information, and in particular genetic information. They have since become an important tool in the probabilistic modeling of genomic sequences.Description
A hidden Markov model describes the joint probability of a collection of "hidden" and observed discrete random variables. It relies on the assumption that the i-th hidden variable given the -th hidden variable is independent of previous hidden variables, and the current observation variables depend only on the current hidden state.The Baum–Welch algorithm uses the well known EM algorithm to find the maximum likelihood estimate of the parameters of a hidden Markov model given a set of observed feature vectors.
Let be a discrete hidden random variable with possible values. We assume the is independent of time, which leads to the definition of the time-independent stochastic transition matrix
The initial state distribution is given by
The observation variables can take one of possible values. We also assume the observation given the "hidden" state is time independent. The probability of a certain observation at time for state is given by
Taking into account all the possible values of and, we obtain the matrix where belongs to all the possible states and belongs to all the observations.
An observation sequence is given by.
Thus we can describe a hidden Markov chain by. The Baum–Welch algorithm finds a local maximum for .
Algorithm
Set with random initial conditions. They can also be set using prior information about the parameters if it is available; this can speed up the algorithm and also steer it toward the desired local maximum.Forward procedure
Let, the probability of seeing the observations and being in state at time. This is found recursively:Since this series converges exponentially to zero, the algorithm will numerically underflow for longer sequences. However, this can be avoided in a slightly modified algorithm by scaling in the forward and in the backward procedure below.
Backward procedure
Let that is the probability of the ending partial sequence given starting state at time. We calculate as,Update
which is the probability of being in state at time given the observed sequence and the parameters
which is the probability of being in state and at times and respectively given the observed sequence and parameters.
The denominators of and are the same ; they represent the probability of making the observation given the parameters.
The parameters of the hidden Markov model can now be updated:
which is the expected frequency spent in state at time.
which is the expected number of transitions from state i to state j compared to the expected total number of transitions away from state i. To clarify, the number of transitions away from state i does not mean transitions to a different state j, but to any state including itself. This is equivalent to the number of times state i is observed in the sequence from t = 1 to t = T − 1.
where
is an indicator function, and is the expected number of times the output observations have been equal to while in state over the expected total number of times in state.
These steps are now repeated iteratively until a desired level of convergence.
Note: It is possible to over-fit a particular data set. That is,. The algorithm also does not guarantee a global maximum.
Multiple sequences
The algorithm described thus far assumes a single observed sequence. However, in many situations, there are several sequences observed:. In this case, the information from all of the observed sequences must be used in the update of the parameters,, and. Assuming that you have computed and for each sequence, the parameters can now be updated:where
is an indicator function
Example
Suppose we have a chicken from which we collect eggs at noon everyday. Now whether or not the chicken has laid eggs for collection depends on some unknown factors that are hidden. We can however assume that there are only two states that determine whether the chicken lays eggs. Now we don't know the state at the initial starting point, we don't know the transition probabilities between the two states and we don't know the probability that the chicken lays an egg given a particular state. To start we first guess the transition and emission matrices.We then take a set of observations : N, N, N, N, N, E, E, N, N, N This gives us a set of observed transitions between days: NN, NN, NN, NN, NE, EE, EN, NN, NN The next step is to estimate a new transition matrix. For example, the probability of the sequence NN and the state being then is given by the following, Thus the new estimate for the to transition is now . We then calculate the to, to and to transition probabilities and normalize so they add to 1. This gives us the updated transition matrix:
|