理解机器学习中常用优化方法

理解机器学习中常用优化方法

最优化方法是一种数学方法,它是研究在给定约束之下如何寻求某些因素(的量),以使某一(或某些)指标达到最优的一些学科的总称。

大部分的机器学习算法的本质就是建立优化模型,通过最优化方法对目标函数(或损失函数)进行优化,从而训练出最好的模型。

梯度下降法

梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向,因为该方向为当前位置的最快下降方向,所以也被称为是”最速下降法“。注意这里的最快下降不是全局来说,只是针对当前位置。

最速下降法和梯度下降还是有区别的,梯度下降法可以看作是欧式范数(2)下的最速下降法。此外最速下降的步长t是直线搜索的当前的最优步长,梯度下降一般提前指定,t为固定步长。

搜索方向为什么选负梯度方向

回忆:向量的方向可以用方向角向量进行表示, 阅读了解 矩阵求导常用公式 Hessian矩阵 Jacobian矩阵 | Oath2yangmen’s Blog

方向导数角度

方向导数代表多元函数在各个方向上的变化率,梯度是方向导数最大的方向。所以负梯度方向是当前位置下降最快方向。

阅读参考 为什么梯度下降法每次找到的都是下降最快的点-忆臻的回答

一阶泰勒展开+柯西-施瓦茨不等式角度

梯度下降推导

最速下降法的搜索路径

搜索路径一般呈直角锯齿,新点处的梯度与搜索方向垂直。

梯度下降搜索路径

从任意迭代点A1出发,沿其负梯度方向T1一维搜索到极小点A2,则A2点应为向量与目标函数等值线的切点。下次迭代从点A2出发,沿其负梯度方向一维搜索,根据梯度方向的性质可知应是目标函数等值线在A2点的法线T2,因而T1与T2必为正交向量。这就表明,梯度法迭代过程中前后两次迭代向量为正交。故梯度法迭代过程是呈直角锯齿形路线曲折走向目标函数的极小点。

当目标函数的等值线接近一个圆(球)时,最速下降法下降较快,当等值线是个扁长的椭圆(球)时,最速下降法刚开始几步比较快,后来出现锯齿变的缓慢。圆上的任意点的切线的法线都指向圆心最小值点,而椭圆不一定。

解决直角锯齿搜索的方法

选择合适的初始点

锯齿现象和初始点有关,举个例子:当该点的梯度方向和等值线的切线的法线指向全局最小点时,一步到位。如何选择初始点是个很难的问题。

不精确的一维搜索

比如梯度下降法采用定长的t,而未采用最速下降里直线搜索使得下降最大的t。

三种梯度下降优化框架

批量梯度下降(Batch gradient descent)

优点是每次更新都会朝着正确的方向进行,最后能够保证收敛于极值点(凸函数收敛于全局极值点,非凸函数可能会收敛于局部极值点),但是其缺点在于每次学习时间过长,并且如果训练集很大以至于需要消耗大量的内存,并且全量梯度下降不能进行在线模型参数更新

随机梯度下降(Stochastic gradient descent)

每次的学习是非常快速的,并且可以进行在线更新。随机梯度下降最大的缺点在于每次更新可能并不会按照正确的方向进行,因此可以带来优化波动(扰动)。

不过从另一个方面来看,随机梯度下降所带来的波动有个好处就是,对于类似盆地区域(即很多局部极小值点)那么这个波动的特点可能会使得优化的方向从当前的局部极小值点跳到另一个更好的局部极小值点,这样便可能对于非凸函数,最终收敛于一个较好的局部极值点,甚至全局极值点。

由于波动,因此会使得迭代次数(学习次数)增多,即收敛速度变慢。不过最终其会和全量梯度下降算法一样,具有相同的收敛性,即凸函数收敛于全局极值点,非凸损失函数收敛于局部极值点。

小批量梯度下降(Mini-batch gradient descent)

相对于随机梯度下降,Mini-batch梯度下降降低了收敛波动性,即降低了参数更新的方差,使得更新更加稳定。相对于全量梯度下降,其提高了每次学习的速度。并且其不用担心内存瓶颈从而可以利用矩阵运算进行高效计算。

梯度下降法的缺点

靠近极小值时速度减慢。

直线搜索可能会产生一些问题。

可能会“之字型”地下降。

选择一个合理的学习速率很难。如果学习速率过小,则会导致收敛速度很慢。如果学习速率过大,那么其会阻碍收敛,即在极值点附近会振荡。

学习速率调整(又称学习速率调度,Learning rate schedules)试图在每次更新过程中,改变学习速率,如退火。一般使用某种事先设定的策略或者在每次迭代中衰减一个较小的阈值。无论哪种调整方法,都需要事先进行固定设置,这边便无法自适应每次学习的数据集特点。

