当今世界,深度学习应用已经渗透到了我们生活的方方面面,深度学习技术背后的核心问题是最优化(Optimization)。最优化是应用数学的一个分支,它是研究在给定约束之下如何寻求某些因素(的量),以使某一(或某些)指标达到最优的一些学科的总称。
![梯度下降法 梯度下降法](http://zhuanlan.51cto.com/art/201903/https:/s2.51cto.com/oss/201903/27/2a677e88dc456a8a469e1b207da9428b.jpg-wh_651x-s_360702242.jpg)
梯度下降法(Gradient descent,又称最速下降法/Steepest descent),是无约束最优化领域中历史最悠久、最简单的算法,单独就这种算法来看,属于早就“过时”了的一种算法。但是,它的理念是其他某些算法的组成部分,或者说在其他某些算法中,也有梯度下降法的“影子”。例如,各种深度学习库都会使用SGD(Stochastic Gradient Descent,随机梯度下降)或变种作为其优化算法。
今天我们就再来回顾一下梯度下降法的基础知识。
1. 名字释义
在很多机器学习算法中,我们通常会通过多轮的迭代计算,最小化一个损失函数(loss function)的值,这个损失函数,对应到最优化里就是所谓的“目标函数”。
在寻找最优解的过程中,梯度下降法只使用目标函数的一阶导数信息——从“梯度”这个名字也可见一斑。并且它的本意是取目标函数值“最快下降”的方向作为搜索方向,这也是“最速下降”这个名字的来源。
于是自然而然地,我们就想知道一个问题的答案:沿什么方向,目标函数 f(x) 的值下降最快呢?
2. 函数值下降最快的方向是什么
先说结论:沿负梯度方向
![沿负梯度方向 沿负梯度方向](http://zhuanlan.51cto.com/art/201903/https:/s1.51cto.com/oss/201903/27/039ba59c727d16f62d1fa194e3610e0e.jpg)
函数值下降最快。此处,我们用 d 表示方向(direction),用 g 表示梯度(gradient)。
下面就来推导一下。
将目标函数 f(x) 在点
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s1.51cto.com/oss/201903/27/57dffe94dbfa547ec9647ae3b3a1c6f5.jpg)
处泰勒展开(在最优化领域,这是一个常用的手段):
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s3.51cto.com/oss/201903/27/6c6897ef78b2c9278d0055d5af457f31.jpg)
高阶无穷小 o(α)可忽略,由于我们定义了步长α>0(在ML领域,步长就是平常所说的learning rate),
因此,当
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s1.51cto.com/oss/201903/27/6c28e586cb5a57a274de552f0a3dfd8b.jpg)
时
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s3.51cto.com/oss/201903/27/755df8a7bbc5ccbd8159bdc7bfb29cd4.jpg)
即函数值是下降的。
此时
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s4.51cto.com/oss/201903/27/dde1d3d304eeed55acc0fb71da68804d.jpg)
就是一个下降方向。
但是
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s1.51cto.com/oss/201903/27/8f0c1ef1c5c289a0be888db680a02bdb.jpg)
具体等于什么的时候,可使目标函数值下降最快呢?
数学上,有一个非常著名的不等式:Cauchy-Schwartz不等式(柯西-许瓦兹不等式)①,它是一个在很多场合都用得上的不等式:
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s4.51cto.com/oss/201903/27/ef254a5d67f7a4c58ebb684c7bd3b3f6.jpg)
当且仅当:
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s2.51cto.com/oss/201903/27/96e46f47dff3bb2fd49bdbe079e9f485.jpg)
时等号成立。
由Cauchy-Schwartz不等式可知:
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s1.51cto.com/oss/201903/27/004686541b102f62ea7255b6b921cd9e.jpg)
当且仅当
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s1.51cto.com/oss/201903/27/19e0f48ee536c97a52ecf98cba95954f.jpg)
时,等号成立,
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s3.51cto.com/oss/201903/27/5b15b505f2c5112a3c9bda3fa9ec5121.jpg)
最大(>0)。
所以,
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s2.51cto.com/oss/201903/27/acadae955b0b8fd8eb72fffc312137f3.jpg)
时
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s4.51cto.com/oss/201903/27/827f2804746828db7bdf4a1184ad2f81.jpg)
最小(<0),f(x) 下降量最大。
#p#分页标题#e#
所以,
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s1.51cto.com/oss/201903/27/d5d2ca367a091333b72aa1ead9733e3c.jpg)
是最快速下降方向。
3. 缺点
它真的如它的名字所描述的,是“最快速”的吗?从很多经典的最优化书籍你会了解到:并不是。
事实上,它只在局部范围内具有“最速”性质;对整体求最优解的过程而言,它让目标函数值下降非常缓慢。
4. 感受一下它是如何“慢”的
先来看一幅图②
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s4.51cto.com/oss/201903/27/807f8490db90036195f6fffb9272d2c5.jpg)
这幅图表示的是对一个目标函数寻找最优解的过程,图中锯齿状的路线就是寻优路线在二维平面上的投影。从这幅图我们可以看到,锯齿一开始比较大(跨越的距离比较大),后来越来越小;这就像一个人走路迈的步子,一开始大,后来步子越迈越小。
这个函数的表达式是这样的:
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s2.51cto.com/oss/201903/27/22f3b5d33a3b45e596191d7048dc2aba.jpg)
它叫做Rosenbrock function(罗森布罗克函数)③,是个非凸函数,在最优化领域,它可以用作一个最优化算法的performance test函数。这个函数还有一个更好记也更滑稽的名字:banana function(香蕉函数)。
我们来看一看它在三维空间中的图形:
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s4.51cto.com/oss/201903/27/97f1ee770a7d289fb6824b3dd2ce3937.jpg)
它的全局最优点位于一个长长的、狭窄的、抛物线形状的、扁平的“山谷”中。
找到“山谷”并不难,难的是收敛到全局最优解(在 (1,1) 处)。
正所谓:
世界上最遥远的距离,不是你离我千山万水,而是你就在我眼前,我却要跨越千万步,才能找到你。
我们再来看下面这个目标函数的寻优过程④:
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s3.51cto.com/oss/201903/27/d40e771e9b56bcb982ef91a74bb9eed4.jpg)
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s3.51cto.com/oss/201903/27/78ba3e3da4449edbcce1ae55a204b852.jpg)
和前面的Rosenbrock function一样,它的寻优过程也是“锯齿状”的。
它在三维空间中的图形是这样的:
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s3.51cto.com/oss/201903/27/82889da3bcc31518e778c83ce93c3c1a.jpg)
总而言之就是:当目标函数的等值线接近于圆(球)时,下降较快;等值线类似于扁长的椭球时,一开始快,后来很慢。
5. 为什么“慢”?
从上面花花绿绿的图,我们看到了寻找最优解的过程有多么“艰辛”,但不能光看热闹,还要分析一下原因。
在最优化算法中,精确的line search满足一个一阶必要条件,即:梯度与方向的点积为零
(当前点在
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s4.51cto.com/oss/201903/27/eb6ccaf07210f7559ab9e7a3714b91a1.jpg)
方向上移动到的那一点
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s5.51cto.com/oss/201903/27/6515fcc326b5fd242af0f74b84a665de.jpg)
处的梯度,与当前点的搜索方向
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s2.51cto.com/oss/201903/27/46a6a38fd03dfd742390aa2e7b3098f3.jpg)
的点积为零)。
由此得知:
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s4.51cto.com/oss/201903/27/9d4efe67ad8d5b77947ed3cfa7a60821.jpg)
即:
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s1.51cto.com/oss/201903/27/91f061ea1e2790cf057fc63c9fe74383.jpg)
故由梯度下降法的
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s4.51cto.com/oss/201903/27/f04d7467cd419d364efd1b9c86d14aa3.jpg)
得:
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s2.51cto.com/oss/201903/27/976cb0b18a2b1268c147052ead4de96a.jpg)
即:相邻两次的搜索方向是相互直交的(投影到二维平面上,就是锯齿形状了)。
如果你非要问,为什么
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s1.51cto.com/oss/201903/27/7bb2a3522b9035f852385275abcdfc70.jpg)
就表明这两个向量是相互直交的?那是因为,由两向量夹角的公式:
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s4.51cto.com/oss/201903/27/21e55d08bb19d6000e1c7f918a18213b.jpg)
可知两向量夹角为90度,因此它们直交。
6. 优点
这个被我们说得一无是处的方法真的就那么糟糕吗?
其实它还是有优点的:程序简单,计算量小;并且对初始点没有特别的要求;此外,许多算法的初始/再开始方向都是最速下降方向(即负梯度方向)。
7. 收敛性及收敛速度
梯度下降法具有整体收敛性——对初始点没有特殊要求。
采用精确的line search的梯度下降法的收敛速度:线性。
引用:
https://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality
https://en.wikipedia.org/wiki/Gradient_descent
https://en.wikipedia.org/wiki/Rosenbrock_function
https://en.wikipedia.org/wiki/Gradient_descent
【本文是51CTO专栏机构360技术的原创文章,微信公众号“360技术( id: qihoo_tech)”】
![浅谈梯度下降法/Gradient descent](http://zhuanlan.51cto.com/art/201903/https:/s5.51cto.com/oss/201903/26/6f86c4e91f4d7b090141998644a762e0.jpg)
戳这里,看该作者更多好文
【编辑推荐】
如何理解深度学习的优化?通过分析梯度下降的轨迹
2018年下半年,别错过这些深度学习项目!
深度学习果实即将摘尽?11位大牛谈AI的当下(2018)与未来(2019)
深度学习已经触到天花板了吗
人脸识别技术总结:从传统方法到深度学习