机器学习系列（八）- 优化梯度下降法

• 视频参考：“随机梯度下降、牛顿法、动量法、Nesterov、AdaGrad、RMSprop、Adam”，打包理解对梯度下降法的优化
• 参考知乎：比Momentum更快：揭开Nesterov Accelerated Gradient的真面目
• 参考CSDN：深度学习优化函数详解（5）– Nesterov accelerated gradient (NAG)

梯度下降法优化方法

• 调整神经网络结构，如增加池化层，$Dropout$ 层。
  • 池化层：特征不变性；特征降维；在一定程度上防止过拟合发生；
  • $Dropout$ 层：一般加在全连接层，防止过拟合；提升模型泛化能力；
• 优化梯度下降法算法自身（本篇文章根据该点展开）

随机梯度下降法（$mini-batch$）

• 梯度下降法每次计算整个数据集，而随机梯度下降法则是抽样部分数据（一批）计算，减少计算量。
• 时间复杂度：虽然梯度下降法收敛速度快于随机梯度下降法，但时间复杂度最快不超过 $\frac{1}{k}$，与随机梯度下降法相近，计算量大且收益小。
  1. 凸问题：$f(x^k)-f^{\star}=O(\frac{1}{\sqrt{k}})$
  2. 强凸问题：$f(x^k)-f^{\star}=O(\frac{1}{k})$

  $k$ 表示迭代次数，$f^\star$ 表示极值点，$O$ 表示时间复杂度

牛顿法

• 寻找优于线性梯度下降的下降曲线，牛顿法将多维度同时考虑。

一维情况

• 理解

  1. 由上图可知，线性梯度下降为橙色直线；最优线性梯度下降为灰色直线；则存在优于线性梯度下降曲线，即绿色曲线；
  2. 梯度下降曲线在一定范围内优于线性梯度下降，当超出范围则劣于线性梯度下降；
  3. 当梯度下降曲线取值 $\Delta x$ 时，为曲线上最优解，即导数为零；

• 公式推导

  1. $f(x)$ 泰勒展开保留二阶导：$f(x)=J(a_0)+J’(a_0)(x-a_0)+J’‘(a_0)(x-a_0)^2$

  2. 求 $f(x)$ 极值，即对 $(x-a_0)$ 求导，令 $f’(x)=0$ ，则

     $f’(x)=J’(a_0)+J’‘(a_0)(x-a_0)=0 \Rightarrow x=a_0-\cfrac{J’(a_0)}{J’‘(a_0)}$

     其中 $\Delta x = \cfrac{J’(a_0)}{J’‘(a_0)}$

  3. 故可得公式：$W=W-\cfrac{J’(a_0)}{J’‘(a_0)}=W-\Delta x$ ；

多维情况

• 公式：$W=W-\Delta^2J(W)^{-1}·\Delta J(W)$

  其中 $\Delta J(W)$ 为一阶偏导； $\Delta^2J(W)^{-1}$ 为二阶偏导矩阵的逆，因作为分母则求逆矩阵。

• $\Delta J(W)=[\cfrac{\partial J}{\partial W_1},\cfrac{\partial J}{\partial W_2},\cdots,\cfrac{\partial J}{\partial W_n}]$

• $\Delta^2J(W)$ 是 $Hessian$ 矩阵 $H(W)$ ，其中

  $H(W)=\begin{bmatrix} \cfrac{\partial}{\partial W_1}\cfrac{\partial f}{\partial W_1} & \cfrac{\partial}{\partial W_2}\cfrac{\partial f}{\partial W_1} & \cdots & \cfrac{\partial}{\partial W_n}\cfrac{\partial f}{\partial W_1} \newline \cfrac{\partial}{\partial W_1}\cfrac{\partial f}{\partial W_2} & \cfrac{\partial}{\partial W_2}\cfrac{\partial f}{\partial W_1} & \cdots & \cfrac{\partial}{\partial W_n}\cfrac{\partial f}{\partial W_2} \newline \vdots & \vdots & \ddots & \vdots \newline \cfrac{\partial}{\partial W_1}\cfrac{\partial f}{\partial W_n} & \cfrac{\partial}{\partial W_2}\cfrac{\partial f}{\partial W_n} & \cdots & \cfrac{\partial}{\partial W_n}\cfrac{\partial f}{\partial W_n} \end{bmatrix}$

牛顿法将多维数据同时考虑计算，计算量极大；以下方法均依次考虑单个维度。

动量法（冲量法）

• 利用历史数据优化梯度方向

  

