No subtraction in log semiring

[jyuhuan]

In line 48 of ExpectedRecall.java, a subtraction is performed. If the algebra in use is LogSemiring, there will almost always be an illegal state exception thrown, saying that

x must be >= y

The problem originates from line 63 of LogSemiring.java. The minus method of LogSemiring calls FastMath.logSubtract(x,y), which requires x >= y.

In ExpectedRecall.java, x (i.e., the variable expectedRecall) is initialized to be the zero of the algebra, and y is a belief. The exception will be thrown almost every time due y is usually greater than the zero.

Mathematically speaking, subtraction does not exist in a semiring. Is it intended that only algebras like a real ring should be used to perform ERMA training?

[mgormley]

As your comment noted, it doesn't actually make sense for a semiring to have a subtract method. Further, the LogSemiring can only represent non-negative numbers. That's why the class is called LogSemiring and not LogAlgebra. However, there are certain situations (e.g. the ProjDepTreeFactor) where we can guarantee that the subtraction won't go negative and it's valid to use this semiring.

The ExpectedRecall objective is not one of those cases: we must use an algebra that can represent both positive and negative values. LogSignAlgebra addresses exactly this issue. See Li & Eisner (2009) for a description of this semiring. This is the same semiring that was used in Gormley et al. (2015). The short summary is that it uses a single bit to represent the sign of the number and the remaining bits to represent the log of the absolute value of that number.