Computing the

- product of small probabilities OR
- the sum of product of small probabilities

can result in 0, since we reach the numerical limitations of representation of very small numbers in our computer.

Moving to the log-domain and the log-sum-exp-trick help us to avoid or reduce these numerical problems.

This video describes the log-sum-exp trick for computing sums of products of probabilities (especially in the context of Hidden Markov Models)

Here the log-sum-exp-trick is described

% Computes the log sum exponential for some vector of values. It is used % to avoid numerical underflow when calculcating the log of a sum of small % numbers like probabilities. % % In a mixture model the probability of an event x is % P(x) = pi1*P1(x) + pi2*P2(x)... % The problem is usually that P1, P2,... are small at x which makes % underflow happen. To fix underflow one usually operates in the log % domain i.e. log(P(x)) = log(pi1*P1(x) + pi2*P2(x)...) % The problem with this is that the log cannot decompose sums and we % still get underflow. To fix this(somewhat) we can write: % log(P(x)) = log( exp(log(pi1) + log(P1(x)) ) + % log( exp(log(pi2) + log(P2(x)) ) + ...). Now by finding the max value % of pi1*P1(x),pi2*P2(x),... and deducting it we can remove most of the % value in the equation and get it out. It is simple if one looks at the % following calculations % % log(p) = log(p1 + p2) = log(exp(log(p1))+exp(log(p2))) % pMax = max([log(p1),log(p2)]) % log(p) = log( exp(pMax) * ( exp(log(p1)-pMax)+exp(log(p2-pMax)) ) % log(p) = pMax + log( exp(log(p1)-pMax) + exp(log(p2)-pMax) ) % % Now if we for example assume log(p1)>log(p2) then % log(p) = pMax + log( exp(0) + exp(log(p2)-pMax) ) = % pMax + log( 1 + exp(log(p2)-pMax) ) % % This means that we gotten out most of the probability mass from the % sum and we have avoided summing several small numbers. Hopefully % the exp(log(p2)-pMax) will be nice as well.

public/numerical_problems_for_sums_and_products_of_small_probabilities.txt · Last modified: 2014/01/01 15:25 (external edit) · []