log-sum-exp技巧，为什么不递归 [英] log-sum-exp trick why not recursive

问题描述

我一直在研究log-sum-exp问题.我有一个以对数形式存储的数字列表，我想对其求和并以对数形式存储.

I have been researching the log-sum-exp problem. I have a list of numbers stored as logarithms which I would like to sum and store in a logarithm.

天真的算法是

def naive(listOfLogs):
    return math.log10(sum(10**x for x in listOfLogs))

许多网站，包括: 用C语言实现logsumexp? 和 http://machineintelligence.tumblr.com/post/4998477107/ 建议使用

many websites including: logsumexp implementation in C? and http://machineintelligence.tumblr.com/post/4998477107/ recommend using

def recommend(listOfLogs):
    maxLog = max(listOfLogs)
    return maxLog + math.log10(sum(10**(x-maxLog) for x in listOfLogs))

aka

def recommend(listOfLogs):
    maxLog = max(listOfLogs)
    return maxLog + naive((x-maxLog) for x in listOfLogs)

我不明白的是，如果推荐的算法更好，为什么我们应该递归地调用它呢? 会带来更多好处吗?

what I don't understand is if recommended algorithm is better why should we call it recursively? would that provide even more benefit?

def recursive(listOfLogs):
    maxLog = max(listOfLogs)
    return maxLog + recursive((x-maxLog) for x in listOfLogs)

当我问其他方法时，还可以使该计算在数值上更稳定吗?

while I'm asking are there other tricks to make this calculation more numerically stable?

推荐答案

其他背景:当您直接计算以下类型的表达式时

Some background for others: when you're computing an expression of the following type directly

ln( exp(x_1) + exp(x_2) + ... )

您可能会遇到两种问题:

you can run into two kinds of problems:

• exp(x_i)可能溢出(x_i太大)，导致您无法将数字相加
• exp(x_i)可能下溢(x_i太小)，导致一堆零

• exp(x_i) can overflow (x_i is too big), resulting in numbers that you can't add together
• exp(x_i) can underflow (x_i is too small), resulting in a bunch of zeroes

如果所有值都大，或者全部都小，我们可以除以一些exp(const)并将const添加到ln的外部以得到相同的值.因此，如果我们选择正确的const，则可以将值移到某个范围内以防止上溢/下溢.

If all the values are big, or all are small, we can divide by some exp(const) and add const to the outside of the ln to get the same value. Thus if we can pick the right const, we can shift the values into some range to prevent overflow/underflow.

OP的问题是，为什么我们为此常量选择max(x_i)而不是其他任何值?为什么我们不递归地执行此计算，从每个子集中选择最大值并重复计算对数?

The OP's question is, why do we pick max(x_i) for this const instead of any other value? Why don't we recursively do this calculation, picking the max out of each subset and computing the logarithm repeatedly?

答案:因为没关系.

原因?假设x_1 = 10大而x_2 = -10小. (这些数字的大小不是很大，对吧?)表达式

The reason? Let's say x_1 = 10 is big, and x_2 = -10 is small. (These numbers aren't even very large in magnitude, right?) The expression

ln( exp(10) + exp(-10) ) 

将为您提供非常接近10的值.如果您不相信我，请尝试一下.实际上，通常，如果某个特定的x_i比所有其他的都大得多，则ln( exp(x_1) + exp(x_2) + ... )会非常接近max(x_i). (顺便说一句，这种函数形式渐近地实际上使您可以从数学上从一组数字中选择最大值.)

will give you a value very close to 10. If you don't believe me, go try it. In fact, in general, ln( exp(x_1) + exp(x_2) + ... ) will give be very close to max(x_i) if some particular x_i is much bigger than all the others. (As an aside, this functional form, asymptotically, actually lets you mathematically pick the maximum from a set of numbers.)

因此，我们选择最大值而不是其他任何值的原因是因为较小的值几乎不会影响结果.如果它们下溢，那么它们将太小而无法影响总和，因为它将由最大的数字和任何接近它的东西控制.在计算方面，计算 ulp >.因此，如果它们最终会丢失在最终结果中，那么就没有理由浪费时间递归地为较小的值计算表达式了.

Hence, the reason we pick the max instead of any other value is because the smaller values will hardly affect the result. If they underflow, they would have been too small to affect the sum anyway, because it would be dominated by the largest number and anything close to it. In computing terms, the contribution of the small numbers will be less than an ulp after computing the ln. So there's no reason to waste time computing the expression for the smaller values recursively if they will be lost in your final result anyway.

如果您真的想实施此方法，可以用exp(max(x_i) - some_constant)除以将结果值居中"在1左右，以避免上溢和下溢，这可能会给您带来一些额外的数字结果的精度.但是，避免溢出对于避免发生下溢更为重要，因为前者确定结果而后者则不能，因此以这种方式进行操作要简单得多.

If you wanted to be really persnickety about implementing this, you'd divide by exp(max(x_i) - some_constant) or so to 'center' the resulting values around 1 to avoid both overflow and underflow, and that might give you a few extra digits of precision in the result. But avoiding overflow is much more important about avoiding underflow, because the former determines the result and the latter doesn't, so it's much simpler just to do it this way.

这篇关于log-sum-exp技巧，为什么不递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！