梯度下降法小结

2019/07/24 00:19
阅读数 119

关于机器学习的方法,大多算法都用到了最优化求最优解问题。梯度下降法(gradient descent)是求解无约束最优化问题的一种最常用的方法。它是一种最简单,历史悠长的算法,但是它应用非常广。下面主要在浅易的理解:

一、梯度下降的初步认识

先理解下什么是梯度,用通俗的话来说就是在原变量的基础上每次迭代增加一定的量,比较各个变量下目标函数的大小。

例如有一个目标函数 y = 2χ,那么求目标函数的最小值,我们先给x赋一个值-5,然后每次给x加一个值(有正负方向的值),这样y每次都会有一个值,当值减小幅度达到一定精确度时停止,这是的x就是我们求的最优解。

是不是有一点感觉了,上面的例子比较简单,通常在求解最优解的时候,目标函数就是我们要优化的,找出满足目标函数的最优解。有时候目标函数是比较复杂的,这时候梯度下降法就比较有用了。

    

 

 

 

 

 

 

 

 

 

 

 

 

所谓梯度,如果目标函数可微,我们把目标函数的各个变量的偏导组成一个向量,既是梯度。主要是在优化过程中,我们怎么给变量增加还是减少的方向变量。如上例中我们怎么知道给x增加一定的量的,就是靠方向变量了。

二、梯度下降法的概念

梯度:即对变量的偏微分的组成的向量,(∂f/∂x1,∂f/∂x2 ...)。

步长:即每次迭代给变量增加的值,通常是一个值*梯度

梯度下降法就是沿着负方向迭代,直到找到最小值。

与之相反的是梯度上升法,沿着梯度正方向迭代。

梯度下降法的有缺点:

优点:实现比较简单,当目标函数是凸函数可以找到全局最优解。

缺点:容易陷入局部最优,靠近极小值时收敛速度会变慢,可能成之字下降,直线搜索可能会产生一些问题。

三、具体实现的算法例子

我们以逻辑回归的参数最大似然估计为例。

目标函数:求目标函数的极大值。我们要对式中的w进行参数估计。

(1)我们这里初始化w1,w2 , ... w都为0

(2)计算梯度,即各个w的偏导∂L(w)/∂w

  (3) gi+1= L(w)i+1-L(w)i   ,i表示第i次迭代,gi+1代表第i+1次的目标函数和第i次的差

(4)对变量进行迭代  wij=wi+1j+∂L(w)i/∂wj  ...

代入计算wij,再计算gi+1,若gi+1大于阈值,重复3、4,直至g小于阈值,既是我们要的最优解。

四、梯度下降算法的调优

1、步长。在设定步长的时候如果设置过大收敛较快但是可能错过最优解,步长太小收敛较慢。实际用法中可以根据样本进行决定。设置多组步长实验。

2、初始值。初始值不同不仅影响算法的收敛速度,还影响变量的是否陷入局部最优。需要多次用不同的初始值进行运算,选择目标最优的一组解。

3、特征归一化:由于不同的特征取值范围不一样,可能导致迭代很慢,可以参数归一化解决。

 

五、梯度下降算法的衍生

下面摘自:https://baijiahao.baidu.com/s?id=1613121229156499765&wfr=spider&for=pc

1、全量梯度下降法(Batch gradient descent)

  全量梯度下降法每次学习都使用整个训练集,因此每次更新都会朝着正确的方向进行,最后能够保证收敛于极值点,凸函数收敛于全局极值点,非凸函数可能会收敛于局部极值点,缺陷就是学习时间太长,消耗大量内存。

2、随机梯度下降法(Stochastic Gradient Descent)

  SGD一轮迭代只用一条随机选取的数据,尽管SGD的迭代次数比BGD大很多,但一次学习时间非常快。

  SGD的缺点在于每次更新可能并不会按照正确的方向进行,参数更新具有高方差,从而导致损失函数剧烈波动。不过,如果目标函数有盆地区域,SGD会使优化的方向从当前的局部极小值点跳到另一个更好的局部极小值点,这样对于非凸函数,可能最终收敛于一个较好的局部极值点,甚至全局极值点。

  缺点是,出现损失函数波动,如下图所示,并且无法判断是否收敛。

3、小批量梯度下降法(Mini-Batch Gradient Descent)

  SGD相比BGD收敛速度快,然而,它也的缺点,那就是收敛时浮动,不稳定,在最优解附近波动,难以判断是否已经收敛。这时折中的算法小批量梯度下降法,MBGD就产生了,道理很简单,SGD太极端,一次一条,为何不多几条?MBGD就是用一次迭代多条数据的方法。

  并且如果Batch Size选择合理,不仅收敛速度比SGD更快、更稳定,而且在最优解附近的跳动也不会很大,甚至得到比Batch Gradient Descent 更好的解。这样就综合了SGD和Batch Gradient Descent 的优点,同时弱化了缺点。总之,Mini-Batch比SGD和Batch Gradient Descent都好。