模型所有的参数每次更新都是使用相同的学习速率。如果数据特征是稀疏的或者每个特征有着不同的取值统计特征与空间,那么便不能在每次更新中每个参数使用相同的学习速率,那些很少出现的特征应该使用一个相对较大的学习速率。

对于非凸目标函数,容易陷入那些次优的局部极值点中,如在神经网路中。

对于后面的几个缺点,在深度学习神经网络中,对梯度下降求解方法进行了各自优化。可参考【干货】机器学习最常用优化之一——梯度下降优化算法综述搜狐科技搜狐网

牛顿法

从梯度下降法可以知道,负梯度方向不能说是一个特别好的方向,牛顿法提出的方向要比负梯度更具有全局性。

牛顿法搜索方向推导

牛顿法推导

牛顿法和梯度下降法

阅读了解 椭球范数范数与距离的关系以及在机器学习中的应用 - CSDN博客
梯度下降法是欧式范数下的最速下降,牛顿法是椭球范数下的最速下降。

牛顿法的几点说明

图片来自 本章要点:最速下降法的基本思想及特点牛顿方向Newton法 - 道客巴巴

牛顿法几点说明

一维搜索牛顿法

针对上面的说明,在牛顿法中加入一维搜索。

一维搜索牛顿法

牛顿法优缺点

牛顿法收敛快,但每次需要存储二阶导数矩阵,且需要对其求逆运算。大规模场景下存储和计算代价太大,所以适合中小规模场景的算法。

MarQuart法

MarQuart法将牛顿法和最速下降法相结合,在初始时采用最速下降,靠近最小值点时采用牛顿法。

MarQuart法

拟牛顿法

为了避免每次循环都需要算Hessian矩阵并求逆运算,所以提出了拟牛顿方法。通过拟合一个近似的Hessian矩阵来求牛顿方向。

在学习过程中,参考了几个资料,在某些方面资料之间有些出入。几点说明里会写查了其他资料后我对出入的地方的理解

资料 牛顿法与拟牛顿法学习笔记(二)拟牛顿条件 - CSDN博客
逻辑回归:从入门到精通
wiki-Limited-memory_BFGS
wiki-BFGS
wiki-DFP

拟牛顿条件

拟牛顿条件

DFP

DFP推导

BFGS

BFGS推导

L-BFGS

L-BFGS推导-1

L-BFGS推导-2

L-BFGS的两步循环方法

下面两个资料写的很详细,可阅读:

逻辑回归:从入门到精通
wiki-Limited-memory_BFGS

几点说明

BFGS和DFP的区别

DFP拟合的是Hessian矩阵的逆,BFGS拟合的是Hessian矩阵本身并最终利用Sherman-Morrison公式直接推出直接从Dk的逆到Dk+1的逆

BFGS比DFP好在哪

BFGS和DFP都有一定能力进行自我修正,如果某个位置选择的矩阵不好,在未来几步,可以自我修正。这个能力,BFGS比DFP效果要好,这也是BFGS比较常用的原因。

换句话理解就是DFP有时候会震荡,而互换了y和s之后的BFGS更稳定,BFGS有自校正的性质(self-correcting property)。通俗来说,如果某一步BFGS对Hessian阵的估计偏了,导致优化变慢,那么BFGS会在较少的数轮迭代内(取决于线搜索的质量),校正估计的Hessian阵。

L-BFGS占用的存储空间

需要存储前m个 Si 和 Yi, 还有第k次的梯度gk。二次循环过程中的alpha, p, r。
其实要说的是初始的Hessian矩阵到底怎么取,取D0? 取 Dk-m?当然Dk-m肯定不行,为了省存储提出的L-BFGS方法,不会存储o(n^2)的Dk-m。所以这里需要一个对Dk-m的估计,与直接取D0 = I 相比,下面的近似好很多。

wiki-L-BFGS

各自的优缺点

BFGS和DFP一个比较好的性质是,如果H_k是正定的,则下一个Hk+1也是正定的,可以从公式中推导出来。不好的地方就是:需要存储这个对称矩阵。

L-BFGS需要的存储空间更小。

OWL-QN

QWL-QN 可阅读 逻辑回归:从入门到精通

由于L1正则项 | X | 在0点不可微,所以L-BFGS不能直接用来求解L1正则问题。QWL-QN方法通过定义伪梯度,将搜索限定在Xk的某个象限内,也就是说限定了Xk的每一项的正负,此时| X | 变成了一个线性项。

wiki-QWL-QN


0 Comments