寻求一个光滑的最大值函数
By 苏剑林 | 2015-05-02 | 120946位读者 |在最优化问题中,求一个函数的最大值或最小值,最直接的方法是求导,然后比较各阶极值的大小。然而,我们所要优化的函数往往不一定可导,比如函数中含有最大值函数$\max(x,y)$的。这时候就得求助于其他思路了。有一个很巧妙的思路是,将这些不可导函数用一个可导的函数来近似它,从而我们用求极值的方法来求出它近似的最优值。本文的任务,就是探究一个简单而有用的函数,它能够作为最大值函数的近似,并且具有多阶导数。下面是笔者给出的一个推导过程。
在数学分析中,笔者已经学习过一个关于最大值函数的公式,即当$x \geq 0, y \geq 0$时,我们有
$$\max(x,y)=\frac{1}{2}\left(|x+y|+|x-y|\right)\tag{1}$$
那么,为了寻求一个最大值的函数,我们首先可以考虑寻找一个能够近似表示绝对值$|x|$的函数,这样我们就把问题从二维降低到一维了。那么,哪个函数可以使用呢?
直接观察挺难发现哪个函数可以使用的,我们将问题逐步向简单推进。我们对$f(x)=|x|$求导,除了$x=0$这一点外,其他都可以顺利求导
$$f'(x) = \left\{\begin{aligned}1,&\,x > 0\\
-1,&\, x < 0\end{aligned}\right.\tag{2}$$
这是一个简单的分段函数,在物理中,这类函数十分常见,跟它最接近的,应该是单位阶跃函数$\theta(x)$:
$$\theta(x) = \left\{\begin{aligned}1,&\,x > 0\\
0,&\, x < 0\end{aligned}\right.\tag{3}$$
那么
$$f'(x)=2\theta(x)-1\tag{4}$$
下面只需要寻求$\theta(x)$的近似函数,物理学家已经提供现成的函数给我们了,一个比较简单的形式是[来源:维基百科]
$$\theta(x)=\lim_{k\to +\infty} \frac{1}{1+e^{-k x}}\tag{5}$$
那么我们就可以取$\frac{1}{1+e^{-k x}}$作为近似函数了,代入$(4)$式得到$\frac{2e^{k x}}{1+e^{k x}}-1$,积分得到
$$\begin{aligned}f(x)&=\frac{2}{k}\ln(1+e^{kx})-x\\
&=\frac{1}{k}\left[\ln(1+e^{kx})+\ln(1+e^{-kx})\right]\\
&=\frac{1}{k}\ln(2+e^{kx}+e^{-kx})\end{aligned}\tag{6}$$
不难发现,$(6)$式中的对数部分,在$k$足够大的时候,常数$2$的影响微乎其微,把它去掉之后,我们有一个比较简单的绝对值函数:
$$|x|=\lim_{k\to +\infty} \frac{1}{k}\ln(e^{kx}+e^{-kx})\tag{7}$$
结合$(7)$式和$(1)$式,我们就得到
$$\max(x,y)=\lim_{k\to +\infty} \frac{1}{2k}\left\{\ln[e^{k(x+y)}+e^{-k(x+y)}]+\ln[e^{k(x-y)}+e^{-k(x-y)}]\right\}\tag{8}$$
$(8)$式还可以再化简,我们得到
$$\max(x,y)=\lim_{k\to +\infty} \frac{1}{2k}\ln(e^{2kx}+e^{-2kx}+e^{2ky}+e^{-2ky})\tag{9}$$
并且由于$(1)$式是在$x\geq 0,y\geq 0$时成立的,所以$(9)$式中的$e^{-2kx}$和$e^{-2ky}$均变得不重要了,我们也把它们去掉,进一步得到
$$\max(x,y)=\lim_{k\to +\infty} \frac{1}{2k}\ln(e^{2kx}+e^{2ky})\tag{10}$$
或者写成
$$\max(x,y)=\lim_{k\to +\infty} \frac{1}{k}\ln(e^{kx}+e^{ky})\tag{11}$$
$(11)$式正是我们希望得到的理想的最大值函数。虽然我们的推导基于$x\geq 0,y\geq 0$,但是不难发现,对于$x,y$中出现负数时,上述公式仍然成立!它甚至还可以推广到多个变量的最大值函数:
$$\max(x,y,z,\dots)=\lim_{k\to +\infty} \frac{1}{k}\ln(e^{kx}+e^{ky}+e^{kz}+\dots)\tag{12}$$
关于$(11)$式更多的展示,请阅读Matrix67的《如何构造一个平滑的最大值函数》:
http://www.matrix67.com/blog/archives/2830
观察$(11)$式的结构可以看出,这实际上是做了这样的一个事情:找一个在整个实数域上都单调递增的函数,而且增长速度要快于线性增长,然后求和,最后取逆函数。因此,不难构造出类似的函数:我们选$y=x^{2k+1}$,那么得到
$$\max(x,y)=\lim_{k\to+\infty} \sqrt[2k+1]{x^{2k+1}+y^{2k+1}}\tag{13}$$
当然,$(13)$的精度(或者说收敛速度)远没有$(11)$那么好,要提高精度也不难,比如
$$\max(x,y)=\lim_{k\to +\infty} \frac{1}{k}\ln\ln\left(e^{e^{kx}}+e^{e^{ky}}\right)\tag{14}$$
综合精度和简洁两方面考虑,估计最优的选择就是$(11)$了。
转载到请包括本文地址:https://www.spaces.ac.cn/archives/3290
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (May. 02, 2015). 《寻求一个光滑的最大值函数 》[Blog post]. Retrieved from https://www.spaces.ac.cn/archives/3290
@online{kexuefm-3290,
title={寻求一个光滑的最大值函数},
author={苏剑林},
year={2015},
month={May},
url={\url{https://www.spaces.ac.cn/archives/3290}},
}
September 25th, 2020
x,y都小于0等式就不成立了
依然成立
如果x+y小于0的话,可以把(1)式中的|x+y|换成-|x+y|,最后到第(8)式时会出现两个ln相减,化简后的分母是e^(2kx+2ky)+1,趋近于1,即可得到最后的结果
补充下,当x和y没有限制时,max(x,y)=1/2(x+y+|x-y|)
最近刷到一篇对激活函数光滑近似的文章就用到这个思路:
SMU: smooth activation function for deep networks using smoothing maximum technique
https://arxiv.org/abs/2111.04682
嗯嗯,这种挺没意思的,前不久我才介绍了一篇:https://kexue.fm/archives/8718
嗯,是的,其实楼主直接用\[\max(x, y) = \frac{1}{2} \left( |x - y| + x + y \right) \tag{1}\]证明会更好
嗯嗯,其实这篇文章有些年代的局限性,当时我刚好学到了文章中的公式,就直接从文章中的公式出发了,现在看来自然有很多地方可以简化一下。
但是不难发现,对于x,y中出现负数时,上述公式仍然成立!
当X,Y 只有一个负数的时候很容易证明成立。 当X,Y 都小于零的时候
\max(x,y)=\frac{1}{2}\left(|x-y|+x+y\right)\tag{1}
用然后带入|x|=\lim_{k\to +\infty} \frac{1}{k}\ln(e^{kx}+e^{-kx})\tag{7}就可以得到:
\max(x,y)=\lim_{k\to +\infty} \frac{1}{2k}\ln(e^{2kx}+e^{2ky})\tag{10}这个结论了。
自己推导了一下。作者的一个很容易证明,有时候我要理解很久。
但是不难发现,对于 \(x, y\) 中出现负数时,上述公式仍然成立!当 \(x < 0, y < 0\) 时,有:
\[\max(x, y) = \frac{1}{2} \left( |x - y| + x + y \right) \tag{1}\]
然后带入 \(|x| = \lim_{{k \to +\infty}} \frac{1}{k} \ln(e^{kx} + e^{-kx}) \tag{7}\) 就可以得到:
\[\max(x, y) = \lim_{{k \to +\infty}} \frac{1}{2k} \ln(e^{2kx} + e^{2ky}) \tag{10}\]
这个结论由作者证明,尽管有时我需要花些时间理解。这些公式可以通过 LaTeX 语法嵌入到你的文档中,用于显示数学公式和推导过程。
February 7th, 2021
您好,请问“(13)的精度(或者说收敛速度)远没有(11)那么好”中的精度和收敛速度具体是什么意思?我不太理解。
对于同一个$k$,几乎都有
$$\left|\max(x,y)-\frac{1}{k}\ln(e^{kx}+e^{ky})\right| < \left|\max(x,y)-\sqrt[2k+1]{x^{2k+1}+y^{2k+1}}\right|$$
May 22nd, 2021
您好,公式(5)分母中e的指数不是应该是是-2kx吗?
有什么区别呢?反正都是要$k\to\infty$。
August 4th, 2023
请问(8)到(9)的化简是如何推的?
$\ln a + \ln b = \ln (ab)$,然后展开$ab$。
October 24th, 2023
留一个有意思的发现,选择tanh作为逼近f(x)=|x|导数时可以发现得到的就是式7
嗯嗯。但写这篇文章的时候,其实我还不大熟悉tanh~
June 16th, 2024
苏神,为什么“找一个在整个实数域上都单调递增的函数,而且增长速度要快于线性增长,然后求和,最后取逆函数”,其极限还是max(x)啊?要怎么证明$\lim_{\tau \rightarrow 0^{+}} \tau F^{-1} (\sum_{j=1}^n e^{F(x_j)/\tau}) =\max(\mathbf x)$啊?
我要表达的意思是
$$f^{-1}(\sum_i f(x_i))\approx \max_i x_i$$
这是因为当$f(x)$的增长速度远快于线性时,$\sum_i f(x_i)\approx f(\max_i x_i)$,即以最大那一项为主,所以
$$f^{-1}(\sum_i f(x_i))\approx f^{-1}(f(\max_i x_i)) = \max_i x_i$$
June 20th, 2024
请问一下,从公式(11)到公式(12),这步扩展怎么理解or证明呢?
可以用两面夹直接证明。。。[手动狗头]
假设$x_1 > x_2 > \cdots > x_n$,那么
$$\frac{1}{k}\ln\sum_i e^{k x_i} = \frac{1}{k}\ln e^{k x_1}\sum_i e^{k (x_i-x_1)} = x_1 +\frac{1}{k}\sum_i e^{k (x_i-x_1)}$$
其中
$$\sum_i e^{k (x_i-x_1)} = 1 + e^{k(x_2-x_1)} + e^{k(x_3-x_1)} + \cdots $$
后面的指数都是负数,当$k\to\infty$时它们$\to 0$,所以$\sum_i e^{k (x_i-x_1)}\to 1$,取对数后是0,所以最后等于最大值$x_1$。
厉害!!!