Learning rate decay

$$\alpha =\frac{1}{1+decayRate\ast epochNum}\ast {\alpha }_0$$$$\alpha =0.95^{epochNum}\ast {\alpha }_0$$ $$\alpha =\frac{k}{\sqrt{epochNum}}\ast {\alpha }_0$$

SGD (stochastic gradient descent)

这里指 mini-batch gradient descent

$$W\leftarrow W-\eta \frac{\partial L}{\partial W}$$

• 其中 $\eta$ 为学习率

---

缺点：

• (1) SGD 依赖于一个较好的初始学习率，且容易陷入局部最优: SGD can reach a local minimum with high probability over the selection of the starting point, and all local minima attain similar loss values. However, the performance on test data, that is, generalizability, can be significantly different among these local minima.
  
• (2) 如果函数的形状非均向（anisotropic），比如呈延伸状，搜索的路径就会非常低效。根本原因是，梯度的方向并没有指向最小值的方向。 如下图所示，虽然最小值在 $(x,y)=(0,0)$ 处，但梯度在很多地方并没有指向 $(0,0)$，SGD 呈“之”字形移动。这是一个相当低效的路径
  

---

class SGD:
    def __init__(self, lr=0.01):
        self.lr = lr

    def update(self, params, grads):
        for key in params:
            params[key] -= self.lr * grads[key]

介绍更多优化方法之前的预热

指数加权平均（Exponentially weighted average）

• 如果我们想找一条线去拟合这个数据，该怎么去做呢？
• 我们知道某一天的气温其实和前几天（前一段时间）相关的，并不是一个独立的随机事件，比如夏天气温都会普遍偏高些，冬天气温普遍都会低一些。我们用 $[{\theta }_1、{\theta }_2、...、{\theta }_n]$ 表示第 1，2，…，$n$ 天的气温，于是有：
  根据上面的公式我们能够画出这条线，如下图所示：
  

---

• 指数加权平均（Exponentially weighted average） 的定义：
  $$V_t=\beta V_{t-1}+(1-\beta ){\theta }_t$$理解：
  
  • 由上式可以看出当 $t\to \infty$ 时各项的权重之和无限接近于 1
  • 因为 ${ϵ}^{\frac{1}{1-ϵ}}\approx \frac{1}{e}\approx 0.35$，所以过去 $\frac{1}{1-\beta }$ 个数据之后，权重下降至 0.35，可以忽略，相当于对过去 $\frac{1}{1-\beta }$ 个数据的加权平均
  • 当将 $\beta$ 设为 0.9 时，相当于对过去 10 个数据的加权平均
• 优点：实现简单且不用存过去$\frac{1}{1-\beta }$个数据的值

---

• 下面看下 $\beta$ 取值不同时曲线的拟合情况：
  
  • $\beta$ 较大时（$\beta$ = 0.98 相当于每一点前 50 天的平均气温），曲线波动相对较小更加平滑（绿色曲线），因为对很多天的气温做了平均处理，正因为如此，曲线还会右移
  • 当 $\beta$ 较小时（$\beta$ = 0.5 相当于每一点前 2 天的平均气温），曲线波动相对激烈，但是它可以更快的适应温度的变化

带偏差修正的指数加权平均 (bias correction in exponentially weighted average)

• 当我们令 $\beta$ = 0.98 时，我们想得到下图中的“绿线”，实际上我们得到的是下图中的“紫线”。对比这两条线，能够发现在“紫线”的起点相比“绿线”非常的低
  • 举个例子，如果第一天的温度是 40℃，按照上面的公式计算，$V_1=0.98V_0+(1-0.98){\theta }_1=0.98\times 0+0.02\times 40=0.8$，按照这个公式预估第一天的温度是 0.8℃，显然距离 40℃，差距非常大。同样，继续计算，第二天的温度也没有很好的拟合，也就是说 指数加权平均不能很好地拟合前几天的数据，因此需要偏差修正
    

---

• 带偏差修正的指数加权平均 (bias correction in exponentially weighted average)公式为：
  $$\begin{array}{rl}{V}_t& =\beta V_{t-1}+(1-\beta ){\theta }_t\\ V_t& =\frac{V_t}{1-{\beta }^t}\end{array}$$
  • 再来按照上述公式对前两天温度进行计算，$V_1=\frac{V_1}{1-{\beta }^1}=\frac{0.8}{1-0.98}=40$，能够发现温度没有偏差。并且当 $t\to \infty$ 时，${\beta }^t\to 0$，这样在后期 $V_t$ 就和没有修正的指数加权平均一样了

