When Gradient Is Small: Local Minimum and Saddle Point

Optimization失败的原因

1. local minima
2. saddle points（鞍点）

critical point（驻点）：gradient is close to zero.
当loss没有办法再下降的时候，也许是因为卡在了critical point。但你不能说是卡在local minima，因为saddle point也是微分为零的点。

为什么要知道到底是卡在local minima还是卡在saddle point呢？

• 因为如果是卡在local minima，那可能就没有路可以走了。这是因为该点四周都比较高，你现在所在的位置已经是最低的点，此时loss最低。往四周走loss都会比较高，你不知道怎么走到其他地方。
• 但saddle point相比较就没有这个问题。如果你今天是卡在saddle point的话，saddle point旁边还是有路可以走的，还是有方向可以让你的loss更低的。你只要逃离saddle point，你就有可能让你的loss更低。

所以判别驻点的类型是有实际意义的，需要借用数学工具。

Tayler Series Approximation（泰勒级数近似法）

如果你今天算出一个 hessian，不需要把它跟所有的 $v$ 都相乘来判断符号，你只要去直接看这个 $H$ 的 eigen value 即可。
如果你发现

• hessian metric 的所有 eigen value 都是正的，即 $v^тHv$ 大于零，也就代表这是一个 local minima。
• 反过来说也是一样。如果 hessian metric 的所有 eigen value 都是负的，即 $v^тHv$ 小于零，也就代表这是一个 local maxima。
• 那如果 eigen value 有正有负，那就代表是 saddle point。

总的来说，你只要算出一个东西，这个东西的名字叫做hessian。它是一个矩阵，如果这个矩阵所有的 eigen value 都是正的，那就代表我们现在在 local minima；如果它有正有负，就代表在 saddle point。

如何处理鞍点

如果模型的训练卡在了驻点，并且通过 $H$ 知道了驻点的类型为鞍点，那么也可以通过 $H$ 知道 update 的方向。
$u$ is an eigen vector of $H$.（$u$是$H$的特征向量）
$\lambda$ is the eigen value of $u$.（$\lambda$是$u$的特征值）
$\lambda u=Hu$
$u^T{H}u=u^T(\lambda u)=\lambda\|u\|^2$
$L(\boldsymbol{\theta})\approx L(\boldsymbol{\theta}^{\prime})+\frac{1}{2}(\boldsymbol{\theta}-\boldsymbol{\theta}^{\prime})^T\boldsymbol{H}(\boldsymbol{\theta}-\boldsymbol{\theta}^{\prime})\implies L(\boldsymbol{\theta})<L(\boldsymbol{\theta}^{\prime})$
$\theta-\theta^\prime=u\quad\theta=\theta^\prime+u$
当 $\lambda$ 小于零时，也就是 eigen value 小于零的话，$\lambda\|u\|^2$ 就会小于零，所以 eigen value 是负的，那 $\lambda\|u\|^2$ 这一整项就会是负的，也就是 $u^THu$ 是负的。
假设 $θ-θ'=u$，则$L（θ）<L（θ'）$
也就是说当 $\theta-\theta^\prime=u$ ，即你在 $\theta^\prime$ 的位置加上 $u$，沿着 $u$ 的方向做 update，也就是沿着特征向量的方向更新得到 $\theta$，就可以让 loss 变小。
所以虽然在 critical point 没有 gradient，如果我们今天是在一个 saddle point，你只要找出负的 eigen value，再找出它对应的 eigen vector，用这个 eigen vector 去加 $θ'$，就可以找到一个新的点，这个点的 loss 比原来还要低。
但是实际上，在实际的 implementation（执行）里面，你几乎不会真的把 Hessian 算出来，这个要二次微分，要计算这个矩阵需要的运算量非常非常的大，更不要说还要把它的 eigen value、eigen vector 找出来。所以在实操上，很少有人用这一个方法来逃离 saddle point。

Saddle Point v.s. Local Minima

那么到底 saddle point 跟 local minima 谁比较常见呢？
从三维的空间来看，两个地方之间没有路可以走，但是在高维的空间中是有路可以走的，error surface 会不会也一样呢？

