Question

7.1 最速下降法

1. 最速下降法是梯度下降法的一个特例：在每次梯度下降时，学习率的选择是使得当前函数值下降最快的那个学习率。

   $ \epsilon^*=\min_{\epsilon} f(\vec\theta_k-\epsilon \mathbf{\vec g}_k) $

   梯度下降法仅仅指明：负梯度的方向是使得代价函数值下降的方向。它并没有说明沿着负梯度的方向推进多少步长。

   最速下降法通过显式对学习率建模，求解沿着负梯度的方向需要推进多少步长。

2. 在最速下降法中，假设上一次搜索方向是 $ \mathbf{\vec d}_{t-1} $ ，当前搜索方向是 $ \mathbf{\vec d}_{t} $ 。可以证明有：

   $ \mathbf{\vec d}_{t} \cdot \mathbf{\vec d}_{t-1}=0 $

   即：前后两次搜索的方向是正交的。

   

   证明过程：

   已知 $ \vec\theta_k $ 的梯度 $ \mathbf{\vec g}_k $ ，根据 $ 0=\frac{\partial f}{\partial \epsilon} $ ，则有：

   $ 0=\frac{\partial f}{\partial \epsilon}=-\nabla f(\vec\theta_k-\epsilon\mathbf{\vec g}_k)\cdot \mathbf{\vec g}_k \\ \rightarrow \nabla f(\vec\theta_{k+1})\cdot \mathbf{\vec g}_k=0\\ \rightarrow \mathbf{\vec g}_{k+1}\cdot \mathbf{\vec g}_k=0 $

3. 在最速下降法中，前进过程是锯齿形的。在某种意义上，这意味着消除了之前的线性搜索方向上取得的进展：

   如果前一次搜索已经找出了某个方向上的最小值，最速下降法不会保持这一方向。

7.2 共轭梯度法

1. 共轭：给定一个正定矩阵 $ \mathbf Q $ ，如果非零向量 $ \mathbf{\vec x},\mathbf{\vec y} $ 满足： $ \mathbf{\vec x}^T\mathbf Q \mathbf{\vec y}=0 $ ，则称向量 $ \mathbf{\vec x},\mathbf{\vec y} $ 关于 $ \mathbf Q $ 共轭。
2. 如果 $ \mathbf Q=\mathbf I $ 为单位矩阵，则有 $ \mathbf{\vec x}^T\mathbf{\vec y}=0 $ 。即：向量共轭是向量点积为0的推广。

7.2.1 共轭梯度原理

1. 对于线性空间 $ \mathbb R^n $ ，如果能找到 $ n $ 个向量 $ \mathbf{\vec d}_1,\mathbf{\vec d_2},\cdots,\mathbf{\vec d}_n $ ，且它们满足： $ \mathbf{\vec d}_i^T\mathbf Q\mathbf{\vec d}_j=0,i\ne j $ ，则可以证明这一组向量是线性无关的。

   此时这一组向量可以作为线性空间的一组基向量，空间中任意向量 $ \mathbf{\vec x} $ 都可以用这组向量表示： $ \mathbf{\vec x}=\sum_{i=1}^na_i\mathbf{\vec d}_i $ 。

2. 对于二次函数极值问题（其中 $ \mathbf Q $ 为正定矩阵）： $ \min_{\mathbf{\vec x}\in \mathbb R^n}\frac 12\mathbf{\vec x}^T\mathbf Q\mathbf{\vec x}-\mathbf{\vec b}^T\mathbf{\vec x} $ ，将 $ \mathbf{\vec x}=\sum_{i=1}^na_i\mathbf{\vec d}_i $ 代入上式，令 $ \mathbf{\vec a}=(a_1,a_2,\cdots,a_n)^T $ ：

   $ \min_{\mathbf{\vec a}\in \mathbb R^n}\frac 12\left(\sum_{i=1}^na_i\mathbf{\vec d}_i\right)^T\mathbf Q\left(\sum_{i=1}^na_i\mathbf{\vec d}_i\right)-\mathbf{\vec b}^T\left(\sum_{i=1}^na_i\mathbf{\vec d}_i\right)\\ =\min_{\mathbf{\vec a}\in \mathbb R^n}\frac 12 \left( \sum_{i=1}^n\sum_{j=1}^na_ia_j\mathbf{\vec d}_i^T\mathbf Q\mathbf{\vec d}_j\right)-\left(\sum_{i=1}^na_i\mathbf{\vec b}^T\mathbf{\vec d}_i\right) $

   根据 $ \mathbf{\vec d}_i\mathbf Q\mathbf{\vec d}_j=0 $ ，有：

   $ \min_{\mathbf{\vec a}\in \mathbb R^n}\frac 12\left(\sum_{i=1}^na_i^2\mathbf{\vec d}_i^T\mathbf Q\mathbf{\vec d}_i\right) -\left(\sum_{i=1}^na_i\mathbf{\vec b}^T\mathbf{\vec d}_i\right) =\min_{\mathbf{\vec a}\in \mathbb R^n}\sum_{i=1}^n\left(\frac 12 a_i^2 \mathbf{\vec d}_i^T\mathbf Q\mathbf{\vec d}_i-a_i\mathbf{\vec b}^T\mathbf{\vec d}_i\right) $

