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 We can now calculate the temporary variables, according to Bayes' theorem: 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