9

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

天真的算法是

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

许多网站，包括： logsumexp 在 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)

虽然我在问还有其他技巧可以使这个计算在数值上更稳定吗？

4

3 回答 3

11

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

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

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

如果您想对实现这一点非常挑剔，您可以除以exp(max(x_i) - some_constant)大约 1 以将结果值“居中”，以避免上溢和下溢，这可能会给您的结果带来一些额外的精度。但是避免溢出对于避免下溢更为重要，因为前者决定了结果，而后者没有，所以这样做要简单得多。

于 2013-03-07T18:03:05.830 回答
2

递归地做这件事并没有更好的办法。问题只是你想确保你的有限精度算术不会淹没答案。通过自己处理最大值，您可以确保任何垃圾在最终答案中保持较小，因为它最重要的组成部分可以保证通过。

为华而不实的解释道歉。自己尝试一些数字（一个合理的列表可能是 [1E-5,1E25,1E-5]），看看会发生什么来感受它。

于 2013-03-07T16:05:47.820 回答
2

正如您所定义的，您的recursive函数将永远不会终止。那是因为((x-maxlog) for x in listOfLogs)仍然具有与 相同数量的元素listOfLogs。

我认为这也不容易修复，不会显着影响性能或精度（与非递归版本相比）。

于 2013-03-07T17:36:52.037 回答