梯度下降-最速下降-共轭梯度
梯度下降-最速下降-共轭梯度

梯度下降-最速下降-共轭梯度

[TOC]

梯度下降-最速下降-共轭梯度

hessian矩阵

黑塞矩阵(Hessian Matrix),是一个多元函数的二阶偏导数构成的方阵,描述了函数的局部曲率。黑塞矩阵常用于牛顿法解决优化问题,利用黑塞矩阵可判定多元函数的极值问题。在工程实际问题的优化设计中,所列的目标函数往往很复杂,为了使问题简化,常常将目标函数在某点邻域展开成泰勒多项式来逼近原函数,此时函数在某点泰勒展开式的矩阵形式中会涉及到黑塞矩阵。

基于Hessian矩阵,可以判断多元函数的极值情况,结论如下:
(1)如果是正定矩阵,则临界点处是一个局部极小值
(2)如果是负定矩阵,则临界点处是一个局部极大值
(3)如果是不定矩阵,则临界点处不是极值

如何判断一个矩阵是否是正定的,负定的,还是不定的。一个最常用的方法就是借助其顺序主子式。实对称矩阵为正定矩阵的充要条件是各顺序主子式都大于0。当然这个判定方法的计算量比较大。对于实二次型矩阵还有一个判定方法:实二次型矩阵为正定二次型的充要条件是矩阵的特征值全大于0。为负定二次型的充要条件是矩阵的特征值全小于0,否则是不定的。

牛顿法是收敛速度最快的方法,其缺点在于要求Hessian矩阵(二阶导数矩阵)。牛顿法大致的思路是采用泰勒展开的二阶近似。若Hessian矩阵是正定的,函数的局部最小值可以通过使上面的二次型的一阶导数等于0来获取

梯度下降法

一文看懂常用的梯度下降算法-转载自知乎

一文看懂常用的梯度下降算法

梯度下降算法(Gradient Descent Optimization)是神经网络模型训练最常用的优化算法。对于深度学习模型,基本都是采用梯度下降算法来进行优化训练的。梯度下降算法背后的原理:目标函数 关于参数 的梯度将是损失函数(loss function)上升最快的方向。而我们要最小化loss,只需要将参数沿着梯度相反的方向前进一个步长,就可以实现目标函数(loss function)的下降。这个步长 又称为学习速率。参数更新公式如下:

其中 是参数的梯度,根据计算目标函数采用数据量的不同,梯度下降算法又可以分为批量梯度下降算法(Batch Gradient Descent)随机梯度下降算法(Stochastic Gradient Descent)小批量梯度下降算法(Mini-batch Gradient Descent)
对于批量梯度下降算法,其 是在整个训练集上计算的,如果数据集比较大,可能会面临内存不足问题,而且其收敛速度一般比较慢。
随机梯度下降算法是另外一个极端, 是针对训练集中的一个训练样本计算的,又称为在线学习,即得到了一个样本,就可以执行一次参数更新。所以其收敛速度会快一些,但是有可能出现目标函数值震荡现象,因为高频率的参数更新导致了高方差。
小批量梯度下降算法是折中方案,选取训练集中一个小批量样本(一般是2的倍数,如32,64,128等)计算,这样可以保证训练过程更稳定,而且采用批量训练方法也可以利用矩阵计算的优势。这是目前最常用的梯度下降算法。

对于神经网络模型,借助于BP算法可以高效地计算梯度,这非常利于采用梯度下降算法对神经网络进行训练。

梯度下降算法中一个重要的参数是学习速率,适当的学习速率很重要:学习速率过小时收敛速度慢,而过大时导致训练震荡,而且可能会发散。

理想的梯度下降算法要满足两点:收敛速度要快;而且能全局收敛。为了这个理想,出现了很多经典梯度下降算法的变种,下面将分别介绍它们。

Exponentially weighted moving averages-指数加权移动平均

其中 是上一时刻的移动平均值,其实也可以看成历史积累量,一般 ,而 是一个系数,其在 0 ~ 1 之间,可以看到移动平均值是按比例合并历史量与当前观测量。

展开上式:

展开之后,每个 值,其权重是不一样的,实际上是指数递减的,从当前往后指数递减,所以距离时刻较近的数据会对当前值影响较大,这样计算的好处是平均数会比较平稳。

