当前位置:   article > 正文

连载|梯度下降_对f(x) = x1 2 + ... + xn 2梯度下降

对f(x) = x1 2 + ... + xn 2梯度下降

梯度下降

梯度下降是什么

简单的说梯度下降就是对于一个函数f(x)不断的去猜想使得f(x)的值最小的自变量x在哪,猜的大了就让这个值小一点,猜的小了就让这个值大一点。它的主要猜想依据就是根据“梯度”去猜的,那么梯度又是什么呢?简单的我们可以直接把梯度理解为导数,当导数大于0(单调递增)或者小于0(单调递减)的时候,我们就有了一个调整自变量的方向。

再让我们用一个更形象的下山场景去理解一下梯度下降,假设我们现在站在山顶处A的位置,现在有急事需要我们下山,正常的思路我们需要找到能见范围内方向最陡的那条路,每隔一段距离寻找一次,一直沿用该方法,最终到达山脚F时便是下山速度最快的一种方式。这种方式就可以称作梯度下降法。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XhwNndxD-1586516003111)(/Users/kuick/Desktop/西瓜书笔记/SGD.png)]

梯度下降是怎么做的

从数学的角度上去想,梯度的方向是函数增长速度最快的方向,那么梯度的反方向就是函数减少最快的方向,假设我们需要求解目标函数 f ( x ) = f ( x 1 , x 2 , . . . , x n ) f(x)=f(x_1,x_2,...,x_n) f(x)=f(x1,x2,...,xn)的最小值,可以从一个初始点 x ( 0 ) = ( x 1 ( 0 ) , . . . , x n ( 0 ) ) x^{(0)}=(x^{(0)}_1,...,x^{(0)}_n) x(0)=(x1(0),...,xn(0))开始,基于学习率(步长) η > 0 \eta>0 η>0来构建一个迭代过程:当 i ≥ 0 i\geq0 i0时:

x 1 ( i + 1 ) = x 1 ( i ) − η ⋅ ∂ f ∂ x 1 ( x ( i ) ) x^{(i+1)}_1=x^{(i)}_1-\eta\cdot\frac{\partial f}{\partial x_1}(x^{(i)}) x1(i+1)=x1(i)ηx1f(x(i))

x n ( i + 1 ) = x n ( i ) − η ⋅ ∂ f ∂ x n ( x ( i ) ) x^{(i+1)}_n=x^{(i)}_n-\eta\cdot\frac{\partial f}{\partial x_n}(x^{(i)}) xn(i+1)=xn(i)ηxnf(x(i))

其中 x ( i ) = ( x 1 ( i ) , . . . , x n ( i ) ) x^{(i)}=(x^{(i)}_1,...,x^{(i)}_n) x(i)=(x1(i),...,xn(i)),一旦达到收敛条件的话,迭代就结束,同样从梯度下降法的迭代公式来看,下一个点的选择与当前点的位置和它的梯度相关。

上面我们说了通过梯度下降去计算最小值,那么反之我们也可以通过梯度上升来计算最大值。

x 1 ( i + 1 ) = x 1 ( i ) + η ⋅ ∂ f ∂ x 1 ( x ( i ) ) x^{(i+1)}_1=x^{(i)}_1+\eta\cdot\frac{\partial f}{\partial x_1}(x^{(i)}) x1(i+1)=x1(i)+ηx1f(x(i))

x n ( i + 1 ) = x n ( i ) + η ⋅ ∂ f ∂ x n ( x ( i ) ) x^{(i+1)}_n=x^{(i)}_n+\eta\cdot\frac{\partial f}{\partial x_n}(x^{(i)}) xn(i+1)=xn(i)+ηxnf(x(i))

其中 x ( i ) = ( x 1 ( i ) , . . . , x n ( i ) ) x^{(i)}=(x^{(i)}_1,...,x^{(i)}_n) x(i)=(x1(i),...,xn(i)),我们发现无论是计算函数的最大值还是最小值,都需要去构建一个迭代关系g,也就是:

$x^{(0)}\overset{g}{\rightarrow} x^{(1)}\overset{g}{\rightarrow} x^{(2)}\overset{g}{\rightarrow}... $

也就是对于所有的 i ≥ 0 i\geq0 i0,都满足迭代关系 x ( i + 1 ) = g ( x ( i ) ) x^{(i+1)}=g(x^{(i)}) x(i+1)=g(x(i)),因此我们可以直接写出梯度下降对应的函数g的表达式为( η \eta η用来表示步长,梯度用来规定方向):

