高效地计算对数量的总和

Question

在使用C++编程时，我想要计算一些量的总和，并对总和取对数：

log(a_1 + a_2 + a_3 + ... + a_n)

然而，我并没有这些量的实际值，我只有它们的对数值：

l_1 = log(a_1), l_2 = log(a_2), ... , l_n = log(a_n)

有没有一种有效的方法来获取a_i之和的对数？我想避免

log(s) = log(exp(l_1) + exp(l_2) + ... + exp(l_n))

如果可能的话 - 当计算被多次执行时，exp 可能会成为瓶颈。

- Mike B

---

嘿，这其实是一个数学问题，只是伪装了一下！ - Frédéric Hamidi

真遗憾，你不是在寻找log(a_1 * ... * a_n)——你可以只需对已有的对数值求和！ - Drew Hall

这些数量是什么？它们之间有任何关系吗？ - Dr. belisarius

a_i是从复杂模型中随机采样的点的概率质量，它们之间没有简单的关系。 - Mike B

@Mike 哦，好吧。有时生活会展现出它丑陋的一面。据我所知没有任何信息。您可以尝试在这里发问。 - Dr. belisarius

我认为你别无选择，只能找到每个c=log(a_i)的2 ** c_i来找到a_i。这意味着要处理大数字，并且它是一个相对较慢的操作。也许math.stackexchange.com上的人们对此有更好的见解。 - wilhelmtell

Answer 1

我不知道有什么方法，因为一般情况下，没有办法进行计算。

e^x + e^y

只使用一个指数运算和加法是无法实现你所要求的计算的。

---

正如Frédéric Hamidi在上面的评论中提到的那样，即使您对指数求和，仍然有另一个问题需要担心：溢出。 他提供的链接 提供了一个相当不错的解决方案（以下是从该链接复制的Fortran代码）：

function log_sum_exp(v) result(e)
  real, dimension(:), intent(in) :: v   ! Input vector
  real                           :: e   ! Result is log(sum(exp(v)))
  real                           :: c   ! Shift constant

  ! Choose c to be the element of v that is largest in absolute value.
  if ( maxval(abs(v)) > maxval(v) ) then
     c = minval(v)
  else
     c = maxval(v)
  end if

  e = log(sum(exp(v-c))) + c
end function log_sum_exp

- BlueRaja - Danny Pflughoeft

Answer 2

n有多大？

这个数量被称为对数和指数，Lieven Vandenberghe在他的书籍第72页上谈到了它。他还有一个优化软件包使用这个操作，并且从简短的查看中，似乎他在那里没有做任何特殊的事情，只是进行指数运算和加法。也许当n足够小以使向量适合内存时，指数运算不是一个严重的瓶颈。

这个操作经常在建模中出现，瓶颈在于项的数量非常庞大。n=2^100的数量级很常见，其中的项是隐含表示的。在这种情况下，有各种技巧来近似这个数量，依赖于对数和指数的凸性质。最简单的技巧是将log(s)近似为max(l1,l2,....,ln)。

- Yaroslav Bulatov

Answer 3

您可以使用以下等式：

log( a + b ) = log(a) + log( 1 + (b/a) )

- mocj

---

这就是Frédéric Hamidi的链接用于防止溢出的方法；但是，这如何帮助处理超过两个变量的情况呢？ - BlueRaja - Danny Pflughoeft

@BlueRaja，这并没有帮助，如果我没错的话，你仍然需要为每个术语计算指数。说得浪漫一点，提问者想要通过交叉对数曲线来预测未来，因此他必须付出代价并计算所有指数（并且要小心溢出/下溢）。 - Frédéric Hamidi

现在只需要调用 n/2 次 exp() 和 n/2 次 log()，而不是 n 次 exp()。由于本地 CPU 指令的快速支持，Log() 应该很快。exp() ~ 不是非常快... - mocj

Answer 4

如果 s_k := sum(a_1 + ... + a_k)，那么 s_{k+1} == s_k + f(l_{k+1} - s_k)，其中

f(x) := log(1+exp(x))

这个函数f可能可以使用泰勒级数或类似方法计算，速度与exp相当，并且可能可以内联。

虽然只能节省大约两个数学函数，但这可能是一个有用的起点。

- aschepler

Answer 5

这个方法可能不是很优雅，但你可以尝试以下步骤：

• 从log a_i中获取lg a_i（除以log 2）。
• 令lg a_i = k + q，其中k为整数，q为实数，且0 >= q >= 1。
• 使用位移运算符计算2^kpow(2,q)来得到a_i（其中2^k = 1 << k）。
• 你可以使用预先计算的有限精度表格来加速pow(2,q)在[0,1]范围内的计算。

因此，整个思路是利用快速幂函数。希望对你有所帮助！

- Jacob