Browse Prior Art Database

Method to Approximate the Logarithm of a Sum

IP.com Disclosure Number: IPCOM000036595D
Original Publication Date: 1989-Oct-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 3 page(s) / 26K

Publishing Venue

IBM

Related People

Merialdo, B: AUTHOR

Abstract

Disclosed is a method to compute an approximation of the logarithm of a sum.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 57% of the total text.

Page 1 of 3

Method to Approximate the Logarithm of a Sum

Disclosed is a method to compute an approximation of the logarithm of a sum.

A number of practical problems can be turned into the search for an optimal path inside a graph. This is very often the case in Artificial Intelligence and Speech Recognition.

When the "value" of a path is defined by a probabilistic model, the basic operations for path manipulation are: extend a path: multiply its probability by the probability of the extension p' = p x q. merge two paths: add the two probabilities p' = p1+ p2 .

Because multiplication is computationally more expensive than addition, it is interesting to consider the log-probability Log p instead of p itself.

In this case: Log (p x q) = Log p + Log q is very easy to compute, but the problem is then to compute (or approximate) the value of Log (p1+ p2) from the value of Log p1 and Log p2 .

In practice, for performance reasons also, integer arithmetic is generally used instead of floating-point arithmetic.

Let us assume that Log a and Log b are known, and that we want to approximate Log (a+b). We can suppose that a & b without loss of generality. We study the function x ---> Log (a+x) for x C"-[a, +B].

When x increases to +B, Log (a+x) is asymptotically equivalent to Log x. So, for x "large enough", we will approximate Log (a+x) by Log x; mathematically, we will choose a value g and define: if x / ga Log (a+x) is approximated by Log x = Y(x) Now we have to approximate when x C"-a...