##### Differences

This shows you the differences between two versions of the page.

 — nlp:log-domain-computations [2015/04/23 21:40] (current)ryancha created 2015/04/23 21:40 ryancha created 2015/04/23 21:40 ryancha created Line 1: Line 1: + When working with very small probabilities,​ it is easy to encounter problems with underflow in the floating point representation. ​ To avoid this problem, it is customary to work in the Logarithmic Domain (or "log space"​). ​ Logarithms scale the quantities in question into a workable range where machine precision issues are not as detrimental. ​ The base of the logarithm, once fixed, can be ignored. + == Multiplication,​ Exponents, and Division == + + Working in the log domain requires that we recall a couple of identities from algebra: + + * $log(a \cdot b) = log(a) + log(b)$ + * $log(a^b) = b \cdot log(a)$ + + Consequently,​ + * $log(1/a) = log(a^{-1}) = - log(a)$ + + Hence, + * $log(a / b) = log(a) - log(b)$ + + Multiplicative identity: + * $log 1 = 0$ + + Additive identity: + + * $log 0 = -Infinity$ + + In other words, we can replace multiplication,​ exponentiation,​ and division by simple operations in the log domain. + + == Addition and Subtraction == + + A more subtle technique is required to replace addition (and subtraction). ​ In other words, if we wish to replace $log(a + b)$ by some operation involving $log(a)$ and $log(b)$, we require the logAdd() method (available in the Stanford and Berkeley NLP libraries, specifically in the SloppyMath package by Dan Klein). + + Here follows a discussion of the logAdd() method: + + First off, logAdd() takes two arguments of type double in log space, logX and logY. + + It returns a double value which closely approximates log(X + Y).  Consequently,​ the inputs and output are in log space, and we need not convert in and out of log space to complete this operation. + + Steps 1-4 are commented in the code.  We will prove why step 4 is correct after the code. + + public static double logAdd(double logX, double logY) { + // 1. make X the max + if (logY > logX) { + double temp = logX; + logX = logY; + logY = temp; + } + // 2. now X is bigger + if (logX == Double.NEGATIVE_INFINITY) { + return logX; + } + // 3. how far "​down"​ (think decibels) is logY from logX? + //    if it's really small (20 orders of magnitude smaller), then ignore + double negDiff = logY - logX; + if (negDiff < -20) { + return logX; + } + // 4. otherwise use some nice algebra to stay in the log domain + //    (except for negDiff) + return logX + java.lang.Math.log(1.0 + java.lang.Math.exp(negDiff));​ + } + + === Here's the proof of correctness for step 4 === + + $logX + log(1.0 + e^{logY-logX})$ + + $= log(X \cdot (1.0 + e^{logY-logX}))$ + + $= log(X + X \cdot e^{logY/​X})$ + + $= log(X + X \cdot Y / X)$ + + $= log(X + Y)$ + + Couldn'​t be nicer.