所以你在一维的空间中，一维的包含一个参数的 error surface 中，会觉得好像到处都是 local minima。但是会不会在二维空间来看它就只是一个 saddle point 呢？常常会有人画类似这样的图，告诉你 Deep Learning 的训练是非常的复杂的。如果我们移动某两个参数，error surface 的变化就会非常的复杂，它有非常多的 local minima。现在有一个 local minima，但是会不会只是在二维的空间中看起来是一个 local minima，在更高维的空间中它看起来就是 saddle point；在二维的空间中我们没有路可以走，那会不会在更高的维度上，其实有路可以走的。
那如果维度越高，是不是可以走的路就越多了呢。所以今天在训练一个 network 的时候，我们的参数往往动輒百万千万以上，所以我们的 error surface 其实是在一个非常高的维度中。我们参数有多少就代表我们的 error surface 的维度有多少，参数是一千万就代表 error surface 它的维度是一千万。既然维度这么高，会不会实际上有非常多的路可以走呢，那既然有非常多的路可以走，会不会其实 local minima 实际上很少呢？
所以从经验上看起来其实 local minima 并没有那么常见。多数的时候你 train 到一个地方，gradient 变的很小，然后你的参数不再更新了，往往是因为你卡在了一个 saddle point。

Batch and Momentum（批次和动量）

Shuffle

实际上在算微分的时候，并不是真的对所有 Data 算出来的 L 作微分而是是把所有的 Data 分成一个一个的 Batch（或者Mini Batch）。

在实际训练过程中，往往会将训练数据分成很多批（batch），对每一个 batch 都会计算一个 Loss 函数，计算一个梯度并进行更新，对所有的 batch 完成一次计算叫做一轮（epoch）。
所有的 Batch 看过一遍，叫做一个 Epoch，实际操作的过程中，在使用 Batch 的时候，你会做一件事情叫做 Shuffle（洗牌，混乱）。
shuffle（中文意思：洗牌，混乱)。shuffle 在机器学习与深度学习中代表的意思是，将训练模型的数据集进行打乱的操作。
Shuffle 有很多不同的做法，一个常见的做法就是在每个 Epoch 开始之前会重新分一次 Batch，从而每一个 Epoch 的 Batch 都不一样。

为什么要使用Batch？

Small Batch v.s. Large Batch

Full Batch：没用使用Batch。

• Large batch size does not require longer time to compute gradient.（大批量不需要更长的时间来计算梯度。）

• Smaller batch requires longer time for one epoch(longer time for seeing all data once).（较小的批次一轮需要更长的时间(一次查看所有数据的时间更长)。）

虽然 GPU 虽然有平行运算的能力，但它平行运算能力终究有个极限，所以你 Batch Size 真的很大的时候时间还是会增加的。
但是在有平行运算的能力的情况下，当你的 Batch Size 小的时候，你要跑完一个 Epoch 花的时间是比大的 Batch Size 还要多，为什么？
如果假设我们的训练资料有60000笔，Batch Size =1。那要60000个 Update 才能跑完一个 Epoch；如果 Batch Size =1000，要60个 Update 才能跑完一个 Epoch；假设 Batch Size=1与 Batch Size =1000要计算 Gradient 的时间差不多，但60000次 Update，跟60次 Update 比起来，它的时间的差距量就非常可观。

在没有考虑平行运算的时候，你觉得大的 Batch 比较慢；但实际上，在有考虑平行运算的时候，一个大的 Batch 计算一个epoch花的时间反而是比较少的。

• Smaller batch size has better performance.“Noisy” update is better for training（小批次拥有更好的性能。“噪音”更新更适合训练。）

如图，Batch Size 越大，Validation Acc 上的结果越差。但这个不是由于Overfitting，因为观察 Training ，会发现 Batch Size 越大，Training 的结果也是越差的。
这个是 Optimization 的问题，当你用大的 Batch Size 的时候，你的 Optimization 可能会有问题，小的 Batch Size，Optimization 的结果反而是比较好的。
为什么会这样呢？

