线性代数|机器学习-P24加速梯度下降(动量法)

1. 概述

我们之前学的最速梯度下降[线搜索方法] 公式如下：
$$\begin{array}{c}{x}_{k+1}=x_k-s_k\nabla f(x_k)\end{array}$$
但对于这种方法来说，步长 $s_k$ 的选择是固定的，因为模型的参数太大，其损失函数具有不确定性，这样我们很难选择合适的步长$s_k$，

• 当我们的步长$s_k$太小，会导致需要很长的时间才能够找到极小值点或者最小值点
• 当我们的步长$s_k$太大，会导致我们迭代的点$P_{k+1}$在目标点$P^{\ast }$附件来回跳动。无法收敛。

根据上面的问题，我们今天研究下加速梯度下降的两种方法：

• Momentum 动量梯度下降法[这节主要内容]
• Nesterov 法[Momentum的变种]
• SGD[Stochastic gradient descent]随机梯度下降法
• mini-batch SGD [小批量随机梯度下降]

2. 引入

假设我们有如下函数$f(x)$
$$\begin{array}{c}f(x)=\frac{1}{2}{X}^{T}SX=\frac{1}{2}(x^2+b{y}^2),X=\left[\begin{array}{c}x\\ \\ y\end{array}\right]S=\left[\begin{array}{cc}1& 0\\ & \\ 0& b\end{array}\right]\end{array}$$

• 一次导数和二次导数如下：
  $$\begin{array}{c}\nabla f(x)=\frac{\partial \frac{1}{2}{X}^{T}SX}{\partial X}=SX=\left[\begin{array}{c}x\\ \\ by\end{array}\right]；{\nabla }^{2}f(x)=S=\left[\begin{array}{cc}1& 0\\ & \\ 0& b\end{array}\right]\end{array}$$
• 通过上面的函数可以看出，我们每次求的值可以表示如下：
  $$\begin{array}{c}f(x)=\frac{1}{2}(x^2+b{y}^2)=c\end{array}$$
• 此函数为一个椭圆，也就是说，我们是在不断地寻找最小的椭圆，如图所述：

• 假设我们定义初始点 $p_0=(x_0,y_0)=(b,1)$
• 步长$s_k=\frac{1}{x_0+y_0}=\frac{1}{b+1}$最后给出原因
  $$\begin{array}{c}{x}_k=b(\frac{b-1}{b+1}{)}^k,y_k=(\frac{1-b}{1+b}{)}^k,f_k=(\frac{1-b}{1+b}{)}^{2k}{f}_0\end{array}$$
• 梯度下降图解
  第一步我们是垂直于当前点$x_1$的负数切线方向$(-\nabla f(x_1))$进行迭代,计算值后，到达第二个点$x_2$，我们再找到垂直于第二个点的负切线方向$(-\nabla f(x_2))$,这样不断地迭代，就形成了如下图所示的Z字型的锯齿状迭代方向。
  
• 动量变化：
  $$\begin{array}{c}{b}_1=(\frac{1-b}{1+b}{)}^2\to b_2=(\frac{1-\sqrt{b}}{1+\sqrt{b}}{)}^2\end{array}$$
• 当b=1/100时，可得：
  $$\begin{array}{c}{b}_1=(\frac{99}{101}{)}^2;b_2=(\frac{9}{11}{)}^2;\to b_1>b_2\end{array}$$

3. 动量法梯度下降

• 迭代方程：$s_k$：步长，$z_k$：速度, $0<\beta <1$：惯量系数
  $$\begin{array}{c}\begin{array}{r}{x}_{k+1}=x_k-S{z}_k；\\ z_k=\nabla f_k+\beta z_{k-1};\end{array}\end{array}$$

• 我们之前算过$\nabla f_k=SX$,将$z_k$改为 $z_{k+1}$

• 我们定义矩阵S的特征向量为q,特征值为$\lambda$,整理可得：
  $$\begin{array}{c}\begin{array}{r}{x}_{k+1}=x_k-S{z}_k；\\ z_{k+1}-S{x}_{k+1}=\beta z_k;\end{array}\end{array}$$

• 矩阵化上述公式可得：
  $$\begin{array}{c}\left[\begin{array}{cc}1& 0\\ & \\ -S& 1\end{array}\right]\left[\begin{array}{c}{x}_{k+1}\\ \\ z_{k+1}\end{array}\right]=\left[\begin{array}{cc}1& -S\\ & \\ 0& \beta \end{array}\right]\left[\begin{array}{c}{x}_k\\ \\ z_k\end{array}\right]\end{array}$$

• 我们可以定义如下特征值和特征向量如下：
  $$\begin{array}{c}Sq=\lambda q,x_k=c_{k}q,x_{k+1}=c_{k+1}q,z_k=d_{k}q,z_{k+1}=d_{k+1}q;\end{array}$$