3. 现在变量 $ a_1,a_2,\cdots,a_n $ 已经被分开，可以分别优化。

   于是求解第 $ i $ 项的最小值：

   $ \min_{a_i}\left(\frac 12 a_i^2 \mathbf{\vec d}_i^T\mathbf Q\mathbf{\vec d}_i-a_i\mathbf{\vec b}^T\mathbf{\vec d}_i\right) $

   直接求导即可得到：

   $ a_i^*=\frac{\mathbf{\vec b}^T\mathbf{\vec d_i}}{\mathbf{\vec d}_i^T\mathbf Q\mathbf{\vec d}_i} $

   最优解为：

   $ \mathbf{\vec x}^*=\sum_{i=1}^na_i^*\mathbf{\vec d}_i=\sum_{i=1}^n\frac{\mathbf{\vec b}^T\mathbf{\vec d_i}}{\mathbf{\vec d}_i^T\mathbf Q\mathbf{\vec d}_i} \mathbf{\vec d}_i $

4. 上述最优解可以这样理解：

   • 目标函数沿着方向 $ \mathbf{\vec d}_i $ （即： $ \mathbf{\vec x}=a_i \mathbf{\vec d}_i $ ）求解极小值，得到 $ a_i^* $ 。
   • 总和所有的 $ n $ 个方向求得的极小值，得到 $ \mathbf{\vec x}^*=\sum_{i=1}^na_i^*\mathbf{\vec d}_i $ 。

   现在的问题是： $ n $ 个关于 $ \mathbf Q $ 共轭的向量组 $ \{\mathbf{\vec d}_1,\mathbf{\vec d}_2,\cdots,\mathbf{\vec d}_n\} $ 未知。

7.2.2 共轭梯度搜索

1. 共轭梯度法通过迭代来搜索关于 $ \mathbf Q $ 共轭的向量组 $ \{\mathbf{\vec d}_1,\mathbf{\vec d}_2,\cdots,\mathbf{\vec d}_n\} $ 。

2. 令梯度 $ \mathbf{\vec g}=\nabla_{\mathbf{\vec x}}f(\mathbf{\vec x}) $ ，由于 $ f(\mathbf{\vec x})=\frac 12\mathbf{\vec x}^T\mathbf Q\mathbf{\vec x}-\mathbf{\vec b}^T\mathbf{\vec x} $ ，则有：

   $ \mathbf{\vec g}=\frac {\mathbf Q^T+\mathbf Q}{2}\mathbf{\vec x}-\mathbf{\vec b}\\ $

   假设 $ \mathbf Q $ 为对称的正定矩阵，则有： $ \mathbf Q=\mathbf Q^T $ 。因此有： $ \mathbf{\vec g}=\mathbf Q\mathbf{\vec x}-\mathbf{\vec b} $ 。