Momentum

• 动量的引入就是为了加快学习过程，特别是对于高曲率、小但一致的梯度，或者噪声比较大的梯度能够很好的加快学习过程。动量的主要思想是积累了之前梯度指数级衰减的移动平均（前面的指数加权平均）

---

SGD VS Momentum

• SGD 每次都会在当前位置上沿着负梯度方向更新（下降，沿着正梯度则为上升），并不考虑之前的方向梯度大小等等。而动量（moment）通过引入一个新的变量 $v$ 去积累之前的梯度（通过指数衰减平均得到），达到加速学习过程的目的
  

---

Momentum 公式

目前主要有两种形式，两种形式应该都可以

• (1) 原论文中的公式更贴近 “动量” 的物理意义
  $$\begin{gathered} v\leftarrow \alpha v-\eta \frac{\partial L}{\partial W} \\ W\leftarrow W+v \end{gathered}$$其中，$v$ 对应物理上的速度，$-\eta \frac{\partial L}{\partial W}$ 表示了物体在梯度方向上受力，在这个力的作用下，物体的速度增加这一物理法则。$\alpha v$ 这一项，在物体不受任何力时，承担使物体逐渐减速的任务（$\alpha$ 设定为 $0.9$ 之类的值），对应物理上的地面摩擦或空气阻力
• (2) pytorch, tensorflow 中的版本则是直接用移动指数加权平均去计算更新量
  $$\begin{gathered} v\leftarrow \beta v+(1-\beta )\frac{\partial L}{\partial W} \\ W\leftarrow W-\eta v \end{gathered}$$其中，$\beta$ 一般取 $0.9$; 移动指数加权平均来对网络参数平滑处理，让梯度的摆动幅度变小
  

---

• 下面以第一种形式进行实现：

class Momentum:
    def __init__(self, lr=0.01, momentum=0.9):
        self.lr = lr
        self.momentum = momentum
        self.v = None

    def update(self, params, grads):
        # initialization
        if self.v is None:
            self.v = {}
            for key in params:
                self.v[key] = np.zeros_like(params[key])

        for key in params:
            self.v[key] =  self.momentum * self.v[key] - self.lr * grads[key]
            params[key] += self.v[key]

Nesterov Momentum

• Nesterov Momentum 是对 Momentum 的改进，可以理解为 Nesterov 动量在标准动量方法中添加了一个校正因子

---

Momentum VS Nesterov

• Momentum
  
• Nesterov
  
• 可以看出 Nesterov 和 Momentum 相比唯一区别就是多了一步红色框框起来的步骤，在计算梯度之前先进行一次临时更新得到参数 $\tilde{\theta }$，然后用 $\tilde{\theta }$ 计算得到梯度。用一张图来形象的对比下 momentum 和 nesterov momentum 的区别：
  
  • Nesterov momentum. Instead of evaluating gradient at the current position (red circle), we know that our momentum is about to carry us to the tip of the green arrow. With Nesterov momentum we therefore instead evaluate the gradient at this “looked-ahead” position.

---

变形版本

• 但是，我们仔细观察上面的算法，你会发现一个很大的缺点，这个算法会导致运行速度巨慢无比，因为这个算法每次都要计算${\nabla }_{\theta }{\sum }_{i}L(f(x^{(i)};\theta +\alpha v),y^{(i)})$，这个相当于又要把 fp、bp 走一遍。 这样就导致这个算法的运行速度比 Momentum 要慢两倍，因此在实际实现过程中几乎没人直接用这个算法，而都是采用了变形版本，该变形版本在形式上近似于 Momentum 的标准实现

下面公式为原始公式
$$\begin{gathered} v_{t+1}=\beta v_t-\alpha {\nabla }_{{\theta }_t}L({\theta }_t+\beta v_t) \\ {\theta }_{t+1}={\theta }_t+v_{t+1}={\theta }_t+\beta v_t-\alpha {\nabla }_{{\theta }_t}L({\theta }_t+\beta v_t) \end{gathered}$$

• 其中 $\beta$ 为动量参数，$\alpha$ 学习率

下面进行公式的变形版本的推导:

