Batch Gradient Descent

中心思想：沿着局部梯度的方向，迭代调整目标函数的参数，使得损失值最小化。

相关参数：

  • 样本量：所有训练数据

  • 目标函数：所有数据的平均损失，如MSE之和的平均

    损失之和的平均：L(θ)=1M∑i=1ML(f(xi,θ),yi)L(θ)=1M∑i=1M(yi−f(xi,θ))2损失之和的平均：L(\theta) = \frac{1}{M} \sum^M_{i=1}L(f(x_i, \theta),y_i) \\ L(\theta) = \frac{1}{M} \sum^M_{i=1}(y_i - f(x_i, \theta))^2

  • 局部梯度：L(θ)L(\theta) 在 θt\theta_t 处的导数 ∇L(θt)\nabla L(\theta_t)

  • 移动步长

    • 移动步长 = 学习率 * 当前梯度
    • 当参数接近最小值时，步长逐渐变小

参数更新：

模型参数的更新公式如下，其中α\alpha为学习率

θt+1=θt−α∇L(θt)\theta_{t+1} = \theta_t - \alpha \nabla L(\theta_t)

梯度更新的特点：

  1. 受到起始点的影响比较大，极有可能收敛到局部极值
  2. 步长太大可能使得函数无法收敛，在山谷间来回震荡
  3. 步长太小时需要大量的迭代次数，耗费时间

优缺点：

  • 缺点
    • 每次迭代都使用了所有数据进行计算，计算量大、时间成本大
    • 容易陷入局部极值点
  • 优点
    • 每次更新都朝着损失函数下降最快的方向移动，更新稳定。

优化的方向：

  1. 由于每次迭代的计算量过大，能否适当的减少计算量？==> SGD ==> Mini-Batch GD
  2. 能否更加贴近最优路径，从而更快到达地极值点？ ==> 牛顿法、Momentum、AdaGrad、RMSProp、Adam

Stochastic Gradient Descent

中心思想：为了减少计算量而提出。每一步在训练集中随机选择一个实例，基于该单个实例来计算梯度。

收敛性：BGD的收敛速度比SGD快，但数学家证明不超过1/k，因此其在计算所有数据的情况下提高效果并不明显，性价比太差。

优缺点：

  • 优点
    • 更新速度快，计算量较小，加快了收敛速度。
    • 随机大，因此有机会跳出局部最优解。
  • 缺点
    • 更新路线不稳定，有可能朝着与上次更新相反的方向前进。
    • 即使达到了最小值，由于迭代没有结束，也会持续反弹，使得最后停下来的结果可能不是最优的。

Mini-Batch GD

中心思想：提高稳定性的同时减少计算量而提出了小批量梯度下降，计算小部分数据的梯度。

batchsize的取值：2的次幂，32、64…等等。

优缺点：

  • 优点
    • 综合了上述两种优缺点。更新路线比SGD稳定，运行速度比BGD快。
  • 缺点
    • 难以摆脱局部最小值

Newton Method

中心思想：

在迭代过程中，找到参数 θt+1\theta_{t+1} 使得L(θt+1)<L(θt)L(\theta_{t+1}) < L(\theta_{t})。梯度下降法使用一阶法来估计LL。

牛顿法利用迭代点θt\theta_{t}处的一阶导数(梯度)和二阶导数( Hessen 矩阵)对目标函数进行二次函数近似，然后把二次模型的极小点作为新的迭代点，并不断重复这一过程，直至求得满足精度的近似极小值。

*也就是进行泰勒二阶在当前点展开后，计算极小值点，作为更好的估计值。

泰勒二阶展开推导：

更新公式：

参数更新公式如下。此时不需要学习率超参数，因为计算出来的结果恰好是二阶下极小点的位置。

θt+1=θt−∇2L(θt)−1∇L(θt)\theta_{t+1} = \theta_t - \nabla^2 L(\theta_t)^{-1} \nabla L(\theta_t)

优缺点：

  • 优点：更加接近最优的更新路线。如上图绿色线条为Newton法，灰色线条为最优路线，橙色线条为标准梯度下降法。、
  • 缺点：矩阵求解的计算量太大。

Momentum

