优化算法(Optimization Algorithms)

mini-batch梯度下降(mini-batch gradient descent)

之前学过，向量化能够有效对所有m个训练样本进行计算，也就是允许处理整个训练集。

但是如果m很大的话，处理速度会变得较慢。

例如如果m是500万或5000万甚至更大的一个数，那么在对整个训练集执行梯度下降时，必须处理整个训练集，然后才能进行一步梯度下降。

如果在处理完所有训练集之前，先让梯度下降法处理一部分，算法速度会变得更快。

可以把训练集分成小一点的子集训练，这些子集被取名为mini-batch，相对应的之前训练全部数据集叫做batch梯度下降。

假设每个子集只有1000个样本，那么把其中的$x^{(1)}$到$x^{(1000)}$去程来，称为第一个子训练集，也叫作mini-batch，然后再取出1000个，以此类推。

把第一个子训练集，$x^{(1)}$到$x^{(1000)}$称为$X^{\{1\}}$，$x^{(1001)}$到$x^{(2000)}$称为$X^{\{2\}}$，以此类推。

即使用大括号{}来表示第几个子训练集。

如果训练样本有500万个，每个mini-batch有1000个样本，那么一共有5000个mini-batch。

$$X = [ \underbrace{ x^{(1)}, x^{(2)},\cdots,x^{(1000)} }_{X^{\{1\}}},|\underbrace{ x^{(1001)}, x^{(1002)},\cdots,x^{(2000)} }_{X^{\{2\}}},|\cdots,|\underbrace{\cdots,x^{(m)} }_{X^{\{5000\}}} ]$$

对Y也要进行同样处理。

$$Y = [ \underbrace{ y^{(1)}, y^{(2)},\cdots,y^{(1000)} }_{Y^{\{1\}}},|\underbrace{ y^{(1001)}, y^{(1002)},\cdots,y^{(2000)} }_{Y^{\{2\}}},|\cdots,|\underbrace{\cdots,y^{(m)} }_{Y^{\{5000\}}} ]$$

mini-batch的数量t组成了$X^{\{t\}},Y^{\{t\}}$。

$X^{\{t\}},Y^{\{t\}}$的维数：如果$X^{\{t\}}$是一个有1000个样本的数据集，那么维数是$(n_x, 1000)$。$Y^{\{t\}}$的维数都(1, 1000)。

使用mini-batch梯度下降其实和之前说的梯度下降基本一样，只是输入变成了$X^{\{t\}}$，数据集输出值变成了$Y^{\{t\}}$。

其余都不变。

使用一个循环for i =1 to 5000，来遍历整个训练集。整个循环结束后，称为一代(1 epoch)的训练，意味着遍历了依次训练集

使用batch梯度下降，遍历一次训练集只能做一次梯度下降，使用mini-batch梯度下降，遍历一次训练集可以做5000个梯度下降。

一般来说，还需要在for i=1 to 5000循环之外另设置一个循环，来多次遍历训练集，从而收敛到一个合适的精度。

理解mini-batch梯度下降

在使用batch梯度下降时，每次迭代都需要遍历整个训练集，可以预期，每次迭代成本值都会下降，所以代价函数应该会随着每次迭代而减少。

在使用mini-batch梯度下降时，如果画出成本函数在整个过程中的值，并不是每次迭代都会下降。因为在每次迭代时，处理的都是$X^{\{t\}},Y^{\{t\}}$，也就是每次迭代都在训练不同的样本集。所以在训练mini-batch梯度下降法时，会经过多代，可能会出现这样的曲线：走势总体向下，但是会产生一些噪声。

需要决定的变量是mini-batch，即每个子集mini-batch中训练样本的数量。

这是一个超参数。

如果mini-batch设为m，那么其实就是batch梯度下降，因为所有训练样本被看做一个mini-batch。

如果mini-batch设为1，那么就有新的算法，称为随机梯度下降法，每个样本都是一个mini-batch。随机梯度下降法平均来看，最终会接近最小值，但是会有很多噪声，而且会一直在最小值附近波动，不会达到最小值并停留。

实际上，mini-batch大小应该在1和m之间。