• 令 ${\theta }_t^{{}^{\prime }}={\theta }_t+\beta v_t$，则 $v_{t+1}=\beta v_t-\alpha {\nabla }_{{\theta }_t}L({\theta }_t^{{}^{\prime }})$; 则：
  $$\begin{array}{rl}{\theta }_{t+1}^{{}^{\prime }}& ={\theta }_{t+1}+\beta v_{t+1}\\ & ={\theta }_t+v_{t+1}+\beta v_{t+1}\\ & ={\theta }_t+(1+\beta )v_{t+1}\\ & ={\theta }_t^{{}^{\prime }}-\beta v_t+(1+\beta )[\beta v_t-\alpha {\nabla }_{{\theta }_t}L({\theta }_t^{{}^{\prime }})]\\ & ={\theta }_t^{{}^{\prime }}+{\beta }^2{v}_t-(1+\beta )\alpha {\nabla }_{{\theta }_t}L({\theta }_t^{{}^{\prime }})\end{array}$$
• 下面就是这种变形版本的精明之处了： ${\theta }_t^{{}^{\prime }}={\theta }_t+\beta v_t$，而且初始速度为 0，即 $v_1=0$，同时模型在收敛时的速度 $v_t\approx 0$。也就是说在训练开始与训练结束的时候 ${\theta }_t^{{}^{\prime }}$ 与 ${\theta }_t$ 都近似是相等的，那么我们直接用 ${\theta }_t^{{}^{\prime }}$ 去替换 ${\theta }_t$ 就行了，即 ${\theta }_t^{{}^{\prime }}$ 可以看作是 ${\theta }_t$ 的一个完全等价的替换，我们在训练的时候根本就不用存储 ${\theta }_t$，一直都只更新 ${\theta }_t^{{}^{\prime }}$ 就可以了！这样，我们就可以在存储的参数值处求梯度，从而避免变量代换。因此用 ${\theta }_t$ 替换掉上面公式中的 ${\theta }_t{}^{\prime }$，就得出了下面的变形公式 (下面出现的 ${\theta }_t$ 其实都表示的是 ${\theta }_t^{{}^{\prime }}$)：
  $$\begin{array}{rl}{v}_{t+1}& =\beta v_t-\alpha {\nabla }_{{\theta }_t}L({\theta }_t)\\ {\theta }_{t+1}& ={\theta }_t+{\beta }^2{v}_t-(1+\beta )\alpha {\nabla }_{{\theta }_t}L({\theta }_t)\\ & ={\theta }_t+\beta v_{t+1}-\alpha {\nabla }_{{\theta }_t}L({\theta }_t)\end{array}$$可以看出由该变形公式实现的 Neterov 算法相比于标准的 Momentum 算法只是在 $v_t$ 和 ${\nabla }_{{\theta }_t}L({\theta }_t)$ 的系数上有所不同，$v_t$ 的系数由 $\beta$ 变为 ${\beta }^2$ (减小了)，${\nabla }_{{\theta }_t}L({\theta }_t)$ 的系数由 $-\alpha$ 变为 $-(1+\beta )\alpha$ (增大了)，在一定意义上减小了累积速度的作用
  • This anticipatory update prevents us from going too fast and results in increased responsiveness, which has significantly increased the performance of RNNs on a number of tasks.
  • It enjoys stronger theoretical converge guarantees for convex functions and in practice it also consistenly works slightly better than standard momentum.

---

class Neterov:
    def __init__(self, lr=0.01, momentum=0.9):
        self.lr = lr
        self.momentum = momentum
        self.v = None

    def update(self, params, grads):
        # initialization
        if self.v is None:
            self.v = {}
            for key in params:
                self.v[key] = np.zeros_like(params[key])

        for key in params:
            self.v[key] =  self.momentum * self.v[key] - self.lr * grads[key]
            params[key] += self.momentum * self.v[key] - self.lr * grads[key]

• 原书代码中的参数更新其实是这样的：

self.v[key] *= self.momentum
self.v[key] -= self.lr * grads[key]
params[key] += self.momentum * self.momentum * self.v[key]
params[key] -= (1 + self.momentum) * self.lr * grads[key]

• 这与上面推出的变形公式实现是不一样的，按公式来的话第三行中的 self.v[key] 应该为 $v_t$，而代码中用的却是 $v_{t+1}$。这里我还没搞清楚为什么 -_-

AdaGrad (Adaptive Gradient)

