Question

1. 有些优化技术并不是真正的算法，而是一个模板：它可以产生特定的算法。

8.1 坐标下降

1. 最小化 $ f(\mathbf{\vec x}) $ 可以采取如下的步骤：

   • 先相对于单一变量 $ x_i $ 最小化。
   • 然后相对于另一个变量 $ x_j $ 最小化。
   • ....
   • 如此反复循环所有的变量，可以保证到达（局部）极小值。

   这种做法被称作坐标下降。

2. 还有一种块坐标下降：它对于全部变量的一个子集同时最小化。

3. 当优化问题中的不同变量能够清晰地划分为相对独立的组，或者优化一组变量明显比优化所有变量的效率更高时，坐标下降最有意义。

4. 当一个变量值很大程度影响另一个变量的最优值时，坐标下降不是个好办法。如：

   $ f(\mathbf{\vec x})=(x_1-x_2)^{2}+\alpha(x_1^{2}+x_2^{2}) $

   • 第一项鼓励两个变量具有相近的值；第二项鼓励它们接近零。

     牛顿法可以一步解决该问题（它是一个正定二次问题），解为零。

   • 对于较小的 $ \alpha $ ，此时函数值由第一项决定。

     此时采用坐标下降法非常缓慢，因为第一项不允许两个变量相差太大。

5. 坐标下降算法可以用于求解稀疏编码的代价函数最小化问题。

   给定训练集 $ \mathbf X $ ，稀疏编码的目标是：寻求一个权重矩阵 $ \mathbf W $ （未知的） 和一个解码字典矩阵 $ \mathbf H $ （也是未知的）来重构训练集 $ \mathbf X $ ，其中要求字典矩阵 $ \mathbf H $ 尽量稀疏 。

   代价函数为： $ J(\mathbf H,\mathbf W)=\sum_{i,j}|\mathbf H_{i,j}|+\sum_{i,j}(\mathbf X-\mathbf W^{T}\mathbf H)_{i,j}^{2} $ 。

   虽然代价函数 $ J $ 不是凸的，但是可以将输入分成两个集合：权重 $ \mathbf W $ 和字典 $ \mathbf H $ 。 $ J $ 关于权重 $ \mathbf W $ 是凸的， $ J $ 关于字典 $ \mathbf H $ 也是凸的。

   因此可以使用块坐标下降（其中可以使用高效的凸优化算法）：交替执行：固定 $ \mathbf H $ 优化 $ \mathbf W $ ，以及固定 $ \mathbf W $ 优化 $ \mathbf H $ 。

8.2 Polyak 平均

1. Polyak 平均的基本思想是：优化算法可能因为震荡，反复穿越极值点而没有落在极值点。因此可以考虑路径的均值来平滑输出。

2. 假设 $ t $ 次迭代，梯度下降的参数迭代路径为 $ \theta^{(1)},\theta^{(1)},\cdots,\theta^{(t)} $ ，则Polyak平均算法的输出为：

   $ \hat \theta^{(t)}=\frac 1t\sum_{i}\theta^{(i)} $
   • 对于凸问题，该方法具有较强的收敛保证。
   • 对于神经网络，这是一种启发式方法，实践中表现良好。

3. 在非凸问题中，优化轨迹的路径可能非常复杂。因此当Polyak应用于非凸问题时，通常会使用指数衰减来计算平均值： $ \hat \theta^{(t)}=\alpha \hat\theta^{(t-1)}+(1-\alpha)\theta^{(t)} $ 。

8.3 贪心监督预训练

1. 有时模型太复杂难以优化，直接训练模型可能太过于困难。此时可以训练一个较简单的模型，然后逐渐使模型复杂化来求解原始问题。

   在直接训练目标模型、求解目标问题之前，训练简单模型求解简化问题的方法统称为预训练。

2. 预训练，尤其是贪心预训练，在深度学习中是普遍存在的。

   贪心监督预训练将复杂的监督学习问题分解成简化的监督学习问题。

3. 贪心监督预训练的一个例子如下图所示：

   • 先训练一个最简单的架构，只有一个隐层，如图 a 所示。图 b 是另一个画法。
   • 然后将第一个隐层的输出 $ h^{(1)} $ 作为输入，再添加一个隐层，来训练 $ h^{(1)}\rightarrow h^{(2)}\rightarrow y $ ，如图 c 所示。图 d 是另一个画法。
   • 然后将第二个隐层的输出作为输入，再添加一个隐层，训练....
   • 在这个过程中，前一步训练的最末尾的隐层的输出作为后一步训练的输入。
   • 为了进一步优化，最后可以联合微调所有层。

   

4. 贪心监督预训练有效的原因，Bengio et al.提出的假说是：它有助于更好地指导深层结构的中间层的学习。

   • 中间层的知识能够有助于训练神经网络。
   • 预训练在优化（提高训练速度）和泛化（提高模型的泛化能力）这两方面都是有帮助的。

8.4 选择有助于优化的模型

1. 改进优化的最好方法是选择一个好的模型，选择一族容易优化的模型比使用一个强大的优化算法更重要。

   • 深度模型中，优化的许多改进来自于易于优化的模型。如：使用relu 激活函数。
   • 神经网络过去30年大多数进步主要来自于改变模型族，而不是优化算法。
   • 1980年代的带动量的随机梯度下降，依然是当前神经网络应用中的前沿算法。

2. 现代神经网络更多使用线性函数，如relu 单元、maxout单元。

8.5 连续方法

1. 许多优化挑战都来自于：因为并不知道代价函数的全局结构，所以不知道最优解所在的区域。

   解决该问题的主要方法是：尝试初始化参数到某个区域内，该区域可以通过局部下降很快达到参数空间中的解。

2. 连续方法的原理：挑选一系列的初始化点，使得在表现良好的区域中执行局部优化。

   方法为：构造一系列具有相同参数的目标函数 $ \{J^{(0)}(\theta),J^{(1)}(\theta),\cdots,J^{(n)}(\theta)\} $ ，其中满足：

   • 这些代价函数逐步提高难度，其中 $ J^{(0)} $ 是最容易优化的。
   • 前一个代价函数的解是下一个的初始化点。

   这样：首先解决一个简单的问题，然后改进解来解决逐步变难的问题，直到求解真正问题的解。

3. 传统的连续方法（非神经网络的）通常是基于平滑目标函数，主要用于克服局部极小值的问题。它用于在有许多局部极小值的情况下，求解一个全局极小值。

   • 它通过“模糊”原始的代价函数来构建更加容易的代价函数。这种模糊操作可以用采样来近似：

     $ J^{(i)}(\theta)=\mathbb E_{\theta^{\prime}\sim \mathcal N(\theta^{\prime};\theta,\sigma^{(i)2})} J(\theta^{\prime}) $

   • 它背后的思想是：某些非凸函数，在模糊之后会近似凸的。

   • 通常这种模糊保留了关于全局极小值的足够多的信息。那么可以通过逐步求解更少模糊的问题，来求解全局极小值。

   • 这种方法有三种失败的可能：

     • 可能需要非常多的代价函数，导致整个过程的成本太高。
     • 不管如何模糊，可能代价函数还是没有办法变成凸的。
     • 函数可能在模糊之后，最小值会逐步逼近到原始代价函数的一个局部极小值，而不是原始代价函数的全局极小值。

4. 对于神经网络，局部极小值已经不是神经网络优化中的主要问题，但是连续方法仍然有所帮助。

   连续方法引入的简化的目标函数能够消除平坦区域、减少梯度估计的方差、提高海森矩阵的条件数，使得局部更新更容易计算，或者改进局部更新方向朝着全局解。