2017-11-22

机器学习-学科-最优化算法

最优化问题（如LR中的最大似然估计MLE求解）就是求一个极值点，是不是直接可以通过让其导数等于0就能找到极值点，我们为什么要采用这种梯度的渐进方式进行求解呢？

1. 首先很多时候我们无法确定数据集是否确定有极值点，找到解析解
2. 其次导数等于0也不代表其是全局最优解，尤其是在一些复杂的情况下，局部最优解非常多，这时候常规的梯度方法也无法解决，所以我们会有很多随机化方法像模拟退火之类，动量项之类，这些都可以应用到梯度上
3. 求导数=0的解并不是一件容易的事情，而且有些情况下即便能够求解，其时间复杂度也远远大于迭代寻优的方法

阅读本文前，建议可以看一下SofaSofa的这篇文章，关于GD、SGD、Mini-batch SGD有个直观的认识，这篇文章讲的非常生动！

机器学习之所以包含“学习”二字，是因为机器学习算法会尝试优化一项特定的指标：它们一般会努力将预测的误差最小化，或者说将预测正确的概率最大化。以下均属于非线性规划中的无约束优化问题的求解方法。

梯度

• 对于最优化问题的求解
• 梯度提升决策树方法簇

概览

• 梯度下降法 Gradient Descent
  • SGD(stochastic)
    • 梯度优化算法
      • Momentum
      • Adagrad ->每次通过，全局学习率逐参数的除以历史梯度平方和的平方根，使得每个参数的学习率不同
      • Adam
  • BGD(batch)
  • Mini-Batch GD
• 牛顿法（因为Hesse矩阵的计算量很大，一般不使用）
• 拟牛顿法（BFGS -> L-BFGS）
• 坐标下降法

batch, iteration与epoch

• 样本的数量
• batchsize 批大小。在深度学习中，一般采用SGD训练，即每次训练在训练集中取batchsize个样本训练
  • 数字越小时，此时就相当于来了一个样本，然后做一次更新，训练过程越接近随机梯度下降sgd
  • 数字越大时，训练越接近梯度下降，即每一次参数更新都要用到全部样本数据
• iteration 1个iteration等于使用batchsize个样本训练一次
• epoch 1个epoch等于使用训练集中的全部样本训练一次（每个epoch顺序可能是一致的，也有可能是不一致的）

GD

梯度下降法是从初始点的领域开始判断，在局部进行最速下降方向，然后步步逼近极值；所以往往会导致梯度下降法比牛顿法迭代的次数更多。

BGD

批量梯度下降和随机梯度下降的区别在于批量的话每次更新参数要用到每个样本（从对每个样本求和可以看到），而随机的话只用一个。

SGD

随机梯度下降（是梯度下降的batch版本，batch_size=1），在SGD中，每次迭代可以只用一个训练数据来更新参数。此时更新的算法，只用到了一个样本。其实具象的理解下，就是来了一条训练数据，算下此时根据模型算出的值和实际值的差距，如果差距大，那么参数更新的幅度大，反之则小。当训练数据过大时，用GD可能造成内存不够用，那么就可以用SGD了，SGD其实可以算作是一种online-learning。另外SGD收敛会比GD快，但是对于代价函数求最小值还是GD做的比较好，不过SGD也够用了。

SGD with Momentum

其实SAG就是SGD with momentum（带动量的随机梯度下降）的姊妹版本。SAG是对过去k次的梯度求均值。

SGD with momentum是对过去所有的梯度求加权平均（权重成指数衰减）。

Adam算法

AdaGrad

该优化算法与普通的sgd算法差别就在于采取了累积平方梯度，简单来讲，设置全局学习率之后，每次通过，全局学习率逐参数的除以历史梯度平方和的平方根，使得每个参数的学习率不同。

RMSProp——AdaGrad的改进

可以看出RMSProp优化算法和AdaGrad算法唯一的不同，就在于累积平方梯度的求法不同。RMSProp算法不是像AdaGrad算法那样暴力直接的累加平方梯度，而是加了一个衰减系数来控制历史信息的获取多少。

1. RMSProp是AdaGrad算法的改进。鉴于神经网络都是非凸条件下的，RMSProp在非凸条件下结果更好，改变梯度累积为指数衰减的移动平均以丢弃遥远的过去历史。
2. 经验上，RMSProp被证明有效且实用的深度学习网络优化算法。与AdaGrad相比，RMSProp增加了一个衰减系数来控制历史信息的获取多少。

牛顿法

在二阶导数的作用下，从函数的凹凸性出发，直接搜索怎样到达极值点。

牛顿迭代与梯度下降法的不同之处在于多了一项二阶导数。这个二阶导数对算法的影响有两个方面，方向和大小。方向，二阶导数的几何含义是曲率，也就是迭代的时候是考虑到梯度下降的方向的。大小，每次迭代的步长是和陡度成反比的，越陡步长越小，平坦的时候步长越大。

拟牛顿法

L-BFGS

引用

1. https://www.zhihu.com/question/19723347
2. https://www.zhihu.com/question/46441403
3. https://zhuanlan.zhihu.com/p/25703402
4. https://zhuanlan.zhihu.com/p/29895933

dzzxjl