Numerical problems for sums and products of small probabilities

The problem

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.

Mindmap

Videos

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

Log-Sum-Exp-Trick

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) · []
Recent changes RSS feed Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki