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 L Loss的微分为零,当你的参数对 L L Loss微分为零的时候,,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 ( θ ) L(θ) L(θ)完整的样子写不出来,但是它在 θ ′ θ’ θ附近,你可以用这个式子来表示它,这个式子是Tayler Series Appoximation泰勒级数展开,这个假设你在微积分的时候已经学过了,所以我就不会细讲这一串是怎么来的,但我们就只讲一下它的概念,这一串里面包含什么东西呢?

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

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

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

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

g g 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这个向量来表示:

  • 如果今天对任何可能的 v v v v T H v v^THv vTHv都大于零,也就是说现在 θ θ θ不管代入任何值,v可以是任何的v,也就是 θ θ θ可以是任何值,不管 θ θ θ代任何值,红色框框里面通通都大于零,那意味着 L ( θ ) > L ( θ ′ ) L(θ)>L(θ’) L(θ)>L(θ) L ( θ ) L(θ) L(θ)不管代多少只要在 θ ′ θ’ θ附近, L ( θ ) L(θ) L(θ)都大于 L ( θ ′ ) L(θ’) L(θ),代表 L ( θ ′ ) L(θ’) L(θ)是附近的一个最低点,所以它是local minima
  • 如果今天反过来说,对所有的 v v v而言, v T H v v^THv vTHv都小于零,也就是红色框框里面永远都小于零,也就是说 θ θ θ不管代什么值,红色框框里面都小于零,意味着 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 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=w1w2x

我们有一个史上最废的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 L是:
L = ( y ^ − w 1 w 2 x ) 2 L=(\hat{y}-w_1 w_2 x)^2 L=(y^w1w2x)2

正确答案 y ^ \hat{y} y^减掉model的输出 w 1 w 2 x w_1w_2x w1w2x后取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^w1w2x)2,那你可以把这一个loss function的gradient求出来, w 1 w_1 w1 L L L的微分, w 2 w_2 w2 L L L的微分写出来是这个样子:
∂ L ∂ w 1 = 2 ( 1 − w 1 w 2 ) ( − w 2 ) \frac{∂L}{∂w_1 }=2(1-w_1 w_2 )(-w_2 ) w1L=2(1w1w2)(w2)

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

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

就是所谓的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 L L的微分和 w 2 w_2 w2 L L 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 L L的二次微分,所以这个矩阵里面第一个row,第一个coloumn的位置,就是 w 1 w_1 w1 L L L微分两次;第一个row 第二个coloumn的位置,就是先用 w 2 w_2 w2 L L L作微分,再用 w 1 w_1 w1 L L L作微分;然后这边第二行第一列就是 w 1 w_1 w1 L L L作微分, w 2 w_2 w2 L L L作微分;然后右下角 w 2 w_2 w2 L L 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} [0220]

这个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特征向量, λ λ λ μ \mu μ的eigen value特征值。如果我们把这边的 v v v换成 μ \mu μ的话,我们把 μ \mu μ乘在H的左边,跟H的右边,也就是 μ T H μ \mu^TH\mu μTHμ H μ H\mu Hμ会得到 λ μ λ\mu λμ,因为 μ \mu μ是一个eigen vector。所以我们在这边得到 μ T \mu ^ T μT乘上 λ μ \lambda\mu λμ,然后再整理一下,把 μ T \mu^T μT μ \mu μ乘起来,得到 ‖ u ‖ 2 ‖u‖^2 u2,所以得到 λ ‖ μ ‖ 2 λ‖\mu‖^2 λμ2(附近这几张图中的 u u 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,我们这边 θ θ θ θ ′ θ’ θ,放的是一个eigen vector的话,会发现说我们这个红色的项里面,其实就是 λ ‖ μ ‖ 2 λ‖\mu‖^2 λμ2

​如果 λ λ λ小于零,即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得到 θ θ θ,你就可以让loss变小。因为根据这个式子,你只要 θ θ θ θ ′ θ’ θ等于 μ \mu μ,loss就会变小,所以你今天只要让 θ θ θ等于 θ ′ θ’ θ μ \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的最后一层。

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