女朋友问我什么是最优化原理(上)——系列连载(9)
后台回复"python",立刻领取100本机器学习必备的Python电子书!
泰勒定理
泰勒展开式
泰勒中值定理
梯度下降法
基本原理
梯度下降是一种简单、好用、经典的使用一阶信息的最优化方法(意味着相对低廉的计算成本),其基本原理可以想象为一个下山问题,当下降方向与梯度方向一致时,目标函数的方向导数最大,即此时目标函数在当前起点位置的下降速度最快。
基于梯度的优化算法通常有两个核心元素:搜索方向和搜索步长,并且一般都会和泰勒定理有某种联系,从泰勒中值定理可以得到下面的等式:
迭代框架
批量梯度下降
按照上面等式,每次迭代,为计算梯度值都需要把所有样本扫描一遍,收敛曲线类似下图:
From michaeljancsy
它的优点如下:
· 模型学习与收敛过程通常是平滑的和稳定的;
· 关于收敛条件有成熟完备的理论;
· 针对它有不少利用二阶信息加速收敛的技术,例如 conjugate gradient;
· 对样本噪声点相对不敏感。
它的缺点如下:
· 收敛速度慢;
· 对初始点敏感;
· 数据集的变化无法被学习到;captured.
· 不太适用于大规模数据。
随机梯度下降
完全随机梯度下降(Stochastic Gradient Descent,可以想想这里为什么用Stochastic而不用Random?)每次选择一个样本更新权重,这样会带来一些噪声,但可能得到更好的解,试想很多问题都有大量局部最优解,传统批量梯度下降由于每次收集所有样后更新梯度值,当初始点确定后基本会落入到离它最近的洼地,而随机梯度下降由于噪声的引入会使它有高概率跳出当前洼地,选择变多从而可能找到更好的洼地。收敛曲线类似下图:
From michaeljancsy
完全随机梯度下降和批量梯度下降的优缺点几乎可以互换:
· SGD的收敛速度更快;
· SGD相对来说对初始点不敏感,容易找到更优方案;
· SGD相对适合于大规模训练数据;
· SGD能够捕捉到样本数据的变化;
· 噪声样本可能导致权重波动从而造成无法收敛到局部最优 解,步长的设计对其非常重要。
实践当中,很多样本都有类似的模式,所以SGD可以使用较少的抽样样本学习得到局部最优解,当然完全的批量学习和完全的随机学习都太极端,所以往往采用对两者的折中。
小批量梯度下降
小批量梯度下降(Mini-batch Gradient Descent)是对SGD和BGD的折中,采用相对小的样本集学习,样本集大小随着学习过程保持或逐步加大,这样既能有随机带来的好处,又能使用二阶优化信息加速收敛,目前主流机器学习工具几乎都支持小批量学习。小批量学习收敛过程如下:
From michaeljancsy
牛顿法
从泰勒展开式可以得到带最优步长的迭代式:
Momentum
SGD的一大缺点是函数只和当前样本有关系,如果样本存在噪声则会导致权重波动,一种自然的想法就是即考虑历史梯度又考虑新样本的梯度:
对动量的运行过程说明如下:
· 在初始阶段,历史梯度信息会极大加速学习过程(比如 n=2时);
· 当准备穿越函数波谷时,差的学习率会导致权重向相反方 向更新,于是学习过程会发生回退,这时有动量项的帮助 则有可能越过这个波谷;
· 最后在梯度几乎为0的时候,动量项的存在又可能会使它 跳出当前局部最小值,于是可能找到更好的最优值点。
Nesterov accelerated gradient 是对动量法的一种改进,具体做法是:首先在之前的方向上迈一大步(棕色向量),之后计算在该点的梯度(红色向量),然后计算两个向量的和,得到的向量(绿色向量)作为最终优化方向。
From G. Hinton's lecture 6c
AdaGrad
Adagrad同样是基于梯度的方法,对每个参数给一个学习率,因此对于常出现的权重可以给个小的更新,而不常出现的则给予大的更新,于是对于稀疏数据集就很有效,这个方法常用于大规模神经网络,Google的FTRL-Proximal也使用了类似方法,可参见:Google Ad Click Prediction a View from the Trenches和Follow-the-Regularized-Leader and Mirror Descent:
Equivalence Theorems and L1 Regularization。
这个方法有点像L2正则,其运作原理如下:
· 在学习前期,梯度比较小regularizer比较大,所以梯度会被放大;
· 在学习后期,梯度比较大regularizer比较小,所以梯度会被缩小。
但它的缺点是,当初始权重过大或经过几轮训练后会导致正则化太小,所以训练将被提前终止。
AdaDelta
Adadelta是对Adagrad的改进,解决了以下短板:
· 经过几轮的训练会导致正则化太小;
· 需要设置一个全局学习率;
· 当我们更新,等式左边和右边的单位不一致。
对于第一个短板,设置一个窗口,仅使用最近几轮的梯度值去更新正则项但计算 太复杂,所以使用类似动量法的策略:
对其他短板,AdaDelta通过以下方法解决。
来源于Becker 和 LeCuns' 的hessian估计法:
完整的算法描述如下:
From Zeiler
对以上算法的比较如下:
From Karpathy
From SGD optimizationon loss surface contours
Adam
Adam是对Adadelta的改进,原理如下:
算法伪代码如下:
往
期
推
荐
2.机器学习原来这么有趣!【第二章】:用机器学习制作超级马里奥的关卡
7.机器学习从零开始系列连载(5)——Bagging and Boosting框架
扫描个人微信号,
拉你进机器学习大牛群。
福利满满,名额已不多…