• 代入矩阵可得：
  $$\begin{array}{c}\left[\begin{array}{cc}1& 0\\ & \\ -S& 1\end{array}\right]\left[\begin{array}{c}{c}_{k+1}q\\ \\ d_{k+1}q\end{array}\right]=\left[\begin{array}{cc}1& -S\\ & \\ 0& \beta \end{array}\right]\left[\begin{array}{c}{c}_{k}q\\ \\ d_{k}q\end{array}\right]\end{array}$$

• 整理可得：
  $$\begin{array}{c}\left[\begin{array}{cc}1& 0\\ & \\ -\lambda & 1\end{array}\right]\left[\begin{array}{c}{c}_{k+1}\\ \\ d_{k+1}\end{array}\right]=\left[\begin{array}{cc}1& -S\\ & \\ 0& \beta \end{array}\right]\left[\begin{array}{c}{c}_{k}q\\ \\ d_{k}q\end{array}\right]\end{array}$$

• 整理可得：
  $$\begin{array}{c}\left[\begin{array}{c}{c}_{k+1}\\ \\ d_{k+1}\end{array}\right]=\left[\begin{array}{cc}1& 0\\ & \\ \lambda & 1\end{array}\right]\left[\begin{array}{cc}1& -S\\ & \\ 0& \beta \end{array}\right]\left[\begin{array}{c}{c}_{k}q\\ \\ d_{k}q\end{array}\right]\end{array}$$

• 整理可得：
  $$\begin{array}{c}\left[\begin{array}{c}{c}_{k+1}\\ \\ d_{k+1}\end{array}\right]=\left[\begin{array}{cc}1& -S\\ & \\ \lambda & -\lambda S+\beta \end{array}\right]\left[\begin{array}{c}{c}_k\\ \\ d_k\end{array}\right]\end{array}$$

• 将系数矩阵为R矩阵可得：
  $$\begin{array}{c}\left[\begin{array}{c}{c}_{k+1}\\ \\ d_{k+1}\end{array}\right]=R\left[\begin{array}{c}{c}_k\\ \\ d_k\end{array}\right]\end{array}$$ $$\begin{array}{c}R=\left[\begin{array}{cc}1& -S\\ & \\ \lambda & -\lambda S+\beta \end{array}\right]\end{array}$$

• 综上所示，对于迭代方程来说，S，$\beta$的选择直接会影响到矩阵R的大小，我们希望的是选择合适的S，$\beta$使得矩阵R的最大的特征值尽可能达到最小，假设矩阵R的特征值为$e_1,e_2$,则可得如下：
  ( S , β ) = arg min ⁡ S , β { max ⁡ ( ∣ e 1 ( λ ) ∣ , ∣ e 2 ( λ ) ∣ ) } , s t : λ min ⁡ ( S ) ≤ λ ≤ λ max ⁡ ( S ) \begin{equation} (S,\beta)=\argmin\limits_{S,\beta}\{\max(|e_1(\lambda)|,|e_2(\lambda)|)\} ,st:\lambda_{\min}(S)\le\lambda\le\lambda_{\max}(S) \end{equation} (S,β)=S,βargmin​{max(∣e1​(λ)∣,∣e2​(λ)∣)},st:λmin​(S)≤λ≤λmax​(S)​​

• 这里只给结论最好的$S,\beta$，后续研究：
  $$\begin{array}{c}s=(\frac{2}{\sqrt{{\lambda }_{\max }}+\sqrt{{\lambda }_{\min }}}{)}^2;\beta =(\frac{\sqrt{{\lambda }_{\max }}-\sqrt{{\lambda }_{\min }}}{\sqrt{{\lambda }_{\max }}+\sqrt{{\lambda }_{\min }}}{)}^2;\end{array}$$

• 之前我们的函数$f(x)=\frac{1}{2}{X}^{T}SX=\frac{1}{2}(x^2+b{y}^2)$中矩阵S, b < 1
  $$\begin{array}{c}{\lambda }_{\max }=1,{\lambda }_{\min }=b\end{array}$$

• 代入可得：
  $$\begin{array}{c}s=(\frac{2}{1+b}{)}^2;\beta =(\frac{1-\sqrt{b}}{1+\sqrt{b}}{)}^2;\end{array}$$

• 我们来看之前的梯度下降Ordinary descent factor：
  $$\begin{array}{c}{\beta }_1=(\frac{1-b}{1+b}{)}^2;\end{array}$$

• 动量法梯度下降 Accelerated descent factor
  $$\begin{array}{c}{\beta }_2=(\frac{1-\sqrt{b}}{1+\sqrt{b}}{)}^2;\end{array}$$

• 也就是当同等b时，动量法给的值更好！