4、第四、Momentum梯度下降法

·  

SGD、BSGD两种改进方法都存在不同程度的震荡,如何避免震荡?或者说震荡是怎么产生的?震荡,从可视图表现来看,就是频繁更改方向,所以,如果能够把之前下降的方向考量进来,那么将会减少振荡。

上边第二个图是带动量的梯度下降法。

下面推导动量下降法。

在普通的梯度下降法W -= V中,每次W的更新量V为V = dW * λ;

当使用冲量时,V考虑为本次的梯度下降量与部分上次更新量的矢量和,即-dW*λ与上次x的更新量V乘以一个介于[0, 1]的系数momemtum的和,即:

V = dW * λ+ V*momemtum。

当本次梯度下降方向与上次更新量的方向相同时,上次的更新量能够对本次的搜索起到一个正向加速的作用。当本次梯度下降方向与上次更新量的方向相反时,上次的更新量能够对本次的搜索起到一个减速的作用。下面两个图,第一图是没有动量的梯度下降法,第二图是有动量的梯度下降法,很明显减少了震荡。

既减少震荡,又大方向不变(本次梯度下降方向),从而保证了效率和正确的收敛。

 

5、第五、NAG梯度下降法

NAG(Nesterov Accelerated Gradient)不仅仅把SGD梯度下降以前的方向考虑,还将Momentum梯度变化的幅度也考虑了进来。

上图是Momentum的优化轨迹,下图是NAG的优化轨迹:

在给出公式之前,先看一个向量图:

 

这个图来源于 G. Hinton’s的文章,网上对这个图的解释大都来源于《An overview of gradient descent optimizationalgorithms》中文翻译,其实并没有真正讲解清楚。本文严格按照愿意解释一下:

Momentum梯度法首先计算的是当前的梯度(图中的小蓝色向量)然后沿着更新的累积梯度的方向来一个大的跳跃(图中大蓝色向量),而NAG梯度法首先沿着先前的累积梯度方向(棕色向量)实现一个大的跳跃,然后加上一个小的按照动量梯度法计算的当前梯度(上图红色向量)进行修正得到上图绿色的向量。此处我抛出一个问题,上图为什么画了两个三角形?如果能理解第二个矢量三解形的意义,才能正在理解NAG。注意第二个矢量三角形的棕色向量与前一个的绿色向量方向一致,因为上一个矢量三角形的结果是绿色向量,而棕色代表的是先前的累积梯度,方向就应该和绿色的一样。然后,再加上当前按照动量梯度法计算出的梯度,就得到第二个三角形的绿色向量。

给出公式表达:

 

我们先给出类似生活体验的通俗的解释:我们要让算法要前瞻性,提前看到前方的地形梯度,如果前面的梯度比当前位置的梯度大,那我就可以把步子迈得比原来大一些,如果前面的梯度比现在的梯度小,那我就可以把步子迈得小一些。这个大一些、小一些,都是相对于原来不看前方梯度、只看当前位置梯度的情况来说的。

NAG的另一个等效形式为(下文会详细推导):

这个NAG的等效形式与Momentum的区别在于,本次更新方向多加了一个,注意到没有,这项其实就是目标函数的二阶导数!所以NAG本质上是多考虑了目标函数的二阶导信息,读过《一篇中矣:彻底理解XGBoost!》一文的读者,是不是觉得很面熟,二阶导数再次发挥作用!其实所谓“往前看”的说法,在牛顿法这样的二阶方法中经常提到,形象说“往前看”,数学思维则是利用了目标函数的二阶导信息。

现在我们由NAG原始形式来推导NAG的等效形式:

为了出现二阶形式,将原始形式按照递推展开:

 

我们观察这个等式,并对应原始公式

观察对比这个长等式:

等式相当于参数在更新量更新基础上的更新,所以为了看上去更有意义,对应的形式,我们作如下记号:

我们在猜想一个形式:

则可作记号:

 

也就是有:

为了变换形式,我们作如下展开:

继续推导:

 

 

到此为止NAG证明就结束,逻辑、意义非常完美!这就是数学之美!

限于篇幅其他非常重要的梯度法AdaGrad、AdaDelta、RMSProp、Adam等在后续文章在详加阐述。

参考网址:https://baijiahao.baidu.com/s?id=1613121229156499765&wfr=spider&for=pc

 

展开阅读全文
nag
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部