如何处理科学计算中的下溢? [英] How to deal with underflow in scientific computing?
问题描述
我正在研究概率模型，并且在对那些模型进行推断时，估计的概率可能会很小.为了避免下溢，我目前在日志域中工作(我存储概率的日志).乘法概率等效于加法，并且求和是通过使用以下公式完成的:
I am working on probabilistic models, and when doing inference on those models, the estimated probabilities can become very small. In order to avoid underflow, I am currently working in the log domain (I store the log of the probabilities). Multiplying probabilities is equivalent to an addition, and summing is done by using the formula:
log(exp(a) + exp(b)) = log(exp(a - m) + exp(b - m)) + m
其中m = max(a, b).
我使用一些非常大的矩阵，并且必须使用这些矩阵的按元素指数计算矩阵向量乘法.此步骤非常昂贵，我想知道在处理概率时是否还存在其他方法来处理下溢.
I use some very large matrices, and I have to take the element-wise exponential of those matrices to compute matrix-vector multiplications. This step is quite expensive, and I was wondering if there exist other methods to deal with underflow, when working with probabilities.
编辑:出于效率原因，我正在寻找使用原始类型而不是使用存储任意实数实数表示形式的对象的解决方案.
for efficiency reasons, I am looking for a solution using primitive types and not objects storing arbitrary-precision representation of real numbers.
我正在寻找比日志域技巧更快的解决方案，而不是更准确的解决方案.我对目前获得的准确性感到满意，但是我需要一种更快的方法.特别是，求和是在矩阵向量乘法过程中发生的，我希望能够使用有效的BLAS方法.
Edit 2: I am looking for a faster solution than the log domain trick, not a more accurate solution. I am happy with the accuracy I currently get, but I need a faster method. Particularly, summations happen during matrix-vector multiplications, and I would like to be able to use efficient BLAS methods.
解决方案:在与Jonathan Dursi讨论之后，我决定按矩阵和向量的最大元素分解因数，并将该因数存储在对数域中.乘法很简单.在进行加法运算之前，我必须通过两个因子的比率来分解一个相加的矩阵/向量.我每十次操作更新一次.
Solution: after a discussion with Jonathan Dursi, I decided to factorize each matrix and vector by its largest element, and to store that factor in the log domain. Multiplications are straightforward. Before additions, I have to factorize one of the added matrices/vectors by the ratio of the two factors. I update the factor every ten operations.
推荐答案
This issue has come up recently on the computational science stack exchange site as well, and although there the immediate worry there was overflow, the issues are more or less the same.
转换为日志空间无疑是一种合理的方法.无论您处于什么空间，要正确地进行大量求和，可以使用两种方法来提高求和的准确性.补偿求和方法，最著名的是 Kahan求和，既可以求和，又可以有效地保持余数". ;它为您提供了使用高精度算术而不带来所有成本(并且仅使用基本类型)的一些优势.其余的术语还可以让您了解您的表现如何.
Transforming into log space is certainly one reasonable approach. Whatever space you're in, to do a large number of sums correctly, there's a couple of methods you can use to improve the accuracy of your summations. Compensated summation approaches, most famously Kahan summation, keep both a sum and what's effectively a "remainder"; it gives you some of the advantages of using higher precision arithmeitic without all of the cost (and only using primitive types). The remainder term also gives you some indication of how well you're doing.
除了改善加法的实际机制外，更改加法条件的顺序也可以带来很大的不同.对术语进行排序，以便从最小到最大进行求和，这将有所帮助，因为这样您就不再需要频繁地添加非常不同的术语(这可能会导致重大的舍入问题)；在某些情况下，对log 2 N个重复的成对和进行求和也可以比仅对直线线性求和进行改进，具体取决于项的长短.
In addition to improving the actual mechanics of your addition, changing the order of how you add your terms can make a big difference. Sorting your terms so that you're summing from smallest to largest can help, as then you're no longer adding terms as frequently that are very different (which can cause significant roundoff problems); in some cases, doing log2 N repeated pairwise sums can also be an improvement over just doing the straight linear sum, depending on what your terms look like.
所有这些方法的有用性在很大程度上取决于数据的属性.任意精度的数学库在使用计算时间(以及可能的内存)上非常昂贵时，却具有作为通用解决方案的优势.
The usefullness of all these approaches depend a lot on the properties of your data. The arbitrary precision math libraries, while enormously expensive in compute time (and possibly memory) to use, have the advantage of being a fairly general solution.
这篇关于如何处理科学计算中的下溢?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