一般来说：

• 如果训练集较小，可以直接使用batch梯度下降法，也就是mini-batch = m；
• 如果训练集较大，那么mini-batch值可以尝试2的次方的值，例如64,128,256,512等，这主要是考虑到电脑内存的设置和使用方式。1024也可以，不过较为少见，64到512较为常见。

最后需要注意的是$X^{\{t\}}$和$Y^{\{t\}}$要符合CPU/GPU内存的大小。

指数加权平均(exponentially weighted averages)

在介绍其他优化算法时，需要涉及到指数加权平均这个概念。

指数加权平均，是一种计算平均值的方法。

比如有100天的温度值，要求这100天的平均温度值。

每天的温度值分别使用$v^1,v^2, \cdots, v^{100}$表示。

那么使用最常用的平均值求法是：

$$v_{aver} = \frac{v_1 + v_2 + \cdots + v_{100}}{100}$$

通过上面公式就可以求出这100天的平均值。

而指数加权平均本质就是一种近似求平均的方法。

先直接给出公式：

$$v_t = \beta v_{t-1} + (1- \beta)\theta_{t}$$

其中:$\boldsymbol{v_t}$代表到第t天的平均温度值， $\boldsymbol{\theta_t}$代表第t天的温度值，$\boldsymbol{\beta}$代表可调节的权重值。

$\boldsymbol{\beta}$一般可取0.9。

写出递推公式为：

$$v_0 = 0 \\ v_1 = \beta v_0 + (1- \beta)\theta_1 \\ v_2 = \beta v_1 + (1- \beta)\theta_2 \\ v_3 = \beta v_2 + (1- \beta)\theta_3 \\ \vdots \\ v_{100} = \beta v_{99} + (1- \beta)\theta_{100} \\$$

如图，计算$\boldsymbol{v_t}$时，前t项值$\boldsymbol{v_1, v_2, \cdots, v_{t-1}}$都参与了计算，但是因为前项系数的不同，不同值的贡献不同，且离t越远，贡献越小。

即指数加权平均就是以指数级递减加权的移动平均，各数值的加权随时间而指数级递减，越近期的数据加权越重，但较旧的数据也给予一定的加权。

而上面提到的平均数求法，每一项权重都相同，如果有n项，那么权重都为1/n。

指数加权平均的求解是一个递推过程，这样就会有一个很大的优点，每当要求从0到每一时刻n的平均值时，不需要使用平均值求法，保留所有的时刻值，累加再除n。

而是只保留0~(n-1)时刻的平均值和n时刻的温度值即可。这对于深度学习的海量数据来说，是一个很好减少内存和空间的做法。

理解指数加权平均

公式为：

$$v_t = \beta v_{t-1} + (1- \beta)\theta_{t}$$

将每天的温度和第几天作图可得：

当$\boldsymbol{\beta} = 0.9$时，得到红线；当$\boldsymbol{\beta} = 0.98$时，得到绿线；当$\boldsymbol{\beta} = 0.5$时，得到黄线。

进一步分析，令$\boldsymbol{\beta = 0.98 }$，那么可以写出指数加权平均的递推公式：

$$v_{100} = 0.9 v_{99} + 0.1\theta_{100} \\ v_{99} = 0.9 v_{98} + 0.1\theta_{99} \\ v_{98} = 0.9 v_{97} + 0.1\theta_{98} \\ \cdots \\$$

那么对于$v_{100}$来说，有：

$$\begin{aligned} v_{100} & =0.1\theta_{100} + 0.9 v_{99} \\ & = 0.1\theta_{100} + 0.9(0.1\theta_{99} + 0.9v_{98}) \\ & = 0.1\theta_{100} + 0.9(0.1\theta_{99} + 0.9(0.1\theta_{98} + 0.9v_{97}) ) \\ & \cdots \\ \end{aligned}$$

以此类推，如果把这些括号都展开，

$$v_{100} = 0.1\theta_{100} + 0.1\times0.9\theta_{99} + 0.1\times(0.9)^2\theta_{98} + 0.1\times (0.9)^3\theta_{97} +0.1\times (0.9)^4\theta_{96} + \cdots$$