• 在神经网络的学习中，学习率的值很重要。学习率过小，会导致学习花费过多时间；反过来，学习率过大，则会导致学习发散而不能正确进行。在关于学习率的有效技巧中，有一种被称为 学习率衰减 learning rate decay 的方法，即随着学习的进行，使学习率逐渐减小
• AdaGrad 会为参数的每个元素适当地调整学习率，与此同时进行学习
  $$\begin{array}{rl}& \mathbf{h}\leftarrow \mathbf{h}+\frac{\partial L}{\partial \mathbf{W}}\odot \frac{\partial L}{\partial \mathbf{W}}\\ & \mathbf{W}\leftarrow \mathbf{W}-\eta \frac{1}{\sqrt{\mathbf{h}}}\frac{\partial L}{\partial \mathbf{W}}\end{array}$$
  • $h$ 保存了以前的所有梯度值的平方和 ($\odot$ 表示对应矩阵元素的乘法) (利用了二阶动量)
  • 在更新参数时，通过乘以$\frac{1}{\sqrt{h}}$，就可以调整学习的尺度。这意味着，参数的元素中变动较大（被大幅更新）的元素的学习率将变小。也就是说，可以按参数的元素进行学习率衰减，使变动大的参数的学习率逐渐减小

---

然而，AdaGrad 的缺点也很明显：

• 学习越深入，更新的幅度就越小。实际上，如果无止境地学习，更新量就会变为 0，完全不再更新
  

class AdaGrad:
    def __init__(self, lr=0.01):
        self.lr = lr
        self.h = None

    def update(self, params, grads):
        if self.h is None:
            self.h = {}
            for key in params:
                self.h[key] = np.zeros_like(params[key])

        for key in params:
            self.h[key] += grads[key] ** 2
            params[key] -= self.lr * grads[key] / (self.h[key] ** 0.5 + 1e-7) # 别忘了加上1e-7这个微小值!!!

RMSprop (root mean square prop)

$$h\leftarrow \beta h+(1-\beta )(\frac{\partial L}{\partial W}\odot \frac{\partial L}{\partial W})$$$$W\leftarrow W-\alpha \frac{1}{\sqrt{h}+ϵ}\frac{\partial L}{\partial W}$$

$ϵ$ 是为了防止分母为 0，取 1e−7

• RMSProp 方法并不是将过去所有的梯度一视同仁地相加，而是逐渐地遗忘过去的梯度，从而改善 AdaGrad 学习率的过早衰减问题
• This optimizer is usually a good choice for RNN

class RMSprop:
    def __init__(self, lr=0.01, decay_rate=0.99):
        self.lr = lr
        self.decay_rate = decay_rate
        self.h = None

    def update(self, params, grads):
        if self.h is None:
            self.h = {}
            for key in params:
                self.h[key] = np.zeros_like(params[key])

        for key in params:
            self.h[key] = self.h[key] * self.decay_rate + (1 - self.decay_rate) * grads[key] ** 2
            params[key] -= self.lr * grads[key] / (self.h[key] ** 0.5 + 1e-7) # 别忘了加上1e-7这个微小值!!!

Adadelta

Adadelta 是对 Adagrad 的改进，主要是为了克服 Adagrad 的两个缺点：

• the continual decay of learning rates throughout training
• the need for a manually selected global learning rate

---

• 为了解决第一个问题，Adadelta 只累积过去 $w$ 窗口大小的梯度，其实就是利用指数加权平均：
  $$s_{t+1}\leftarrow \rho s_t+(1-\rho )(\frac{\partial L}{\partial W}\odot \frac{\partial L}{\partial W})$$
  • $\rho =0.9$ 时，相当于累积前 10 个梯度
• 为了解决第二个问题，Adadelta 最终的公式不需要学习率 $\alpha$

---

Adadelta 的具体算法如下所示:

$$s_{t+1}\leftarrow \rho s_t+(1-\rho )(g_{t+1}\odot g_{t+1})$$$$g_{t+1}^{{}^{\prime }}\leftarrow \sqrt{\frac{\Delta x_t+ϵ}{s_{t+1}+ϵ}}\odot g_{t+1}$$$$x_{t+1}\leftarrow x_t-g_{t+1}^{{}^{\prime }}$$$$\Delta x_{t+1}\leftarrow \rho \Delta x_t+(1-\rho )g_{t+1}^{{}^{\prime }}\odot g_{t+1}^{{}^{\prime }}$$

