Datawhale开源学习，机器学习课程，项目地址：https://github.com/datawhalechina/leeml-notes

Optimization

Critical Point是Saddle Point还是Local Point？

现在我们要讲的是Optimization的部分，所以我们要讲的东西基本上跟Overfitting没有什么太大的关联，我们只讨论在做Optimization时，如何把gradient descent做得更好，那为什么Optimization会失败呢？

你常常在做Optimization时，会发现随着你的参数不断的update，你的training的loss不会再下降，但是你对这个loss仍然不满意，就像我刚才说的，你可以把deep的network，跟linear的model，或比较shallow network比较，发现deep network并没有做得更好，所以会觉得deep network没有发挥它完整的力量，所以Optimization显然是有问题的。但有时候你会甚至发现，一开始你的model就train不起来，一开始你不管怎么update你的参数，你的loss通通都掉不下去，那这时到底发生了什么事情呢？

过去常见的一个猜想，是因为我们现在走到了一个地方，这个地方参数对$L$oss的微分为零，当你的参数对$L$oss微分为零的时候，，gradient descent就没有办法再update参数了，这个时候training就停下来了，loss当然就不会再下降了。讲到gradient为零的时候，大家通常脑海中最先浮现的，可能就是local minima，所以常有人说做deep learning，用gradient descent会卡在local minima，然后所以gradient descent不work，所以deep learning不work。但是如果有一天你要写，跟deep learning相关paper的时候，你千万不要讲卡在local minima这种事情，别人会觉得你非常没有水准，为什么

因为不是只有local minima的gradient是零，还有其他可能会让gradient是零，比如说 saddle point，所谓的saddle point，其实就是gradient是零，但是不是local minima，也不是local maxima的地方，像在右边这个例子里面红色的这个点，它在左右这个方向是比较高的，前后这个方向是比较低的，它就像是一个马鞍的形状，所以叫做saddle point，那中文就翻成鞍点。

像saddle point这种地方，它也是gradient为零，但它不是local minima。那像这种gradient为零的点，统称为critical point，所以你可以说你的loss没有办法再下降，也许是因为卡在了critical point，但你不能说一定是卡在local minima，因为saddle point也是微分为零的点。但是今天如果你发现你的gradient，真的很靠近零，卡在了某个critical point，我们有没有办法知道，到底是local minima，还是saddle point？其实是有办法的。为什么我们想要知道到底是卡在local minima，还是卡在saddle point呢？

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

所以鉴别今天我们走到critical point的时候，到底是local minima，还是saddle point，是一个值得去探讨的问题，那怎么知道今天一个critical point，到底是属于local minima，还是saddle point呢？这边需要用到一点数学，以下这段其实没有很难的数学，就只是微积分跟线性代数，但如果你没有听懂的话，以下这段skip掉是没有关系的。那怎么知道说一个点，到底是local minima，还是saddle point呢？你要知道我们loss function的形状，可是我们怎么知道，loss function的形状呢，network本身很复杂，用复杂network算出来的loss function，显然也很复杂，我们怎么知道loss function，长什么样子，虽然我们没有办法完整知道，整个loss function的样子，但是如果给定某一组参数，比如说蓝色的这个 θ ′ θ’ θ′，在 θ ′ θ’ θ′附近的loss function，是有办法被写出来的，它写出来就像是这个样子：

所以这个$L(\theta )$完整的样子写不出来，但是它在 θ ′ θ’ θ′附近，你可以用这个式子来表示它，这个式子是Tayler Series Appoximation泰勒级数展开，这个假设你在微积分的时候已经学过了，所以我就不会细讲这一串是怎么来的，但我们就只讲一下它的概念，这一串里面包含什么东西呢？

• 第一项是 L ( θ ′ ) L(θ’) L(θ′)，就告诉我们当$\theta$跟 θ ′ θ’ θ′很近的时候，$L(\theta )$应该跟 L ( θ ′ ) L(θ’) L(θ′)还蛮靠近的
• 第二项是 ( θ − θ ′ ) T g (θ-θ’)^Tg (θ−θ′)Tg

$g$是一个向量，这个g就是我们的gradient，我们用绿色的这个g来代表gradient，这个gradient会来弥补， θ ′ θ’ θ′跟$\theta$之间的差距，我们虽然刚才说 θ ′ θ’ θ′跟$\theta$，它们应该很接近，但是中间还是有一些差距的，那这个差距，第一项我们用这个gradient，来表示他们之间的差距，有时候gradient会写成 ∇ L ( θ ′ ) ∇L(θ’) ∇L(θ′)，这个地方的$g$是一个向量，它的第i个component，就是θ的第i个component对$L$的微分，光是看$g$还是没有，办法完整的描述$L(\theta )$，你还要看第三项。

• 第三项跟Hessian有关，这边有一个$H$