假设在Full Batch的情况下，在 Update 参数的时候，你就是沿着一个 Loss Function 来 Update 参数，Update 到一个 驻点的时候就停下来了，此时Gradient =0。如果你不特别去看Hession，只用 Gradient Descent 的方法，你就没有办法再更新参数了。
但是如果在 Small Batch 的情况下。因为每次是挑一个 Batch 出来算它的 Loss。所以相当于每一次 Update 参数的时候，你用的 Loss Function 都是越有差异的。你选到第一个 Batch 的时候，你是用 L1 来算你的 Gradient；你选到第二个 Batch 的时候，你是用 L2 来算你的 Gradient。假设你用 L1 算 Gradient 的时候，发现 Gradient 是零，无法在进行更新。但 L2 它的 Function 跟 L1 又不一样，L2 就不一定会卡在驻点，所以 L1 卡住的话就换下一个 Batch ，用L2 再算 Gradient。
所以相比较在Full Batch的情况下，Small Batch不会因为驻点的存在就早早的结束训练，你还是有办法 Training 你的 Model，还是有办法让你的 Loss 变小。所以今天这种 Noisy 的 Update 的方式结果反而对 Training，其实是有帮助的。

• “Noisy” update is better for generalization

Small batch is better on testing data.

上图中的两条曲线代表了Training Loss和Testing Loss。在Training Loss中可能有很多的Local Minima。在这些局部最小的点上，Loss的值都很低，有的可能都趋近于0。在这些局部最小的点中，有好的Minima跟坏的 Minima 之分。
如果一个Local Minima它在一个曲线峡谷里面（图中的sharp minima），它是坏的 Minima；如果Local Minima它在一个较为平缓的曲线段上（上图中的Flat minima)，它就是好的 Minima。
为什么会有这种差异？

• 假设现在 Training 跟 Testing 中间有一个 Mismatch（不匹配），Training 的 Loss 与Testing 的 Loss所对应的Function不一样。有可能是本来你 Training 跟 Testing 的 Distribution（分布）就不一样。
• 也有可能因为 Training 跟 Testing都是从 Sample 的 Data 算出来的，也许训练集和测试集从样本数据算出来的不一样，所以它们的Loss不一样。

假设Testing的就是把 Training Loss的Function往右平移一点（上图中的虚曲线）。这时候会发现对左边这个在一个盆地里面的Minima（Flat minima）来说，它在 Training 和Testing 上面的结果，不会差太多（Flat minima上的红虚线），只差了一点点；但是右边这个在峡谷中的 Minima就差的比较多了（Sharp minima上的红虚线）
Sharp minima在Training Set上算出来的 Loss 很低，但是Training与Testing 之间有差别，所以在测试的时候，这个误差曲面的移动让Sharp minima算出来的 Loss就变得很大。
很多人相信这个大的 Batch Size会让我们倾向于走到峡谷里面，而小的 Batch Size倾向于让我们走到盆地里面。
但这只是一个解释，学术界有争论，这个其实还是一个尚待研究的问题。

Small Batch的Update的方向比较Noisy，Large Batch的Update 的方向比较稳定。但是 Noisy 的 Update 的方向反而会在 Optimization 的时候会更有优势，而且在 Testing 的时候也会占优。所以Large Batch跟Small Batch各有优缺点。
所以 Batch Size也属于需要人工调整的 Hyperparameter。

Momentum

假设 Error Surface 是在物理的世界中的真正的斜坡，而参数是一个球，你把球从斜坡上滚下来。如果发生Gradient Descent（梯度下降)，它走到 Local Minima 或 Saddle Point 就停住了。
但是在物理的世界中一个球如果从高处滚下来，如果有惯性，球在遇到平面时它还是会继续往右走。如果它的动量够大的话，甚至它走到一个 Local Minima 还是会继续往右走，甚至翻过这个小坡然后继续往右走。
所以今天在物理的世界中一个球从高处滚下来的时候，它并不一定会被 Saddle Point 或 Local Minima 卡住。人们就想到有没有办法运用同样的概念到 Gradient Descent 中，这个就是 Momentum 这个技术。

(Vanilla) Gradient Descent （一般的）梯度下降法

Gradient Descent + Momentum

一个解读是，Momentum是Gradient 的反方向加上前一次移动的方向；
另一个意思是，Momentum 所包含的 Update 的方向不是只考虑现在的 Gradient，而是考虑过去所有 Gradient 的总合。

Adaptive Learning Rate（自适应学习率）