• $\Delta x_t$ 用来记录自变量变化量 $g_t^{{}^{\prime }}$ 按元素平方的指数加权移动平均
• 可以看到，AdaDelta 和 RMSProp 的不同之处即在于使用 $\sqrt{\Delta x_t}$ 来代替学习率

class AdaDelta:
    def __init__(self, rho=0.9):
        self.rho = rho
        self.s = None
        self.delta = None

    def update(self, params, grads):
        if self.s is None:
            self.s = {}
            self.delta = {}
            for key in params:
                self.s[key] = np.zeros_like(params[key])
                self.delta[key] = np.zeros_like(params[key])

        for key in params:
            eps = 1e-7
            self.s[key] = self.rho * self.s[key] + (1 - self.rho) * (grads[key] ** 2)
            g = np.sqrt(self.delta[key] + eps) / np.sqrt(self.s[key] + eps) * grads[key]
            params[key] -= g
            self.delta[key] = self.rho * self.delta[key] + (1 - self.rho) * (g ** 2)

Adam (adaptive momentum estimation)

• Adam 结合了 Momentum 与 RMSProp，并且使用了偏差修正
  $$v_{t+1}\leftarrow {\beta }_1{v}_t+(1-{\beta }_1)g_{t+1}$$$$s_{t+1}\leftarrow {\beta }_2{s}_t+(1-{\beta }_2)g_{t+1}\odot g_{t+1}$$$$v_{t+1}^{correct}\leftarrow \frac{v_{t+1}}{1-{\beta }_1^{t+1}}$$$$s_{t+1}^{correct}\leftarrow \frac{s_{t+1}}{1-{\beta }_2^{t+1}}$$$$g_{t+1}^{{}^{\prime }}\leftarrow \frac{\alpha v_{t+1}^{correct}}{\sqrt{s_{t+1}^{correct}}+ϵ}$$$$x_{t+1}\leftarrow x_t-g_{t+1}^{{}^{\prime }}$$
• 标准设定值：$\alpha =0.001,{\beta }_1=0.9,{\beta }_2=0.999,ϵ=10^{-8}$
  

class Adam:
    def __init__(self, lr=0.001, beta1=0.9, beta2=0.999):
        self.lr = lr
        self.beta1 = beta1
        self.beta2 = beta2
        self.v = None
        self.s = None
        self.iter = 0 # 更新次数

    def update(self, params, grads):
        if self.v is None:
            self.v = {}
            self.s = {}
            for key in params:
                self.v[key] = np.zeros_like(params[key])
                self.s[key] = np.zeros_like(params[key])

        self.iter += 1

        for key in params:
            self.v[key] = self.beta1 * self.v[key] + (1 - self.beta1) * grads[key]
            self.s[key] = self.beta2 * self.s[key] + (1 - self.beta2) * (grads[key]**2)

            unbias_v = self.v[key] / (1 - self.beta1 ** (self.iter))
            unbias_s = self.s[key] / (1 - self.beta2 ** (self.iter))

            params[key] -= self.lr * unbias_v / (np.sqrt(unbias_s) + 1e-8)

AdamW (Adam with decoupled Weight decay)

• AdamW 等价于 Adam + weight decay (L2 正则化)，但是计算效率更高，因为 L2 正则化需要在 loss 中加入正则项，而 AdamW 直接将 L2 正则项的梯度加入反向传播的公式中，省去了手动在 loss 中加正则项这一步
  

参考文献

• 《深度学习入门 – 基于 Python 的理论与实现》
• 几种梯度下降方法对比（Batch gradient descent、Mini-batch gradient descent 和 stochastic gradient descent）
• 深度学习中优化方法——momentum、Nesterov Momentum、AdaGrad、Adadelta、RMSprop、Adam
• CS231n Convolutional Neural Networks for Visual Recognition
• Bengio, Yoshua, Nicolas Boulanger-Lewandowski, and Razvan Pascanu. “Advances in optimizing recurrent networks.” 2013 IEEE international conference on acoustics, speech and signal processing. IEEE, 2013.
• 9987 用Theano实现Nesterov momentum的正确姿势
• Adadelta: Zeiler, Matthew D. “Adadelta: an adaptive learning rate method.” arXiv preprint arXiv:1212.5701 (2012).
• 自适应学习率调整：AdaDelta
• Adam: Kingma, Diederik P., and Jimmy Ba. “Adam: A method for stochastic optimization.” arXiv preprint arXiv:1412.6980 (2014).
• Adam 和 AdamW 的区别