这个$H$叫做Hessian，它是一个矩阵，这个第三项是 ( θ − θ ′ ) T H ( θ − θ ′ ) (θ-θ’)^TH(θ-θ’) (θ−θ′)TH(θ−θ′)，第三项会再作为一部分补足，再加上gradient以后，与真正的$L(\theta )$之间的差距。H里面放的是$L$的二次微分，它第i个row，第j个column的值，就是把$\theta$的第i个component，对$L$作微分，再把$\theta$的第j个component，对$L$作微分，再把$\theta$的第i个component，对$L$作微分，做两次微分以后的结果 就是这个 H i j H_i{_j} Hi​j​。如果这边你觉得有点听不太懂的话也没有关系，反正你就记得这个$L(\theta )$，这个loss function，这个error surface在 θ ′ θ’ θ′附近，可以写成这个样子，这个式子跟两个东西有关系，跟gradient有关系，跟hessian有关系，gradient就是一次微分，hessian就是里面有二次微分的部分。那如果我们今天走到了一个critical point，意味著gradient为零，也就是绿色的这一项完全都不见了

$g$是一个zero vector，绿色的这一项完全都不见了，只剩下红色的这一项，所以当在critical point的时候，这个loss function可以被近似为 L ( θ ′ ) L(θ’) L(θ′)加上红色的这一项。我们可以根据红色的这一项来判断，在 θ ′ θ’ θ′附近的error surface到底长什么样子，知道error surface长什么样子，我就可以判断 θ ′ θ’ θ′处的loss function是一个local minima，是一个local maxima，还是一个saddle point我们可以靠这一项来了解，这个error surface的地貌，大概长什么样子，知道它地貌长什么样子，我们就可以知道现在是在什么样的状态。

那我们就来看一下怎么根据Hessian或者怎么根据红色的这一项，来判断 θ ′ θ’ θ′附近的地貌：

为了符号方便起见，我们把 ( θ − θ ′ ) (θ-θ’) (θ−θ′)用$v$这个向量来表示：

