View source

From NLPWiki

You do not have permission to do that, for the following reason:

The action you have requested is limited to users in the group user.

You can view and copy the source of this page:

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:

* <math>log(a \cdot b) = log(a) + log(b)</math>
* <math>log(a^b) = b \cdot log(a)</math>

Consequently,
* <math>log(1/a) = log(a^{-1}) = - log(a)</math>

Hence,
* <math>log(a / b) = log(a) - log(b)</math>

Multiplicative identity:
* log 1 = 0

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 <math>log(a + b)</math> by some operation involving <math>log(a)</math> and <math>log(b)</math>, 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 ===

<math>logX + log(1.0 + e^{logY-logX})</math>

<math>= log(X \cdot (1.0 + e^{logY-logX}))</math>

<math>= log(X + X \cdot e^{logY/X})</math>

<math>= log(X + X \cdot Y / X)</math>

<math>= log(X + Y)</math>

Couldn't be nicer.

=== Additive identity ===

log 0 = -Infinity

Return to Log Domain Computations.

Retrieved from "http://nlp.cs.byu.edu/mediawiki/index.php/Log_Domain_Computations"

View source

From NLPWiki

Views

Personal tools

Navigation

Search

Toolbox