所有的这些系数($0.1, 0.1\times(0.9)^2,\cdots$)相加为1或逼近1，称为偏差修正，后面会讲到。

可以发现，离的第一百天越远，权重越小。

实际上，$(0.9)^{10} \approx 0.35 \approx \frac{1}{e}$，也就是说，当$\beta = 0.9$，计算第100天的温度平均值时，基本是只关注了过去10天的温度，因为10天后，权重下降到不到当日权重的三分之一，可以忽略。

而当$\beta = 0.98$时，有$(0.98)^{50} \approx \frac{1}{e}$。也就是说，当$\beta = 0.98$，计算第100天的温度平均值时，大约平均了过去50天的温度。

由此可以得到一个公式，当计算某天温度平均值时，大概平均了前$\boldsymbol{\frac{1}{1- \beta}}$天的温度。不过这只是一个大致数字，并不是正式的数学证明。

偏差修正(Bias correction)

在指数加权平均中的计算初期，还以上面的温度计算为例子。

令$\beta = 0.98$。

则有：

$$v_0 = 0 \\ v_1 = 0.98v_0 + 0.02\theta_1 \\ v_2 = 0.98v_1 + 0.02 \theta_2$$

初始化$v_0 = 1$，因此$0.98v_0 = 0$，所以$v_1 = 0.02v_0$。

因此如果第一天温度是40度，则$v_1 = 0.02 \times 40 = 8$，得到的值会小很多，所以第一天的温度估测不准。

$v_2 = 0.98v_1 + 0.02 v_2$，如果带入$v_1$，$v_2 = 0.98\times0.02\theta_1 + 0.02\theta_2 = 0.0196\theta_1 + 0.02\theta_2$，假设$\theta_1,\theta_2$都是正数，则计算出的$v_2$要远小于$\theta_1,\theta_2$，所以$v_2$同意不能估计前两天的平均温度。

有个办法可以修改这一偏差，使得估测能够更准确，特别是在估测的初期。

不使用$v_t$，而是使用$\boldsymbol{\frac{v_t}{1-\beta^t}}$，t就是当前天数。

例如，当t=2时，$(1-\beta^t) = 1-{0.98}^2 = 0.0396$。

所以对第二天的温度估测变成：

$$v_2 = \frac{0.0196\theta_1 + 0.02\theta_2}{0.0396}$$

会发现，随着t增大，$\beta^t$接近于0，所以当t很大时，偏差修正几乎没有作用。

所以只会在估测的初期发挥作用，修正偏差。

在机器学习中，计算指数加权平均的大部分时候，大家并不在乎执行偏差修正，因为大部分人宁愿熬过初始时期，拿着具有偏差的估测，继续计算下去。

所以如果关心初始时期的偏差，就可以使用偏差修正；

如果不关心，则可以忽略，不使用偏差修正。

动量梯度下降法(Gradient descent with Momentum)

还有一种优化算法叫做Momentum，或者叫做动量梯度下降法。

运行速度几乎总是快于标准的梯度下降算法。

基本的思想是：计算梯度的指数加权平均数，然后利用计算的平均数更新权重。

例如，如果要优化代价函数，函数形状如图，红点代表最小值位置。

从某一点(图中蓝点)开始梯度下降，如果进行梯度下降法的一次迭代(batch或mini-batch)，可以看到图中会出现上下波动，慢慢地摆动到了最小值。

这种上下波动减慢了梯度下降的速度，也无法使用更大的学习率，因为如果是移动较大的学习率，可能会偏离函数的范围。就像下图这样。

另一个看待这个问题的角度是，在纵轴(上下方向)上，希望学习的慢一点，减少上下的摆动，而在横轴(左右方向)上，希望快速地从左向右移动，移到最小值。

所以使用动量梯度下降法，需要做的是，在每次迭代时：

$$v_{dW} = \beta v_{dW} + (1- \beta)dW \\ v_{db} = \beta v_{db} + (1- \beta)db \\ \\ W = W - \alpha v_{dW} \\ b = b - \alpha v_{db} \\$$

(这里省略了参数 迭代次数t)

