Question

1. 机器学习中，通常会仔细设计目标函数和约束，从而保证最优化问题是凸的。但是神经网络中，通常遇到的都是非凸的最优化问题。

2.1 病态黑塞矩阵

1. 病态ill-conditioning 的黑塞矩阵 $ \mathbf H $ 是凸优化或者其他形式优化中普遍存在的问题。

   • 在神经网络训练过程中，如果 $ \mathbf H $ 是病态的，则随机梯度下降会“卡”在某些地方：此时即使很小的更新步长也会增加代价函数。
   • 当黑塞矩阵是病态时，牛顿法是一个很好的解决方案。但是牛顿法并不适用于神经网络，需要对它进行较大改动才能用于神经网络。

2. 将 $ f(\mathbf{\vec x}) $ 在 $ \mathbf{\vec x}_0 $ 处泰勒展开： $ f(\mathbf{\vec x}) \approx f(\mathbf{\vec x}_0)+(\mathbf{\vec x}-\mathbf{\vec x}_0 )^{T}\mathbf{\vec g}+\frac 12(\mathbf{\vec x}-\mathbf{\vec x}_0)^{T}\mathbf H (\mathbf{\vec x}-\mathbf{\vec x}_0) $ 。其中 $ \mathbf{\vec g} $ 为 $ \mathbf{\vec x}_0 $ 处的梯度； $ \mathbf H $ 为 $ \mathbf{\vec x}_0 $ 处的海森矩阵。

   根据梯度下降法： $ \mathbf{\vec x}^{\prime}= \mathbf{\vec x}-\epsilon\nabla _{\mathbf{\vec x}} f(\mathbf{\vec x}) $ 。应用在点 $ \mathbf{\vec x}_0 $ ，有：

   $ f(\mathbf{\vec x}_0-\epsilon\mathbf{\vec g})\approx f(\mathbf{\vec x}_0)-\epsilon\mathbf{\vec g}^{T}\mathbf{\vec g}+\frac 12\epsilon^{2}\mathbf{\vec g}^{T}\mathbf H \mathbf{\vec g} $

   因此沿着负梯度的方向，步长 $ -\epsilon\mathbf{\vec g} $ 将导致代价函数 $ f $ 增加： $ -\epsilon\mathbf{\vec g}^{T}\mathbf{\vec g}+\frac 12\epsilon^{2}\mathbf{\vec g}^{T}\mathbf H \mathbf{\vec g} $ 。

   当 $ \frac \epsilon 2 \mathbf{\vec g}^{T}\mathbf H \mathbf{\vec g} \gt \mathbf{\vec g}^{T}\mathbf{\vec g} $ 时，黑塞矩阵的病态会成为问题。此时沿着负梯度的方向，代价函数 $ f $ 的值反而在增长！

3. 理论上，随着训练的推进，梯度的平方范数 $ \mathbf{\vec g}^{T}\mathbf{\vec g} $ 应该逐步降低并最终收敛到 0 。因为代价函数 $ f $ 取极小值时，梯度为 0 。

   实际上在很多问题中，梯度的平方范数 $ \mathbf{\vec g}^{T}\mathbf{\vec g} $ 并不会在训练过程中显著缩小，而是随着时间的延长在增加，且并不随着训练过程收敛到临界点而减小。

   下面左图为梯度的范数随着时间的变化，右图为验证集上的分类误差随着时间的变化。

   

   这是因为 $ \mathbf{\vec g}^{T}\mathbf H\mathbf{\vec g} $ 会更快速的增长（相对于 $ \mathbf{\vec g}^{T}\mathbf{\vec g} $ ） 。它带来两个结果：

   • 尽管梯度很强，但是训练却可以成功，因为它使得代价函数 $ f $ 的增量不断逼近0（增量为0表示到达极值点）。
   • 尽管梯度很强，但是学习会变得非常缓慢，因为学习率必须减小从而适应更强的曲率。

2.2 局部极小值

1. 对于非凸函数，如神经网络，可能存在多个局部极小值。实际上这并不是一个严重的问题。