Training stuck ≠ Small Gradient（训练卡住不代表小梯度）

人们在训练一个 network 的时候往往会把它的 loss 记录下来，就会发现 loss 原来很大，随着参数不断的更新，loss 会越来越小，最后就卡住了，loss 不再下降。
一般在遇到这个情况的时候人们大多都在猜想是不是走到了 critical point，因为 gradient 为零，所以没有办法再更新参数。
但是真的是这样吗？ 当走到 critical point 的时候，意味着 gradient 非常的小，但 loss 不再下降的时候 gradient 真的很小吗?

gradient 是一个向量，上图中下面的图是 gradient 的 norm（范数)，即 gradient 这个向量的长度随参数更新时的变化。你会发现虽然 loss 不再下降，但是 gradient 的大小并没有真的变得很小。
也许遇到的是上图中左边这个曲线代表的情况。这个曲线是我们的 error surface，现在 gradient 在 error surface 山谷的两个谷壁间不断的来回的震荡 这个时候 loss 不会再下降，所以你会觉得它卡在 critical point。但实际上不是的，它的 gradient 仍然很大，只是 loss 不会再减小了。
所以要注意，训练一个 network 的时候，train 到后来发现 loss 不再下降的时候不要随便说卡在驻点，有时候并不是卡在两类驻点上，只是单纯的 loss 没有办法再下降。
实际上，在真实的训练过程中，Model 训练到驻点的位置是比较困难的事情，除非是用十分特殊的 gradient descend train。大多数情况是在梯度还没有变小（或训练到驻点) 的时候训练就停下来了。

Different parameters needs different learning rate（不同的参数需要不同的学习率）

Training can be difficult even without critical points（即使没有驻点，训练也会很困难）.
Learning rate cannot be one-size-fits-all.

Root Mean Square（均方根）—— Used in Adagrad

$\theta_i^1\leftarrow\theta_i^0-\frac\eta{\sigma_i^0}g_i^0\quad\sigma_i^0=\sqrt{\left(g_i^0\right)^2}=|g_i^0|$

$\theta_i^2\leftarrow\theta_i^1-\frac\eta{\sigma_i^1}g_i^1\quad\sigma_i^1=\sqrt{\frac12\left[\left(g_i^0\right)^2+\left(g_i^1\right)^2\right]}$

$\theta_i^3\leftarrow\theta_i^2-\frac\eta{\sigma_i^2}{g_i^2}\quad\sigma_i^2=\sqrt{\frac13\left[\left(g_i^0\right)^2+\left(g_i^1\right)^2+\left(g_i^2\right)^2\right]}$

…

$\begin{aligned}\\&\boldsymbol{\theta}_i^{t+1}\leftarrow\boldsymbol{\theta}_i^t-\frac\eta{\sigma_i^t}\boldsymbol{g}_i^t\quad\sigma_i^t=\sqrt{\frac1{t+1}\sum_{i=0}^t(\boldsymbol{g}_i^t)^2}\end{aligned}$

Adagrad

上面这个方法被应用在 Adagrad 算法中，Adagrad 是解决不同参数应该使用不同的更新速率的问题。Adagrad 为自适应地为各个参数分配不同学习率的算法。

为什么可以做到当坡度比较大的时候 learning rate 就减小，坡度比较小的时候 learning rate 就放大呢?

假设有两个参数：一个是 $\theta_i^1$，一个是 $\theta_i^2$ 。$\theta_i^1$ 坡度小，$\theta_i^2$ 坡度大

• $\theta_i^1$ 因为坡度小，所以在 $\theta_i^1$ 这个参数上面算出来的 gradient 值都比较小。
• 因为 gradient 算出来的值比较小，所以 $\sigma$ 就比较小，由于$\frac{\eta}{\sigma_{i}^{t}}$，所以 learning rate 就比较大。
• 同理，$\theta_i^2$ 的 learning rate 就比较小。

所以有了 $\sigma$ 这一项以后，就可以随着每一个参数的 gradient 的不同，来自动的调整 learning rate 的大小。但这个方法还有改进的余地。

RMSProp