有两个超参数：$\alpha,\beta$。$\beta$控制着指数加权平均数，$\beta$最常用的值时0.9.也就是平均了过去十次迭代的梯度值。

而关于偏差修正，一般不会再用$v_{dW}, v_{db}$除以$1-\beta^t$，因为十次迭代后，移动平均已经过了初始阶段。

实际上，在使用动量梯度下降法时，不会受到偏差修正的困扰。

当然$v_{dW}, v_{db}$的初始值都是0，其中$v_{dW}$和$dW$维度相同，也就是和$W$维度相同；而$v_{db}$的维度和$db,b$的维度相同。

在其他资料中，可能会看到一个其他版本的动量梯度下降法，$1-\beta$被删掉了。

$$v_{dW} = \beta v_{dW} + dW \\ v_{db} = \beta v_{db} + db \\$$

这两种版本的效果都不错，但是这个公式有一个影响，如果最后要调整超参数$\beta$，那么会影响到$v_{dW},v_{db}$，也许还需要修改学习率$\alpha$。

所以通常会使用上面的公式，也就是带着$1-\beta$。

RMSprop

RMSprop算法全称为root mean square prop算法，同样可以加快梯度下降。

以之前例子为例。

执行梯度下降，虽然横轴方向在接近最小值，但是纵轴方向会有大幅度摆动，为了分析这个例子，假设纵轴代表参数$b$,横轴代表参数$W$。可能有$W_1,W_2$或其他的参数，但是为了便于理解，只使用这两个参数。

所以，想要减缓纵轴方向的学习，同时加快(至少不是减缓)横轴方向的学习速度。

RMSprop算法中，在第t次迭代时，会照常计算当下mini-batch的微分$dW,db$。

并且使用新符号$S_{dW}, s_{db}$。

并有公式：

$$S_{dW} = \beta S_{dW} + (1- \beta)(dW)^2 \\ S_{db} = \beta S_{db} + (1- \beta)(db)^2 \\$$

这里的平方操作是Hadamard乘积，也就是维度相同矩阵对应位置元素相乘，得到一个同样维度的矩阵。

$C =A \bigodot B, C_{i,j} = A_{i,j}*B_{i, j}$

然后RMSprop会更新参数：

$$W = W - \alpha \frac{dW}{\sqrt{S_{dW} } } \\ b = b - \alpha \frac{db}{\sqrt{S_{db} } } \\$$

在横轴方向($W$方向)，希望能加快学习速度，而在纵轴方向($b$方向)，希望能减缓摆动。

因此有了$S_{dW}, S_{db}$。

代价函数图像上，垂直方向的微分或导数要比水平方向的大得多，所以斜率在$b$方向上较大，$W$方向上较小，从而$db$较大，$dW$较小。

因此$S_{dW}$会相对较小，这样除以一个较小的数，$W$的变化幅度就会比较大，从而加快学习速度。

而$S_{db}$会比较大，这样除以一个较大的数，$b$的变化幅度就会较小，从而减轻摆动。

要说明的是，把纵轴、横轴称为b和W，是为了方便展示。

实际中，参数是高维度的，$dW,db$都是一个高维度的参数向量。

要注意，在使用RMSprop时，要确保算法不会除以0，因此为了确保数值稳定，在实际中，在分母上加上一个很小很小的$\varepsilon$，$\varepsilon$是多少没关系，可以是$10^{-8}$。这只是为了保证数值稳定。

因此公式变为：

$$W = W - \alpha \frac{dW}{\sqrt{S_{dW} + \varepsilon } } \\ b = b - \alpha \frac{db}{\sqrt{S_{db} + \varepsilon } } \\$$

使用该算法的另一个好处是，可以使用一个更大的学习率$\alpha$，从而加快学习。

Adam优化算法

Adam算法将Momentum和RMSprop算法结合起来。

使用Adam算法步骤为：

1. 初始，$v_{dW} = 0, s_{dW} = 0, v_{db} = 0, s_{db} = 0$；

2. 在第t次迭代中，用当前mini-batch计算$dW,db$；