2. 如果一个训练集可以唯一确定一组模型参数，则该模型称作可辨认的identifiable 。

   • 带有隐变量的模型通常是不可辨认的。因为可以批量交换隐变量，从而得到等价的模型。如：交换隐单元 $ i $ 和 $ j $ 的权重向量。

     这种不可辨认性称作权重空间对称性weight space symmetry 。

   • 也可以放大权重和偏置 $ \alpha $ 倍，然后缩小输出 $ \frac 1\alpha $ 倍，从而保持模型等价。

   • 模型可辨认性问题意味着：神经网络的代价函数具有非常多、甚至是无限多的局部极小解。

   • 由可辨认性问题产生的局部极小解都具有相同的代价函数值，它并不是代价函数非凸性带来的问题。

3. 如果局部极小解和全局极小解相差很大时，此时多个局部极小解会带来很大隐患。它将给基于梯度的优化算法带来很大的问题。

   • 实际中的网络，是否存在大量严重偏离全局极小解的局部极小解、优化算法是否会遇到这些局部极小解？

     这些都是未决的问题。

   • 目前学者们猜想：对于足够大的神经网络，大部分局部极小值都具有很小的代价函数值。

     是否找到全局极小值并不重要，实际上只需要在参数空间中找到一个使得损失函数很小的点。

4. 目前很多人将神经网络优化中的所有困难都归结于局部极小值。

   有一种方案是排除局部极小值导致的困难（说明是其他原因导致的困难）：绘制梯度范数随着时间的变化：

   • 如果梯度范数没有缩小到一个很小的值，则问题的原因既不是局部极小值引起的，也不是其他形式的临界点（比如鞍点）引起的。
   • 如果梯度范数缩小到一个很小的值，则问题的原因可能是局部极小值引起的，也可能是其他原因引起的。

5. 神经网络训练中，通常不关注代价函数的精确全局极小值，而是关心将代价函数值下降到足够小，从而获得一个很好的泛化误差。

   关于优化算法能否到达这个目标的理论分析是极其困难的。

2.3 鞍点

1. 鞍点是另一类梯度为零的点。鞍点附近的某些点的函数值比鞍点处的值更大，鞍点附近的另一些点的函数值比鞍点处的值更小。

2. 在鞍点处，黑塞矩阵同时具有正负特征值：

   • 正特征值对应的特征向量方向的点，具有比鞍点更大的值。
   • 负特征值对应的特征向量方向的点，具有比鞍点更小的值。

3. 通常在低维空间中，局部极小值很普遍；在高维空间中，局部极小值很少见，鞍点更常见。

   • 对于函数 $ f:\mathbb R^{n}\rightarrow \mathbb R $ ，鞍点和局部极小值的数量之比的期望随着 $ n $ 呈指数级增长。

   • 假如黑塞矩阵的特征值的正负号由抛硬币来决定的话：

     • 在一维情况下，很容易抛硬币得到正面向上。
     • 而在 $ n $ 维中，很难出现 $ n $ 次抛硬币都是正面向上。

4. 当位于函数值较低的区间时，黑塞矩阵的特征值为正的可能性更大。这意味着：

   • 具有较大函数值的临界点更可能是鞍点，因为此时黑塞矩阵的特征值可能既存在正值、也存在负值。
   • 具有较小函数值的临界点更可能是局部极小值点，因为此时黑塞矩阵的特征值更可能全部为正值。
   • 具有极高函数值的临界点更可能是局部极大值点，因为此时黑塞矩阵的特征值更可能全部为负值。

5. 鞍点对于训练算法的影响：

   • 对于只使用了梯度的一阶优化算法而言：情况不明。

     • 理论上，鞍点附近的梯度通常会非常小，这导致梯度下降算法沿着梯度方向的步长非常小。
     • 实际上，梯度下降算法似乎在很多情况下都能够逃离鞍点。

   • 对于牛顿法而言，鞍点是个大问题。

     因为梯度下降的原则是：朝着下坡路的方向移动。而牛顿法的原则是：明确寻找梯度为零的点。如果不做任何修改，则牛顿法会主动跳入一个鞍点。

