local minima 的问题如何解决

🚀 在初始神经网络那一节（链接如下：初识机器学习）是遇到了两个问题，第一个是在求解函数未知参数数时会遇到local minima的问题，在哪里我们并没有过多解释，就是说一般遇不到并且很好解决；第二个问题是当时使用的是线性模型，大大限制住了准确率，所以在第二节（线性模型到神经网络）就将模型变得有弹性进化为了神经网路以及深度网络；而这一节将进一步了解local minima的问题

1）优化求解失败

在定义好模型后，就进入训练阶段，即得出相应的损失函数（Loss函数），然后对损失函数使用梯度下降的方法求解最优的参数，但是使用梯度下降求解参数的时候可能就会卡在local minima(局部最优)，从而导致梯度下降求解不出来最优的未知参数（全局最优）。

其实所谓的要通过梯度下降走到全局最优点的话，也就是要该点的偏导都为零，即要为极值点。而local minima的问题就在于，梯度下降走到一点，要是该点的偏导都为零，则会停下来，可是偏导为零的点并不一定最优，也并不一定为极值点；所以这些导数为零的点都会导致梯度下降求解停下来，而这些点并不一定是local minima，也有可能为下图中的saddle point（鞍点），而只有真正遇见local minima的时候，才是真的无路可走了，而导数为零导致梯度下降求解停下来不是正真的local minima 而是saddle point 的话，那也许是有路可走的，对于鞍点来说，四周仍然有两侧可以走，使其损失更低。

所以总结来说，导数为零的是crititical point ( 可疑点 )，若为local minima则无路可走，若为saddle point则有路可走。

该怎么区分是local minima还是saddle point？

对于给定一组 ${\theta }^{{}^{\prime }}$，其实我们是可以通过泰特展开知道${\theta }^{{}^{\prime }}$附近的一个近似的损失函数，即如下图所示的 $L({\theta }^{{}^{\prime }})$ 函数。

其中的$(\theta -{\theta }^{{}^{\prime }}{)}^{T}g$的g也是一个向量，因为损失函数中的$\theta$本身就是一个向量，一组待求解的未知参数，所以求一阶导数，需要对 $\theta$ 向量中的每一个分别求导，同样的当泰勒展开到二阶的时候，其中的$H$ 就表示对 $\theta$求二阶导数。

其中 $H$ 也叫Hessian，是一个矩阵。 其中是对每一个未知参数的二阶导数，所以未知参数为2个的时候，其$H$矩阵就为2×2的矩阵。

由于是crititical point ，其该点的一次微分都为零，所以$(\theta -{\theta }^{{}^{\prime }}{)}^{T}g$这项是零，所以对于在${\theta }^{{}^{\prime }}$这点来说，在该点的近似的损失函数函数就变成了$$L(\theta )=L({\theta }^{{}^{\prime }})+1/2(\theta -{\theta }^{{}^{\prime }}{)}^{T}H(\theta -{\theta }^{{}^{\prime }})$$

这样就可以通过$1/2(\theta -{\theta }^{{}^{\prime }}{)}^{T}H(\theta -{\theta }^{{}^{\prime }})$式子来判断crititical point 的类型，到底是local minima 、local max 还是saddle point。

为了表示方便将 $\theta -{\theta }^{{}^{\prime }}$ 使用 $v$ 来代替，

• 要是对于点 ${\theta }^{{}^{\prime }}$ 附近的任意一点 $\theta$ 带入其$v^{T}Hv$都大于零的话，说明$L(\theta )>L({\theta }^{{}^{\prime }})$，也就是说，在 ${\theta }^{{}^{\prime }}$附近的点都大于$L({\theta }^{{}^{\prime }})$的值，所以为local minima。
  

• local max
  

• saddle point
  

显然不可能将所有的$v$都带进去计算看其是否是大于零的，但是在线性代数中学过，对于式子$v^{T}Hv$都大于零的话，说明 $H$ 矩阵它是正定的，即所有的特征值都是正的（eigen values are positive）；同样的要判定式子$v^{T}Hv$小于零的话，即要说明 $H$ 矩阵它是负定的，即所有的特征值都是负的（eigen values are negtive）；所以以后要判定一个点到底是什么点，就只需要计算Hessian矩阵的特征值，特征值都为正，则为local minima；特征值都为负，则为local max；特征值有正有负的话，则为saddle point。

