Question

1. 为了简化问题，这里考察目标函数为经验风险函数（即：不考虑正则化项）：

   $ J(\vec\theta)=\mathbb E_{\mathbf{\vec x},y\sim \hat p_{data}(\mathbf{\vec x},y)}[L(f(\mathbf{\vec x};\vec\theta),y)]=\frac 1m\sum_{i=1}^{m}L(f(\mathbf{\vec x}_i;\vec\theta),y_i) $

   .

6.1 牛顿法

6.1.1 牛顿法算法

1. 牛顿法在某点 $ \vec\theta_0 $ 附近，利用二阶泰勒展开来近似 $ J(\vec\theta) $ ：

   $ J(\vec\theta)\approx J(\vec\theta_0)+(\vec\theta-\vec\theta_0)^{T}\nabla_{\vec\theta}J(\vec\theta_0)+\frac 12(\vec\theta-\vec\theta_0)^{T}\mathbf H(\vec\theta-\vec\theta_0) $

   其中 $ \mathbf H $ 为 $ J $ 对于 $ \vec\theta $ 的海森矩阵在 $ \vec\theta_0 $ 处的值。

   如果求解这个函数的临界点，根据 $ \frac{\partial J(\vec\theta)}{\partial \vec\theta}=\mathbf{\vec 0} $ ，则得到牛顿法的更新规则：

   $ \vec\theta^{*}=\vec\theta_0-\mathbf H^{-1}\nabla_{\vec\theta}J(\vec\theta_0) $

   • 如果 $ J $ 为 $ \vec\theta $ 的二次函数，则牛顿法会直接跳到极值或者鞍点。

     • 如果 $ \mathbf H $ 是正定的，则跳到的点是极小值点。
     • 如果 $ \mathbf H $ 是负定的，则跳到的点是极大值点。
     • 如果 $ \mathbf H $ 是非正定、非负定的，则跳到的点是鞍点。因此，牛顿法会主动跳到鞍点。

   • 如果 $ J $ 为 $ \vec\theta $ 的高阶的，则需要迭代。

2. 牛顿法：

   • 输入：

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

   • 算法步骤：

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

     • 计算梯度： $ \mathbf{\vec g}\leftarrow \nabla_{\vec\theta}J(\vec\theta) $
     • 计算海森矩阵： $ \mathbf H\leftarrow \nabla^{2}_{\vec\theta}J(\vec\theta) $
     • 计算海森矩阵的逆矩阵： $ \mathbf H^{-1} $
     • 计算更新： $ \Delta\vec\theta=-\mathbf H^{-1}\mathbf{\vec g} $
     • 应用更新： $ \vec\theta=\vec\theta+\Delta\vec\theta $

6.1.2 牛顿法性质

1. 只要海森矩阵保持正定，牛顿法就能够迭代的使用。

2. 在深度学习中目标函数具有很多鞍点，海森矩阵的特征值并不全为正的，因此使用牛顿法有问题：在靠近鞍点附近，牛顿法会导致参数更新主动朝着鞍点的方向移动，这是错误的移动方向。

   解决的办法是：使用正则化的海森矩阵。

3. 常用的正则化策略是：在海森矩阵的对角线上增加常数 $ \alpha $ 。

   于是更新过程为： $ \vec\theta=\vec\theta-[\mathbf H+\alpha\mathbf I]^{-1}\nabla_{\vec\theta}J(\vec\theta) $ 。

   • 这个正则化策略是牛顿法的近似。

   • 只要海森矩阵的负特征值都在零点附近，则可以起到效果。

   • 当有很强的负曲率存在时（即存在绝对值很大的负的特征值）， $ \alpha $ 可能需要特别大。

     但是如果 $ \alpha $ 增大到一定程度，则海森矩阵就变得由对角矩阵 $ \alpha\mathbf I $ 主导。此时，牛顿法选择的方向就是 $ -\frac 1\alpha\mathbf{\vec g} $ 的方向。

4. 海森矩阵的元素的数量是参数数量的平方。如果参数数量为 $ n $ ，则牛顿法需要计算一个 $ n\times n $ 矩阵的逆，计算一次参数更新的复杂度为 $ O(n^{3}) $ 。

   由于每次参数更新时都将改变参数，因此每轮迭代训练都需要计算海森矩阵的逆矩阵，计算代价非常昂贵。因此只有参数很少的网络才能够在实际中应用牛顿法训练，绝大多数神经网络不能采用牛顿法训练。

5. 综上所述，牛顿法有两个主要缺点：

   • 主动跳向鞍点。
   • 逆矩阵的计算复杂度太大，难以计算。

6.2 BFGS

1. BFGS算法具有牛顿法的一些优点，但是没有牛顿法的计算负担。

   大多数拟牛顿法（包括 BFGS）采用矩阵 $ \mathbf M_t $ 来近似海森矩阵的逆矩阵，当 $ \mathbf M_t $ 更新时，下降方向为 $ \vec{\mathbf d}_t=\mathbf M_t\mathbf{\vec g}_t $ 。

   在该方向上的线性搜索到的最佳学习率为 $ \epsilon^{*} $ ，则参数更新为： $ \vec\theta_{t+1}=\vec\theta_t+\epsilon^{*}\vec{\mathbf d}_t $ 。

2. BFGS算法迭代了一系列线性搜索，其方向蕴含了二阶信息。

   与共轭梯度不同，BFGS的成功并不需要线性搜索真正找到该方向上接近极小值的一点（而是探索一部分点）。因此BFGS在每个线性搜索上花费更少的时间。

3. BFGS算法必须存储海森矩阵逆矩阵的近似矩阵 $ \mathbf M_t $ ，需要 $ O(n^{2}) $ 的存储空间。因此BFGS不适用于大多数具有百万级参数的现代深度学习模型。

   L-BFGS通过避免存储完整的海森矩阵的逆的近似矩阵 $ \mathbf M_t $ 来降低存储代价，它假设起始的 $ \mathbf M_0 $ 为单位矩阵，每步存储一些用于更新 $ \mathbf M $ 的向量，并且每一步的存储代价是 $ O(n) $ 。