This module presents a type for storing numbers in the log-domain. The main reason for doing this is to prevent underflow when multiplying many small probabilities as is done in Hidden Markov Models and other statistical models often used for natural language processing. The log-domain also helps prevent overflow when multiplying many large numbers. In rare cases it can speed up numerical computation (since addition is faster than multiplication, though logarithms are exceptionally slow), but the primary goal is to improve accuracy of results. A secondary goal has been to maximize efficiency since these computations are frequently done within a O(n^3) loop.
- log :: (Floating a, Transfinite a) => a -> a
- toFractional :: (Real a, Fractional b) => a -> b
- data LogFloat
- logFloat :: Real a => a -> LogFloat
- logToLogFloat :: Real a => a -> LogFloat
- fromLogFloat :: (Fractional a, Transfinite a) => LogFloat -> a
- logFromLogFloat :: (Fractional a, Transfinite a) => LogFloat -> a
- module Data.Number.Transfinite
Since the normal
log throws an error on zero, we
have to redefine it in order for things to work right. Arguing
from limits we can see that
log 0 == negativeInfinity. Newer
versions of GHC have this behavior already, but older versions
and Hugs do not.
This function will raise an error when taking the log of negative
numbers, rather than returning
notANumber as the newer GHC
implementation does. The reason being that typically this is a
logical error, and
notANumber allows the error to propegate
In order to improve portability, the
Transfinite class is
required to indicate that the
Floating type does in fact have
a representation for negative infinity. Both native floating
Float) are supported. If you define your
own instance of
Transfinite, verify the above equation holds
negativeInfinity. If it doesn't, then you
should avoid importing our
log and will probably want converters
to handle the discrepancy when dealing with
LogFloat data type and conversion functions
LogFloat is just a
Double with a special interpretation.
logFloat function is presented instead of the constructor,
in order to ensure semantic conversion. At present the
instance will convert back to the normal-domain, and so will
underflow at that point. This behavior may change in the future.
Performing operations in the log-domain is cheap, prevents
underflow, and is otherwise very nice for dealing with miniscule
probabilities. However, crossing into and out of the log-domain
is expensive and should be avoided as much as possible. In
particular, if you're doing a series of multiplications as in
lp * logFloat q * logFloat r it's faster to do
lp * logFloat
(q * r) if you're reasonably sure the normal-domain multiplication
won't underflow, because that way you enter the log-domain only
once, instead of twice.
Even more particularly, you should avoid addition whenever
possible. Addition is provided because it's necessary at times
and the proper implementation is not immediately transparent.
However, between two
LogFloats addition requires crossing the
exp/log boundary twice; with a
LogFloat and a regular number
it's three times since the regular number needs to enter the
log-domain first. This makes addition incredibly slow. Again,
if you can parenthesize to do plain operations first, do it!
A constructor which does semantic conversion from normal-domain to log-domain.
Constructor which assumes the argument is already in the log-domain.
Return our log-domain value back into normal-domain. Beware of overflow/underflow.
Return the log-domain value itself without costly conversion
Exceptional numeric values