• 公式推导

  1. 原式为：$W_{[t]}=W_{(t-1)}-\eta·\Delta J$ ，对应分量计算

     $\begin{bmatrix} b_{t} \newline W_{[t]1} \newline W_{[t]2} \newline \vdots \newline W_{[t]n} \end{bmatrix} = \begin{bmatrix} b_{[t-1]} - \eta·\frac{\partial J}{\partial b} \newline W_{[t-1]1} - \eta·\frac{\partial J}{\partial W_1} \newline W_{[t-1]2} - \eta·\frac{\partial J}{\partial W_2} \newline \vdots \newline W_{[t-1]n} - \eta·\frac{\partial J}{\partial W_n} \end{bmatrix}$

  2. 令 $\Delta W_{[t]i}=\cfrac{\partial(W_{[t-1]i})}{\partial W_i}$ ，则 $W_{[t]i}=W_{[t-1]i}-\eta·\Delta W_{[t]i}$

  3. 令 $V_{[t]}=V_{[t-1]}+\Delta W_{[t]i}$ ，表述为该分量历史改变的和；

  4. 因历史数据对现梯度影响意义较小，故作加权处理；使用指数加权移动平均法，推导出

     $V_{[t]}=\beta ·V_{[t-1]}+(1-\beta)·\Delta W_{[t]i}$

  5. 则原式改为： $W_{[t]i}=W_{[t-1]i}-\eta·V_{[t]}$

• 设 $\beta=0.9$，则展开可得

  $V_{[t]}=0.1·0.9^0·\Delta W_{[t]i}+0.1·0.9^1·\Delta W_{[t-1]i}0.1·0.9^2·\Delta W_{[t-2]i}+\cdots+0.1·0.9^{t-1}·\Delta W_{[1]i}$

  $0.1·0.9^{t-1}$ 接近 $0$，历史数据对结果影响越来越小；

$Nesterov$ 方法（牛顿冲量法）

• 超前参考未来数据优化梯度方向

• 公式推导

  1. $V_{[t]}=\beta ·V_{[t-1]}+(1-\beta)·\Delta W_{[t]i}$ ，其中

     $\Delta W_{[t]i}=\cfrac{\partial(W_{[t-1]i})}{\partial W_i}$ 转变为 $\Delta W_{[t]i}=\cfrac{\partial(W_{[t-1]i}+\gamma V_{[t-1]})}{\partial W_i}$

     目标点为 $W_{[t-1]i}-\eta·V_{[t]}$ ，则超前预测点为 $W_{[t-1]i}+\gamma V_{[t-1]}$ ，故所求梯度为目标点相近的超前预测点的梯度

  2. 公式依然为： $W_{[t]i}=W_{[t-1]i}-\eta·V_{[t]}$

$AdaGrad$ 方法

• 参考历史数据优化学习步长，该算法适合稀疏数据

• 公式

  $W_{[t]i}=W_{[t-1]i}-\cfrac{\eta}{\sqrt{S_{[t]}+\varepsilon}}·\Delta W_{[t]i}$ ；$\varepsilon$ 为极小值，避免分母为 $0$；其中

  $S_{[t]}=S_{[t-1]}+\Delta W_{[t]i}·\Delta W_{[t]i}$

  $\Delta W_{[t]i}=\cfrac{\partial(W_{[t-1]i})}{\partial W_i}$

$RMSprop$ 方法

• 在 $AdaFrad$ 方法的基础上，对学习率做指数加权平均法优化

• 公式

  $W_{[t]i}=W_{[t-1]i}-\cfrac{\eta}{\sqrt{S_{[t]}+\varepsilon}}·\Delta W_{[t]i}$ ；其中

  $S_{[t]}=\beta ·S_{[t-1]}+(1-\beta )·\Delta W_{[t]i}·\Delta W_{[t]i}$

$Adam$ 方法

• 结合 $RMSprop$ 方法与动量法

• 公式

  $W_{[t]i}=W_{[t-1]i}-\cfrac{\eta}{\sqrt{S_{[t]}+\varepsilon}}·\Delta W_{[t]i}$ ；其中

  $V_{[t]}=\beta_1 ·V_{[t-1]}+(1-\beta_1)·\Delta W_{[t]i}$

  $S_{[t]}=\beta_2 ·S_{[t-1]}+(1-\beta_2 )·\Delta W_{[t]i}·\Delta W_{[t]i}$

$Nadam$ 方法

• 结合 $RMSprop$ 方法与 $Nesterov$ 方法