Deficiency in direct algorithm for HMM

Question

I implement a direct HMM calculation algorithm to calculate the probability that a given HMM emits a given sequence of observations. I would like my algorithm to be flow resistant. I can’t work in the log space because a direct algorithm requires multiplication AND adding probabilities. What is the best way to avoid overflow?

I read some sources about this, but the best suggestion I get is to scale the probabilities at each time step of Section 6 here . By the end of the algorithm, you will not be left with an exact probability (observation sequence). In addition, if I'm not mistaken, if you scale the probabilities at each time step, as suggested in the link above, you cannot make a meaningful comparison of the probability that a given sequence of observations will have two different HMMs (to find out which one is more likely total will output a sequence). Any suggestions?

Answer 1

In equation 32, at the end of your link, you multiply each alpha_t (i) probability value by C_t. So at the end, you multiplied your final probabilities by the product of all C_t. You can track all of this by keeping track of the log amount (C_t). Then at the end you can work out log (alpha_t (i)) - SUM_ (j <= t) log (C_j), which will give you the logarithmic probability of the final alpha_t (i) or log (SUM_t alpha_t (i)) - SUM_ (j < = t) log (C_j), which will give you the logarithmic probability of the whole sequence.