Mini-batch梯度下降
Q：为什么Mini-batch比普通的梯度下降快？
普通的梯度下降——vanilla gradient descent，是将整个数据集同时做运算，而Mini-batch梯度下降算法是以一组为单位，分别进行梯度下降，所有组执行完毕后再进行下一次迭代。
假设现在有m个样本。 \[
X = \begin{pmatrix}x^1&x^2&x^3&\cdots&x^m\end{pmatrix}\\
Y = \begin{pmatrix}y^1&y^2&x^3&\cdots&y^m\end{pmatrix}\\
\] 使用Mini-batch，假设每1000个样本为一组： \[
X = \begin{pmatrix}\underbrace{x^1\cdots x^{1000}}_{X^{\{1\}}} & \underbrace{x^{1001}\cdots x^{2000}}_{X^{\{2\}}} & \cdots&\underbrace{\cdots x^m}_{X^{\{t\}}}\end{pmatrix}\\
Y = \begin{pmatrix}\underbrace{y^1\cdots y^{1000}}_{Y^{\{1\}}} & \underbrace{y^{1001}\cdots y^{2000}}_{Y^{\{2\}}} & \cdots&\underbrace{\cdots y^m}_{Y^{\{t\}}}\end{pmatrix}\\
\] 如果使用代码实现就是类似下面这样的伪代码： 1
2
3
4
5for t = 1, ..., t
forwardprop on X^{t}
compute cost
backprop to compute grads
update weights and bais
理解mini-batch
1. 如果将batch设为m，那它就是普通的梯度下降算法。 2. 如果将batch设为1，就叫做随机梯度下降——SGD 3. batch在1到m之间就是mini-batch
SGD和普通梯度下降的区别，“+”代表代价最小点。 
SGD和mini-batch的区别。 
应该记住的有：
- 普通梯度下降、mini-batch和SGD之间的区别就是执行一次参数更新所需的样本数量不同。
- 你需要自己调整学习速率\(\alpha\)。
- 当mini-batch的量调整良好时，它通常优于普通梯度下降和SGD（尤其是在训练集特别大时）。
mini-bacth实现步骤
- 打乱数据。创建一个打乱数据之后的副本，其中X和Y的每一列都代表一个训练样本。注意X和Y是同步地随机打乱样本，即X中第\(i^{th}\)个样本和Y中第\(i^{th}\)标签在打乱之后还是是对应的。此步骤确保样本被随机地分割到不同的mini-batches中。下图是步骤示意图：
- 切分。将打乱数据后的XY切分进
mini_batch_size大小（下图是64）的mini-batches中。不过注意训练样本的数量并不总能被mini_batch_size整除。最后的mini-batch可能要小点，但是不需要担心这点。使用math.floor()向上取整即可。
一些经验
如果小数据量（大约小于2000）的话，只执行步骤1即可；如果样本数目较大，执行步骤1和步骤2，一般将batch设置在64~512之间，考虑到电脑的内存设置和使用方式，batch的大小设置为2的次方，代码的运行速度会比较快；
指数加权平均
为了更好地理解其他优化算法，需要使用到指数加权平均。这章介绍一下它。
Exponentially weighted averages，在统计学中被称为指数加权移动平均——Exponentially weighted moving averages。
指数加权平均有一个公式：\(V_t = \beta * V_{t-1} + (1- \beta) * \theta_t\)，\(V_0 = 0\)，其目的是使用\(V_t\)代替\(\theta_t\)。\(V_t\)可视为约等于\(\frac{1}{1 - \beta}\)个样本的平均值。这里可能会有疑问，为什么\(V_t\)可视为约等于\(\frac{1}{1 - \beta}\)个样本的平均值？将 \(1 - \beta\) 除到等式左边，可以看到 \(\frac{1}{1 - \beta} V_t \approx \theta_t\)。
下图中的数据为伦敦一年之间的温度，来源于吴恩达的深度学习视频，可以看到其中的数据十分杂乱，也就是常在网络上看到别人所说的“噪点”多。我们可以使用指数加权平均来画出一条线，就是下图的红线，来代表温度变化的趋势，这样会使得更容易让人类理解和观察。
下图中的\(\beta\)为0.9。而\(\frac{1}{1 - 0.9} = 10\)，所以\(V_t\)代表过去十天内的平均温度。如果\(\beta\)为0.98，那么\(V_t\)代表过去五十天内的平均温度 
下图是不同\(\beta\)值的对比。注意到一点，绿色（\(\beta\)=0.98）的线比红色的线要平坦一点，这是因为你多平均了几天的温度，所以这根线波动更新、更平坦。但是缺点是曲线进一步向右移，拟合的不是很好。 
现在看到了平均了10天和50天温度的曲线，现在试试\(\beta=0.5\)，也就是只平均两天的温度。由于只平均了两天的温度，数据太少，所以曲线有更多的噪声，更有可能出现异常值。但是这个曲线能更快适应温度变化。 
理解其作用
略。至今看不懂。
偏差修正
之前的曲线其实都是理想状态下的，回想绿色的曲线是50天内的温度平均值。但是其实绿色曲线会是紫色曲线那样的轨迹。初始化\(V_0=0\)，原数据中\(\theta_0 = 40\)，所以其实\(V_1 = 0.02 * 40 = 8\)，从而绿色曲线的起点实际上很低。因为起点并没有计算50天内的温度平均，我们默认将\(V_0\)初始化为0。
我们可以用下图右边的公式将其修正。算出\(V_t\)后再做如下计算：\(\frac{V_t}{1 - \beta^t}\)，其中\(\beta\)的上标t是指t次方。
另外由于t越大，\(\beta^t\)的值越接近0，所以对后面的值几乎没影响。 
优化算法总结
| 算法 | 介绍 |
|---|---|
| SGD | 问：为什么 SGD 比 batch gradient descent 快？答：因为 SGD 可以使用极小的 epoch 更新多次权重，而 BGD 必须要大 epoch 才可以。详见此处 |
| 优点： 1）在损失函数是凸函数的情况下能够保证收敛到一个较好的全局最优解；2）数据量过大时，batch 方法可以减少机器压力，从而更快地收敛；3）当训练集有很多冗余时（类似的样本出现多次），batch方法收敛更快。 缺点： 1）\(\alpha\) 是一个定值，它的选取直接决定了解的好坏，过小会导致收敛太慢，过大会导致震荡而无法收敛到最优解；2）对于非凸问题，只能收敛到局部最优，并且没有任何摆脱局部最优的能力（一旦梯度为0就不会再有任何变化）；3）更新方向完全依赖当前的 batch |
|
| Momentum | 累积梯度，充当动量，注：虽然 Momentum 和 RMSprop 类似，但是实际上在计算上并不一样， RMSprop 要多一个除以 \(\sqrt{S_{dW}} + \epsilon\) 的步骤，且没有偏差修正这一步骤 |
| 优点：1）一定程度上缓解了 SGD 收敛不稳定的问题，并且有一定的摆脱局部最优的能力（即如同一个滚轮下坡一样，它拥有惯性，在到达鞍点时不会立即停止，会因为惯性再向前一点距离，从而可能离开此鞍点）。 缺点：1）多了一个超参数需要调整，它的选取同样会影响到结果。 |
|
| RMSprop | 通过除以 \(\sqrt{S_{dW}} + \epsilon\) 减小波动幅度从而收敛更快 |
| 优点：1）不需要手动调整学习率，可以自动调整。 | |
| Adam | 优点：1）结合 Momentum 和 RMSProp，稳定性好，同时相比于 Adagrad 不用存储全局所有的梯度，适合处理大规模数据。 缺点：1）有三个超参数需要调整 |
| Adagrad | RMSProp 的简化版 适用场景：Adagrad非常适合处理稀疏数据（如 one-hot） |
| 优点：1）不需要手动调节 \(\alpha\)，它会发生自适应的变化。 缺点：1）学习率单调递减，在迭代后期可能导致学习率变得特别小而导致收敛及其缓慢。 |
|
| Adadelta | Adadelta 是 Adagrad 的一种扩展算法，以处理Adagrad学习速率单调递减的问题。RMSprop 可以算作 Adadelta 的一个特例 |
| 优点：1）不需要手动调整学习率，可以自动调整；2）不需要手动设置初始 \(\alpha\)。 缺点：1）后期容易在小范围内产生震荡 |
|
| ----------- | 机器学习各优化算法的简单总结 An overview of gradient descent optimization algorithms An overview of gradient descent optimization algorithms ARXIV An overview of gradient descent optimization algorithms 中文翻译 |
凸优化与非凸优化： 
动量梯度下降——Momentum
Momentum改进自SGD，让每一次的参数更新方向不仅取决于当前位置的梯度，还受到上一次参数更新方向的影响。 不管是普通的梯度下降、mini-batch、SGD 还是其他的什么，都是通过 \(W -= \alpha * dW\) 来更新权重。但是在动量梯度下降中，使用到了指数加权平均。尤其是针对mini-batch算法，因为mini-batch算法抖动过大，上面的章节介绍了mini-batch的梯度下降误差曲线，指数加权平均正好可以解决。 可以观察下图发现，梯度下降的波动比较大，也就是噪点较多，我们可以使用指数加权平均来减少噪点。下面的公式就是用其减少了梯度dW和db。下式中还对指数加权平均进行了优化，使用了偏差修正。 \[
\begin{cases}
compute\ dW, db\\
V_{dW} = \beta * (V_{dW})_{prev} + (1 - \beta) * dW,\quad V_{db} = \beta * (V_{db})_{prev} + (1 - \beta) * db\\
V^{corrected}_{dW} = \frac{V_{dW}}{1 - \beta^t},\quad V^{corrected}_{db} = \frac{V_{db}}{1 - \beta^t} \\
W -= \alpha * V^{corrected}_{dW}\\
b -= \alpha * V^{corrected}_{db}\\
\end{cases}
\] 
在梯度下降时的这种波动减慢了下降的速度，无法使用更大的学习速率。因为梯度已经很大了，如果使用更大的学习速率，可能梯度直接爆炸了，直接无法收敛。为了避免摆动过大需要使用较小的学习速率。 还可以从另一种角度看待。我们希望在纵轴上学习的慢点，我们希望摆动小点，不就是希望纵轴小点吗。而在横轴上我们又希望学习的快点，因为我们希望越快接近中心越好。 这个视频讲的直观一点，可以参考一下，从36:00开始看，虽然讲的是RMSprop但是讲的原理跟Momentum的原理一样。
补充
在课后练习中有更详细的说明，在此补充一下。
Because mini-batch gradient descent makes a parameter update after seeing just a subset of examples, the direction of the update has some variance, and so the path taken by mini-batch gradient descent will "oscillate" toward convergence. Using momentum can reduce these oscillations.
大致意思就是使用Momentum可以使得mini-batch的振荡更小，观察下图。。。说实话我并没有观察出什么，不知道Coursera是怎么想的。我把此图的提示贴出来：
Figure 3: The red arrows shows the direction taken by one step of mini-batch gradient descent with momentum. The blue points show the direction of the gradient (with respect to the current mini-batch) on each step. Rather than just following the gradient, we let the gradient influence v and then take a step in the direction of v .
Momentum takes into account the past gradients to smooth out the update. We will store the 'direction' of the previous gradients in the variable v . Formally, this will be the exponentially weighted average of the gradient on previous steps. You can also think of v as the "velocity" of a ball rolling downhill, building up speed (and momentum) according to the direction of the gradient/slope of the hill.
Momentum考虑到了之前的梯度，从而用其来缓和参数更新。我们将前一次梯度的“方向”存进变量v。后续不翻译了。
均方根传播——RMSprop
问题：对梯度做平方，且 \(S_{dW}\) 的计算公式是加法（即修改过的指数加权平均），那么 \(S_{dW}\) 岂不是会越来越大？不就意味着动量越来越大，到最后停不下来了？
当然不是，可以减小。设 \(dW_1 = 15 \quad S_{dW1} = 20 \quad \beta = 0.9 \quad dW_2 = 2\)，则 \(S_{dW2} = 0.9 * 20 + (1 - 0.9) * 15 = 19.5\)，而 \(S_{dW3} = 0.9 * 19.5 + (1 - 0.9) * 2 = 17.75\)。比较 \(S_{dW1} \, S_{dW2} \, S_{dW3}\) = 20 19.5 17.75，明显在下降，比较 \(dW_1 \, dW_2\) 发现梯度减少引起得 \(dS\) 减少。
RMSProp 的本质是：在梯度大的地方，减小 \(\alpha\)（即陡坡则减小步伐）；在梯度小的地方，增大 \(\alpha\)（即缓坡则增大步伐）。解释如下：
RMSProp的更新公式为： \[ \begin{cases} S_{dW} = \beta_2 * (S_{dW})_{prev} + (1 - \beta_2) * (dW)^2 \\ W -= \alpha * \frac{dW}{\sqrt{S_{dW}} + \epsilon} \\ \end{cases} \] 对于 \(W -= \alpha * \frac{dW}{\sqrt{S_{dW}} + \epsilon}\) 来说，其实就是普通的权重更新公式多除以一个 \(\sqrt{S_{dW}} + \epsilon\)。而由于 \(\sqrt{S_{dW}} + \epsilon\) 是梯度的累加，故为简便起见，将 \(\sqrt{S_{dW}} + \epsilon\) 看作梯度（Q：为什么可以将这个视为梯度？A：\(\sqrt{S_{dW}}\) 是对梯度 dW 的类似累加操作，开个根号后差不多就是梯度）。
我们知道在陡坡处梯度大，我们需要减小步伐，要不然容易一步迈长了，而减小步伐的意思就是减小 \(\alpha\)。
假设现在陡坡处梯度为 100，那么就是将原本的梯度下降公式多除以了 100（因为我们已将 \(\sqrt{S_{dW}} + \epsilon\) 视为梯度）。是不是梯度越大，则分母越大？分母越大则意味着 \(\alpha\) 越小。
反之，缓坡梯度小，我们就需要增大步伐，假设梯度为 0.1，那么就代表将原本的权重更新公式除以 0.1。分母越小，则 \(\alpha\) 越大。
Root mean square prop.
一个类似Momentum的算法，没必要死记公式，略。视频地址。
或者另一个参考视频，36:00开始。
RMSprop 没有使用偏差修正。但是在 Adam 中的 RMSprop 使用了偏差修正。 \[ \begin{cases} compute\ dW, db\\ S_{dW} = \beta_2 * (S_{dW})_{prev} + (1 - \beta_2) * (dW)^2,\quad S_{db} = \beta_2 * (S_{db})_{prev} + (1 - \beta_2) * (db)^2\\ W -= \alpha * \frac{dW}{\sqrt{S_{dW}} + \epsilon}\\ b -= \alpha * \frac{db}{\sqrt{S_{db}} + \epsilon}\\ \end{cases} \] 在更新 W 和 b 时的算法与之前的 Momentum 算法略微不同。另外为了防止 dW 和 db 等于 0，导致分母为 0，所以在分母加了一个极小值\(\epsilon\)，在 Keras 中取了 1e-7， 吴恩达老师说 1e-8 是个不错的选择。
RMSprop 算法也是使用了指数加权平均算法。并且还结合了 Adagrad。
对于理解 RMSprop。可以观察出 RMSprop 和 Momentum 长得有点像，但是这两个算法的具体关系暂时不清楚。并且 RMSprop 其实还有简化版的算法，叫做 Adagrad。之前对这些优化算法（Momentum, RMSprop, Adam 等）的理解都是改变 W 和 b 的大小从而使得梯度下降更快。但是又今天看了一遍李宏毅老师的视频，发现还有其他的理解。其实这些算法都在改变学习速率的大小。
比如 RMSprop 算法，观察\(W -= \alpha * \frac{dW}{\sqrt{S_{dW}} + \epsilon}\)，我们可以改写成\(W = W - \frac{\alpha}{\sqrt{S_{dW}} + \epsilon} * dW\)。看dW之前的那项\(\frac{\alpha}{\sqrt{S_{dW}} + \epsilon}\)实际上就是对学习速率\(\alpha\)乘上了\(\frac{1}{\sqrt{S_{dW}} + \epsilon}\)。
所以对RMSprop的理解是：如果梯度过大\(\frac{\alpha}{\sqrt{S_{dW}} + \epsilon}\)就会相对减小，如果梯度过小\(\frac{\alpha}{\sqrt{S_{dW}} + \epsilon}\)就会相对增大。因为其实\(S_{dW}\)就是 dW 算出来的，而梯度过大就是 dW 过大，dW过大就是\(S_{dW}\)过大。一个很大的数取倒数，这个数就变很小了。梯度过小同理。
而为什么梯度过大就要是学习速率\(\alpha\)变小呢？因为梯度过大就是说梯度较为陡峭，可以想象一座陡峭的山，如果跨一大步是不是直接掉下去了？而掉在哪是未知的，很有可能掉到最低点的前面，这样大概率是回不到最低点的（或者是极小值点）。而如果\(\alpha\)小点就很好了，因为可以一小步一小步的走，最终可能会走到极小值点（或者最小值点）。梯度过小同理。平原地方肯定要大跨步走，你小步伐走要走到什么时候才能走到极小值点？
另外 RMSprop 可以算是 Adagrad 算法的改进版，但是这二者的具体关系未知。
优化算法历史介绍
在深度学习的历史中，有不少学者，包括许多知名学者，提出了优化算法并解决了一些问题。但之后这些算法被指出并不能一般化，并不能适用于多种神经网络。
时间久了，深度学习圈子里的人开始多少有点质疑全新的优化算法。
但是RMSprop和Adam是少有的经受住人们考验的两种算法。已被证明适用于不同的深度学习结构。
Adam
全称：Adaptive Moment Estimation
这里的 RMSprop 使用了偏差修正。
Adam 算法是 Momentum 和 RMSprop 结合起来的算法。Momentum算法解决算法在纵轴上波动过大的问题，它可以使用类似于物理中的动量来累积梯度。而RMSprop可以在横轴上收敛速度更快同时使得波动的幅度更小。所以将两种算法结合起来表现可能会更好。
\[ \begin{array}{l} compute\ dW, db\\ V_{dW} = \beta_1 * V_{dW} + (1 - \beta_1) * dW,\quad V_{db} = \beta_1 * V_{db} + (1 - \beta_1) * db\\ S_{dW} = \beta_2 * S_{dW} + (1 - \beta_2) * (dW)^2,\quad S_{db} = \beta_2 * S_{db} + (1 - \beta_2) * (db)^2\\ V^{corrected}_{dW} = \frac{V_{dW}}{1 - \beta_1},\quad V^{corrected}_{db} = \frac{V_{db}}{1 - \beta_1}\\ S^{corrected}_{dW} = \frac{S_{dW}}{1 - \beta_2},\quad S^{corrected}_{db} = \frac{S_{db}}{1 - \beta_2}\\ W -= \alpha * \frac{V^{corrected}_{dW}}{\sqrt{S^{corrected}_{dW}} + \epsilon}\\ b -= \alpha * \frac{V^{corrected}_{db}}{\sqrt{S^{corrected}_{db}} + \epsilon}\\ \end{array} \] adam paper在这。
超参数的选择
- \(\alpha\)需要自行调整。
- \(\beta_1\)一般设置为0.9，计算\(dW\)。
- \(\beta_2\)Adam的作者推荐0.999，计算\((dW)^2\)。
- \(\epsilon\)其实不是很重要，但是Adam作者推荐设置为\(10^{-8}\)。其实不设置也可以，并不会影响算法的性能。
所以在该算法中其实只要调整\(\alpha\)就够了，其他的参数也可以调整，但是一般不调整。
adam是否还需要调节学习率？
The Marginal Value of Adaptive Gradient Methods in Machine Learning
其他的学习速率衰减算法
Adagrad
让学习率适应参数，对于出现次数较少的特征，我们对其采用更大的学习率，对于出现次数较多的特征，我们对其采用较小的学习率。因此，Adagrad非常适合处理稀疏数据。
李宏毅 Adagrad 参考视频，从06:30开始。
优化算法总结
| optimization method | accuracy | cost shape |
|---|---|---|
| Gradient descent | 79.7% | oscillations |
| Momentum | 79.7% | oscillations |
| Adam | 94% | smoother |
优化算法实战
在实践中，可能可以先使用 Adam 让模型快速收敛，然后使用 SGD 让模型跑出更好的效果。
