math - log-sum-exp 技巧为什么不递归

Question

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

简单的算法是

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

许多网站，包括: logsumexp implementation in C?和 http://machineintelligence.tumblr.com/post/4998477107/推荐使用

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

又名

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

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

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

当我问是否还有其他技巧可以使该计算在数值上更加稳定时？

Answer 1

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

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

您可能会遇到两种问题:

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

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

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

答案:因为这并不重要。

原因是？比方说x_1 = 10大，并且x_2 = -10是小。 (这些数字甚至不是很大，对吧？)表达式

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

会给你一个非常接近10的值。如果你不相信我，那就去试试吧。事实上，一般来说，ln( exp(x_1) + exp(x_2) + ... )将非常接近 max(x_i)如果有一些特定的x_i比其他所有的都大得多。 (顺便说一句，这种渐近函数形式实际上可以让您从数学上从一组数字中选择最大值。)

因此，我们选择最大值而不是任何其他值的原因是因为较小的值几乎不会影响结果。如果它们下溢，它们就太小而无法影响总和，因为它将由最大数和任何接近它的数主导。在计算方面，小数字的贡献将小于 ulp计算 ln 后。因此，如果较小值无论如何都会在最终结果中丢失，则没有理由浪费时间递归计算较小值的表达式。

如果你想在实现这个问题上非常挑剔，你可以除以 exp(max(x_i) - some_constant)左右将结果值“居中”在 1 附近，以避免溢出和下溢，这可能会给结果带来一些额外的精度。但避免上溢比避免下溢更重要，因为前者决定结果，而后者则不决定结果，所以这样做要简单得多。