23年版前言
本文最初发布于2018年,然因今23年年初在写ChatGPT笔记故而研究RL,研究RL又开始系统重修微积分、概率统计,然后就注意到了此文,仔细审视本文之前18年的版本之后,发现写的和网上不少千篇一律的同类优化文章没啥区别,按好懂、好理解的标准本文得全部推倒重写,故便有了目前的23年修订版。
修订版注重两点:
- 好懂、好理解,要求每一句话都是人话,不说模棱两可、或人云亦云、千篇一律的说明解释
- 每一个公式的符号要求准确、统一,不要小看这点,比如网上大量关于SGD的文章,很多符号表示乱七八糟的且不各自一套符号表示,比如这种,两个 表示的可不是同一个概念
不啰嗦,请看23年修订版吧
第一部分 梯度下降法
1.1 梯度下降法的应用背景:经常遇到求解函数极值的问题
求函数极值是经常要面对的一个问题,比如当我们要做一个房屋价值的评估系统,那都有哪些因素决定或影响房屋的价值呢?比如说面积、房子的大小(几室几厅)、地段、朝向等等,这些影响房屋价值的变量被称为特征(feature)。
为了简单,我们假定房屋只由一个变量影响,那就是房屋的面积。假设有一个二线城市的房屋销售的数据如下:
面积() | 销售价钱(万元) |
123 | 250 |
150 | 320 |
87 | 160 |
102 | 220 |
… | … |
我们可以做出一个图,轴是房屋的面积,轴是房屋的售价,如下:
如果来了一个新的房子/面积,假设在房屋销售价格的记录中没有的,我们怎么办呢?我们可以用一条曲线去尽量准的拟合这些数据,然后如果有新的输入面积,我们可以在将曲线上这个点对应的值返回
如果用一条直线去拟合房屋价格数据,可能如下图这个样子:
而图中绿色的点就是我们想要预测的点。
为了数学建模,首先给出一些概念和常用的符号
- 房屋销售记录表–训练集(training set)或者训练数据(training data),是我们流程中的输入数据,一般称为
- 房屋销售价钱–输出数据,一般称为
- 拟合的函数(或者称为假设或者模型),一般写做
- 训练数据的条目数(#training set),一条训练数据是由一对输入数据和输出数据组成的
- 输入数据的维度(特征的个数,#features),
然后便是一个典型的机器学习的过程,给出一个输入数据,算法会通过一系列的过程得到一个估计的函数,这个函数有能力对没有见过的新数据给出一个新的估计
我们用去描述feature里面的分量(为特征数目),比如=房间的面积,=房间的朝向等等,我们可以做出一个估计函数:
在这儿称为参数( 表示第 个权重),在这儿的意思是调整feature中每个特征的权重/影响力,代表到底是房屋的面积更重要还是房屋的地段更重要,而的上标 表示第个训练样本
为评估模型好坏,需要一个机制去评估是否比较好,相当于对函数进行评估,一般这个进行评估的函数称为损失函数(loss function),用于描述函数不好的程度,这里设为函数
换言之,我们把对的估计值与真实值差的平方和作为损失函数,前面乘上的系数是为了方便求导(且在求导的时候,这个系数会消掉),至于 表示的是样本的数量,决定你是用10套房子的各项数据训练这个函数,还是用100套房子的各项数据训练这个函数,比如当时,
如何调整以使得取得最小值有很多方法,其中有最小二乘法(min square),是一种完全是数学描述的方法,另外一种就是梯度下降法,那到底什么是梯度下降法呢?
维基百科给出的定义是梯度下降法(Gradient descent)是一个一阶最优化算法,通常也称为最速下降法。 要使用梯度下降法找到一个函数的局部极小值,必须向函数上当前点对应梯度(或者是近似梯度)的反方向的规定步长距离点进行迭代搜索
如果相反地向梯度正方向迭代进行搜索,则会接近函数的局部极大值点,从而被称为梯度上升法
我个人觉得啊,如果此前从来没有接触过『梯度下降』这4个字的,看完上面这段话后之后除了懵懵懂懂可能也不会剩啥了,其实想从零理解梯度下降,则先理解什么是方向导数、什么是梯度
1.2 什么是方向导数和梯度
说出来你可能不信,方向导数和梯度其实在我们大学时学的高等数学下册上有讲,之所以忘了肯定有多种原因,但对于不少人而言是教材讲得不够通俗易懂所以当时理解的不够深刻,所以,还是一步步来吧:导数 偏导数 方向导数 梯度
- 首先,在一元函数中的某一点A,对改点求导,即是过改点切线的斜率
- 其次,所谓偏导数,是针对二元函数而言,如果只有自变量变化,而自变量固定(即把看做常理),这时相当于的一元函数,此时对的导数就称为偏导数
记作,,或 - 最后,这个在A点在这个方向上也是有切线的,其切线的斜率就是方向导数
- 然有个小问题就是,针对曲面上A这个点的切线是可以有很多条的,那到底什么是梯度呢? 所谓的梯度是一个矢量,其方向上的方向导数最大,其大小正好是此最大方向导数(配图来自知乎上的马同学)
这个时候,你是不就能回忆起高数教材上对于梯度的定义了
设函数在平面区域内具有一阶连续偏导数,则对每一点,都可以定出一个向量
则该向量称为在点处的梯度,记作,或
1.3 按最好懂、最易懂的标准从零推导梯度下降法
通过导数的定义,当想求极小值或极大值时,则是看导数即切线斜率为0的点
而偏导数也是类似的,让函数取得极小值的必要条件是
然问题就在于一元函数的导数好求,但二元函数的导数在实际中经常不好求解,而梯度下降(也称最速下降)则提供了求解函数极小值的一个间接求解思路(求极大值则通过梯度上升),即其本质是为了确定最快下降的方向,从而最快达到极小值
很多文章(包括本文的18年版本)在介绍梯度下降法的时候,都会用上这个配图,然后举这个例子,即一个人蒙着眼睛从山顶往下走,山脚下有个湖,然后梯度下降的目标就是最快走到山脚下的湖
- 具体做法是每走到一个位置的时候,求解当前位置的梯度,沿着梯度的负方向(即当前最陡峭的位置向下,这个最陡峭很关键,毕竟你也可以一直斜着走下山)走一步
就这样,每要走一步都根据上一步所在的位置选择当前最陡峭最快下山的方向走下一步,一步步走下去,一直走到我们感觉已经到了山脚 - 总之,梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向,因为该方向为当前位置的最快下降方向,所以也被称为是“最速下降法”。最速下降法越接近目标值,步长越小,前进越慢
值得一提的是,下山这个例子其实不如泉水下山更形象(或者天黑后,打着手电筒最快下山,毕竟谁没事蒙着眼睛下山呢)
- 比如水受重力影响,会在当前位置,沿着最陡峭的方向流动,有时会形成瀑布(梯度的反方向为函数值下降最快的方向)
- 水流下山的路径不是唯一的,在同一个地点,有可能有多个位置具有同样的陡峭程度,而造成了分流(可以得到多个解)
- 遇到坑洼地区,有可能形成湖泊,而终止下山过程(下文1.4节会解释具体为何不一定能得到全局最优解,而是局部最优解)
看起来很简单不是,还是不要大意了,把理论抽象建模成数学问题还是有一段距离的,以下咱们从零推导出梯度下降法(可能是你网上所能见过最好懂、最易懂的推导过程了,毕竟不少阐述混乱不堪甚至是错误的)
- 想象一个乒乓球在一个斜坡上面,你需要不断变化乒乓球所处位置的,使得乒乓球以最快速度滚落到斜坡底部(相当于要求解最陡峭的方向从而通过最短路径达到斜坡底部) 当变化时,变化时,函数的变化值为
注意,理解此处的非常重要,首先别忘了咱们的目标是为了让不断减小,相当于无论怎么变化都是一个负值,那么想要减小最快,则意味着得更快最小,所以咱们的目标就变为了让更快最小 - 接下来,又得唤醒下你的高数记忆了,你可曾还记得微分..,假定你已经忘了,回顾一下 第一步,在定义微分的时候,我们知道当变化到时,函数的变化量,可表示为,其中为常数,且我们把定义为微分
好比一个边长为的正方形,当边长增加时,原正方形的面积增加: 第二步,再把式子的两边都除以个,可得
当时,上式可得,这就是导数的定义
第三步,最终可以写成
所以当很小时,是不有着,由于故可得,,从而有 - 有了这个重要结论后,再扩展到二元函数时,可得当、很小时 这个结论相当重要啊,此举便意味着我们在步骤1的
- 这个时候该说另一个小概念了,向量内积总还记得吧?
阶段3最后的结果是不是可以理解为两个向量、內积的结果,而两个向量的方向相反时,內积的结果是最小的,意味着啥呢?意味着可达到最小(即减小的最快)
相当于当从向移动时,要想减小的最快,则需满足如下关系 也可简写为,其中为正的微小常数,俗称学习率或步长 举个小例子,假定函数,那使该函数减少最快的向量是多少呢,直接套用公式便是,当,则此时让函数减小最快的方向便是
此外,如果扩展到过个变量的情况则如下表达,设变量改变为,当满足以下关系式时,函数减小的最快
而这些向量即称为在处的梯度
1.4 梯度下降算法的具体应用
回到1.1节最后那个问题,现在我们要最小化
通过梯度下降求解的步骤如下:
- 首先对赋值,这个值可以是随机的,也可以让是一个全零的向量
- 改变的值,使得按梯度下降的方向进行减少,具体而言是
先对函数求偏导
没看明白?其具体推导如下(设定,)
接下来,更新,向着梯度最小的方向进行减少,表示更新之前的值,后面的部分表示按梯度方向减少的量,表示步长或学习率learning rate,也就是每次按照梯度减少的方向变化多少
推广到个样本,且有个权重时,则是
- 一个很重要的地方值得注意的是,梯度是有方向的,对于一个向量,每一维分量都可以求出一个梯度的方向,我们就可以找到一个整体的方向,在变化的时候,我们就朝着下降最多的方向进行变化就可以达到一个最小点,不管它是局部的还是全局的
用更简单的数学语言进行描述是这样的:
为了描述的更清楚,给出下面一个表示参数与误差函数的关系图,红色的部分是表示有着比较高的取值,我们需要的是,能够让的值尽量的低,也就是达到深蓝色的部分(让误差/损失最小嘛),、表示向量的两个维度
- 梯度下降法的第一步是给给一个初值,假设随机给了两个初值,一个左侧的十字点,一个右侧的十字点
- 对于图中顶部左侧的十字点,我们将按照梯度下降的方向进行调整,就会使得往更低的方向进行变化(如上图左侧的路径曲线所示),算法的结束将是在下降到无法继续下降为止
- 对于图中顶部右侧的十字点,可能梯度下降的最终点并非是全局最小点,即也可能是一个局部最小点(如上图的右侧曲线所示)
意味着,算法在很大的程度上会被初始点的选择影响而陷入局部最小点
也就是说,梯度下降法并不一定是下降最快的方向,它只是目标函数在当前的点的切平面(当然高维问题不能叫平面)上下降最快的方向。在practical implementation中,牛顿方向(考虑海森矩阵)才一般被认为是下降最快的方向,可以达到superlinear的收敛速度。梯度下降类的算法的收敛速度一般是linear甚至sublinear的(在某些带复杂约束的问题)。
正因为梯度度下降法在接近最优解的区域收敛速度明显变慢,所以利用梯度下降法求解需要很多次的迭代
第二部分 从批量梯度下降(BGD)到随机梯度下降(SGD)、小批量梯度下降(MBGD)
2.1 批量梯度下降(BGD)
普通的梯度下降算法在更新回归系数时要遍历整个数据集,是一种批处理方法,这样训练数据特别忙庞大时,可能出现如下问题:
- 收敛过程可能非常慢,毕竟梯度下降公式中的误差是针对于所有训练样本而得到的(相当于目标函数是训练数据集中每个样本的损失函数的平均值,注意这个求和函数,即为对所有样本进行计算处理)
-
然后对每个参数 、、...、运用梯度下降法:
相当于更新一个 需要遍历整个样本集
如果误差曲面上有多个局极小值,那么不能保证这个过程会找到全局最小值
2.2 随机梯度下降
2.2.1 什么是随机梯度下降
为了解决上面的问题,实际中我们应用的是梯度下降的一种变体被称为随机梯度下降
而随机梯度下降的思想是根据每个单独的训练样本来更新权值『换言之,如果每次迭代过程中都要对 n个样本进行求梯度,开销会非常大,而随机梯度下降的思想就是随机采样一个样本来更新参数,计算开销从 O(n)下降到 O(1)』,这样我们上面的梯度公式就变成了:
经过推导后,我们就可以得到最终的权值更新的公式:
有了上面权重的更新公式后,我们就可以通过输入大量的实例样本,来根据我们预期的结果不断地调整权值,从而最终得到一组权值使得我们的算法能够对一个新的样本输入得到正确的或无限接近的结果
比如其代价函数可为
参数更新为:
相当于(是样本编号,m为样本数目,是样本维数下标,所以更新一个只需要一个样本就可以,所以这里没有求和符号了)
下面两幅图可以很形象的对比各种优化方法在损失曲面上的表现(图来源:http://sebastianruder.com/optimizing-gradient-descent/):
从上图可以看出, Adagrad、Adadelta与RMSprop在损失曲面上能够立即转移到正确的移动方向上达到快速的收敛。而Momentum 与NAG会导致偏离(off-track)。同时NAG能够在偏离之后快速修正其路线,因为其根据梯度修正来提高响应性。
此外,如何优化随机梯度法呢?详情请点击:论文公开课第一期:详解梯度下降等各类优化算法(含视频和PPT下载)
2.2.2 SGD的收敛:平均损失-迭代次数与学习率α选择
在随机梯度下降中,我们在每一次更新θ前都先计算一下损失函数cost(),并绘制平均损失和迭代次数的图表,用图表我们可以评估模型学习情况,损失下降情况。
譬如我们可以采用这种方式,每经过1000个数据样本,算一次平均损失,将平均损失和当前迭代的轮数作为坐标绘图,我们绘制的图表可能如下图所示:从左至右分别命名为图1、图2、图3和图4
- 图一,假设我们的数据集大小为1000,蓝色图像为SGD的损失曲线,可以看出学习效果不错,模型最终趋于收敛(即损失不再降低),那此时如果我们改用更小的学习率来训练模型,得出的可能是红色曲线,我们发现,红色曲线下降到了更低的损失点,表面模型更优(同时也表明,蓝色曲线只是收敛到了局部最优解而不是全局最优解)
- 图二,蓝色的曲线是正常SGD的损失曲线,此时我们不改变学习率,只是简单地将绘图间隔改为每5000个数据点一次,则我们可能会发现,绘制出的图(红色曲线)更为平滑。(因为拓宽了间隔,会导致cost变化幅度更服从整体,即趋于平滑)
- 图三,蓝色曲线是SGD曲线,不过从曲线来看,模型并没有收敛,此时我们可以同样增加间隔至5000,此时绘制出的曲线如红色,可以看出,虽然损失下降的比较慢,不过还是正常下降的,即模型是正常学习的。如果画出的曲线如粉色线,那么则表明模型训练出了问题。可能是数据集、学习率、特征等情况需要调整。
- 图四,蓝色曲线是SGD曲线,很明显是异常的,损失不降反升,我们可以尝试减小学习率
我们也可以令学习率随着迭代次数的增加而减小,例如令:
相当于用两个常量+迭代次数来构造学习率的公式,使得随着迭代次数的增加,公式分母增加,学习率逐渐减小
理论上来说,学习率越小越好,学习率越小,则意味着每次迭代过程损失降低的较小,即向全局最优点前进的步伐越小,从而不容易导致陷入“局部最优解”的情况。但是不可能一开始就将α设置的很小,不然模型训练时间将大大增加,而且通常在模型训练的前期,损失降低的越快,此时利用较大的可以迅速降低loss,加快训练速度,因此便可以采用式子中的方式,逐渐降低α的方式来训练
2.3 小批量梯度下降
小批量梯度下降Mini-Batch Gradient Descent 算法是介于传统梯度下降算法(批量梯度下降)和随机梯度下降算法之间的算法,每计算常数b次训练实例,便更新一次参数θ
换言之,对于每更新一次θ,传统梯度下降算法 遍历整个数据集m个样本,SGD则每更新一次θ 遍历1个样本,而小批量梯度下降每更新一次θ 遍历b个数据样本,b取值范围通常介于2~100之间
举个例子,数据集有数据1000个,我们可以采取每批10个数据进行梯度下降:
第三部分 牛顿法、拟牛顿法、共轭梯度
3.1 牛顿法
// 23年5.7日update:以下部分待更
3.2 拟牛顿法
3.3 共轭梯度
4 参考文献与推荐阅读
- 如何直观形象地理解方向导数与梯度以及它们之间的关系?
- 什么是梯度下降法?
- 梯度下降法 —— 经典的优化方法
- 为什么说随机最速下降法(SGD)是一个很好的方法?
- 《深度学习的数学》
- 如何理解随机梯度下降(stochastic gradient descent,SGD)?
- 理解梯度下降法、梯度下降法、牛顿法和拟牛顿法、随机梯度下降SGD
- 动手学深度学习:7.2. 梯度下降和随机梯度下降
- 第十周—大规模机器学习和随机梯度下降算法
23年版后记
近期一直看各种数学教材、数学讲解书,数学教材的优点是追求严谨尽量不出错,缺点则因优点而起 丧失了可读性 通俗性,从而导致大部分大学生在学数学时基本都是死记硬背,没有理解或理解不深,特别是工作多年想从传统IT转行AI的,则第一关就是复习数学,成了难关
至于网上各种资料虽然是围绕数学教材做各种解释说明,但兼顾可读性和准确性的,就相对少了。