DJCM’s Trick for log(sum(exp(-x_i)))
Using floating-point math on computers sometimes results in frustrating round-off error. One example is this:
[tex]\ln\left(\sum_{I}\exp(-x_{i})\right)[/tex]
My supervisor showed me a trick to approximate it without experiencing as much round-off. I don’t know why I didn’t think of this before. Since you have this identity:
[tex]\ln\left(\sum_{I}\exp(-x_{i})\right) = \ln\left(\sum_{I}\exp(-x_{i} + \alpha)\right) + \alpha[/tex]
A good approximation is to set [tex]\alpha = \min_{I}x_{i}[/tex]. Then you can perform successive approximations recursively until you reach your satisfactory level of accuracy.
July 16th, 2005 at 1:55 pm
This is exactly what logsumexp.m in Tom Minka’s lightspeed does. There are similar functions in most probabilistic packages.
Regardingly floating point, I recently ran into this, which was interesting:
http://docs.sun.com/source/806-3568/ncg_goldberg.html
December 20th, 2007 at 3:53 pm
I believe your second equation should be:
[tex]\ln\left(\sum_{I}\exp(-x_{i})\right) = \ln\left(\sum_{I}\exp(-x_{i} + \alpha)\right) – \alpha[/tex]
or
[tex]\ln\left(\sum_{I}\exp(-x_{i})\right) = \ln\left(\sum_{I}\exp(-x_{i} – \alpha)\right) + \alpha[/tex]
but not
[tex]\ln\left(\sum_{I}\exp(-x_{i})\right) = \ln\left(\sum_{I}\exp(-x_{i} + \alpha)\right) + \alpha[/tex]
April 18th, 2008 at 10:56 pm
I agree with Zaid on the equation change. The alpha outside the ln should be subtracted, not added.