3. 计算Momentum指数加权平均数，

   $$v_{dW} = \beta_1 v_{dW} + (1- \beta_1)dW \\ v_{db} = \beta_1 v_{db} + (1- \beta_1)db \\$$

   ($\beta_1$是为了与后面RMSprop使用的参数区别开来)

4. 使用RMSprop更新，用超参数$\beta_2$，

   $$S_{dW} = \beta_2 S_{dW} + (1- \beta_2)(dW)^2 \\ S_{db} = \beta_2 S_{db} + (1- \beta_2)(db)^2 \\$$

5. 一般使用Adam算法时，要计算偏差修正，

   $$v_{dW}^{corrected} = \frac{v_{dW} }{1- \beta^{t}_1 } \\ v_{db}^{corrected} = \frac{v_{db} }{1- \beta^{t}_1 } \\$$

   同样，S也使用偏差修正，

   $$S_{dW}^{corrected} = \frac{S_{dW} }{1- \beta^{t}_2 } \\ S_{db}^{corrected} = \frac{S_{db} }{1- \beta^{t}_2 } \\$$

6. 更新参数，

   $$W = W - \alpha \frac{v_{dW}^{corrected} }{\sqrt{S_{dW}^{corrected} } + \varepsilon } \\ b = b - \alpha \frac{v_{db}^{corrected} }{\sqrt{S_{db}^{corrected} } + \varepsilon } \\$$

Adam算法结合了Momentum和RMSprop梯度下降法，是一种及其常见的学习算法，并证明能有效适用于不同神经网络。

本算法中有几个超参数：

• $\beta_1$：默认值为0.9；
• $\beta_2$：Adam算法论文作者建议值为0.999；
• $\varepsilon$：推荐使用$10^{-8}$，一般不需要修改，并不会影响算法性能；

上面三个超参数一般不需要修改。

通过调整超参数学习率$\alpha$来查看算法性能表现。

学习率衰减(Learning rate decay)

加快学习算法的一个办法就是随时间慢慢减小学习率，称为学习率衰减。

一个直观的理解是：

如果保持学习率固定，那么在梯度下降迭代时，每一步的下降幅度是基本相同的，最后可能会在最小值附近摆动，而不是收敛到最小值。

而如果慢慢减小学习率，那么在学习初期，下降幅度可以较大一些，当慢慢开始收敛时，较小学习率，从而尽快收敛。

将训练集拆分成不同的mini-batch，第一遍遍历整个数据集称为epoch 1，第二次遍历就是epoch 2，以此类推。

因此可以将遍历次数作为减小学习率的一个参数。

例如：

$$\alpha = \frac{\alpha_0}{1 + decayrate * epochnum}$$

其中decayrate称为衰减率，是一个超参数，epochnum是遍历次数，$\alpha_0$是初始学习率。

当然也有一些其他的学习率衰减公式：

$$\alpha = (0.95)^{epochnum} * \alpha_0$$

这个称为指数衰减，每经过一个epoch，学习率就小一点。0.95也可以为别的值，决定了幅度减缓的速度。

$$\alpha = \frac{k}{\sqrt{epochnum} } \alpha_0$$

这是另一个学习率衰减公式，k是一个超参数。

局部最优问题

在深度学习研究早期，在考虑局部优化时，通常会有这样一个图：

有两个参数，平面的高度就是损失函数，在图中似乎有很多局部最优点，梯度下降法可能会困在一个局部最优中，不会到达全局最优。

但这样的图其实并不正确，低维空间的图影响了对局部最优的理解。

事实上，一个神经网络代价函数梯度为零的点，通常不是上图的局部最优点，而是鞍点。

鞍点(saddle point)

一个不是局部最优点的驻点称为鞍点。

例如上图中的红点，就是鞍点(因为图片像马背上的马鞍，所以称为鞍点)。

因此对低纬度空间的大部分直觉，无法应用到高维度空间中。

如果有几万个参数，那么更可能遇到鞍点，而不是局部最优点。

由此带来的问题是：平稳段会减慢学习。

平稳段是一块区域，导数长时间接近于0，曲面很平坦，因此需要花费很长时间才能从曲面上下降。