3. 任取一个初始点 $ \mathbf{\vec x}_1 $ 。

   • 如果 $ \nabla_{\mathbf{\vec x}}f(\mathbf{\vec x}_1)=\vec 0 $ ，则停止计算。因为此时 $ \mathbf{\vec x}_1 $ 就是极值点。

   • 否则，令 $ \mathbf{\vec d}_1=\mathbf {\vec g}_1=-\nabla_{\mathbf{\vec x}}f(\mathbf{\vec x}_1) $ ，即： $ \mathbf{\vec d}_1 $ 沿着点 $ \mathbf{\vec x}_1 $ 的梯度方向。

     沿着 $ \mathbf{\vec d}_1 $ 方向搜索： $ \mathbf{\vec x}_2=\mathbf{\vec x}_1+\lambda \mathbf{\vec d}_1 $ ，使得沿着这个方向，目标函数下降最多。

     $ \min_{\lambda}\left(\frac 12(\mathbf{\vec x}_1+\lambda \mathbf{\vec d}_1)^T\mathbf Q(\mathbf{\vec x}_1+\lambda \mathbf{\vec d}_1)-\mathbf{\vec b}^T(\mathbf{\vec x}_1+\lambda \mathbf{\vec d}_1)\right)-\left(\frac 12\mathbf{\vec x}_1^T\mathbf Q\mathbf{\vec x}_1-\mathbf{\vec b}^T\mathbf{\vec x}_1\right) $

     解得：

     $ \lambda=-\frac{\mathbf{\vec x}_1^T\mathbf Q\mathbf{\vec d}_1-\mathbf{\vec b}^T\mathbf{\vec d}_1}{\mathbf{\vec d}_1^T\mathbf Q\mathbf{\vec d}_1} $

     由于 $ \mathbf{\vec g}^T=\mathbf{\vec x}^T\mathbf Q-\mathbf{\vec b}^T $ ，因此有：

     $ \lambda=- \frac{ \mathbf{\vec g}_1 ^T\mathbf{\vec d}_1}{\mathbf{\vec d}_1^T\mathbf Q\mathbf{\vec d}_1} $

4. 选择第二个迭代点：

   $ \mathbf{\vec x}_2=\mathbf{\vec x}_1+\lambda \mathbf{\vec d}_1=\mathbf{\vec x}_1- \frac{ \mathbf{\vec g}_1 ^T\mathbf{\vec d}_1}{\mathbf{\vec d}_1^T\mathbf Q\mathbf{\vec d}_1}\mathbf{\vec d}_1 $

   注意：这里有 $ \mathbf{\vec g}_1=\mathbf{\vec d}_1 $ ，但是不保证后面的 $ \mathbf{\vec g}_i=\mathbf{\vec d}_i $ 。

   构建下一个搜索方向，使得 $ \mathbf{\vec d}_2 $ 与 $ \mathbf{\vec d}_1 $ 关于 $ \mathbf Q $ 共轭。

   令： $ \mathbf {\vec d}_2=-\mathbf{\vec g}_2+\beta_1\mathbf{\vec d}_1 $ ，代入 $ \mathbf{\vec d}_1^T\mathbf Q\mathbf{\vec d}_2=0 $ ，有：

   $ \beta_1=\frac{\mathbf{\vec d}_1^T\mathbf Q\mathbf{\vec g}_2}{\mathbf{\vec d_1^T\mathbf Q\mathbf{\vec d}_1}},\quad \mathbf {\vec d}_2=-\mathbf{\vec g}_2+\frac{\mathbf{\vec d}_1^T\mathbf Q\mathbf{\vec g}_2}{\mathbf{\vec d_1^T\mathbf Q\mathbf{\vec d}_1}}\mathbf{\vec d}_1 $

5. 同理：得到 $ \mathbf{\vec x}_{k+1} $ 时，计算梯度 $ \mathbf{\vec g}_{k+1} $ ，同时用 $ -\mathbf{\vec g}_{k+1} $ 和 $ \mathbf{\vec d}_k $ 来构建下一个搜索方向：

   $ \mathbf {\vec d}_{k+1}=-\mathbf{\vec g}_{k+1}+\beta_k\mathbf{\vec d}_k,\quad \mathbf{\vec d}_k^T\mathbf Q\mathbf{\vec d}_{k+1}=0 $

   得到：

   $ \beta_k=\frac{\mathbf{\vec d}_k^T\mathbf Q\mathbf{\vec g}_{k+1}}{\mathbf{\vec d_k^T\mathbf Q\mathbf{\vec d}_k}},\quad \mathbf {\vec d}_{k+1}=-\mathbf{\vec g}_{k+1}+\frac{\mathbf{\vec d}_k^T\mathbf Q\mathbf{\vec g}_{k+1}}{\mathbf{\vec d_k^T\mathbf Q\mathbf{\vec d}_k}}\mathbf{\vec d}_k $

   .

7.2.3 共轭梯度算法

1. 共轭梯度法的搜索方向 $ \mathbf{\vec d}_t $ 会保持前一次线性搜索方向上 $ \mathbf{\vec d}_{t-1} $ 取得的进展：

   $ \mathbf{\vec d}_t=-\nabla_{\vec\theta} J(\vec\theta)+\beta_t\mathbf{\vec d}_{t-1} $

   其中 $ \beta_t $ 的大小控制了：要保留多大比例的上一次搜索方向。

