algorithm - 我们如何找到所有子集的 logsumexp(或近似值)？

Question

我有一组数字n_1, n_2, ... n_k。我需要找到这组数字的所有可能子集的 logsumexp 之和(或平均值，相同)。有没有办法近似或精确计算它？

注意，a, b, c 的 logsumexp 为 log(e_a + e_b + e_c) (exp，后跟 sum，后跟日志)

Answer 1

我不知道这是否足够准确，但 log sum exp 是 max 的平滑模拟，因此一种可能性是排序，以便 n₁ ≥ n₂ ≥ ... ≥ n_k 并返回 Σ_i (2^k−i/(2^{k − 1)) n_i，它通过 0 和 log k 之间的误差项来低于真实平均值。}

您还可以使用 {n_i} ∪ 的对数和 exp 的样本均值({n_i+1, n _{的随机子集) i+2}, …, n_k}) 而不是总和中的 n_i。通过使用足够的样本，您可以使近似值达到您想要的程度(尽管显然在某些时候使用强力评估更便宜)。

(我假设空集被省略。)