• 如果今天对任何可能的$v$， v T H v v^THv vTHv都大于零，也就是说现在$\theta$不管代入任何值，v可以是任何的v，也就是$\theta$可以是任何值，不管$\theta$代任何值，红色框框里面通通都大于零，那意味着 L ( θ ) > L ( θ ′ ) L(θ)>L(θ’) L(θ)>L(θ′)。$L(\theta )$不管代多少只要在 θ ′ θ’ θ′附近，$L(\theta )$都大于 L ( θ ′ ) L(θ’) L(θ′)，代表 L ( θ ′ ) L(θ’) L(θ′)是附近的一个最低点，所以它是local minima
• 如果今天反过来说，对所有的$v$而言， v T H v v^THv vTHv都小于零，也就是红色框框里面永远都小于零，也就是说$\theta$不管代什么值，红色框框里面都小于零，意味着 L ( θ ) < L ( θ ′ ) L(θ)<L(θ') L(θ)<L(θ′)，代表 L ( θ ′ ) L(θ’) L(θ′)是附近最高的一个点，所以它是local maxima
• 第三个可能是假设， v T H v v^THv vTHv，有时候大于零 有时候小于零，你代不同的v进去 代不同的θ进去，红色这个框框里面有时候大于零，有时候小于零，意味著说在θ’附近，有时候L(θ)>L(θ’) 有时候L(θ)<L(θ’)，在L(θ’)附近，有些地方高 有些地方低，这意味著什么，这意味著这是一个saddle point

但是你这边是说我们要代所有的$v$，去看 v T H v v^THv vTHv是大于零，还是小于零。我们怎么有可能把所有的v，都拿来试试看呢，所以有一个更简便的方法，去确认说这一个条件或这一个条件，会不会发生。这个就直接告诉你结论，线性代数理论上是有教过这件事情的，如果今天对所有的v而言， v T H v v^THv vTHv都大于零，那这种矩阵叫做positive definite 正定矩阵，positive definite的矩阵，它所有的eigen value特征值都是正的（>0）。所以如果你今天算出一个hessian，你不需要把它跟所有的v都乘看看，你只要去直接看这个H的eigen value，如果你发现：

• 所有eigen value都是正的，那就代表说这个条件成立，就 v T H v v^THv vTHv，会大于零，也就代表说是一个local minima。所以你从hessian metric可以看出，它是不是local minima，你只要算出hessian metric算完以后，看它的eigen value发现都是正的**，它就是local minima**。
• 那反过来说也是一样，如果今天在这个状况，对所有的v而言， v T H v v^THv vTHv小于零，那H是negative definite，那就代表所有eigen value都是负的，就保证他是local maxima
• 那如果eigen value有正有负，那就代表是saddle point。

那假设在这里你没有听得很懂的话，你就可以记得结论，**你只要算出一个东西，这个东西的名字叫做hessian，它是一个矩阵，这个矩阵如果它所有的eigen value，都是正的，那就代表我们现在在local minima，如果它有正有负，就代表在saddle point。**那如果刚才讲的仍然让你没有听得很懂的话，我们这边举一个例子：我们现在有一个史上最废的network，输入一个x，它只有一个neuron，乘上 w 1 w_1 w1​，而且这个neuron，还没有activation function，所以x乘上 w 1 w_1 w1​之后就输出，然后再乘上 w 2 w_2 w2​然后就再输出，就得到最终的数据就是y。总之这个function非常的简单：
y = w 1 ∗ w 2 ∗ x y= w_1*w_2*x y=w1​∗w2​∗x

我们有一个史上最废的training set，这个data set说，我们只有一笔data，这笔data是x = 1的时候，它的level是1所以输入1进去，你希望最终的输出跟1越接近越好。而这个史上最废的training，它的error surface，也是有办法直接画出来的，因为反正只有两个参数 w 1 w_1 w1​和 w 2 w_2 w2​，连bias都没有，假设没有bias，只有 w 1 w_1 w1​跟 w 2 w_2 w2​两个参数，这个network只有两个参数 w 1 w_1 w1​跟 w 2 w_2 w2​，那我们可以穷举所有 w 1 w_1 w1​跟 w 2 w_2 w2​的数值，算出所有 w 1 w_1 w1​和 w 2 w_2 w2​数值所代来的loss，然后就画出error surface长这个样。

四个角落loss是高的，好 那这个图上你可以看出来，有一些critical point，这个黑点点的地方(0，0)原点的地方是critical point，然后事实上，右上三个黑点也是一排critical point，左下三个点也是一排critical point。如果你更进一步要分析，他们是saddle point，还是local minima的话，那圆心原点这个地方它是saddle point，为什么它是saddle point呢？你往左上这个方向走loss会变大，往右下这个方向走loss会变大，往左下这个方向走loss会变小，往右上这个方向走loss会变小，所以它是一个saddle point。而这两群critical point，它们都是local minima，所以这个山沟里面，有一排local minima，然后在原点的地方有一个saddle point，这个是我们把error surface，暴力所有的参数，得到的loss function的loss的值以后画出的error surface，可以得到这样的结论。

现在假设如果不暴力所有可能的loss，如果要直接算一个点，想要判断这个点是local minima还是saddle point的话，该怎么算呢？我们可以把loss的function写出来，这个loss的function 这个$L$是：
L = ( y ^ − w 1 w 2 x ) 2 L=(\hat{y}-w_1 w_2 x)^2 L=(y^​−w1​w2​x)2

正确答案 y ^ \hat{y} y^​减掉model的输出 w 1 w 2 x w_1w_2x w1​w2​x后取square error，这边只有一笔data，所以就不会summation over所有的training data，因为反正只有一笔data，x取1， y ^ \hat{y} y^​取1，我刚才说过只有一笔训练资料最废的，所以只有一笔训练资料，所以loss function就是 L = ( y ^ − w 1 w 2 x ) 2 L=(\hat{y}-w_1 w_2 x)^2 L=(y^​−w1​w2​x)2，那你可以把这一个loss function的gradient求出来， w 1 w_1 w1​对$L$的微分， w 2 w_2 w2​对$L$的微分写出来是这个样子：
∂ L ∂ w 1 = 2 ( 1 − w 1 w 2 ) ( − w 2 ) \frac{∂L}{∂w_1 }=2(1-w_1 w_2 )(-w_2 ) ∂w1​∂L​=2(1−w1​w2​)(−w2​)

∂ L ∂ w 2 = 2 ( 1 − w 1 w 2 ) ( − w 1 ) \frac{∂L}{∂w_2 }=2(1-w_1 w_2 )(-w_1 ) ∂w2​∂L​=2(1−w1​w2​)(−w1​)

这个东西
[ ∂ L ∂ w 1 ∂ L ∂ w 2 ] \begin{bmatrix} \frac{∂L}{∂w_1 }\\\ \frac{∂L}{∂w_2 } \end{bmatrix} [∂w1​∂L​∂w2​∂L​​]

就是所谓的g，所谓的gradient，什么时候gradient会零呢，什么时候会到一个critical point呢？举例来说， w 1 = 0 , w 2 = 0 w_1=0,w_2=0 w1​=0,w2​=0即圆心这地方，若 w 1 w_1 w1​代0， w 2 w_2 w2​代0， w 1 w_1 w1​对$L$的微分和 w 2 w_2 w2​对$L$的微分，算出来就都是零，这个时候我们就知道原点就是一个critical point，但它是local minima还是saddle point呢，那你就要看hessian才能够知道。

当然我们刚才已经暴力所有可能的 w 1 w_1 w1​和 w 2 w_2 w2​了，所以你已经知道它显然是一个saddle point，但是现在假设还没有暴力所有可能的loss，所以我们要看看能不能够用Hessian看出它是什么样的critical point，那怎么算出这个H呢？

看上图的二次偏微分，H它是一个矩阵，这个矩阵里面元素就是$L$的二次微分，所以这个矩阵里面第一个row，第一个coloumn的位置，就是 w 1 w_1 w1​对$L$微分两次；第一个row 第二个coloumn的位置，就是先用 w 2 w_2 w2​对$L$作微分，再用 w 1 w_1 w1​对$L$作微分；然后这边第二行第一列就是 w 1 w_1 w1​对$L$作微分， w 2 w_2 w2​对$L$作微分；然后右下角 w 2 w_2 w2​对$L$微分两次，这四个值组合起来，就是我们的hessian，那这个hessian的值是多少呢？这个hessian的式子，我都已经把它写出来了，你只要把 w 1 w_1 w1​=0 w 2 w_2 w2​=0代进去，代进去你就得到在原点的地方，hessian是这样的一个矩阵：
[ 0 − 2 − 2 0 ] \begin{bmatrix} {0}&-2\\\ {-2}&0 \end{bmatrix} [0−2​−20​]

这个hessian告诉我们，它是local minima，还是saddle point呢，那你就要看这个矩阵的eigen value，算一下发现，这个矩阵有两个eigen value，2跟-2，eigen value有正有负，代表saddle point，所以我们现在就是用一个例子，跟你操作一下告诉你说，你怎么从hessian看出一个critical point是saddle point还是local minima。

Don’t afraid of saddle point

如果今天你卡的地方是saddle point，也许你就不用那么害怕了，因为如果你今天你发现，你停下来的时候，是因为saddle point停下来了，那其实就有机会可以放心了，因为H它不只可以帮助我们判断，现在是不是在一个saddle point，它还指出了我们参数，可以update的方向，就之前我们参数update的时候，都是看gradient看g，但是我们走到某个地方以后，发现g变成0了就不能再看g了，g不见了gradient没有了，但如果是一个saddle point的话，还可以再看H，怎么再看H呢，H怎么告诉我们，怎么update参数呢？

我们这边假设$\mu$是H的eigen vector特征向量，$\lambda$是$\mu$的eigen value特征值。如果我们把这边的$v$换成$\mu$的话，我们把$\mu$乘在H的左边，跟H的右边，也就是 μ T H μ \mu^TH\mu μTHμ， $H\mu$会得到$\lambda \mu$，因为$\mu$是一个eigen vector。所以我们在这边得到 μ T \mu ^ T μT乘上$\lambda \mu$，然后再整理一下，把 μ T \mu^T μT跟$\mu$乘起来，得到 ‖ u ‖ 2 ‖u‖^2 ‖u‖2，所以得到 λ ‖ μ ‖ 2 λ‖\mu‖^2 λ‖μ‖2（附近这几张图中的$u$其实就是我们所说的$\mu$）

1 2 ( θ − θ ′ ) T H ( θ − θ ′ ) = 1 2 λ ∣ ∣ θ − θ ′ ∣ ∣ 2 \frac{1}{2}(\theta-\theta^{‘})^TH(\theta-\theta^{‘}) = \frac{1}{2}\lambda||\theta-\theta^{‘}||^2 21​(θ−θ′)TH(θ−θ′)=21​λ∣∣θ−θ′∣∣2

对于上式，假设v代的是一个eigen vector，我们这边$\theta$减 θ ′ θ’ θ′，放的是一个eigen vector的话，会发现说我们这个红色的项里面，其实就是 λ ‖ μ ‖ 2 λ‖\mu‖^2 λ‖μ‖2。

​如果$\lambda$小于零，即eigen value小于零的话，那 λ ‖ μ ‖ 2 λ‖\mu‖^2 λ‖μ‖2就会小于零（因为 ‖ μ ‖ 2 ‖\mu‖^2 ‖μ‖2一定是正的，所以eigen value是负的，那这一整项就会是负的），也就是$\mu$的transpose乘上H乘上$\mu$是负的，也就是红色这个框里是负的。所以这意思是说假设 θ − θ ′ = μ θ-θ’=\mu θ−θ′=μ，那这一项 ( θ − θ ′ ) T H ( θ − θ ′ ) (θ-θ’)^TH(θ-θ’) (θ−θ′)TH(θ−θ′)就是负的，也就是 L ( θ ) < L ( θ ′ ) L(θ)<L(θ') L(θ)<L(θ′)。也就是说若 θ − θ ′ = μ θ-θ’=\mu θ−θ′=μ，你在 θ ′ θ’ θ′的位置加上$\mu$，沿著$\mu$的方向做update得到$\theta$，你就可以让loss变小。因为根据这个式子，你只要$\theta$减 θ ′ θ’ θ′等于$\mu$，loss就会变小，所以你今天只要让$\theta$等于 θ ′ θ’ θ′加$\mu$，你就可以让loss变小，你只要沿着$\mu$，也就是eigen vector的方向，去更新改变你的参数，你就可以让loss变小了。

所以虽然在critical point没有gradient，如果我们今天是在一个saddle point，你也不一定要惊慌，你只要找出负的eigen value，再找出它对应的eigen vector，用这个eigen vector去加 θ ′ θ’ θ′，就可以找到一个新的点，这个点的loss比原来还要低。

举具体的例子：

刚才我们已经发现，原点是一个critical point，它的Hessian长这个样，那现在这个Hessian有一个负的eigen value，这个eigen value等于-2，那它对应的eigen vector会有很多个（其实有无穷多个对应的eigen vector），我们就取一个出来，我们取 [ 1 1 ] \begin{bmatrix}{1} \\\ {1}\end{bmatrix} [11​]是它对应的一个eigen vector，那我们其实只要顺著这个$\mu$的方向，顺著 [ 1 1 ] \begin{bmatrix}{1} \\\ {1}\end{bmatrix} [11​]这个vector的方向，去更新我们的参数，就可以找到一个比saddle point的loss还要更低的点。如果以今天这个例子来看的话，你的saddle point在(0，0)这个地方，你在这个地方会没有gradient，Hessian的eigen vector告诉我们，只要往 [ 1 1 ] \begin{bmatrix}{1} \\\ {1}\end{bmatrix} [11​]的方向更新，你就可以让loss变得更小，也就是说你可以逃离你的saddle point，然后让你的loss变小，所以从这个角度来看，似乎saddle point并没有那么可怕。

如果你今天在training的时候，你的gradient你的训练停下来，你的gradient变成零，训练停下来是因为saddle point的话，那似乎还有解。但是当然实际上，在实际的implementation里面，你几乎不会真的把Hessian算出来，这个要是二次微分，要计算这个矩阵的computation，需要的运算量非常非常的大，更遑论你还要把它的eigen value跟eigen vector找出来，所以在实作上，你几乎没有看到有人用这一个方法来逃离saddle point。

等一下我们会讲其他有机会逃离saddle point的方法，他们的运算量都比要算这个H，还要小很多，那今天之所以我们把这个saddle point跟eigen vector、跟Hessian的eigen vector拿出来讲，是想要告诉你，如果是卡在saddle point，也许没有那么可怕，最糟的状况下你还有这一招可以告诉你要往哪一个方向走。

Saddle Point v.s. Local Minima

讲到这边你就会有一个问题了，这个问题是：那到底saddle point跟local minima，谁比较常见呢？saddle point其实并没有很可怕，那如果我们今天常遇到的是saddle point，比较少遇到local minima，那就太好了，那到底saddle point跟local minima哪一个比较常见呢？这边我们要讲一个不相干的故事，先讲一个故事吧。

这个故事发生在1543年，1543年发生了什么事呢，那一年君士坦丁堡沦陷，这个是君士坦丁堡沦陷图，君士坦丁堡本来是东罗马帝国的领土，然后被鄂图曼土耳其帝国佔领了，然后东罗马帝国就灭亡了，在鄂图曼土耳其人进攻，君士坦丁堡的时候，那时候东罗马帝国的国王，是君士坦丁十一世，他不知道要怎么对抗土耳其人，有人就献上了一策，找来了一个魔法师叫做狄奥伦娜。这是真实的故事，出自三体的故事，这个狄奥伦娜这样说，狄奥伦娜是谁呢，他有一个能力跟张飞一样，张飞不是可以万军从中取上将首级如探囊取物吗，狄奥伦娜也是一样，他可以从万军中取得苏丹的头，大家想说狄奥伦娜怎么这么厉害，他真的有这么强大的魔法吗，所以大家就要狄奥伦娜先展示一下他的力量，这时候狄奥伦娜就拿出了一个圣杯，大家看到这个圣杯就大吃一惊，为什么大家看到这个圣杯要大吃一惊呢，因为这个圣杯本来是放在圣索菲亚大教堂的地下室，而且它是被放在一个石棺里面，这个石棺是密封的，没有人可以打开它。但是狄奥伦娜他从里面取得了圣杯，而且还放了一串葡萄进去，君士坦丁十一世为了要验证狄奥伦娜是不是真的有这个能力，就带了一堆人真的去撬开了这个石棺，发现圣杯真的被拿走了，里面真的有一串新鲜的葡萄，就知道狄奥伦娜真的有，那为什么迪奥伦娜可以做到这些事呢，那是因为这个石棺你觉得它是封闭的，那是因为你是从三维的空间来看，这个石棺是封闭的，没有任何路可以进去，但是狄奥伦娜可以进入四维的空间，从高维的空间中，这个石棺是有路可以进去的，它并不是封闭的，至于狄奥伦娜有没有成功刺杀苏丹呢，你可以想像一定是没有嘛，所以君坦丁堡才沦陷，那至于为什么没有，大家请见于三体。

总之这个**从三维的空间来看，是没有路可以走的东西，在高维的空间中是有路可以走的，error surface会不会也一样呢？**所以你在一维的空间中，一维的一个参数的error surface，你会觉得好像到处都是local minima，但是会不会在二维空间来看，它就只是一个saddle point呢，常常会有人画类似这样的图，告诉你说Deep Learning的训练，是非常的复杂的，如果我们移动某两个参数，error surface的变化非常的复杂，是这个样子的，那显然它有非常多的local minima，我的这边现在有一个local minima，但是会不会这个local minima只是在二维的空间中，看起来是一个local minima，在更高维的空间中，它看起来就是saddle point，在二维的空间中，我们没有路可以走，在更高的维度上，虽然我们没办法visualize它，没办法真的拿出来看，但是会不会在更高维的空间中，其实有路可以走的？那如果维度越高，是不是可以走的路就越多了呢？所以今天我们在训练一个network的时候，参数往往动輒百万千万以上，所以我们的error surface，其实是在一个非常高的维度中，对不对，我们参数有多少，就代表我们的error surface的维度有多少，参数是一千万就代表error surface的维度是一千万，竟然维度这么高，会不会其实根本就有非常多的路可以走呢，那既然有非常多的路可以走，会不会其实local minima，根本就很少呢？

而经验上，如果你自己做一些实验的话，也支持这个假说

这边是训练某一个network的结果，每一个点代表训练完那个network之后，把它的Hessian拿出来进行计算，所以这边的每一个点，都代表一个network，就我们训练某一个network，然后把它训练训练，训练到gradient很小，卡在critical point，把那组参数出来分析，看看它比较像是saddle point，还是比较像是local minima

• 纵轴代表training的时候的loss，就是我们今天卡住了，那个loss没办法再下降了，那个loss是多少，那很多时候，你的loss在还很高的时候，训练就不动了，就卡在critical point，那很多时候loss可以降得很低，才卡在critical point，这是纵轴的部分。
• 横轴的部分是minimum ratio，minimum ratio是eigen value的数目分之正的eigen value的数目，又如果所有的eigen value都是正的，代表我们今天的critical point，是local minima，如果有正有负代表saddle point，那在实作上你会发现说，你几乎找不到完全所有eigen value都是正的critical point，你看这边这个例子里面，这个minimum ratio代表eigen value的数目分之正的eigen value的数目，最大也不过0.5到0.6间而已，代表说只有一半的eigen value是正的，还有一半的eigen value是负的，

所以今天虽然在这个图上，越往右代表我们的critical point越像local minima，但是它们都没有真的，变成local minima，就算是在最极端的状况，我们仍然有一半的case，我们的eigen value是负的，这一半的case，eigen value是正的，代表说在所有的维度里面有一半的路，这一半的路如果要让loss上升，还有一半的路可以让loss下降。所以从经验上看起来，其实local minima并没有那么常见，多数的时候你觉得你train到一个地方，你gradient真的很小，然后所以你的参数不再update了，往往是因为你卡在了一个saddle point。

Batch and Momentum are helpful for crital point

Review： Optimization with Batch

其实我们在使用深度学习对数据进行微分迭代的时候，是将所有数据分成一个一个的Batch（有人叫Mini Batch，其实都是一个含义）。这所有的Batch都训练一遍，就是一个Epoch。

Batch的大小代表了不同含义，Batch越大，说明一次需要的数据也越多，需要的数据多，那拟合出来的也就越稳定；反之Batch越小，说明一次训练所需数据也就越少，那拟合出来的也就不那么稳定。使用Batch，若Batch Size = 1的话代表我们每次更新参数时，只需拿一笔Data算Loss。看一笔Data就更新一次参数。如果数据集总共划分为20笔Data，那在每在一个Epoch里，参数会更新20次。用一笔Data算出来的 Loss显然是比较Noisy的，所以迭代更新的方向是曲曲折折的。

左边的方法有一个优点就是它这一步走的是稳的。而右边这个方法它的缺点就是它每一步走的是不稳的。但是越稳定就一定越好吗？那也不见得，On Large-Batch Training For Deep Learning，Generalization Gap And Sharp Minima，这篇 Paper 的实验结果如下：

可以看到在测试集上，小的Batch（SB，Small Batch）明显效果要比大的Batch效果好。那又为何会就这样的现象？文章给出了解释：

假设这个是我们的Training Loss，那在这个Training Loss 上面呢，可能有很多个Local Minima，有不只一个Local Minima，那这些 Local Minima 它们的 Loss 都很低，它们 Loss 可能都趋近于 0，但是这个 Local Minima，还是有好 Minima 跟坏 Minima 之分。如果一个 Local Minima 它在一个峡谷里面，它是坏的 Minima，然后它在一个平原上，它是好的 Minima，为什么会有这样的差异呢？

因为假设现在 Training 跟 Testing 中间，有一个 Mismatch，Training 的 Loss 跟 Testing 的 Loss，它们那个 Function 不一样，有可能是本来你 Training 跟 Testing 的 Distribution就不一样。那也有可能是因为 Training 跟 Testing，你都是从 Sample 的 Data 算出来的，也许 Training 跟 Testing，Sample 到的 Data 不一样，那所以它们算出来的 Loss，当然是有一点差距。那我们就假设说这个 Training 跟 Testing，它的差距就是把 Training 的 Loss这个 Function 往右平移一点，这时候你会发现，对左边这个在一个盆地里面的 Minima 来说，它的在 Training 跟 Testing 上面的结果，不会差太多，只差了一点点，但是对右边这个在峡谷里面的 Minima 来说，一差就可以天差地远。

它在这个 Training Set 上，算出来的 Loss 很低，但是因为 Training 跟 Testing 之间的不一样，所以 Testing 的时候，这个 Error Surface 一变，它算出来的 Loss 就变得很大，而很多人相信这个大的 Batch Size，会让我们倾向于走到峡谷里面，而小的 Batch Size，倾向于让我们走到盆地里面。那他直觉上的想法是这样，就是小的 Batch，它有很多的 Loss，它每次 Update 的方向都不太一样，所以如果今天这个峡谷非常地窄，它可能一个不小心就跳出去了，因为每次 Update 的方向都不太一样，它的 Update 的方向也就随机性，所以一个很小的峡谷，没有办法困住小的 Batch。

如果峡谷很小，它可能动一下就跳出去，之后停下来如果有一个非常宽的盆地，它才会停下来，那对于大的 Batch Size，反正它就是顺著规定 Update，然后它就很有可能，走到一个比较小的峡谷里面。但这只是一个解释，那也不是每个人都相信这个解释，那这个其实还是一个尚待研究的问题。

那这边对大小Batch做一个总结，如图：

Momentum

Momentum，这也是另外一个有可能可以对抗 Saddle Point 或 Local Minima 的技术，Momentum 的运作是这个样子的：

它的概念，你可以想像成在物理的世界里面，假设 Error Surface 就是真正的斜坡，而我们的参数是一个球，你把球从斜坡上滚下来，如果今天是 Gradient Descent，它走到 Local Minima 就停住了，走到 Saddle Point 就停住了，但是在物理的世界里，一个球如果从高处滚下来，从高处滚下来就算滚到 Saddle Point，如果有「惯性」，它从左边滚下来，因为惯性的关系它还是会继续往右走，甚至它走到一个 Local Minima，如果今天它的动量够大的话，它还是会继续往右走，甚至翻过这个小坡然后继续往右走，那所以今天在物理的世界里面，一个球从高处滚下来的时候，它并不会被 Saddle Point，或 Local Minima卡住，不一定会被 Saddle Point，或 Local Minima 卡住，我们有没有办法运用这样子的概念，到 Gradient Descent 里面呢，那这个就是我们等一下要讲的，Momentum 技术。

Vanilla Gradient Descent

那我们先很快的复习一下，原来的 Gradient Descent 长得是什么样子，这个是 Vanilla 的 Gradient Descent，Vanilla 的意思就是一般的的意思，它直译是香草的，但就其实是一般的，一般的 Gradient Descent 长什么样子呢

一般的 Gradient Descent 是说，我们有一个初始的参数叫做 θ 0 θ^0 θ0，我们计算一下 Gradient，然后计算完这个 Gradient 以后呢，我们往 Gradient 的反方向去 Update 参数：
θ 1 = θ 0 − η g 0 θ^1 = θ^0 – {\eta}g^0 θ1=θ0−ηg0

我们到了新的参数以后，再计算一次 Gradient，再往 Gradient 的反方向，再 Update 一次参数，到了新的位置以后再计算一次 Gradient，再往 Gradient 的反方向去 Update 参数，这个 Process 就一直这样子下去。

Gradient Descent + Momentum

加上 Momentum 以后，每一次我们在移动我们的参数时，我们不是只往 Gradient Desent 的反方向来移动参数，我们是 Gradient 的反方向，加上前一步移动的方向，两者加起来的结果，去调整去到我们的参数，

那具体说起来是这个样子，一样找一个初始的参数，然后我们假设前一步的参数的 Update 量呢，就设为 0。
m 0 = 0 m^0 = 0 m0=0

接下来在 θ 0 θ^0 θ0 的地方，计算 Gradient 的方向 g 0 g^0 g0，然后接下来你要决定下一步要怎么走，它是 Gradient 的方向加上前一步的方向，不过因为前一步正好是 0，现在是刚初始的时候所以前一步是 0，所以 Update 的方向，跟原来的 Gradient Descent 是一样的，这没有什么有趣的地方。

m 1 = λ m 0 − η g 0 θ 1 = θ 0 + m 1 m^1 = {\lambda}m^0- {\eta}g^0 \\\ θ^1 = θ^0 + m^1 m1=λm0−ηg0θ1=θ0+m1

但从第二步开始，有加上 Momentum 以后就不太一样了，从第二步开始，我们计算 g 1 g^1 g1，然后接下来我们 Update 的方向，不是 g 1 g^1 g1的反方向，而是根据上一次 Update 方向，也就是 m 1 m^1 m1 减掉 g 1 g^1 g1，当做我们新的 Update 的方向，这边写成 m 2 m^2 m2：
m 2 = λ m 1 − η g 1 m^2 = {\lambda}m^1-{\eta}g^1 m2=λm1−ηg1

那我们就看下面这个图：

g 1 g^1 g1 告诉我们，Gradient 告诉我们要往红色反方向这边走，但是我们不是只听 Gradient 的话，加上 Momentum 以后，我们不是只根据 Gradient 的反方向，来调整我们的参数，我们也会看前一次 Update 的方向：

• 如果前一次说要往 m 1 m^1 m1蓝色及蓝色虚线这个方向走
• Gradient 说要往红色反方向这个方向走
• 把两者相加起来，走两者的折中，也就是往蓝色 m 2 m^2 m2这一个方向走，所以我们就移动了 m 2 m^2 m2，走到 θ 2 θ^2 θ2 这个地方

接下来就反覆进行同样的过程，在这个位置我们计算出 Gradient，但我们不是只根据 Gradient 反方向走，我们看前一步怎么走，前一步走这个方向，走这个蓝色虚线的方向，我们把蓝色的虚线加红色的虚线，前一步指示的方向跟 Gradient 指示的方向，当做我们下一步要移动的方向。

每一步的移动，我们都用 m 来表示，那这个 m 其实可以写成之前所有算出来的，Gradient 的 Weighted Sum.从右边的这个式子，其实就可以轻易的看出来

m 0 = 0 m 1 = − η g 0 m 2 = − λ η g 0 − η g 1 . . . m^0 = 0\\\ m^1 = -{\eta}g^0\\\ m^2 = -{\lambda}{\eta}g^0-{\eta}g^1\\\ … m0=0m1=−ηg0m2=−ληg0−ηg1...

m 0 m^0 m0 我们把它设为 0， m 1 m^1 m1 是 m 0 m^0 m0 减掉 g 0 g^0 g0， m 0 m^0 m0 为 0，所以 m 1 m^1 m1 就是 g 0 g^0 g0 乘上负的 $\eta$， m 2 m^2 m2 是 $\lambda$ 乘上 m 1 m^1 m1，$\lambda$ 就是另外一个参数，就好像 $\eta$ 是 Learning Rate 我们要调，$\lambda$ 是另外一个参数，这个也是需要调的， m 2 m^2 m2 等于 $\lambda$ 乘上 m 1 m^1 m1，减掉 $\eta$ 乘上 g 1 g^1 g1，然后 m 1 m^1 m1 在哪里呢， m 1 m^1 m1 在这边，你把 m 1 m^1 m1 代进来，就知道说 m 2 m^2 m2，等于负的 $\lambda$ 乘上 $\eta$ 乘以 g 0 g^0 g0，减掉 $\eta$ 乘上 g 1 g^1 g1，它是 g 0 g^0 g0 跟 g 1 g^1 g1 的 Weighted Sum。以此类推，所以你会发现说，现在这个加上 Momentum 以后，一个解读是 Momentum 是，Gradient 的负反方向加上前一次移动的方向，那但另外一个解读方式是，所谓的 Momentum，当加上 Momentum 的时候，我们 Update 的方向，不是只考虑现在的 Gradient，而是考虑过去所有 Gradient 的总合.

总结就是，Monmentum类似于物理的动量或惯性，在迭代的时候不会因为梯度下降为0则立刻停止，它会有一个向前制动的过程，然后缓慢停止。这带来的好处就是，不会说遇到梯度下降为0的 critial point 时，无法继续迭代，让我们使用者不好判断到底是 saddle point 还是 local minima。

Adaptive Learning Rate

前面说到，训练一个network，train到发现loss不再下降的時候，并不一定是梯度为0或者极小，也可能是saddle point，除此之外也可能是我们训练时，batch-size的大小设置不当导致的。那之前也说到，梯度下降时，是有学习率的，也可能是因为学习率过小导致的（但是学习率太大的话，又有可能在local minima上放反复横条，如下图左图），因为学习率过小，无法到达的话，就如下图右图所示：

这个训练永远走不到终点，就是因为learning rate已经太小了，可以看到，上图右图在左拐的时候，迭代了10万次仍然只走了一小部分，上面这个地方坡度已经非常的平滑了，这么小的learning rate根本没有办法再让训练前进。在之前的gradient descend，所有的参数都是设同样的learning rate。这里我们可以客制化学习率，让其自动调整，「不会因为」梯度下降时偏微分的值越来越小的同时而保持学习率不变。

那我们要怎么客制化learning rate呢，不同的参数到底需要什么样的learning rate？从刚才的例子里面，其实我们可以看到一个大原则，如果在某一个方向上，我们的gradient的值很小，非常的平坦，那我们会希望learning rate调大一点，如果在某一个方向上非常的陡峭，坡度很大，那我们其实期待，learning rate可以设得小一点。

那么我直接列出一下几种变化学习率的方式：

1. Root mean square

在 θ i 2 θ_i^2 θi2​这个方向上loss的变化比较大，所以算出来的gradient都比较大，$\sigma$就比较大；$\sigma$比较大，update的时候step就比较小。所以有了$\sigma$这一项以后呢，就可以随着gradient的不同来自动的调整learning rate的大小。但是这个有个问题：就算是同一个参数，它需要的learning rate也会随着时间而改变。

3. RMSProp

Summary of Optimization

所以我们从最原始的gradient descent，进化到这一个版本：

这个版本里面：

• 我们有Momentum，也就是说现在不是完全顺著gradient的方向，现在不是完全顺著这一个时间点，算出来的gradient的方向，来update参数，而是把过去所有算出来gradient的方向，做一个总和当作update的方向，这个是momentum。
• 接下来应该要update多大的步伐呢，我们要除掉gradient的Root Mean Square。

那么你可能会觉得很困惑，这一个momentum是考虑过去所有的gradient，这个$\sigma$也是考虑过去所有的gradient，一个放在分子一个放在分母，都考虑过去所有的gradient，不就是正好抵销了吗，但是其实这个Momentum跟这个$\sigma$，它们在使用过去所有gradient的方式是不一样的，Momentum是直接把所有的gradient通通都加起来，所以它有考虑方向，它有考虑gradient的正负号，它有考虑gradient是往左走还是往右走；但是这个Root Mean Square，它就不考虑gradient的方向了，它只考虑gradient的大小，记不记得在算$\sigma$时，都要把gradient取一个平方项，我们是把平方的结果加起来，所以我们只考虑gradient的大小，不考虑它的方向，所以Momentum跟这个$\sigma$，算出来的结果并不会互相抵销掉。

• 那最后我们还会加上，一个learning rate的scheduling。

最后说说在分类任务上，应该如何优化神经网络，从optimization的角度，cross-entropy比Mean Square Error更加适合用在分类上。使用cross-entropy这个loss function时，pytorch自动帮你把softmax加到你的Network的最后一层。

以上就是本次学习的内容，理论内容还是非常多的，需要好好消化一下。