我有一組數字n_1, n_2, ... n_k。我需要找到logsumexp這組數字的所有可能子集的總和（或平均值，它相同）。有沒有辦法近似或精確計算它？
注意，logsumexpofa, b, c是log(e_a e_b e_c)（exp，后跟sum，后跟log）
uj5u.com熱心網友回復：
我不知道這是否足夠準確，但 log sum exp 是 max 的一種平滑模擬，因此一種可能性是排序使得 n 1 ≥ n 2 ≥ … ≥ n k并回傳 ∑ i (2 k?i / (2 k ? 1)) n i，它通過 0 和 log k 之間的誤差項來低估真實平均值。
您還可以使用 {n i } ∪ （{n i 1 , n i 2 , …, n k }的隨機子集）的對數總和 exp 的樣本平均值，而不是總和中的 n i。通過使用足夠多的樣本，您可以根據自己的喜好制作近似值（盡管顯然在某些時候用蠻力進行評估會更便宜）。
（我假設省略了空集。）
uj5u.com熱心網友回復：
換一種說法，這是一個確定性方案，其附加誤差至多為 ε。就像在我的另一個答案中一樣，我們對 n 1 ≥ … ≥ n k 進行排序，在最小索引為 i 的非空子集上定義平均對數和 exp 的近似 f(i)，并評估 ∑ i (2 k?i / ( 2 k ? 1)) f(i)。如果每個 f(i) 都在 ε 之內，那么結果也是如此。
固定 i 并且對于 1 ≤ j ≤ k?i 定義 d j = n i j ? n i。注意 d j ≤ 0。我們定義 f(i) = n i g(i) 其中 g(i) 將近似于均值對數 1 加上 {d j |子集的總和 exp。j}。
我不想正式寫下一部分，因為我相信它會更難理解，所以我的想法是，隨著 log sum exp 是可交換和關聯的，我們將加速初始化結果串列為 [0]，然后，對于每個 j，通過將每個當前元素的d j附加到對數總和 exp 將串列的大小加倍。我聲稱，如果我們將每個中間結果向下舍入到最接近的 δ = ε/k 倍數，那么結果將至多低于 ε。通過從串列切換到直方圖，我們可以按時間與不同條目的數量成比例地執行每個步驟。最后，我們將 g(i) 設定為直方圖平均值。
為了分析運行時間，在最壞的情況下，我們有所有 j 的d j = 0，使得最大可能的結果 log k。這意味著串列最多可以有 (log k)/δ = ε -1 k log k 1 個條目，使得總運行時間為 O(ε -1 k 3 log k)。（這無疑可以通過更快的卷積演算法和/或通過舍入 d j并利用來稍微改善。）
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/325477.html
上一篇：用于代數操作方程的編程語言