分析下图可知，对于第一个和第二个更新点而言，横轴分量方向相同，纵轴方向相反，这是令更新反复震荡的主要原因。因此引出了优化目标：减弱纵轴的震荡幅度，增加横轴的移动距离，加快收敛速度。

主要思想：用历史数据上的分量对当前梯度进行修正，相同增强，相反抵消。同时，距离很久之前的训练数据对当前的影响要变小。整个更新过程具有一定的“惯性”。

更新公式：

再看上图的前两个更新点：

纵轴上，P2的梯度方向与P1相反，两者相加之后抵消，使得步长变短。

在横轴上，两者的梯度方向相同，相加之后步长增加。

加上β\beta可以削减距离久远的梯度影响。

优缺点：

  • 优点：适当减少了震荡

  • 缺点：有的时候会走弯路，当前梯度的方向和下一梯度的方向存在很大的夹角，如果能提前预知的话，可以使得更新路径更接近最优路径。

Nesterov

中心思想：扩展了momentum法，顺着惯性方向，计算未来可能位置处的梯度方向而非当前位置的，有机会使得收敛速度加快。

如下图所示，本来是求当前点的梯度（灰色点）。但加上红色框内数值后，将求得左图红色点的梯度，最后的移动方向如红色箭头指向。

上面几种方法的学习率一直是固定值，这有可能使得其在极值点附近来回震荡无法停止。最佳效果应该是一开始采用较大的学习率，步长较大，在接近最小值时学习率慢慢减小。

AdaGrad

中心思想：自适应地更新参数的学习率，不同参数的更新幅度不同。若历史数据修改的多，学习率减少的越多，相应的更新幅度减少。

更新公式：采用”历史梯度平方和“来衡量不同参数梯度的稀疏性，取值越小表明越稀疏，更需要更新。

数据呈现稀疏性：

例如，数据集在某一维度上的可利用信息很少，会导致梯度在多数情况下为0，该参数无法更新。如果其他参数的梯度比较大，则有可能出现震荡的情况。

优缺点：

  • 优点

    • 适合稀疏数据，在稀疏数据上的训练效果很好。
    • 随着时间推移，学习速率越来越小，保证了算法的最终收敛。

  • 缺点：考虑了所有历史数据。在经过一个平地之后，由于之前的梯度大多为0，之后的更新速度会变慢。

RMSProp

中心思想：优化AdaGrad方法，但同时参考了momentum，邻近点梯度的影响较大。如下图所示，经过平台期后的变化会逐渐加快。

更新公式：

使用指数衰退平均，用过往梯度的均值替代直接求和。

Adam

主要思想：将惯性保持和环境感知两个优点集于一身。

  • 考虑过往梯度与当前梯度，保持惯性。
  • 为不同参数产生自适应的学习率，同时时间久远的梯度对当前平均值的贡献成指数衰减。

*结合的是Momentum和RMSProp方法

更新公式：

分析：

  • Vt大St大，说明梯度大且稳定更新，此时在一个大坡上。
  • Vt趋于0, St大，说明梯度不稳定，可能遇到了峡谷，容易引起震荡。（这个我还没懂为啥
  • 两者都趋于0，说明可能到达了局部最低点，或者走到了一片平地。

相关问题

Q1. 梯度下降需要标准化的原因

左边的训练集上两特征具有相同的数值规模，损失函数等高线呈现正圆。

右边的训练集上特征1的数值比特征2小，呈现一个细长的碗状。每一步在横轴方向上的移动很小，因此移动的步数会增多，因此收敛时间也会变长。

*因为特征1的值比较小，它需要更大的变化来影响损失函数，这也是为什么呈现细长状的原因

Q2. 山谷和鞍点地形

山谷

  • 地形：狭长的小道，左右两边是峭壁（像上图的长碗，且两边高，中间低）
  • 特点：想象一下，峭壁向谷底的梯度大，因此更新的步长也更大。同一侧峭壁间的梯度小，更新步长也小。准确的梯度方向是沿着山道向下，但实际上变成在峭壁间反复震荡，而山道方向的下降速度慢。

鞍点

  • 地形：两头翘，与之垂直方向上两头垂。
  • 特点：四周的梯度变化不明显，有可能导致走错方向或者停下。