log-sum-exp trick

매우 작은 양수(0과 가까운 수)나 매우 큰 수를 나타내는 한 가지 방법은 log를 활용하는 것이다. 이 때 두 수의 곱셈은 자명하다.

Very small or large numbers can be easily stored in computers by taking logs. And mutiplying two numbers expressed in log-scale is straight-forward.

하지만 덧셈은 약간의 trick(소위 말해 log-sum-exp trick)이 필요하다.

But the addition of two extreme numbers need some trick(so called, log-sum-exp trick).

두 큰 수 exp(800)과 exp(900)을 더하고자 한다. 문제는 log에서 덧셈은 곱셈처럼 간단하지 않다는 것이다. 따라서 exp(800)+exp(900)을 하자.

Let's say we want to add exp(800) to exp(900). The problem is adding is not so simple as multiplication on log scale. So the simple way is to add exp(800) and exp(900).

하지만 두 수가 컴퓨터에서 정확하게 나타낼 수 없으므로(OVERFLOW!), 정확하게 나타낼 수 있는 수준으로 작게 만든다.

But exp(800) is just Inf in R, at least in my computer. So we need to make it smaller.

예를 들어 나누기 exp(800)을 해주는 것이다. 그렇게 하면 두 수 exp(800)과 exp(900)은 exp(0)과 exp(100)이 되고 이 두 수는 컴퓨터가 손쉽게 더할 수 있다.

How about dividing it by exp(800)? exp(800)/exp(800)=1, exp(900)/exp(800)=exp(100). And exp(0)+exp(100) is easily computed and stored.

이제 더한 수를 exp(800)를 곱해주면 원래 수가 된다.

And for the final step, we multiply exp(0)+exp(100) by exp(800) and Volia... Inf!

그런데 수가 너무 커서 log로 나타내기로 하지 않았는가? 따라서 더한 두 수를 log를 취하고, log(exp(800)), 즉 800을 더해주면 된다.

Remember! We used log-scale because numbers are too large or small... so we log exp(0)+exp(100) and add 800... and the result is on log-scale.

0과 가까운, 매우 작은 수도 마찬가지 방법을 쓰면 된다. 

If the numbers are small and close to 0, we need to make it larger so that computers can easily store and add them. Simple enough.

같은 이유는 아니지만, log는 위대한 수학 발견의 하나로 손꼽힌다.

I doubt it's the same reason but LOG is selected as one of the greatest discovery of mathematics... by whom? try googling. :)

a=-745; b=-746;

c=max(a,b)

log(exp(a)+exp(b)) # -744.4401

log(exp(a-c)+exp(b-c))+c  # -744.6867

# -744.6867 cf) result from Mathematica : -744.686738312...

a=-801; b=-800;

c=max(a,b)

log(exp(a)+exp(b)) # -Inf

log(exp(a-c)+exp(b-c))+c # -799.6867

3줄 요약

1. log를 사용해서 저장하자

2. 곱셈은 단순히 덧셈으로

3. 덧셈은 log-sum-exp으로, 하지만 exp x가 너무 커지니까 exp(x-c)를 하고 나중에 다시 더해준다.

Summary

1. use log

2. multiplication is just addition in log-scale

3. addition needs log-sum-exp but if exp x gets to large or small for computers to handle use exp(x-c) and add c in the end.