由于权重指数衰减,所以移动平均数只是计算比较相近时刻数据的加权平均数,一般可认为这个时间范围为 ,比如 ,近似认为只是平均了10时刻之内的数据,因为再往前权重太小了,基本没影响了。
如果你熟悉级数的话,也可以计算出权重和是近似为1的,这是在无穷的情况下,但是在前期计算时,权重之和是会小于1的,为了解决这个问题,指数加权移动平均数会引入偏差修正:

就是前期计算时要放大一下计算结果,而后期不需要,此时 的值也接近1了。

Momentum optimization-动量优化

冲量梯度下降算法是Boris Polyak在1964年提出的,其基于这样一个物理事实:将一个小球从山顶滚下,其初始速率很慢,但在加速度作用下速率很快增加,并最终由于阻力的存在达到一个稳定速。

对于冲量梯度下降算法,其更新方程如下:

参数更新时不仅考虑当前梯度值,而且加上了一个积累项(冲量),但多了一个超参 ,一般取接近1的值如0.9。相比原始梯度下降算法,冲量梯度下降算法有助于加速收敛。当梯度与冲量方向一致时,冲量项会增加,而相反时,冲量项减少,因此冲量梯度下降算法可以减少训练的震荡过程。

有时候,冲量梯度下降算法也可以按下面方式实现:

冲量项其实只是梯度的指数加权移动平均值。这个实现和之前的实现没有本质区别,只是学习速率进行了放缩一下而已。

TensorFlow中提供了冲量梯度下降算法的实现:

1
tf.train.MomentumOptimizer(learning_rate=learning_rate, momentum=0.9)

Nesterov Accelerated Gradient(NAG)-加速梯度

NAG算法是Yurii Nesterov在1983年提出的对冲量梯度下降算法的改进版本,其速度更快。其变化之处在于计算“超前梯度”更新冲量项,具体公式如下:

既然参数要沿着 更新,不妨计算未来位置 的梯度,然后合并两项作为最终的更新项,其具体效果如下所示,可以看到一定的加速效果。

NAG效果图

在TensorFlow中,NAG优化器为:

1
tf.train.MomentumOptimizer(learning_rate=learning_rate, momentum=0.9, use_nesterov=True)

AdaGrad

AdaGrad是Duchi在2011年提出的一种学习速率自适应的梯度下降算法。
在训练迭代过程,其学习速率是逐渐衰减的,经常更新的参数其学习速率衰减更快,这是一种自适应算法。

其更新过程如下:

梯度平方的积累量 ,在进行参数更新时,学习速率要除以这个积累量的平方根,其中加上一个很小值 是为了防止除0的出现。由于 是逐渐增加的,那么学习速率是衰减的。考虑如下图所示的情况,目标函数在两个方向的坡度不一样,如果是原始的梯度下降算法,在接近坡底时收敛速度比较慢。而当采用AdaGrad,这种情况可以被改观。由于比较陡的方向 比较大,其学习速率将衰减得更快,这有利于参数沿着更接近坡底的方向移动,从而加速收敛。

AdaGrad效果图

前面说到AdaGrad其学习速率实际上是不断衰减的,这会导致一个很大的问题,就是训练后期学习速率很小,导致训练过早停止,因此在实际中AdaGrad一般不会被采用,下面的算法将改进这一致命缺陷。不过TensorFlow也提供了这一优化器:tf.train.AdagradOptimizer

RMSprop

RMSprop是Hinton在他的课程上讲到的,其算是对Adagrad算法的改进,主要是解决学习速率过快衰减的问题。其实思路很简单,类似Momentum思想,引入一个超参数,在积累梯度平方项进行衰减:

此时可以看到 是梯度平方的指数加权移动平均值,其中 一般取值0.9,此时 更平稳,减少了出现的爆炸情况,因此有助于避免学习速率很快下降的问题。

同时Hinton也建议学习速率设置为0.001。RMSprop是属于一种比较好的优化算法了,在TensorFlow中当然有其身影:

1
tf.train.RMSPropOptimizer(learning_rate=learning_rate, momentum=0.9, decay=0.9, epsilon=1e-10)

同时期还有一个Adadelta算法,其也是Adagrad算法的改进,而且改进思路和RMSprop很像,但是其背后是基于一次梯度近似代替二次梯度的思想。

Adaptive moment estimation(Adam)-自适应矩估计

