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

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

朴素的算法是

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

许多网站包括：logsumexp 在 C 中的实现？ and http://machineintelligence.tumblr.com/post/4998477107/推荐使用

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)

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

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

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

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

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 附近以避免溢出和下溢，这可能会给结果带来一些额外的精度。但避免上溢比避免下溢更重要，因为前者决定结果，而后者则不决定，所以这样做要简单得多。