举一个例子，来看看梯度下降遇到微分为零的点而导致的终止训练，判断该点是否为鞍点，若为鞍点怎么一步步逃离鞍点去往global minima 。

例子中，其模型的函数如下图所示，是含两个未知参数$w_1{w}_2$的模型。同时其训练数据也只有（1，1）。

先采用暴搜的方式，穷举所有的$w_1{w}_2$绘制了如下的误差平面图（error surface）。在error surface中，其颜色越艳丽表示误差就越大，显然存在很多的crititical point，在原点处的点显然是saddle point ，在向二四象限走的时候误差会增大，在向一三象限走的时候误差会减小。显然就是一个saddle point。

假设现在不进行暴搜，只是通过计算来看是否是saddle point，即只需要先得到损失函数，如下图所示：

然后先计算损失函数的一阶导数值，然后来判断（0，0）是什么点，通过下图可以看出，分别计算了$w_1{w}_2$的偏导数，将（0，0）带入得到其一阶导数都为零，所以（0，0）是一个可疑点。

现在需要进一步判断可疑点（0，0）到底为什么点，即需要计算二阶导数，即计算Hessian矩阵所有特征值即可判断。

如上图所示，分别得到了二阶导数的值，也就是得到了Hessian矩阵，其如下$$\left[\begin{array}{cc}0& -2\\ -2& 0\end{array}\right]\text{\hspace{1em}(Hessian)}$$
然后再计算Hessian矩阵所有的特征值，其有两个特征值，一个特征值为2，一个为-2，所以该点为鞍点。

2）怎么逃离鞍点

在某一点处停下来之后，若判断其为鞍点，说明还是有路可以走的，那该怎么逃离鞍点呢？

同样的Hessian矩阵也可以告诉我们参数的跟新方向，假设 $u$ 是 $H$ 矩阵的特征向量，$\lambda$ 是 $H$ 矩阵的特征值，所以对于$u^{T}Hu$ 来说，其进一步被化简为了$\lambda ||u|{|}^2$，那么此时假设$\lambda$是小于零的话，立马就可以推得$u^{T}Hu$ 小于零。

从而进一步推得$L(\theta )<L({\theta }^{{}^{\prime }})$

所以可以得到，只要 $u$ 是 $H$ 矩阵的特征向量且$u=\theta -{\theta }^{{}^{\prime }}$ 时，就是让损失更小，所以只需要让 $\theta$ 朝着$\theta =u+{\theta }^{{}^{\prime }}$的方向走，就可以让损失变小；所以也就是让其朝着Hessian矩阵为负的特征值对应的特征向量的方向走，因为更新的$\theta$是$u+{\theta }^{{}^{\prime }}$，即在${\theta }^{{}^{\prime }}$的基础上再走$u$，即Hessian矩阵的特征向量。

例子， 在求得上述例子的Hessian矩阵$$\left[\begin{array}{cc}0& -2\\ -2& 0\end{array}\right]\text{\hspace{1em}(Hessian)}$$
其有两个特征值，一个特征值为$\lambda =2$ ，一个为$\lambda =-2$，该点为鞍点，选择其中$\lambda =-2$的特征值，其中一个特征向量为$$\left[\begin{array}{c}1\\ 1\end{array}\right]\text{\hspace{1em}(特征向量)}$$，即如下图所示向（1，1）的方向去寻找最优解，很显然这是正确的。

3）local minima怎么解决

在上面很好的解决了，如果遇到的是鞍点的话可以通过 $H$ 矩阵很好的逃离，那local minima 呢？又该怎么解决？

其实所谓的local minima真的很少，在二维来看，这就是一个local minima ，可是一旦扩展到三维世界后，也许就是一个saddle point，所以说，也许在低纬度的世界里，可能无路可走，可是一旦到了高维世界以后，也许到处都是路，不在有local minima。

而在我们今天训练的数据当中，输入动辄成百上千甚至更大，在这么高的维度上，也许到处是路，几乎不会出现local minima的问题。

如下图所示，图中每一个点都代表训练完成停下来（即到了crititical point）的一个神经网络，纵轴为训练完成后的损失，横轴为minimum ratio，其为H矩阵正的特征值的数量比上总的特征值数量。

可以看见大多数网络训练停下来后，最极端的情况minimum ratio为0.6，也还是有负的特征值的，每个停下来的点都还是saddle point，都还是有路可走的！