Adam是Kingma等在2015年提出的一种新的优化算法,其结合了Momentum和RMSprop算法的思想。相比Momentum算法,其学习速率是自适应的,而相比RMSprop,其增加了冲量项。

所以,Adam是两者的结合体:

可以看到前两项和Momentum和RMSprop是非常一致的, 由于和的初始值一般设置为0,在训练初期其可能较小,第三和第四项主要是为了放大它们。最后一项是参数更新。其中超参数的建议值是: 。Adm是性能非常好的算法,在TensorFlow其实现如下:

1
tf.train.AdamOptimizer(learning_rate=0.001, beta1=0.9, beta2=0.999, epsilon=1e-08)

学习速率

对于梯度下降算法,这应该是一个最重要的超参数。
如果学习速率设置得非常大,那么训练可能不会收敛,就直接发散了;如果设置的比较小,虽然可以收敛,但是训练时间可能无法接受;如果设置的稍微高一些,训练速度会很快,但是当接近最优点会发生震荡,甚至无法稳定。不同学习速率的选择影响可能非常大,如下图所示。

不同学习速率的训练效果

理想的学习速率是:刚开始设置较大,有很快的收敛速度,然后慢慢衰减,保证稳定到达最优点。所以,前面的很多算法都是学习速率自适应的。除此之外,还可以手动实现这样一个自适应过程,如实现学习速率指数式衰减:

在TensorFlow中,你可以这样实现:

1
2
3
4
5
6
7
8
9
10
11
initial_learning_rate = 0.1
decay_steps = 10000
decay_rate = 1/10
global_step = tf.Variable(0, trainable=False)

learning_rate = tf.train.exponential_decay(initial_learning_rate,
global_step, decay_steps,
decay_rate)
# decayed_learning_rate = learning_rate *decay_rate ^ (global_step / decay_steps)
optimizer = tf.train.MomentumOptimizer(learning_rate, momentum=0.9)
training_op = optimizer.minimize(loss, global_step=global_step)

局部最优和鞍点

前面说到,我们希望优化算法能够收敛速度快,并且想找到全局最优。对于凸函数来说,其仅有一个极值点,就是全局最优点,如下图所示,此时采用梯度下降算法是可以收敛到最优点的,因为沿着下坡的道路走就可以了。

凸函数,无局部最优

但是其实现在的深度学习模型是一个庞大的非线性结构,这样其一般是非凸函数,就如下图所示那样,存在很多局部最优点(local optimum),一旦梯度下降算法跳进局部陷阱,可以想象其很难走出来,这就很尴尬了,此时梯度下降算法变得不再那么可靠,因为我们想要的是全局最优。

存在很多局部最优点的非凸函数

很难找到全局最优,这可能是目前优化算法共同面对的问题,如进化算法。不过到底深度学习的损失函数是不是存在很多局部最优点呢?前面所有的分析都是基于低维空间,我们很容易观察到局部最优点。但是深度学习的参数一般庞大,其损失函数已经成为了超高维空间。但是Bengio等最新的研究表明,对于高维空间,非凸函数最大的存在不是局部最优点,而是鞍点(saddle point),鞍点也是梯度为0的点,但是它不像局部最优点或者全局最优点。对于局部最优或者全局最优点,其周围的所有方向要朝向上(最小)或者朝向上(最大),但是考虑到参数庞大,很有可能是一部分方向朝下,一部分方向朝上,这就成为了鞍点。意思就是说在高维度空间,不大可能像低维度空间那样出现很多局部最优。而且鞍点也不大可能会成为梯度下降算法的葬身之地。那么真正影响梯度下降算法会是什么呢?可能是平稳区(plateaus),如果出现大面积梯度很小或者近似为0的区域,那么梯度下降算法就找不到方向,想象你自己站在一望无际的平原,估计你也方向感全无了。

存在鞍点的函数

维基百科-梯度下降

维基百科-梯度下降

梯度下降法(英语:Gradient descent)是一个一阶最优化算法,通常也称为最陡下降法,但是不该与近似积分的最陡下降法(英语:Method of steepest descent)混淆。 要使用梯度下降法找到一个函数的局部极小值,必须向函数上当前点对应梯度(或者是近似梯度)的反方向的规定步长距离点进行迭代搜索。如果相反地向梯度正方向迭代进行搜索,则会接近函数的局部极大值点;这个过程则被称为梯度上升法。

