女朋友问我什么是最优化原理(上)——系列连载(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的改进,原理如下:

算法伪代码如下:



1.机器学习原来这么有趣!【第一章】

2.机器学习原来这么有趣!【第二章】:用机器学习制作超级马里奥的关卡

3.机器学习从零开始系列连载(1)——基本概念

4.机器学习从零开始系列连载(2)——线性回归

5.机器学习从零开始系列连载(3)——支持向量机

6.机器学习从零开始系列连载(4)——逻辑回归

7.机器学习从零开始系列连载(5)——Bagging and Boosting框架

扫描个人微信号,

拉你进机器学习大牛群。

福利满满,名额已不多…

(0)

相关推荐