如何构造一个平滑的最大值函数
icon2 Brain Storm | icon4 2010-02-19 3:08| icon329 Comments | 本文内容遵从CC版权协议 转载请注明出自matrix67.com

    在处理最优化问题时，我们常常通过分析导函数来寻找极值点，因此往往希望目标函数是可导的；但在很多实际问题中，目标函数里经常带有取最大值函数，它的存在将破坏函数的可导性。一个有趣的问题由此产生：能否设计一个平滑的二元函数 f(x,y) ，它的效果近似于 max(x,y) ，足以用来代替最大值函数？在设计这样的函数时，下面这些条件需要尽可能满足：

   · 函数简洁而美观
   · 可以调整函数的“平滑度”
   · 可以很方便地扩展到多个变量


    我在这里发现了一个非常漂亮的构造： ln(exp(x) + exp(y)) 。由于 x 和 y 都在指数位置上，因此它们的差距将会放得很大。比方说， 3 和 8 这两个数虽然相隔不远，但 e^3≈20.0855 ， e^8≈2980.96 ，两个幂差了几个数量级。因此，把 e^3 加到 e^8 上，几乎不会改变 e^8 的大小。对 e^3+e^8 取对数的结果和直接对 e^8 取对数的结果相差不多。事实上， ln(exp(3) + exp(8))≈8.00672 ，非常逼近最大值函数的结果。

 
    这个函数有很多好处。首先，它看上去非常漂亮，并且很容易参与到其它运算中。其次，它可以非常方便地扩展到 n 个变量的情况，即 ln(exp(x_1) + exp(x_2) + ... + exp(x_n)) 。另外，这个函数的精确程度是可以控制的。显然，由于指数函数越到后面变化幅度越大，因此这个函数对尺度较大的变量来说会变得更加精确。如果把 3 和 8 变成 30 和 80 ，函数结果可以精确到小数点后 20 多位。因此，我们可以用一个系数 k 来调节变量的尺度，让 x 和 y 同时扩大 k 倍，最后结果再除以 k 。换句话说，把函数重新写成 ln(exp(k·x) + exp(k·y))/k ， k 越大整个函数将越逼近最大值函数， k 越小函数也就变得越平滑。

 
    有了这个函数后，很多本身不可导的函数立即有了可导的近似函数。例如，绝对值函数 abs(x) 其实可以写作 max(x,-x) ，因此可以用可导函数 ln(exp(x) + exp(-x)) 近似代替：

 
    对于复合函数的情形，用 ln(exp(g(x,y)) + exp(h(x,y))) 代替 max(g(x,y), h(x,y)) 同样能带来很好的效果：

Posted in Brain Storm
Tags: , , ,
Trackback: http://www.matrix67.com/blog/archives/2830/trackback
我猜您可能还喜欢：

29 条回复

  • 楼层: 沙发 | 2010-02-19 3:30 | NaDa_Nick 说：

    OMG... I love it!!

  • 楼层: 板凳 | 2010-02-19 8:44 | 小楠 说：

    不错，赞一个。开始没明白“平滑”的意思，后来明白了。

  • 楼层: 地毯 | 2010-02-19 9:02 | gnaggnoyil 说：

    善

  • 楼层: 地板 | 2010-02-19 9:39 | ppwwyyxx 说：

    写程序的话，用这个代替max函数处理整数变量会很好吗

  • 楼层: 地下室 | 2010-02-19 9:51 | NULL 说：

    终于有一篇能看懂的文章了
    觉得此思想极其王道，顶之，@地板，我觉得这个还是没有必要的吧

  • 楼层: 地基 | 2010-02-19 10:16 | wecing 说：

    好强大的构造，膜拜。

  • 楼层: 地壳 | 2010-02-19 11:39 | Aule 说：

    啊哈 新发现啊

  • 楼层: 地幔 | 2010-02-19 12:12 | onion 说：

    Orz
    看来我要试图拓展自己的订阅范围了，不能被E文吓到= =b

  • 楼层: 地核 | 2010-02-19 12:16 | maa04 说：

    abs(0)的值和ln(exp(0)+exp(0))的距离有点远……

  • 楼层: 10楼 | 2010-02-19 13:02 | CrazyWong 说：

    嗯，同上。
    其实只是个探索嘛……要是地板同学还是用if或者三目运算符吧

  • 楼层: 11楼 | 2010-02-19 14:50 | someone 说：

    膜拜牛淫。强势围观

  • 楼层: 12楼 | 2010-02-19 15:28 | junglerubik 说：

    这个牛逼

  • 楼层: 12a楼 | 2010-02-19 16:44 | se7en 说：

    这个就是Lie group对黎曼几何的表述吧

  • 楼层: 14楼 | 2010-02-19 19:46 | anythingjixu 说：

    好强！

  • 楼层: 15楼 | 2010-02-19 21:34 | 白左 说：

    哈？
    看懂了，但是这个有什么用呢……

  • 楼层: 16楼 | 2010-02-19 23:09 | jayhaizeizai 说：

    替M67牛回LS
    没啥用
    Blog本来就是要消遣一下嘛
    Geek的消遣

  • 楼层: 17楼 | 2010-02-20 3:33 | lpiszdf 说：

    第一段就是用处，楼上两个居然说没啥用……

  • 楼层: 18楼 | 2010-02-20 3:57 | lpiszdf 说：

    后续的文章
    http://www.johndcook.com/blog/2010/01/20/how-to-compute-the-soft-maximum/
    说到了如何避免当x太大（比如1000）或者太小（比如-1000）时，exp(x)会返回无穷大或者0的情况。有兴趣的可以去看看。

  • 楼层: 19楼 | 2010-02-20 9:24 | cat 说：

    地幔惊现onion
    说实话我米看懂

  • 楼层: 20楼 | 2010-02-20 13:20 | hplonline 说：

    这个近似太好了！！！唉他们是杂想到的喃，

  • 楼层: 21楼 | 2010-02-20 20:10 | 超子 说：

    talented！

  • 楼层: 22楼 | 2010-02-20 21:36 | cat 说：

    嗯，我看懂了。
    洗澡的时候灵光一现，再来看了一遍，果然懂了

  • 楼层: 23楼 | 2010-02-21 3:15 | chipper 说：

    不过当x,y非常接近的时候，误差似乎就比较大了。比如如果x=y=1那么误差就有ln2了。

  • 楼层: 24楼 | 2010-02-22 13:35 | ted 说：

    @chipper
    所以需要一个常数k.只要x!=y,即可用此法.

  • 楼层: 25楼 | 2010-02-26 15:44 | 风筝 说：

    这个做聚类分析应该可以用上吧，大家有没有用这个函数做过聚类？

  • 楼层: 26楼 | 2010-02-26 18:30 | qyjubriskxp 说：

    orz,虽然考试用不上，但确实太牛逼了

  • 楼层: 27楼 | 2010-03-02 17:59 | LS-GH 说：

    调整平滑度--类似脑筋急转弯感觉

  • 楼层: 28楼 | 2010-03-10 12:16 | Dreamz 说：

    这个实在是太帅了,多谢楼主分享美文^^

  • 楼层: 29楼 | 2010-03-11 9:22 | lll 说：

    Max-Log approxiamtion?

您也随便说几句吧：

您可以在 Gravatar 设置您的头像。