algorithm - 通过日志处理小概率

Question

资料来源:谷歌代码挑战赛。 https://code.google.com/codejam/contest/10224486/dashboard#s=a&a=1

我们被要求计算 Prob(N 次试验的 K 次成功)，其中 N 次试验中的每一次都有已知的成功概率 p_n。

在 Code Jam 之后给出了对问题的一些分析和思考。

他们观察到评估 N 次试验的所有可能结果将花费 N 的指数时间，因此他们提供了一个很好的“动态规划”式解决方案，即 O(N^2)。

令 P(p#q) = Prob(p 在第 q 次试验后成功)然后观察以下事实:

Prob(p#q) = Prob(qth trial succeeds)*P(p-1#q-1) + Prob(qth trial fails)*P(p#q-1)

现在我们可以建立一个 P(i#j) 的表，其中 i<=j，因为 i = 1...N

这一切都很棒 - 我遵循了所有这些并且可以实现它。

---

然后作为最后的评论，他们说:

In practice, in problems like this, one should store the logarithms of
probabilities instead of the actual values, which can become small
enough for floating-point precision errors to matter.

我想我大体上理解他们试图表达的观点，但我特别想不通如何使用这个建议。

将上面的等式代入一些字母变量:

P = A*B + C*D

如果我们想在日志空间中工作，那么我们有:

Log(P) = Log(A*B + C*D),

我们已经递归地预先计算了 Log(B) 和 Log(D)，以及 A 和 B 是已知的、易于处理的小数。

但我没有看到任何方法来计算 Log(P) 而不是只做 e^(Log(B)) 等，感觉就像失败到在日志空间中工作的地步`?

有没有人更详细地了解我应该做什么？

Answer 1

从初始关系开始:

P = A⋅B + C⋅D

由于其对称性，我们可以假设 B 大于 D，而不失一般性。以下处理很有用:

log(P) = log(A⋅B + C⋅D) = log(A⋅e^log(B) + C⋅e^log(D) ) = log(e^log(B)⋅(A + C⋅e^{log(D) - log(B)})

log(P) = log(B) + log(A + C⋅e^{log(D) - log(B)}).

这很有用，因为在这种情况下，log(B) 和 log(D) 都是负数(某些概率的对数)。假设 B 大于 D，因此其对数更接近于零。因此 log(D) - log(B) 仍然为负，但不如 log(D) 负。

所以现在，我们不需要分别对 log(B) 和 log(D) 求幂，我们只需要对 log(D) - log(B) 求幂，这是一个轻微的负数。因此，与使用对数和以平凡的方式应用求幂相比，或者等效地，与根本不使用对数相比，上述处理导致更好的数值行为。