g ( x ) = { x − η ▽ f ( x )   梯 度 下 降 法 x + η ▽ f ( x )   梯 度 上 升 法 g(x)=\left\{

xηf(x) x+ηf(x) 
\right. g(x)={xηf(x) x+ηf(x) 

我们根据每一次迭代所使用的训练数据集范围的不同,可以把梯度下降算法区分为:批量梯度下降、随机梯度下降、小批量梯度下降。

批量梯度下降(BGD)

批量梯度下降(Batch Gradient Descent,BGD),也称之为最速下降法,误差损失函数由全部训练数据的误差构成,当我们的数据量很大的时候,速度会非常的慢,同时当我们有新的元素加入的时候,需要对全量的数据进行更新,效率会变得很低,所以目前我们所使用的梯度下降法一般都不会采用BGD的策略。

随机梯度下降(SGD)

随机梯度下降(Stochastic Gradient Descent,SGD),SGD是对BGD的一种改进,在SGD中每进行一次更新,只考虑一个样本数据的误差损失,这也是提高它速度的主要原因所在,同样当新元素加入的时候,SGD也能够继续进行更新。但是SGD的缺点在于,由于单个样本会出现重复或者相似的情况,这会导致我们对数据的更新产生冗余;并且单个数据之间的差异会比较大,从而造成每一次迭代的损失函数会出现较大的波动。如下图所示:

在这里插入图片描述

小批量梯度下降(MBGD)

小批量梯度下降(Mini-Batch Gradient Descent,MBGD),MBGD的策略是每次的参数更新都是由n个样本数据构成的,通常n的取值比较小,一般取10-500之间的数字,MBGD有如下的几个优点:

  • 每一批的数据量较小,特别适合高效的矩阵运算,尤其是在GPU的并行加速上。
  • MBGD每一次计算的时候考虑了更多的样本数据,数据整体之间的差异会更小,更平均,也就避免了SGD中的波动的出现。
  • 与BGD相比,MBGD适合于对于新元素加入时的参数更新。

通常情况下对于梯度下降,我们都会采用MBGD的策略。

从传统到动量

对于传统的梯度下降,我们假设参数向量是 θ \theta θ,梯度为 d ( θ ) d(\theta) d(θ),学习率(步长)为 η \eta η则此时参数更新的策略为:

θ = θ − η d ( θ ) \theta=\theta-\eta d(\theta) θ=θηd(θ)

上文中我们一直在讨论数据的大小对于梯度下降的影响,现在再让我们来考虑一下步长带来的影响:

  • 当步长过小的时候,会导致算法收敛速度过慢;当步长过大的时候会,容易在迭代的过程中出现震荡的现象,甚至无法收敛。步长过大时的效果如下图所示:

在这里插入图片描述

  • 当遇到较为平坦的区域的时候,由于梯度接近于0,因此每一次迭代的变化都非常小,会造成学习率的下降,甚至有可能会被误判为最优解而提前终止迭代。效果如下图所示:

在这里插入图片描述

对于上述的种种问题,我们有一种思考,是不是可以把上一次更新的方向保留,结合下一次更新的方向一起去做更更新呢?来看一下下面的策略。

动量更新(momentum)

动量更新是借助了物理学的思想来进行参数的更新,我们都知道一个运动的物体往往都具有惯性(动量),我们把惯性的思想放到梯度下降中去,也就可以使得更新时在保留了之前的更新方向的同时,也能利用当前的梯度方向进行相应的调整,这样的做法能够让更新的方向根据实际的数据变化做出相应的调整。

具体一点我们可以认为我们每一次的迭代更新中,迭代方向都是由两部分组成的。具体的图示如下:

在这里插入图片描述

第一部分就是上一个时刻的迭代方向,即动量,可以记作 μ v i − 1 \mu v_{i-1} μvi1 v i − 1 v_{i-1} vi1就是上一时刻的迭代方向,而 μ \mu μ就是动量系数(和我们之前所说的步长一样)。

第二部分是当前的梯度方向,和之前一样我们记作 η d ( θ ) \eta d(\theta) ηd(θ)

所以对于当前的迭代我们就可以写成:

v i = μ v i − 1 + η d ( θ i − 1 ) v_i=\mu v_{i-1}+\eta d(\theta^{i-1}) vi=μvi1+ηd(θi1)

θ i = θ i − 1 − v i \theta^i=\theta^{i-1}-v_i θi=θi1vi

这样做的好处在于,当我们上一次的迭代方向与当前的梯度方向相反时,动量能起到一个减速的作用,防止走偏;相反当上一次的迭代方向与当前的梯度方向相同时,动量能起到一个加速的作用,避免在平坦的曲面上迭代过慢。

改进的动量更新(NAG)

对于上一小节中提到的动量更新,我们还可以有优化的策略,对于momentum来说我们同时计算了当前梯度的方向和上一时刻迭代的方向,对于这种同时计算的方式,我们也可以把迭代的方向分为两步走,第一步是沿着上次更新的方向继续前进 μ v i − 1 \mu v_{i-1} μvi1,到达点 ( θ i − 1 ) ′ (\theta^{i-1})^{'} (θi1),即:

( θ i − 1 ) ′ = θ i − 1 − μ v i − 1 (\theta^{i-1})^{'}=\theta^{i-1}-\mu v_{i-1} (θi1)=θi1μvi1

然后沿着 θ i − 1 \theta^{i-1} θi1的梯度方向前进 η θ \eta\theta ηθ,到达点 θ i \theta^i θi,即:

θ i = ( θ i − 1 ) ′ − η d ( θ i − 1 ) \theta^i=(\theta^{i-1})^{'}-\eta d(\theta^{i-1}) θi=(θi1)ηd(θi1)

我们可以发现对比momentum来说我们第二步中的当前点已经不再是 θ i − 1 \theta^{i-1} θi1,而是新的 ( θ i − 1 ) ′ (\theta^{i-1})^{'} (θi1),很自然的我们可以想到,我们在第二步是不是可以去求点 ( θ i − 1 ) ′ (\theta^{i-1})^{'} (θi1)的梯度呢?此时的策略图示如下:

在这里插入图片描述

此时我们可以得到NAG的计算形态如下:

( θ i − 1 ) ′ = θ i − 1 − μ v i − 1 (\theta^{i-1})^{'}=\theta^{i-1}-\mu v_{i-1} (θi1)=θi1μvi1

v i = μ v i − 1 + η d ( ( θ i − 1 ) ′ ) v_i=\mu v_{i-1}+\eta d((\theta^{i-1})^{'}) vi=μvi1+ηd((θi1))

θ i = θ i − 1 − v i \theta^i=\theta^{i-1}-v_i θi=θi1vi

这种做法,从向量加法的角度来看和momentum是相同的,而从细微的角度来看,这种做法的效率其实要高于momentum(具体的验证过程较复杂,不在这里呈现)。

自适应梯度策略(AdaGrad)

上面我们讲到的种种算法,都是针对梯度下降的方向进行了优化,而步长却一直是固定的,也就是说对于所有的参数都共享了相同的学习率,然而这种不考虑步长的做法很容易导致算法卡在鞍点处,本节再让我们来了解一个可以自动调节步长的算法AdaGrad。

这次先让我们来看一下公式:

a c c i = a c c i − 1 + ( d ( θ i − 1 ) ) 2 acc_i=acc_{i-1}+(d(\theta_{i-1}))^2 acci=acci1+(d(θi1))2

θ i = θ i − 1 − η a c c i + ϵ d ( θ i − 1 ) \theta_i=\theta_{i-1}-\frac{\eta}{\sqrt{acc_i+\epsilon}}d(\theta_{i-1}) θi=θi1acci+ϵ ηd(θi1)

其中 η \eta η依旧是学习率(步长), ϵ \epsilon ϵ是一个很小的常数,为了防止分母为0。根据公式我们的可以发现此时的方向依旧是由 d ( θ i − 1 ) d(\theta_{i-1}) d(θi1)来决定的,但是步长却不再是固定的了,具体的策略如下:

  • 当迭代的时间越长,则累加的梯度acc越大,使得下式中的学习率会随着迭代次数的增加而减少,此时当接近目标函数的最小值时,不会因为学习率过大而走过头。
  • 对于不同的参数之间可以有不同的学习率,与前面的算法相比,不容易卡在鞍点的位置。
  • 根据表达式我们可以发现,如果参数的梯度累加比较小,则学习率会变得比较大,此时我们参数迭代的步长也会比较大,反之,如果参数梯度累加比较大,则学习率会比较小,参数的步长也会比较小。

除了文中提到的梯度下降算法,常用的还有Adadelta、RMSprop、Adam等,后面有机会我们再来讨论这些算法的原理~
在这里插入图片描述

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop】
推荐阅读
相关标签
  

闽ICP备14008679号