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)而不是其他任何值？爲什麼我們不遞歸地進行這種計算，從每個子集中挑選最大值並重復計算對數？

答案：因爲沒關係。

原因？假設x_1 = 10很大，並且x_2 = -10很小。 （這些數字還沒出來幅度非常大的，對吧？）表達

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

會給你非常接近10的值。如果你不相信我，去試試吧。實際上，如果某些特定的x_i比其他所有其他的更大，則通常ln(exp(x_1) + exp(x_2) + ...)將非常接近max(x_i)。 （順便說一句，這個函數形式，漸進，其實可以讓你在數學從一組數字中挑選最大。）

因此，我們之所以挑選最大，而不是任何其他值是因爲較小的值幾乎不會影響結果。如果它們下溢，它們本來會太小而不能影響總和，因爲它會被最大數量和接近它的任何東西所支配。在計算方面，在計算ln之後，小數的貢獻將小於ulp。所以沒有理由浪費時間遞歸地計算較小值的表達式，否則它們將在最終結果中丟失。

如果你想真正實現這個目標，你會除以exp(max(x_i) - some_constant)左右將結果值「居中」在1左右，以避免溢出和下溢，這可能會給你一些額外的精度數字在結果中。但是避免溢出對於避免下溢更爲重要，因爲前者決定結果，後者不會，所以僅僅這樣做就簡單多了。

Answer 2

遞歸地做它不是更好。問題只是你想確保你的有限精度算術不會在噪音中淹沒答案。通過自己處理最大值，你可以確保任何垃圾在最終答案中保持較小，因爲它的最重要的組成部分是保證通過的。

道歉爲waffly解釋。嘗試用一些數字自己（一個合理的清單開始可能是[1E-5,1E25,1E-5]），看看會發生什麼感覺。

Answer 3

正如您所定義的那樣，您的recursive函數將永不終止。這是因爲((x-maxlog) for x in listOfLogs)的元素數量仍然與listOfLogs相同。

我不認爲這是很容易修復的，不會對性能或精度造成太大影響（與非遞歸版本相比）。