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

Question

我一直在研究log-sum-exp问题.我有一个以对数形式存储的数字列表,我希望将它们相加并存储在对数中.

天真的算法是

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

许多网站包括: 在C中实现logsumexp？ 和 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.(顺便说一下,这个函数形式,渐近地,实际上让你从数学上选择一组数字的最大值.)

因此,我们选择max而不是任何其他值的原因是因为较小的值几乎不会影响结果.如果它们下溢,它们本来就太小而无法影响总和,因为它将由最大数量和接近它的任何东西支配.在计算方面,小数字的贡献在计算之后将小于ulpln.因此,如果它们在最终结果中丢失,那么没有理由浪费时间递归计算较小值的表达式.

如果你真的想要实现这个,那么你要除以exp(max(x_i) - some_constant)或者将结果值"居中"在1左右,以避免溢出和下溢,这可能会在结果中给你一些额外的精度数字.但是避免溢出对于避免下溢更为重要,因为前者决定了结果而后者没有,因此以这种方式做到这一点要简单得多.