6. 也可能出现一个恒值的、平坦的宽区域：在这个区域中，梯度和黑塞矩阵都为零。

2.4 悬崖

1. 多层神经网络通常有像悬崖一样的区域，悬崖是指代价函数斜率较大的区域。

2. 产生悬崖的原因：由于几个较大的权重相乘，导致求导的时候，其梯度异常巨大。

   在RNN网络的代价函数中悬崖结构很常见，因为RNN 这一类模型会涉及到多个时间步长中的因子的相乘，导致产生了大量的权重相乘。

3. 悬崖的影响：在梯度更新时，如果遇到悬崖，则会导致参数更新的步长非常大（因为此时梯度非常大），从而跨了非常大的一步，使得参数弹射的非常远。这样可能会使得已经完成的大量优化工作无效。

   因为当弹射非常远时，可能横跨了参数空间的很多个区域而进入到另一个区域。这样已经探索的参数区域就被放弃了。

   下图是一个悬崖的例子：第二根路径就是由于遇到悬崖，导致参数更新的步长非常大。

   

4. 解决悬崖问题的方案：使用梯度截断策略。

   梯度下降法只是指明了参数更新的方向（负梯度的方向），但是未指明最佳步长。当常规的梯度下降算法建议更新一大步时，梯度截断会干涉并缩减步长，从而使其基本上贴着悬崖来更新。如上图的第一根路径所示。

2.5 长期依赖

1. 当计算图非常深时，容易产生另一种优化困难：长期依赖。

   假设计算图中包含一条重复地、与矩阵 $ \mathbf W $ 相乘的路径。经过 $ t $ 步，则相当于与 $ \mathbf W^{t} $ 相乘。在第 $ i $ 步有： $ \mathbf{\vec h}_t = \mathbf W^{t-i}\mathbf{\vec h}_i $ 。

   根据反向传播原理，有： $ \nabla_{\mathbf{\vec h}_i} J = \left(\frac{\partial \mathbf{\vec h}_t}{\partial \mathbf{\vec h}_i}\right)^T\nabla_{\mathbf{\vec h}_t} J =( \mathbf W^{t-i})^T \nabla_{\mathbf{\vec h}_t} J $ 。

   考虑到权重 $ \mathbf W $ 参与到每个时间步的计算，因此有： $ \nabla_{\mathbf W}=\sum_{i=1}^t \frac{\partial J}{\partial \mathbf{\vec h}_i} \mathbf{\vec h}_{i-1}^T=\sum_{i=1}^t ( \mathbf W^{t-i})^T (\nabla_{\mathbf{\vec h}_t} J ) \mathbf{\vec h}_{i-1}^T $ 。

   其中记 $ \mathbf{\vec x}=\mathbf{\vec h}_0 $ 。假设矩阵 $ (\nabla_{\mathbf{\vec h}_t} J ) \mathbf{\vec x}^T = c \mathbf I $ ，则有：

   $ \nabla_{\mathbf W}= \sum_{i=1}^t ( \mathbf W^{t-i})^T (\nabla_{\mathbf{\vec h}_t} J )(\mathbf W^{i-1} \mathbf{\vec x})^T = \sum_{i=1}^t c (\mathbf W^{t-1}) ^T=c\times t \times (\mathbf W^{t-1}) ^T $

   假设 $ \mathbf W $ 有特征值分解 $ \mathbf W=\mathbf V \Lambda \mathbf V^{-1} $ ，则： $ \mathbf W^{t-1}=\mathbf V \Lambda^{t-1}\mathbf V^{-1} $ 。其中：

   $ \Lambda=\begin{bmatrix} \lambda_1&0&\cdots&0\\ 0&\lambda_2&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&\lambda_n \end{bmatrix} $

   考虑特征值 $ \lambda_i $ ，当它不在 1 附近时：

   • 如果量级大于 1， $ \lambda_i^{t} $ 非常大，这称作梯度爆炸问题exploding gradient problem。

     梯度爆炸使得学习不稳定，悬崖结构是梯度爆炸的一个例子。

   • 如果量级小于 1， $ \lambda_i^{t} $ 非常小，这称作梯度消失问题 vanishing gradient problem。

     梯度消失使得学习难以进行，此时学习的推进会非常缓慢。

   

