对数概率 Java 实现的数值精度
Numerical accuracy with log probability Java implementation
有时,当您使用常见数据类型(例如双精度数据)进行概率非常小的计算时,数值不准确会叠加多次计算并导致不正确的结果。因此,建议使用 log probabilities,以提高数值稳定性。我已经在 Java 中实现了对数概率并且我的实现有效,但是它比使用原始双打具有 更差 的数值稳定性。我的实施有什么问题?在 Java 中以小概率执行许多连续计算的准确有效方法是什么?
我无法提供这个问题的完整演示,因为许多计算都存在不准确之处。但是,这里证明存在问题:this submission to a CodeForces contest fails due to numerical accuracy. Running test #7 and adding debug prints clearly show that from day 1774, numerical errors begin cascading until the sum of probabilities drops to 0 (when it should be 1). After replacing my Prob class with a simple wrapper over doubles 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);
}
}
问题是由在这一行中使用 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));
有时,当您使用常见数据类型(例如双精度数据)进行概率非常小的计算时,数值不准确会叠加多次计算并导致不正确的结果。因此,建议使用 log probabilities,以提高数值稳定性。我已经在 Java 中实现了对数概率并且我的实现有效,但是它比使用原始双打具有 更差 的数值稳定性。我的实施有什么问题?在 Java 中以小概率执行许多连续计算的准确有效方法是什么?
我无法提供这个问题的完整演示,因为许多计算都存在不准确之处。但是,这里证明存在问题:this submission to a CodeForces contest fails due to numerical accuracy. Running test #7 and adding debug prints clearly show that from day 1774, numerical errors begin cascading until the sum of probabilities drops to 0 (when it should be 1). After replacing my Prob class with a simple wrapper over doubles 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);
}
}
问题是由在这一行中使用 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));