梯度下降方法基于以下的观察:如果实值函数 在点 处可微且有定义,那么函数 点沿着梯度相反的方向 下降最多。

因而,如果:

对于一个足够小数值 时成立,那么 考虑到这一点,我们可以从函数 的局部极小值的初始估计 出发,并考虑如下序列 使得

因此可得到

如果顺利的话序列 收敛到期望的局部极小值。注意每次迭代步长 可以改变。

下图示例了这一过程,这里假设 定义在平面上,并且函数图像是一个碗形。蓝色的曲线是等高线(水平集),即函数 为常数的集合构成的曲线。红色的箭头指向该点梯度的反方向。(一点处的梯度方向与通过该点的等高线垂直)。沿着梯度下降方向,将最终到达碗底,即函数 局部极小值的点。

梯度下降法的描述

梯度下降法处理一些复杂的非线性函数会出现问题,例如Rosenbrock函数:

其最小值在 处,数值为 。但是此函数具有狭窄弯曲的山谷,最小值 就在这些山谷之中,并且谷底很平。优化过程是之字形的向极小值点靠近,速度非常缓慢。

Rosenbrock函数

下面这个例子也鲜明的示例了”之字”的上升(非下降),这个例子用梯度上升(非梯度下降)法求 的局部极大值(非局部极小值)。

之字上升示例-1 之字上升示例-2

梯度下降法的缺点包括:

  • 靠近局部极小值时速度减慢。
  • 直线搜索可能会产生一些问题。
  • 可能会“之字型”地下降。

百度百科-梯度下降

百度百科-梯度下降

梯度下降是迭代法的一种,可以用于求解最小二乘问题(线性和非线性都可以)。在求解机器学习算法的模型参数,即无约束优化问题时,梯度下降(Gradient Descent)是最常采用的方法之一,另一种常用的方法是最小二乘法。在求解损失函数的最小值时,可以通过梯度下降法来一步步的迭代求解,得到最小化的损失函数和模型参数值。反过来,如果我们需要求解损失函数的最大值,这时就需要用梯度上升法来迭代了。在机器学习中,基于基本的梯度下降法发展了两种梯度下降方法,分别为随机梯度下降法和批量梯度下降法。

梯度:对于可微的数量场 ,以 为分量的向量场称为f的梯度或斜量。

梯度下降法(gradient descent)是一个最优化算法,常用于机器学习和人工智能当中用来递归性地逼近最小偏差模型。

顾名思义,梯度下降法的计算过程就是沿梯度下降的方向求解极小值(也可以沿梯度上升方向求解极大值)。

其迭代公式为 ,其中 代表梯度负方向, 表示梯度方向上的搜索步长。梯度方向我们可以通过对函数求导得到,步长的确定比较麻烦,太大了的话可能会发散,太小收敛速度又太慢。一般确定步长的方法是由线性搜索算法来确定,即把下一个点的坐标看做是 的函数,然后求满足 的最小值的 即可。

因为一般情况下,梯度向量为0的话说明是到了一个极值点,此时梯度的幅值也为0。而采用梯度下降算法进行最优化求解时,算法迭代的终止条件是梯度向量的幅值接近0即可,可以设置个非常小的常数阈值。

举一个非常简单的例子,如求函数 的最小值。
利用梯度下降的方法解题步骤如下:
1、求梯度,
2、向梯度相反的方向移动 ,如下

其中的函数

求解这类的问题可以分为两大类:一个是最优条件法和迭代法。

最优条件法是是指当函数存在解析形式,能够通过最优性条件求解出显式最优解。对于无约束最优化问题,如果 在最优点 附近可微,那么 是局部极小点的必要条件为:
我们常常就是通过这个必要条件去求取可能的极小值点,再验证这些点是否真的是极小值点。当上式方程可以求解的时候,无约束最优化问题基本就解决了。
实际中,这个方程往往难以求解。这就引出了第二大类方法:迭代法。

最速下降法就是一种迭代法。

最速下降法计算步骤

由以上计算步骤可知,最速下降法迭代终止时,求得的是目标函数驻点的一个近似点。

  • 第一步:迭代法的初始点选择。
  • 第二步:终止条件的解释:
最速下降法-定理2

最终如果到达了局部最优解的话,求出来的梯度值是为0的,也就是说该点梯度为0是该点是局部最优解的必要条件。

