如何计算或近似计算数值集合所有子集的logsumexp之和？

以下默认所有子集指非空子集（空子集的logsumexp为log(0)无定义），总和与平均值仅差2^k - 1的常数系数，确实等价。 #

精确计算方法 #

适用于k规模较小的场景：

• 暴力枚举：当k ≤ 20时，总子集数不超过100万，直接遍历所有非空子集，逐个计算logsumexp求和即可。计算时注意用平移技巧避免数值溢出：logsumexp(n_1,n_2,...,n_m) = M + log(sum_{i=1}^m e^{n_i - M})，其中M = max(n_1,n_2,...,n_m)。
• 折半枚举（Meet-in-the-Middle）：当k在20~40区间时，将集合拆分为大小接近的两个子集，分别枚举两半所有非空子集的指数和（即sum_{i∈S} e^{n_i}），存为两个有序数组，再合并计算两个数组元素的组合贡献，总时间复杂度为O(k*2^{k/2})，比暴力枚举效率高两个数量级。

近似计算方法 #

适用于k > 40，无法暴力枚举的场景：

• 上界快速估计：利用凹函数的Jensen不等式可得平均值的上界为 log( (sum_{i=1}^k e^{n_i}) / 2 )，总和上界为(2^k -1) * log( (sum_{i=1}^k e^{n_i}) / 2 )，当各n_i数值差距较小时，该上界和真实值的误差非常小，可直接作为近似值使用。
• 蒙特卡洛采样：随机采样m个非空子集（m通常取1000~10000即可满足大多数精度要求），计算采样子集的logsumexp平均值，再乘以总子集数2^k -1得到总和的近似值，可通过调整采样数控制误差，实现成本极低。
• 分层近似：当各n_i数值差异较大时，先取最大值n_max，包含n_max的子集共有2^{k-1}个，这部分子集的logsumexp近似等于n_max，贡献为n_max * 2^{k-1}，剩余不包含n_max的子集递归用同样逻辑计算即可，该方法在数值差异大的场景下误差极低。

内容的提问来源于stack exchange，提问作者piedpiper