放牧代码和思想
专注自然语言处理、机器学习算法
    恕不接待索要源码语料者、索求技术方案者、以及不Google的懒人。

计算指数函数的和的对数

目录

译自哈佛大学《Computing Log-Sum-Exp》。在许多ML库中,经常看到这类函数,如scipy中的misc.logsumexp、CRF++中的CRFPP::logsumexp,其意义何在?

maxresdefault.jpg

这篇文章旨在讲解这个必学,却没有任何ML课程会特意教的技巧。假设我们有N个实数quicklatex.png,我们想求下式:

quicklatex (1).png

这是非常常见的需求,比如你想用softmax去计算一个多项式分布(多分类逻辑回归)。你要计算对数似然的话,你就得计算上式这种规范化因子。如果quicklatex (2).png很大或很小,朴素的直接计算会上溢出或下溢出,从而导致严重问题。举个例子,对于quicklatex (3).png,直接计算是可行的,我们可以得到1.55。但对于quicklatex (4).png,却并不可行,我们会得到quicklatex (6).png;对于quicklatex (7).png,还是不行,我们会得到quicklatex (9).png。这是怎么回事?很简单,你的浮点数只有64位,在计算指数函数的环节,quicklatex (10).png,会发生上溢出;quicklatex (11).png,会发生下溢出。即便在数学世界上式的值显然不是无穷大,但在计算机的浮点数世界里就是求不出来。怎么办呢?

解决方案很简单:

quicklatex (13).png

对任意a都成立,这意味着我们可以自由地调节指数函数的指数部分,一个典型的做法是取quicklatex.png中的最大值:

quicklatex (14).png

这可以保证指数最大不会超过0,于是你就不会上溢出。即便剩余的部分下溢出了,你也能得到一个合理的值。

证明

屏幕快照 2016-08-13 下午9.23.38.png

实现

CRF++中的实现如下:

#define MINUS_LOG_EPSILON  50
// log(exp(x) + exp(y));
//    this can be used recursivly
// e.g., log(exp(log(exp(x) + exp(y))) + exp(z)) =
// log(exp (x) + exp(y) + exp(z))
inline double logsumexp(double x, double y, bool flg)
{
    if (flg)
        return y;  // init mode
    const double vmin = std::min(x, y);
    const double vmax = std::max(x, y);
    if (vmax > vmin + MINUS_LOG_EPSILON)
    {
        return vmax;
    }
    else
    {
        return vmax + std::log(std::exp(vmin - vmax) + 1.0);
    }
}

Reference

https://hips.seas.harvard.edu/blog/2013/01/09/computing-log-sum-exp/

http://www.xarg.org/2016/06/the-log-sum-exp-trick-in-machine-learning/

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » 计算指数函数的和的对数

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机