所以我们的终止条件就是到达某处的梯度为0,在一些条件不是太苛刻的情况下,我们也可以不让它严格为0,只是逼近于0即可。这就是第二步的解释。

  • 第三步:这步在是在选取迭代方向,也就是从当前点迭代的方向。这里选取当前点的梯度负方向,为什么选择这个方向,是因为梯度的负方向是局部下降最快的方向。
  • 第四步:第四步也是非常重要的,因为在第三步我们虽然确定了迭代方向,并且知道这个方向是局部函数值下降最快的方向,但是还没有确定走的步长,如果选取的步长不合适,也是非常不可取的,下面会给出一个例子图,那么第四步的作用就是在确定迭代方向的前提上,确定在该方向上使得函数值最小的迭代步长。
最速下降法步长-合适步长

其中确定最优步长 的方法如下:

最速下降法步长计算方法
  • 算法缺点

某点的负梯度方向,通常只是在该点附近才具有这种最速下降的性质。

在一般情况下,当用最速下降法寻找极小点时,其搜索路径呈直角锯齿状(如下图),在开头 几步,目标函数下降较快;但在接近极小点时,收敛速度长久不理想了。特别适当目标函数的等值 线为比较扁平的椭圆时,收敛就更慢了。

最速下降法-算法缺点

因此,在实用中常用最速下降法和其他方法联合应用,在前期使用最速下降法,而在接近极小值点时,可改用收敛较快的其他方法。

  • 最速下降法与梯度下降法的区别

准确来说,它们并不是完全等价。

对于梯度下降法,我们需要预先设定步长

而最速下降法的步长 是通过一个优化函数计算得到的:

最优化学习笔记(四)——最速下降法

最优化学习笔记(四)——最速下降法

最速下降法是梯度方法的一种实现,它的理念是在每次的迭代过程中,选取一个合适的步长,使得目标函数的值能够最大程度的减小。可以认为是函数的极小值点:

由梯度迭代公式可知: ,上式的解释是找到最优的迭代点 ,使得函数 取得极小值时,求出步长

概述最速下降法的过程:在每一步的迭代中,从点 出发,沿着梯度的负方向(求极小值点)展开一维搜索,直到找到步长最优值,确定新的迭代点 最速下降法的相邻搜索方向都是正交的

共轭梯度法

维基百科-共轭梯度

维基百科-共轭梯度

共轭梯度法(英语:Conjugate gradient method),是求解系数矩阵为对称正定矩阵的线性方程组的数值解的方法。共轭梯度法是一个迭代方法,它适用于系数矩阵为稀疏矩阵的线性方程组,因为使用像Cholesky分解这样的直接方法求解这些系统所需的计算量太大了。这种方程组在数值求解偏微分方程时很常见。

共轭梯度法也可以用于求解无约束的最优化问题。

双共轭梯度法(英语:BiConjugate gradient method)提供了一种处理非对称矩阵情况的推广。

共轭梯度法通俗讲义

共轭梯度法通俗讲义

二次型

对于正定阵最直观的理解方式就是它的二次型函数的图形是一个开口向上的抛物面。如果矩阵A非正定,那么其全局最小值点就可能不止一个。

不同情况下的二次型函数图

(a) 正定矩阵的二次型函数图形。
(b) 负定矩阵二次函数图。
(c) 正定奇异阵的函数图,过谷底的一条直线为解集。
(d) 不定矩阵函数图对于三维及以上的情况,奇异矩阵也可能会存在鞍点

共轭梯度法, 百度百科

共轭梯度法, 百度百科

共轭梯度法(Conjugate Gradient)是介于最速下降法与牛顿法之间的一个方法,它仅需利用一阶导数信息,但克服了最速下降法收敛慢的缺点,又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点,共轭梯度法不仅是解决大型线性方程组最有用的方法之一,也是解大型非线性最优化最有效的算法之一。 在各种优化算法中,共轭梯度法是非常重要的一种。其优点是所需存储量小,具有步收敛性,稳定性高,而且不需要任何外来参数。

共轭梯度法是一个典型的共轭方向法,它的每一个搜索方向是互相共轭的,而这些搜索方向d仅仅是负梯度方向与上一次迭代的搜索方向的组合,因此,存储量少,计算方便。

文章作者: HibisciDai
文章链接: http://hibiscidai.com/2023/10/08/梯度下降-最速下降-共轭梯度/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 HibisciDai
好用、实惠、稳定的梯子,点击这里