Numerically Stable Implementation

Question

I need to compute a normalized exponential of a vector in Matlab.

Simply writing

res = exp(V)/sum(exp(V))

overflows in an element of V is greater than log(realmax) = 709.7827. (I am not sure about underflow conditions.)

How should I implement it to avoid numerical instability?

Update: I received excellent responses about how to avoid overflow. However, I am still happy to hear your thoughts about the possibility of underflow in the code.

Tijuana

Answer 1

The following approach avoids the overflow by subtracting the exponents and then taking the exponential, instead of dividing the exponentials:

res = 1./sum(exp(bsxfun(@minus, V(:), V(:).')))

As a general rule, overflow can be avoided by working in the log domain for as long as possible, and taking the exponential only at the end.

Vaenfila

Thanks. I am new to bsxfun. What if V is a matrix, and we want this to apply along dimension dim? – Tijuana

@Tijuana How would that be? exp(V) would then be a matrix and sum(exp(V),dim) would be a vector. How do you define exp(V)/sum(exp(V,dim)) in that case? – Vaenfila

I mean if the variable called dim is 1, I want your previous code to be applied to each column. If dim is 2, the code is applied row-wise. – Tijuana

@Tijuana That would be harder. And it changes the question completely. The simple answer would be: loop over each row or column. – Vaenfila

@Tijuana Welcome! Feel free to ask that new requirement as a new question, if the loop solution is not good enough – Vaenfila

Nice solution, should have a better precision than my solution. – Gretna

Answer 2

The answer is pretty similar to your previous question. Use Math!

exp(V)=exp(V-max(V))*exp(max(V))
sum(exp(V))=sum(exp(V-max(V))*exp(max(V)))=exp(max(V)*sum(exp(V-max(V))))

Putting both together:

res=exp(V-max(V))*exp(max(V))/exp(max(V)*sum(exp(V-max(V)))=exp(V-max(V))/sum(exp(V-max(V)))

A code which is robust to the input range:

res=exp(V-max(V))/sum(exp(V-max(V)))

Gretna

Nice idea! Subtract the maximum – Vaenfila