2
$\begingroup$

I need to translate a training algorithm that involves sums and multiplications of probabilities to actual code. For that I need some sort of scaling procedure that allows me to avoid underflows, that is, misleading 0 probabilities.

A typical method is to apply the logs of probabilities but because of the sums this is not readily possible for my case. Another approach I saw in Rabiner's tutorial on HMMs, was his scaling procedure only dependent on t (time) applied to the forward algorithm and (the other way around) the backward algorithm, that when combined cancel each other to obtain the desired trained probabilities.

My question I wonder if there are books or text resources explaining common approaches to tackle the underflow problem that results in working with continuous multiplications of probabilities. Do you know any?

I hope I can get some ideas from that.

$\endgroup$
  • 1
    $\begingroup$ This seems out of scope for this site. $\endgroup$ – Suresh Venkat Mar 11 '11 at 17:05
  • 1
    $\begingroup$ @Suresh: Care to explain why? $\endgroup$ – Tsuyoshi Ito Mar 11 '11 at 18:01
  • 1
    $\begingroup$ Well, as stated it appears to be about implementation issues when dealing with discrete probabilities. $\endgroup$ – Suresh Venkat Mar 11 '11 at 18:21
  • 2
    $\begingroup$ If you're interested in practical methods for improving implementations when dealing with probabilities, you might want to ask the question also on StackOverflow. On the other hand, Vor's answer looks pretty good. $\endgroup$ – Peter Shor Mar 11 '11 at 20:22
  • 2
    $\begingroup$ @Tsuyoshi I think what I'm suggesting is that there's a better question lurking within, that would be about numerical analysis in general. But the question as stated is much more limited in scope. $\endgroup$ – Suresh Venkat Mar 11 '11 at 21:30
3
$\begingroup$

A simplee trick (explained here) that let you use the $\log$ approach even when you must sum probabilities.

Problem: $\log(\exp(a) + \exp(b))$ can lead to an underflow, to avoid it you can use this formula:

$\log(x + y) = \log(x) + \log(1.0 + \exp( \log(y) - \log(x) ) )$

Or use another approach:

$\log(\exp(a) + \exp(b)) = \log( \exp(a - C) + \exp(b - C)) + C$

Setting $C = \max(a,b)$

For example: $\log(e^{-120}+e^{-121}) = \log(e^{-120}(e^0 + e^{-1}))= \log(e^0+e^{-1})-120$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.