Daily Archives: January 7, 2011

Notes on Calculating Log Sum of Exponentials 1   Recently updated !

This entry was posted in Research in General on by

Sometimes, you want to calculate the logarithm of a sum of exponentials, like:

(1)   \begin{align*} \log \sum_{i=1}^{n} \exp (x_{i}) \end{align*}

The problem to directly calculate this equation is that if one x_{i} gets sufficient large, it will overflow when you calculate the exponential of the number. We can get more arithmetic stability with a little algebra. First, find the maximum value m in \mathbf{x}:

(2)   \begin{align*} m = \underset{x^{\prime}}{\arg\max} \, x_{i} \end{align*}


Then, we have:

(3)   \begin{align*} \log \sum_{i=1}^{n} \exp (x_{i}) &= \log \Bigr( \sum_{i=1}^{n} \frac{\exp (m)}{\exp (m)} \exp(x_{i}) \Bigl) \\ &= \log \Bigr( \exp (m) \sum_{i=1}^{n} \frac{1}{\exp (m)} \exp(x_{i}) \Bigl) \\ &= \log \exp( m) + \log \Bigr( \sum_{i=1}^{n} \exp(-m) \exp(x_{i}) \Bigl) \\ &= m + \log \Bigr( \sum_{i=1} \exp( x_{i} -m ) \Bigl) \end{align*}

So the largest value passed to the exponential function is 0. If there are really tiny values after subtraction, they’ll become zero and drop out, as they should with limited precision arithmetic.

By using the technique introduced here, we can also calculate:

(4)   \begin{align*} \log \sum_{i=1}^{n} y_{i} & = \log \Bigr( \sum_{i=1}^{n} \exp \log (y_{i}) \Bigl) \\ &= \log m + \log \Bigr( \sum_{i=1}^{n} \exp ( \log y_{i} - \log m) \Bigl) \end{align*}

where m = \underset{y^{\prime}}{\arg\max} \, y_{i}.

Reference

[1] Log Sum of Exponentials
[2] log-sum-exp trick