局部极小值与鞍点
临界点：
局部极小值 ：
鞍点：
局部极小值与鞍点
我们在做优化的时候经常会发现，随着参数不断更新，训练的损失不会再下降, 但是我们对这个损失仍然不满意。把深层网络（deep network）、线性模型和浅层网络（shallow network）做比较，可以发现深层网络没有做得更好——深层网络没有发挥出它完整的力量，所以优化是有问题的。但有时候，模型一开始就训练不起来，不管我们怎么更新参数，损失都降不下去。这个时候到底发生了什么事情？
临界点及其种类
过去常见的一个猜想是我们优化到某个地方，这个地方损失关于参数的微分为零，如图所示。图中的两条曲线对应两个神经网络训练的过程。当损失关于参数的微分为零的时候，梯度下降就不能再更新参数了，训练就停下来了，损失不再下降了。
提到梯度为零的时候，大家最先想到的可能就是局部极小值（local minimum），如图 3.2a 所示。所以经常有人说，做深度学习时使用梯度下降会收敛在局部极小值，梯度下降不起作用。但其实损失不是只在局部极小值的梯度是零，还有其他可能会让梯度是零的点，比如鞍点（saddle point）。鞍点其实就是梯度是零且区别于局部极小值和局部极大值（local maximum）的点。图 3.2b 红色的点在 $y$ 轴方向是比较高的，在 $x$ 轴方向是比较低的，这就是一个鞍点。鞍点的叫法是因为其形状像马鞍。鞍点的梯度为零，但它不是局部极小值。我们把梯度为零的点统称为临界点（critical point）。损失没有办法再下降，也许是因为收敛在了临界点，但不一定收敛在局部极小值，因为鞍点也是梯度为零的点。
但是如果一个点的梯度真的很接近零，我们走到临界点的时候，这个临界点到底是局部极小值还是鞍点，是一个值得去探讨的问题。因为如果损失收敛在局部极小值，我们所在的位置已经是损失最低的点了，往四周走损失都会比较高，就没有路可以走了。但鞍点没有这个问题，旁边还是有路可以让损失更低的。只要逃离鞍点，就有可能让损失更低。
判断临界值种类的方法
判断一个临界点到底是局部极小值还是鞍点需要知道损失函数的形状。可是怎么知道损失函数的形状？网络本身很复杂，用复杂网络算出来的损失函数显然也很复杂。虽然无法完整知道整个损失函数的样子，但是如果给定某一组参数，比如 $\theta^{\prime}$，在 $\theta^{\prime}$ 附近的损失函数是有办法写出来的——虽然 $L(\theta)$ 完整的样子写不出来。$\theta^{\prime}$ 附近的 $L(\theta)$ 可近似为
$$
L(\theta)\approx L\left(\theta^{\prime}\right)+\left(\theta-\theta^{\prime}\right)^{T} g+\frac{1}{2}\left(\theta-\theta^{\prime}\right)^{T} H\left(\theta-\theta^{\prime}\right).\qquad(3.1)
$$
式(3.1)是泰勒级数近似(Tayler series approximation)。
- 第一项 $L(\theta^{\prime})$ 告诉我们，当 $\theta$ 跟 $\theta^{\prime}$ 很近的时候，$L(\theta)$ 应该跟 $L\left(\theta^{\prime}\right)$ 还蛮靠近的；
- 第二项 $\left(\theta-\theta^{\prime}\right)^{T} g$ 中，$g$ 代表梯度，它是一个向量，可以弥补 $L\left(\theta^{\prime}\right)$ 跟 $L(\theta)$ 之间的差距。有时候梯度 $g$ 会写成 $\nabla L\left(\theta^{\prime}\right)$。$g_i$ 是向量 $g$ 的第 $i$ 元素，就是 $L$ 于 $\theta$ 的第 $i$ 元素的偏导数，即
$$
g_i=\frac{\partial L\left(\theta^{\prime}\right)}{\partial\theta_i}.\qquad(3.2)
$$
- 光看 $g$ 还是没有办法完整地描述 $L(\theta)$，还要看式(3.1)的第三项 $\frac{1}{2}\left(\theta-\theta^{\prime}\right)^{T} H\left(\theta-\theta^{\prime}\right)$。第三项跟海森矩阵(Hessian matrix) $H$ 关。$H$ 面放的是 $L$ 的二次微分，它第 $i$ ，第 $j$ 的值 $H_{i j}$ 就是把 $\theta$ 的第 $i$ 个元素对 $L\left(\theta^{\prime}\right)$ 作微分，再把 $\theta$ 的第 $j$ 元素对 $\frac{\partial L\left(\theta^{\prime}\right)}{\partial\theta_i}$ 作微分后的结果，即
$$
H_{i j}=\frac{\partial^2}{\partial\theta_i\partial\theta_j} L\left(\theta^{\prime}\right).\qquad(3.3)
$$
总结一下，损失函数 $L(\theta)$ 在 $\theta^{\prime}$ 附近可近似为式(3.1)，式(3.1)跟梯度和海森矩阵有关，梯度就是一次微分，海森矩阵里面有二次微分的项。
在临界点，梯度$g$ 零，因此 $\left(\theta-\theta^{\prime}\right)^{T} g$ 为零。所以在临界点的附近，损失函数可被近似为
$$ L(\theta)\approx L\left(\theta^{\prime}\right)+\frac{1}{2}\left(\theta-\theta^{\prime}\right)^{T} H\left(\theta-\theta^{\prime}\right);\quad(3.4) $$
我们可以根据 $\frac{1}{2}\left(\theta-\theta^{\prime}\right)^{T} H\left(\theta-\theta^{\prime}\right)$ 来判断在 $\theta^{\prime}$ 附近的误差表面(error surface)到底长什么样子。知道误差表面的“地貌”，我们就可以判断 $L\left(\theta^{\prime}\right)$ 是局部极小值、局部极大值，还是鞍点。为了符号简洁，我们用向量 $v$ 表示 $\theta-\theta^{\prime},\left(\theta-\theta^{\prime}\right)^{T} H\left(\theta-\theta^{\prime}\right)$ 可改写为 $v^{T} H v$，有如下三种情况。
(1) 如果对所有 $v, v^{T} H v>0$。这意味着对任意 $\theta, L(\theta)>L\left(\theta^{\prime}\right)$。只要 $\theta$ 在 $\theta^{\prime}$ 附近，$L(\theta)$ 都大于 $L\left(\theta^{\prime}\right)$。这代表 $L\left(\theta^{\prime}\right)$ 是附近的一个最低点，所以它是局部极小值。
(2) 如果对所有 $v, v^{T} H v<0$。这意味着对任意 $\theta, L(\theta)<L\left(\theta^{\prime}\right)$，$\theta^{\prime}$ 是附近最高的一个点，$L\left(\theta^{\prime}\right)$ 是局部极大值。
(3) 如果对于 $v, v^{T} H v$ 有时候大于零，有时候小于零。这意味着在 $\theta^{\prime}$ 附近，有时候 $L(\theta)>L\left(\theta^{\prime}\right)$，有时候 $L(\theta)<L\left(\theta^{\prime}\right)$。因此在 $\theta^{\prime}$ 附近，$L\left(\theta^{\prime}\right)$ 既不是局部极大值，也不是局部极小值，而是鞍点。
有一个问题，通过 $\frac{1}{2}\left(\theta-\theta^{\prime}\right)^{T} H\left(\theta-\theta^{\prime}\right)$ 判断临界点是局部极小值还是鞍点还是局部极大值，需要代入所有的 $\theta$。但我们不可能把所有的 $v$ 拿来试试看，所以有一个更简便的方法来判断 $v^{T} H v$ 的正负。算出一个海森矩阵后，不需要把它跟所有的 $v$ 都乘乘看，只要看 $H$ 特征值。若 $H$ 所有特征值都是正的，$H$ 正定矩阵，则 $v^{T} H v>0$，临界点是局部极小值。若 $H$ 所有特征值都是负的，$H$ 负定矩阵，则 $v^{T} H v<0$，临界点是局部极大值。若$H$ 特征值有正有负，临界点是鞍点。
如果 $n$ 对称矩阵 $A$ 于任意非零的 $n$ 向量 $x$ 都有 $x^{T} A x>0$，则称矩阵 $A$ 为正定矩阵。如果 $n$ 对称矩阵 $A$ 对于任意非零的 $n$ 向量 $x$ 都有 $x^{T} A x<0$，则称矩阵$A$ 负定矩阵。
举个例子，我们有一个简单的神经网络，它只有两个神经元，而且这个神经元还没有激活函数和偏置。输入 $x$，$x$ 上 $w_1$ 以后输出，然后再乘上 $w_2$，接着再输出，最终得到的数据就是 $y$。
$$
y=w_1 w_2 x.\qquad(3.5)
$$
我们还有一个简单的训练数据集，这个数据集只有一组数据(1,1)，也就是 $x=1$ 的标签是 1。所以输入 1进去，我们希望最终的输出跟 1越接近越好，如图 3.3所示。
可以直接画出这个神经网络的误差表面，如图 3.4所示，可以取[-2,2]之间的 $w_1$ 跟 $w_2$ 的数值，算出这个范围内 $w_1, w_2$ 数值所带来的损失，四个角落的损失是高的。我们用黑色的点来表示临界点，原点(0,0)是临界点，另外两排点是临界点。我们可以进一步地判断这些临界点是鞍点还是局部极小值。原点是鞍点，因为我们往某个方向走，损失可能会变大，也可能会变小。而另外两排临界点都是局部极小值。这是我们取[-2,2]之间的参数得到的损失函数以后，得到的损失的值后，画出误差表面后得到的结论。
除了尝试取所有可能的损失，我们还有其他的方法，比如把损失的函数写出来。对于图 3.3所示的神经网络，损失函数 $L$ 正确答案 $y$ 掉模型的输出 $\hat{y}=w_1 w_2 x$ 后取平方误差(square error)，这里只有一组数据，因此不会对所有的训练数据进行加和。令 $x=1, y=1$，损失函数为
$$ L=\left(y-w_1 w_2 x\right)^2=\left(1-w_1 w_2\right)^2.\qquad(3.6) $$
可以求出损失函数的梯度 $g=\left[\frac{\partial L}{\partial w_1},\frac{\partial L}{\partial w_2}\right]$：
$$
\begin{cases}
\frac{\partial L}{\partial w_1} &= 2\left(1-w_1 w_2\right)\left(-w_2\right); \
\frac{\partial L}{\partial w_2} &= 2\left(1-w_1 w_2\right)\left(-w_1\right).
\end{cases}
\qquad(3.7)
$$
什么时候梯度会为零（也就是到一个临界点）呢？比如，在原点时，$w_1=0, w_2=0$，此时的梯度为零，原点就是一个临界点，但通过海森矩阵才能判断它是哪种临界点。刚才我们通过取[-2,2]之间的 $w_1$ 和 $w_2$ 来判断出原点是一个鞍点，但是假设我们还没有取所有可能的损失，我们要看看能不能够用海森矩阵来判断原点是什么临界点。
海森矩阵$H$ 集了$L$ 二次微分：
$$
\left{
\begin{align*}
H_{1,1} &= \frac{\partial^2 L}{\partial w_1^2} = 2\left(-w_2\right)\left(-w_2\right) \
H_{1,2} &= \frac{\partial^2 L}{\partial w_1\partial w_2} = -2 + 4 w_1 w_2 \
H_{2,1} &= \frac{\partial^2 L}{\partial w_2\partial w_1} = -2 + 4 w_1 w_2 \
H_{2,2} &= \frac{\partial^2 L}{\partial w_2^2} = 2\left(-w_1\right)\left(-w_1\right)
\end{align*}
\right.
$$
对于原点，只要把 $w_1=0, w_2=0$ 代进去，有海森矩阵
$$
H=\left[\begin{array}{rr}
0 & -2 \
-2 & 0
\end{array}\right].
\qquad(3.9)
$$
通过海森矩阵来判断原点是局部极小值还是鞍点，要看它的特征值，这个矩阵有两个特征值：2和-2，特征值有正有负，因此原点是鞍点。
如果我们当前处于鞍点，就不用那么害怕了。$H$ 只可以帮助我们判断是不是在一个鞍点，还指出了参数可以更新的方向。之前我们参数更新的时候，都是看梯度 $g$，但是我们走到某个地方以后发现 $g$ 成 0了，就不能再看 $g$ ，$g$ 见了。但如果临界点是一个鞍点，还可以再看 $H$，怎么再看 $H$ ，$H$ 么告诉我们怎么更新参数呢？
设 $\lambda$ 为 $H$ 一个特征值 $\lambda$，$u$ 为其对应的特征向量。对于我们的优化问题，可令 $u=\theta-\theta^{\prime}$，则
$$
u^{T} H u = u^{T}(\lambda u) = \lambda|u|^2.
\qquad(3.10)
$$
若 $\lambda<0$，则 $\lambda|u|^2<0$。所以 $\frac{1}{2}\left(\theta-\theta^{\prime}\right)^{T} H\left(\theta-\theta^{\prime}\right)<0$。此时，$L(\theta)<L\left(\theta^{\prime}\right)$，且
$$
\theta = \theta^{\prime} + u\text{.}
\qquad(3.11)
$$
沿着 $u$ 方向更新 $\theta$，损失就会变小。因为根据式(3.10)和式(3.11)，只要 $\theta=\theta^{\prime}+u$，沿着特征向量 $u$ 方向去更新参数，损失就会变小，所以虽然临界点的梯度为零，如果我们是在一个鞍点，只要找出负的特征值，再找出这个特征值对应的特征向量。将其与 $\theta^{\prime}$ 相加，就可以找到一个损失更低的点。
在前面的例子中，原点是一个临界点，此时的海森矩阵如式(3.9)所示，该海森矩阵有一个负的特征值：-2，特征值-2对应的特征向量有无穷多个。不妨取 $u=[1,1]^{ T}$，作为-2对应的特征向量。我们其实只要顺着u的方向去更新参数，就可以找到一个比鞍点的损失还要更低的点。以这个例子来看，原点是鞍点，其梯度为零，所以梯度不会告诉我们要怎么更新参数。但海森矩阵的特征向量告诉我们只要往 $[1,1]^{\text{T}}$ 的方向更新。损失就会变得更小，就可以逃离鞍点。
所以从这个角度来看，鞍点似乎并没有那么可怕。但实际上，我们几乎不会真的把海森矩阵算出来，因为海森矩阵需要算二次微分，计算这个矩阵的运算量非常大，还要把它的特征值跟特征向量找出来，所以几乎没有人用这个方法来逃离鞍点。还有一些其他逃离鞍点的方法的运算量都比要算海森矩阵小很多。
如图 3.5(a)所示的一维空间中的误差表面，有一个局部极小值。但是在二维空间（如图3.5(b)所示），这个点就可能只是一个鞍点。常常会有人画类似图3.5(c)这样的图来告诉我们深度学习的训练是非常复杂的。如果我们移动某两个参数，误差表面的变化非常的复杂，有非常多局部极小值。低维度空间中的局部极小值点，在更高维的空间中，实际是鞍点。同样地，如果在二维的空间中没有路可以走，会不会在更高维的空间中，其实有路可以走？更高的维度难以视化它，但我们在训练一个网络的时候，参数数量动辄达百万千万级，所以误差表面其实有非常高的维度参数的数量代表了误差表面的维度。既然维度这么高，会不会其实就有非常多的路可以走呢？既然有非常多的路可以走，会不会其实局部极小值就很少呢？而经验上，我们如果自己做一些实验，会发现实际情况也支持这个假说。图3.6是训练某不同神经网络的结果，每个点对应一个神经网络。纵轴代表训练网络时，损失收敛到临界点，损失没法下降时的损失。我们常常会遇到两种情况：损失仍然很高，却遇到了临界点而不再下降；或者损失降得很低，才遇到临界点。图 3.6中，横轴代表最小值比例（minimum ratio），最小值比例定义为
$$
\text{最小值比例} = \frac{\text{正特征值数量}}{\text{总特征值数量}}.
\qquad(3.12)
$$
实际上，我们几乎找不到所有特征值都为正的临界点。在图 3.6所示的例子中，最小值比例最大也不过处于 $0.5\sim 0.6$ 的范围，代表只有约一半的特征值为正，另一半的特征值为负，代表在所有的维度里面有约一半的路可以让损失上升，还有约一半的路可以让损失下降。虽然在这个图上，越靠近右侧代表临界点“看起来越像”局部极小值，但是这些点都不是真正的局部极小值。所以从经验上看起来，局部极小值并没有那么常见。多数的时候，我们训练到一个梯度很小的地方，参数不再更新，往往只是遇到了鞍点。
