通过日志来处理小概率

Question

资料来源:Google Code Jam.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 Space中工作,那么我们有:

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,而不失一般性.以下处理很有用:

日志(P)=日志(A⋅B+ C*d)=日志(A⋅e ^日志(B) +C⋅e ^日志(d))=日志(E ^日志(B) ⋅(A +C⋅e ^{日志(D) - log(B)})

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

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

所以现在,不需要分别执行log(B)和log(D)的取幂,我们只需要执行log(D) - log(B)的取幂,这是一个温和的负数.因此,上述处理导致更好的数值行为,而不是使用对数和以平凡的方式应用求幂,或者等效地,而不是完全不使用对数.