$\theta_i^1\leftarrow\theta_i^0-\frac\eta{\sigma_i^0}g_i^0\quad\sigma_i^0=\sqrt{\left(g_i^0\right)^2}$
$\theta_i^2\leftarrow\theta_i^1-\frac\eta{\sigma_i^1}g_i^1\quad{\sigma_i^1}=\sqrt{\alpha(\sigma_i^0)^2+(1-\alpha)(g_i^1)^2}$$0<\alpha<1$
$\theta_i^3\leftarrow\theta_i^2-\frac\eta{\sigma_i^2}{g_i^2}\quad\sigma_i^2=\sqrt{\alpha{\left(\sigma_i^1\right)}^2+(1-\alpha){\left(g_i^2\right)}^2}$
…
$\begin{aligned}{\theta}_{i}^{t+1}\leftarrow{\theta}_{i}^{t}-\frac\eta{\sigma_i^t}{g}_{i}^{t}\quad\sigma_{i}^{t}=\sqrt{\alpha{\left(\sigma_{i}^{t-1}\right)}^2+(1-\alpha){\left(g_{i}^{t}\right)}^2}\end{aligned}$
这个 α 就像 learning rate 一样，需要人工调整，是一个 hyperparameter。

• 如果 α 设很小趋近于 0，就代表 $g^1_i$ 相较于之前所算出来的 gradient，比较重要
• α 设很大趋近于1，那就代表现在算出来的 $g^1_i$ 不重要，之前算出来的 gradient 比较重要。

RMSProp 可以通过 α 决定 $g^1_i$ 相较于之前存在于 $\sigma_i^{t-1}$ 中的 $g_i^1$、$g_i^2$、$g_i^3$、……、$g_i^{t-1}$ 它的重要性有多大。使用用 RMS Prop，可以动态调整 σ 这一项。

Adam

Adam是现在最常用的optimization的策略。
Adam：RMSProp + Momentum

Learning Rate Scheduling（学习速率调度）

$\boldsymbol{\theta}_i^{t+1}\leftarrow\boldsymbol{\theta}_i^t-\frac{\eta^t}{\sigma_i^t}\boldsymbol{g}_i^t$

• Learning Rate Decay（学习速率衰减）：随着时间的不断地前进、随着参数不断的更新，让η越来越小。
• Warm up：让 learning rate 要先变大后变小。其中变大变小的程度、速度都属于 hyperparameter，要自己手动调，但是大方向的大策略就是 learning rate 要先变大后变小。

Summary of optimization

Loss of Classification

如何做分类 ( classification ) ?
首先想到的方法是把类别用数字表示，例如，输出按类别表示为 1，2，3，……，这样转化为一个回归问题 ( regression ) 。
但是这样做有一个问题：不同类别并不一定有大小、顺序关系，比如颜色红、黄、蓝，如果按数字来定类别，就人为设置了相邻的两个类别更接近，这不符合事实，容易造成误判。
classification as regression.Class as one-hot vector.
解决办法：使用 one-hot vector，对应类别处值为 1 ，其余地方值为 0。这样，原来 1 个输出变成多个输出。

进一步地，因为 one-hot vector 的值都是 0 或者 1，用 softmax 把输出值限制到 [0，1] 之间，好和 one-hot vector 计算相似度。
对于二分类问题，用 sigmoid 与 softmax 等效。

对于Classification，loss function 还是和 regression 一样，用 MSE 吗？

不，用 cross entropy 比 MSE 更好。
MSE：$e=\sum_{i}(\widehat{y}_{i}-y_{i}^{\prime})^{2}$
Cross-entropy：$e=-\sum_i\widehat{y}_ilnl{y}_i^{\prime}$
假设有一个三分类的模型，其中 $y_1$ 和 $y_2$ 这两类起主要作用， 由 $y_1$ 和 $y_2$ 绘制的 error surface 如下图所示。不论用 MSE 还是 Cross Entropy，都是左上角区域 loss 大，右下角区域 loss 小，假设训练开始时位于图中左上角蓝色点所示位置。如果 loss function 用 MSE，因为这一区域 loss 变化平缓，训练容易卡住。如果 loss function 用 Cross Entropy，因为这一区域 loss 变化陡峭，可以变化到 loss 更低的点。

这也就是说，改变 loss function，可以改变 error surface（平缓或是陡峭)，因此改变训练的难易程度。