java - 具有对数概率 Java 实现的数值精度

Question

有时，当您使用常见数据类型(例如 double 据)进行概率非常小的计算时，数值不准确会叠加多次计算并导致不正确的结果。因此，建议使用 log probabilities , 这提高了数值稳定性。我已经在 J​​ava 中实现了对数概率并且我的实现有效，但是它的数值稳定性比使用原始 double 差。我的实现有什么问题？在 Java 中执行许多小概率连续计算的准确有效方法是什么？

我无法提供这个问题的完整演示，因为许多计算都存在不准确之处。但是，这里证明存在问题:this由于数字准确性，提交给 CodeForces 竞赛失败。运行测试 #7 并添加调试打印清楚地表明，从第 1774 天开始，数字错误开始级联，直到概率总和下降到 0(当它应该是 1 时)。在用 double 的简单包装器替换我的 Prob 类后 the exact same solution passes tests .

我对乘法概率的实现:

a * b = Math.log(a) + Math.log(b)

我的加法实现:

a + b = Math.log(a) + Math.log(1 + Math.exp(Math.log(b) - Math.log(a)))

稳定性问题很可能包含在这两行中，但这是我的整个实现:

class Prob {

        /** Math explained: https://en.wikipedia.org/wiki/Log_probability
         *  Quick start:
         *      - Instantiate probabilities, eg. Prob a = new Prob(0.75)
         *      - add(), multiply() return new objects, can perform on nulls & NaNs.
         *      - get() returns probability as a readable double */

        /** Logarithmized probability. Note: 0% represented by logP NaN. */
        private double logP;

        /** Construct instance with real probability. */
        public Prob(double real) {
            if (real > 0) this.logP = Math.log(real);
            else this.logP = Double.NaN;
        }

        /** Construct instance with already logarithmized value. */
        static boolean dontLogAgain = true;
        public Prob(double logP, boolean anyBooleanHereToChooseThisConstructor) {
            this.logP = logP;
        }

        /** Returns real probability as a double. */
        public double get() {
            return Math.exp(logP);
        }

        @Override
        public String toString() {
            return ""+get();
        }

        /***************** STATIC METHODS BELOW ********************/

        /** Note: returns NaN only when a && b are both NaN/null. */
        public static Prob add(Prob a, Prob b) {
            if (nullOrNaN(a) && nullOrNaN(b)) return new Prob(Double.NaN, dontLogAgain);
            if (nullOrNaN(a)) return copy(b);
            if (nullOrNaN(b)) return copy(a);

            double x = a.logP;
            double y = b.logP;
            double sum = x + Math.log(1 + Math.exp(y - x));
            return new Prob(sum, dontLogAgain);
        }

        /** Note: multiplying by null or NaN produces NaN (repping 0% real prob). */
        public static Prob multiply(Prob a, Prob b) {
            if (nullOrNaN(a) || nullOrNaN(b)) return new Prob(Double.NaN, dontLogAgain);
            return new Prob(a.logP + b.logP, dontLogAgain);
        }

        /** Returns true if p is null or NaN. */
        private static boolean nullOrNaN(Prob p) {
            return (p == null || Double.isNaN(p.logP));
        }

        /** Returns a new instance with the same value as original. */
        private static Prob copy(Prob original) {
            return new Prob(original.logP, dontLogAgain);
        }
    }

Answer 1

问题是由方式引起的Math.exp(z)用于此行:

a + b = Math.log(a) + Math.log(1 + Math.exp(Math.log(b) - Math.log(a)))

当 z达到极值时，double 的数值精度不足以满足 Math.exp(z) 的输出.这会导致我们丢失信息，产生不准确的结果，然后这些结果会级联多次计算。

当 z >= 710然后 Math.exp(z) = Infinity

当 z <= -746然后 Math.exp(z) = 0

在原始代码中，我用 y - x 调用 Math.exp并任意选择哪个是 x 以及哪个是原因。让我们选择 y和 x基于哪个更大，所以 z是消极的而不是积极的。我们溢出的点更偏向于负数(746 而不是 710)，更重要的是，当我们溢出时，我们最终到达 0 而不是无穷大。这就是我们想要的可能性很小。

double x = Math.max(a.logP, b.logP);
double y = Math.min(a.logP, b.logP);
double sum = x + Math.log(1 + Math.exp(y - x));