如何在没有下溢的情况下计算对数空间中的总和?
我正在尝试计算log(a + b)给定log(a)和log(b)。问题是,log(a)而且log(b)非常消极,以至于当我尝试计算a和b它们自己时,它们下溢,我得到log(0),这是未定义的。
对于log(a * b)and log(a / b),这不是问题,因为log(a * b) = log(a) + log(b)and log(a / b) = log(a) - log(b)。有没有类似的方法来计算log(a + b)而不需要a和b他们自己,避免下溢?
回答
简而言之,请使用以下表达式:
fmax(la, lb) + log1p(exp(-fabs(lb - la)))
我在其中使用laandlb作为变量存储log(a)和log(b)分别,函数名称来自 C's math.h。大多数其他语言也将具有这些功能,但它们的名称可能不同,例如absandmax代替fabsand fmax。(注意:这些是我将在整个答案中使用的约定。)
说到函数,Mark Dickinson 有一个很好的观点:您可能想检查是否可以访问一个可以直接为您执行此操作的函数。例如,如果您使用 Python 和 NumPy,则可以访问logaddexp,而 SciPy 具有logsumexp.
如果您想了解有关上述内容的来源、如何添加两个以上的数字以及如何减去的更多详细信息,请继续阅读。
更详细
没有像乘法和除法那样简单的规则,但有一个数学恒等式可以提供帮助:
log(a + b) = log(a) + log(1 + b/a)
我们可以稍微玩一下这个身份来获得以下内容:
log(a + b) = log(a) + log(1 + b/a)
= log(a) + log(1 + exp(log(b) - log(a)))
= la + log(1 + exp(lb - la))
这里还是有问题。如果la远大于lb,您将1 + 0.000...000something在log. 浮点尾数中没有足够的数字来存储something,所以你只会得到log(1),lb完全失去。
幸运的是,大多数编程语言在其标准库中都有一个函数来解决这个问题,log1p,它计算 1 加上它的参数的对数。也就是说,log1p(x)返回log(1 + x)但以一种对非常小的x.
所以,现在我们有:
log(a + b) = la + log1p(exp(lb - la))
我们就快到了。还有另一件事需要考虑。通常,您希望la大于lb。它不会总是问题,但有时这会得到你额外的精度。*如果之间的差别lb,并la为真正的大,这将节省您从溢出exp(lb - la)。在最极端的情况下,当lb为负无穷大(即为b0)时,计算有效,但当为时无效la。
有时,您会知道哪个更大,并且您可以将其用作la. 但是当它可能是其中之一时,您可以使用最大值和绝对值来解决它:
log(a + b) = fmax(la, lb) + log1p(exp(-fabs(lb - la)))
集合的总和
如果你需要对两个以上的数字求和,我们可以推导出上述恒等式的扩展版本:
log(a[0] + a[1] + a[2] + ...)
= log(a[0] * (a[0]/a[0] + a[1]/a[0] + a[2]/a[0] + ...))
= log(a[0]) + log(a[0]/a[0] + a[1]/a[0] + a[2]/a[0] + ...)
= la[0] + log(1 + exp(la[1]-la[0]) + exp(la[2]-la[0]) + ...)
我们将要使用与添加两个数字时类似的技巧。这样,我们就能得到最准确的答案,并尽可能避免上溢和下溢。首先,log1p:
log(a[0] + a[1] + a[2] + ...)
= la[0] + log1p(exp(la[1]-la[0]) + exp(la[2]-la[0]) + ...)
另一个考虑是在log1p. la[0]到目前为止,我用于演示,但是您想使用最好的那个。这与我们la > lb在添加两个数字时想要的所有相同原因。例如,如果la[1]是最大的,你可以这样计算:
log(a[0] + a[1] + a[2] + ...)
= la[1] + log1p(exp(la[0]-la[1]) + exp(la[2]-la[1]) + ...)
将其放入正确的代码中,它看起来像这样(这是 C,但它应该可以很好地翻译成其他语言):
double log_sum(double la[], int num_elements)
{
// Assume index_of_max() finds the maximum element
// in the array and returns its index
int idx = index_of_max(la, num_elements);
double sum_exp = 0;
for (int i = 0; i < num_elements; i++) {
if (i == idx) {
continue;
}
sum_exp += exp(la[i] - la[idx]);
}
return la[idx] + log1p(sum_exp);
}
计算日志空间的差异
这不是问题的一部分,但因为它可能仍然有用:可以类似地执行对数空间中的减法。基本公式是这样的:
log(a - b) = la + log(1 - exp(lb - la))
请注意,这仍然假设la大于lb,但对于减法,它更为重要。如果la小于lb,则取负数的对数!
与加法类似,这有一个准确性问题,可以通过使用专门的函数来解决,但事实证明有两种方法。一个使用与log1p上面相同的函数,但另一个使用expm1, expm1(x)wherereturns exp(x) - 1。这里有两种方式:
log(a - b) = la + log1p(-exp(lb - la))
log(a - b) = la + log(-expm1(lb - la))
您应该使用哪一个取决于 的值-(lb - la)。当-(lb - la)大于大约 0.693(即log(2))时,第一个更准确,当它更小时,第二个更准确。有关原因和log(2)来源的更多详细信息,请参阅评估这两种方法的 R 项目中的此注释。
最终结果如下所示:
(lb - la < -0.693) ? la + log1p(-exp(lb - la)) : la + log(-expm1(lb - la))
或以函数形式:
double log_diff(double la, double lb)
{
if (lb - la < -0.693) {
return la + log1p(-exp(lb - la));
} else {
return la + log(-expm1(lb - la));
}
}
* 这有一点甜蜜点。当之间的差别la和lb小,答案将是准确的两种方式。当差异太大时,结果将始终等于两者中的较大者,因为浮点数没有足够的精度。但是,当差异恰到好处时,您会在la更大时获得更好的准确性。