机器学习中的牛顿法和拟牛顿法

---

1. 训练神经网络的5大算法

在神经网络中, 处理学习进程的程序称为训练算法. 有许多这样的训练算法, 并有不同的特点和效用.

在训练神经网络中, 算法的目的就是求出极值点, 在此之中, 有5大算法.

1. 梯度下降法

梯度下降法式最简单的训练算法, 它需要计算出梯度向量, 根据梯度向量以及当前的点和学习率计算出当前步长, 以此来向极值点更近一步, 经过多次迭代, 最终到达极值点.

2. 牛顿法

与梯度下降法不同, 牛顿法的理论依据是极值点的导函数为0, 所以就是求函数的驻点. 所以需要求二阶导数, 是二阶算法. 拥有更少的迭代次数, 但因为要计算海森矩阵, 计算量比较大.

3. 共轭梯度法

共轭梯度法是中和梯度下降法和牛顿法的一种算法, 该算法的目的是加快梯度下降的收敛速度, 又避免使用海森矩阵来获取优化信息.

4. 拟牛顿法

牛顿法的计算量特别大, 但是迭代次数少, 为了解决这个痛点, 产生了拟牛顿法. 拟牛顿法不计算海森矩阵, 取而代之的是, 计算一个接近海森矩阵或海森矩阵的逆的正定对称阵, 通过损失函数的一阶导计算, 减少了许多的计算量.

5. Levenberg-Marquardt法 (LM法)

LM法也称为衰减最小二乘法（damped least-squares method）, 不需要计算具体的海森矩阵, 使用的只有梯度向量和雅可比矩阵(Jacobian matrix).

本文仅详述5大算法中的牛顿法和拟牛顿法.

2. 牛顿法

牛顿法的主要目的是通过使用损失函数的二阶导来寻找一个更好的训练方向.

理论推导

假设优化目标函数 $f$ , 我么的目的就是求出这个函数的极值点, 根据高数的知识, 函数的极值点在函数的驻点和断点处取得. 在这里, 我们尝试去求函数的驻点, 也就是导函数为0的点. 于是问题就转化为了求解 $f^{'} = 0$ 的问题. 这个问题, 我们使用的是牛顿迭代法, 所以这个方法叫做牛顿法.

为了求出 $f^{'} = 0$的根, 我们把原函数 $f(x)$ 在x处做泰勒展开, 展开到二阶. $$ f(x + \Delta x) = f(x) + f^{'}(x) \Delta x + \frac{1}{2}f^{''}(x)\Delta x^2 + o(x^2) $$ 式子仅当 $\Delta x$ 无限逼近0时成立.

我们对等式进行一个处理: $$ f^{'}(x) + \frac{1}{2}f^{''}(x)\Delta x = 0 $$ 因为 $\Delta x$ 无限逼近于0, 所以常数系数也可以忽略, 等式为: $$ f^{'}(x) + f^{''}(x)\Delta x = 0 $$ 故: $$ \Delta x = -\frac{f^{'}(x)}{f^{''}(x)} $$ 因为是迭代求解, 所以有: $$ x_{n+1} - x_n = -\frac{f^{'}(x)}{f^{''}(x)} (n = 0, 1, 2, ...) $$ 即: $$ x_{n+1} = x_n -\frac{f^{'}(x)}{f^{''}(x)} (n = 0, 1, 2, ...) $$ 此处的 $x_{n+1}$ 要比 $x_{n}$ 更接近目标值.

以上的公式针对于单元函数, 对于多元函数, 我们将所有自变量记为一个多维向量 $X$ , 对于在 $X_0$ 及其邻域内有连续的二阶偏导数的多元函数 $f(X)$ , 其在 $X_0$ 的泰勒(二阶)展开式为: $$ f(X) = f(X_0) + (X - X_0)^T \nabla f(X_0) + \frac{1}{2}(X - X_0)^T Hf(X_0)(X-X_0) + o(||X-X_0||^2) $$ 其中 $o(||X-X_0||^2)$ 是 $X^2$ 的高阶无穷小.

依上: 迭代公式为 $$ X_{n+1} = X_n - \frac{\nabla f(X_0)}{Hf(X_0)(X-X_0)} $$ 由此, 哪怕是高维的也可以使用牛顿迭代法求解, 而且要比梯度向量法迭代次数少很多, 但是计算海森矩阵的时间是很大的.

3. 拟牛顿法

由于牛顿迭代求解的难度很大, 人们提出了拟牛顿法, 不直接计算海森矩阵, 而是寻找一个矩阵来代替海森矩阵, 而这个矩阵的寻找也有多种方法, 近似海森矩阵或者近似海森矩阵的逆.

为明确起见，下文中用$B$表示对海森矩阵$H$本身的近似，而用$D$表示对海森矩阵的逆$H^{-1}$的近似，即$B \approx H, D \approx H^{-1}$

有几大算法来计算 $B$ 和 $D$ , 如下:

Method	$B_{k+1}$	$D_{k+1}$
DFP	$(I - \frac{y_k \Delta x_k^T}{y_k^T \Delta x_k})B_k(I - \frac{\Delta x_k y_k^T}{y_k^T \Delta x_k})+\frac{y_ky_k^T}{y_k^T \Delta x_k}$	$H_k + \frac{\Delta x_k \Delta x_k^T}{\Delta x_k^T y_K} - \frac{H_ky_ky_k^TH_k}{y_k^TH_ky_k}$
BFGS	$B_k + \frac{y_ky_k^T}{y_k^T \Delta x_k} - \frac{B_k \Delta x_k (B_k \Delta x_k)^T}{\Delta x_k^T B_k \Delta x_k}$	$(I - \frac{\Delta x_ky_k^T}{y_k^T \Delta x_k})H_k(I - \frac{y_k \Delta x_k^T}{y_k^T \Delta x_k}) + \frac{\Delta x_k \Delta x_k^T}{y_k^T \Delta x_k}$
Broyden	$B_k + \frac{y_k - B_k \Delta x_k}{\Delta x_k^T \Delta x_k} \Delta x_k^T$	$H_k + \frac{(\Delta x_k - H_ky_k) \Delta x_k^T H_k}{\Delta x_k^T H_k y_k}$
Broyden family	$(1-\varphi_k)B_{k+1}^{BFGS} + \varphi_k B_k^{DEP} , \varphi \in [0,1]$
SR1	$B_k + \frac{(y_k - B_k \Delta x_k)(y_k - B_k \Delta x_k)^T}{(y_k - B_k \Delta x_k)^T \Delta x_k}$	$H_k - \frac{(\Delta x_k - H_ky_k)(\Delta x_k - H_ky_k)^T}{(\Delta x_k - H_k y_k)^T y_k}$

4. 比较

下图绘制了五种算法的计算速度和内存需求。如图所示，梯度下降法往往是最慢的训练方法，它所需要的内存也往往最少。相反，速度最快的算法一般是Levenberg-Marquardt，但需要的内存也更多。拟牛顿法较好地平衡了两者。

总之，如果我们的神经网络模型有上千个参数，则可以用节省存储的梯度下降法和共轭梯度法。如果我们需要训练很多网络模型，每个模型只有几千个训练数据和几百个参数，则Levenberg-Marquardt可能会是一个好选择。其余情况下，拟牛顿法的效果都不错。

---

---