2. 循环网络在每个时间步上使用相同的矩阵 $ \mathbf W $ ，因此非常容易产生梯度爆炸和梯度消失问题。

   前馈神经网络并没有在每一层使用相同的矩阵 $ \mathbf W $ ，因此即使是非常深层的前馈神经网络也能很大程度上避免梯度爆炸和梯度消失问题。

3. 对于梯度爆炸，可以通过梯度裁剪来缓解：限定梯度的范数的上限。

   对于梯度消失，不能够简单的通过放大来解决。因为有两个问题：

   • 当梯度很小的时候，无法分辨它是梯度消失问题，还是因为抵达了极小值点。

   • 当梯度很小的时候，噪音对梯度的影响太大。获得的梯度很可能由于噪音的影响，导致它的方向是随机的。

     此时如果放大梯度，则无法确保此时的方向就是代价函数下降的方向。而对于梯度爆炸，如果缩小梯度，仍然可以保证此时的方向就是代价函数下降的方向。

2.6 非精确梯度

1. 大多数优化算法都假设知道精确的梯度或者Hessian矩阵，实际中这些量都有躁扰，甚至是有偏的估计。如：mini-batch随机梯度下降中，用一个batch 的梯度来估计整体的梯度。

   各种神经网络优化算法的设计都考虑到了梯度估计的不精确。

2. 另外，实际情况中的目标函数是比较棘手的，甚至难以用简洁的数学解析形式给出。

   此时可以选择替代损失函数来避免这个问题。

2.7 局部和全局结构的弱对应

1. 对于最优化问题，即使克服了以上的所有困难，但是并没有到达代价函数低得多的区域，则表现仍然不佳。这就是局部优秀，全局不良。

   • 局部优秀：跨过了鞍点、爬过了悬崖、克服了梯度消失，最终到达局部极小值点。
   • 全局不良：并未到达目标函数全局比较小的值所在的区域。

2. 大多数优化研究的难点集中于：目标函数是否到达了全局最小值、局部最小值、鞍点。

   但是实践中，神经网络不会到达任何一种临界点，甚至不会到达梯度很小的区域，甚至这些临界点不是必然存在的。

   如：损失函数 $ -\log p(y\mid \mathbf{\vec x};\vec\theta) $ 没有全局极小点，而是趋向于某个极限值。

3. 下图的例子说明：即使没有局部极小值和鞍点，还是无法使用梯度下降得到一个好的结果。

   原因是：初始化在山的左侧。左侧向左趋向于一条渐近线，此时梯度的负方向会不停向左来逼近这条渐进线。

   理论上，优化算法要向右跨过山头，从而沿着右侧下降才能到达一个较低的函数值。

   

4. 在局部结构中执行梯度下降（称作局部梯度下降）的问题：

   • 局部梯度下降或许能找出一条解路径，但是该路径可能包含了很多次梯度更新，遵循该路径会带来很高的计算代价。

   • 如果目标函数是类似 $ -\log p(y\mid \mathbf{\vec x};\vec\theta) $ 函数：没有任何鞍点、极值点，而是具有一个宽而平坦的区域（这个区域逼近某个极限）。

     此时，若要寻求一个精确的临界点，则局部梯度下降无法给出解路径。这意味着算法难以收敛。

   • 局部梯度下降可能太过贪心，使得训练虽然朝着梯度下降的方向移动，但是远离了真正的解。

5. 如果存在某个参数区域，当遵循局部梯度下降就能够合理地直接到达最优解，且参数初始化点就位于该区域，则局部梯度下降的问题就得到解决。

6. 现有的很多研究方法在求解局部结构复杂的最优化问题时，解决方案为：寻求良好的初始化点，而不再是寻求良好的全局参数更新算法。