logsumexp

最終更新: 2017-04-16 22:25

logsumexp

確率を扱うDPなどでdoubleで表せないくらい小さい数を扱うときなどに、アンダーフロー・オーバーフローを防ぐための数値計算テクニック。

アンダーフロー・オーバーフローを防ぐためには、出てくる数の対数を取って値を保存することが有効である。このとき、乗算と除算は対数を取った値に対して加算・減算をすればよい。つまり、a=b×ca = b \times cのとき、

loga=logb+logc\log a = \log b + \log c

一方、対数で持っている値に対して加減算を行うには一度対数を元の数に戻してから計算を行う必要がある。何も工夫しないと指数を取ったときに値が表現出来る範囲を溢れる可能性がある。

logsumexpと呼ばれるテクニックでは、m=max(logb,logc)m = \max(\log b, \log c)としてa=b+ca = b+cのとき

loga=m+log(exp(logbm)+exp(logcm))\log a = m + \log(\exp(\log b - m) + \exp(\log c - m))

という関係が成り立つことに注目して加算を行う。こうすることで、指数を取る対象の値が小さくなり値が表せなくなる可能性が下がる。