2. 在实际应用中，目标函数往往是高于二次的函数。此时为非线性共轭梯度， $ \mathbf Q $ 就是海森矩阵 $ \mathbf H $ 。

   直接计算 $ \beta_t $ 也需要计算海森矩阵的逆矩阵，比较复杂。有两个计算 $ \beta_t $ 的流行方法（不需要计算海森矩阵的逆矩阵）：

   这里不再保证 $ \mathbf{\vec d}_t $ 和 $ \mathbf{\vec d}_{t-1} $ 关于 $ \mathbf Q $ 是共轭的。

   • Fletcher-Reeves：

     $ \beta_t=\frac{\mathbf{\vec g}_t^{T}\mathbf{\vec g}_t}{\mathbf{\vec g}_{t-1}^T\mathbf{\vec g}_{t-1}} $

   • Polak_Ribiere：

     $ \beta_t=\frac{(\mathbf{\vec g}_{t}-\mathbf{\vec g}_{t-1})^{T}\mathbf{\vec g}_{t}}{\mathbf{\vec g}_{t-1}^T\mathbf{\vec g}_{t-1}} $

3. 目标函数在高于二次的函数时，往往可能存在局部极值。此时共轭梯度法不能在 $ n $ 维空间内依靠 $ n $ 步搜索到达极值点。

   此时需要重启共轭梯度法，继续迭代，以完成搜索极值点的工作。

4. 共轭梯度法：

   • 输入：

     • 初始参数 $ \vec\theta_0 $
     • 包含 $ m $ 个样本的训练集

   • 算法步骤：

     • 初始化：

       $ \vec{\mathbf d}_0=\mathbf{\vec 0}\\ \mathbf{\vec g}_0=\mathbf{\vec 0}\\ t=1 $

     • 迭代，直到到达停止条件。迭代步骤为：

       • 计算梯度：

         $ \mathbf{\vec g}_t\leftarrow \frac 1m\nabla_{\vec\theta}\sum_{i=1}^{m}L(f(\mathbf{\vec x}_i;\vec\theta),y_i) $

       • 计算 $ \beta_t $

         $ \beta_t=\frac{(\mathbf{\vec g}_t-\mathbf{\vec g}_{t-1})^{T}\mathbf{\vec g}_t}{\mathbf{\vec g}_{t-1}^{T}\mathbf{\vec g}_{t-1}} $

         如果是非线性共轭梯度：则可以以一定的频率重置 $ \beta_t $ 为零（如每当 $ t $ 为 5 的倍数时）。

       • 计算搜索方向： $ \vec {\mathbf d}_t=-\mathbf{\vec g}_t+\beta_t\vec{\mathbf d}_{t-1} $

       • 执行线性搜索： $ \epsilon^{*}=\arg\min_{\epsilon}\frac 1m\sum_{i=1}^{m}L(f(\mathbf{\vec x}_i;\vec\theta_t+\epsilon\vec{\mathbf d}_t),y_i) $

         在前面推导过程中，并没有出现这一步。这是因为：在非线性共轭梯度下，以及修改的 $ \beta_t $ 的情况下，不再满足 $ \mathbf{\vec d}_t $ 和 $ \mathbf{\vec d}_{t-1} $ 关于 $ \mathbf Q $ 是共轭的。

         对于真正的二次函数：存在 $ \epsilon^{*} $ 的解析解，无需显式搜索。

         • 应用更新： $ \vec\theta_{t+1}=\vec\theta_t+ \epsilon^{*}\vec{\mathbf d}_t $
         • $ t\leftarrow t+1 $

7.2.4 共轭梯度算法性质

1. 神经网络的目标函数比二次函数复杂得多，但是共轭梯度法在这种情况下仍然适用。此时非线性共轭梯度算法会偶尔采取一些重置操作（重置 $ \beta_t $ 为零）。

2. 尽管共轭梯度算法是批方法（需要所有的样本来计算梯度），目前也开发出了mini-batch版本。

3. 理论上，对于二次函数的目标函数，需要迭代 $ n $ 步， $ n $ 为参数的个数。每一步中都需要计算梯度。

   在神经网络中，这样有两个问题：

   • 当参数的数量 $ n $ 巨大时，迭代的量非常大，而且难以并行（后面的迭代依赖前面的迭代），计算量非常庞大。
   • 当样本的数量巨大时，每次迭代中的梯度计算的计算量非常庞大。