女朋友问我什么是最优化原理（上）——系列连载（9）

lujohn3li

发布于 2020-03-04 15:19:28

7320

发布于 2020-03-04 15:19:28

文章被收录于专栏：机器学习爱好者社区机器学习爱好者社区

泰勒定理‍

满足一定条件的函数可以通过泰勒展开式对其做近似：

泰勒展开式

泰勒展开式原理如下，主要采用分部积分推导：

泰勒中值定理‍

需要注意泰勒中值定理是一个严格的等式：

梯度下降法

基本原理

梯度下降是一种简单、好用、经典的使用一阶信息的最优化方法（意味着相对低廉的计算成本），其基本原理可以想象为一个下山问题，当下降方向与梯度方向一致时，目标函数的方向导数最大，即此时目标函数在当前起点位置的下降速度最快。

基于梯度的优化算法通常有两个核心元素：搜索方向和搜索步长，并且一般都会和泰勒定理有某种联系，从泰勒中值定理可以得到下面的等式：

迭代框架

批量梯度下降

按照上面等式，每次迭代，为计算梯度值都需要把所有样本扫描一遍，收敛曲线类似下图：

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。