机器学习笔记之优化算法(二十)牛顿法与正则化-Toy模板网

这篇具有很好参考价值的文章主要介绍了机器学习笔记之优化算法(二十)牛顿法与正则化。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

引言

本节我们介绍经典牛顿法在训练神经网络过程中的迭代步骤，并介绍正则化在牛顿法中的使用逻辑。

回顾：经典牛顿法及其弊端

经典牛顿法自身是一个典型的线搜索方法 $(\text{Line-Search Method})$ 。它的迭代过程使用数学符号表示如下：
$x_{k+1} = x_k + \alpha_k \cdot \mathcal P_k$
其中标量 $\alpha_k$ 表示当前第 $k$ 次迭代情况下的更新步长；向量 $\mathcal P_k$ 表示当前迭代步骤的更新方向。与梯度下降法区分的是，在经典牛顿法中：

步长并不是我们关注的信息，我们通常设置 $\alpha_k = 1(k=1,2,3,\cdots)$ ，从而迭代结果 $x_{k+1}$ 可看作是关于方向变量 $\mathcal P$ 的函数：
而 $\mathcal P_k$ 则表示当前迭代步骤的最优更新方向。
$\begin{cases} \begin{aligned} x_{k+1} & = x_k + \mathcal P \\ \mathcal P_k & = \mathop{\arg\min}\limits_{\mathcal P} f(x_{k+1}) \\ & = \mathop{\arg\min}\limits_{\mathcal P} f(x_k + \mathcal P) \end{aligned} \end{cases}$
关于目标函数 $f(\cdot)$ ，我们对其要求是： $f(\cdot)$ 至少二阶可微。这意味着 $\text{Hessian Matrix} \Rightarrow \nabla^2 f(\cdot)$ 存在。因此对目标函数 $f(x_k + \mathcal P)$ 进行二阶泰勒展开：
$f(x_k + \mathcal P) = \phi(\mathcal P) = f(x_k) + \frac{1}{1!} [\nabla f(x_k)]^T \mathcal P + \frac{1}{2!} \mathcal P^T [\nabla^2 f(x_k)] \cdot \mathcal P + \mathcal O(\|\mathcal P\|^2)$
忽略掉高阶无穷小 $\mathcal O(\|\mathcal P\|^2)$ ，通过令 $\nabla \phi(\mathcal P) \triangleq 0$ 来求解 $\mathcal P_k$ ，使 $\phi(\mathcal P_k)$ 取得最小值：
$\nabla \phi(\mathcal P) \triangleq 0 \Rightarrow \nabla^2 f(x_k) \cdot \mathcal P = -\nabla f(x_k)$
我们称该方程组为牛顿方程：
- 如果 $\nabla^2 f(\cdot)$ 在 $x_k$ 出的 $\text{Hessian Matrix} \Rightarrow \nabla^2 f(x_k)$ 是正定矩阵，那么：本次迭代步骤存在合适的 $\mathcal P_k$ ，使 $\phi(\mathcal P_k)$ 达到最小值：
  需要注意的是，这仅仅是当前迭代步骤的最小值,而不是全局最小值。
  $\mathcal P_k = - [\nabla^2 f(x_k)]^{-1} \nabla f(x_k)$
  并且解 $\mathcal P_k$ 描述的方向一定是下降方向。
- 相反，如果 $\nabla^2 f(x_k)$ 不是正定矩阵，那么至少说：无法直接求解，方程组 $\nabla^2 f(x_k) \cdot \mathcal P = -\nabla f(x_k)$ 的解是 $\mathcal P_k$ 的解。

牛顿法：算法步骤

在训练神经网络的方法中，牛顿法是二阶近似方法的代表。这里为了简单表述，将上面提到的目标函数 $f(\cdot)$ 具象化为经验风险 $(\text{Empirical Risk})$ ：
$\begin{aligned} \mathcal J(\theta) & = \mathbb E_{\mathcal P_{data}} \left\{\mathcal L[\mathcal G(x^{(i)};\theta),y^{(i)}]\right\} \\ & = \frac{1}{N} \sum_{i=1}^N \mathcal L [\mathcal G(x^{(i)};\theta),y^{(i)}] \end{aligned}\quad P_{data} = \{(x^{(i)},y^{(i)})\}_{i=1}^N$
其中 $\theta$ 可看作是需要学习的模型参数； $\mathcal G(\cdot)$ 可看作是模型关于 $x$ 的预测函数； $\mathcal L(\cdot)$ 可看作是损失函数，描述预测结果与真实标签的差异性信息。

假设 $\theta_0$ 表示当前迭代过程的起始位置，是已知项；而 $\theta$ 是一个变量，描述当前迭代过程结束后的参数位置。这里直接使用： $\theta -\theta_0$ 表示当前迭代步骤的更新方向，对 $\mathcal J(\theta)$ 进行二阶泰勒展开：

实际上，书中 $\theta - \theta_0$ 本身就将步长 $\alpha = 1$ 包含在内。
这里关于 $\mathcal J(\theta)$ 高于二阶的高阶无穷小直接省略掉了~
关于 $\text{Hessian Matrix} \Rightarrow \nabla^2 \mathcal J(\theta_0)$ 直接使用 $\mathcal H$ 进行表示。
$\mathcal J(\theta) \approx \mathcal J(\theta_0) + \frac{1}{1!}(\theta - \theta_0)^T \nabla_{\theta} \mathcal J(\theta_0) + \frac{1}{2!}(\theta - \theta_0)^T \mathcal H (\theta - \theta_0)$

依然令 $\nabla \mathcal J(\theta) \triangleq 0$ ，有：
$\begin{aligned} \nabla\mathcal J(\theta) & = (1 - 0) \cdot \nabla \mathcal J_{\theta}(\theta_0) + \frac{1}{2} \cdot 2 (\theta - \theta_0)\cdot \mathcal H \triangleq 0\\ & \Rightarrow \mathcal H(\theta - \theta_0) = -\nabla \mathcal J_{\theta}(\theta_0) \end{aligned}$
假设 $\mathcal H$ 是正定的条件下，关于 $\theta$ 与 $\theta_0$ 的递推关系表示如下：
$\theta = \theta_0 - \mathcal H^{-1} \nabla_{\theta} \mathcal J(\theta_0)$

基于递推关系，对应的算法步骤表示如下：

初始化：初始参数 $\theta_{start}$ 以及包含 $N$ 个样本的训练数据集；
$\text{While}$ ：
- 计算 $\nabla_{\theta} \mathcal J(\theta_0)$ ：
  牛顿-莱布尼兹公式~,这是书上的表达。详细位置见末尾~
  $\begin{aligned} \nabla_{\theta} \mathcal J(\theta_0) & = \nabla_{\theta} \left\{\frac{1}{N} \sum_{i=1}^N \mathcal L[\mathcal G(x^{(i)};\theta_0),y^{(i)}]\right\} \\ & = \frac{1}{N} \nabla_{\theta} \sum_{i=1}^N \mathcal L[\mathcal G(x^{(i)};\theta_0),y^{(i)}] \end{aligned}$
- 计算 $\theta_0$ 位置的 $\text{Hessian Matrix} \Rightarrow \mathcal H$ ：
  该公式同样也是书上描述。
  $\begin{aligned} \mathcal H & = \nabla_{\theta}^2 \mathcal J(\theta_0) \\ & = \nabla_{\theta}^2 \left\{\frac{1}{N} \sum_{i=1}^N \mathcal L[\mathcal G(x^{(i)};\theta_0),y^{(i)}]\right\} \\ & = \frac{1}{N} \nabla_{\theta}^2 \sum_{i=1}^N \mathcal L[\mathcal G(x^{(i)};\theta_0),y^{(i)}] \end{aligned}$
- 计算 $\text{Hessian Matrix}$ 的逆： $\mathcal H^{-1}$ ；
- 计算变量 $\theta$ 的变化量 $\Delta \theta$ ：
  $\Delta \theta = -\mathcal H^{-1} \nabla_{\theta} \mathcal J(\theta_0)$
- 对变量 $\theta$ 进行更新：
  $\theta = \theta_0 + \Delta \theta$
$\text{End While}$

迭代过程中可能出现的问题

观察上述迭代步骤，一个核心问题是：该算法必须建立在迭代过程中，各步骤的 $\theta$ 对应的 $\text{Hessian Matrix}$ 必须均是正定的，否则 $\mathcal H^{-1}$ 无法求解。在凸函数 $\text{VS}$ 强凸函数中介绍过关于强凸函数的二阶条件：如果函数 $f(\cdot)$ 二阶可微，有：
其中 $\mathcal I$ 表示单位矩阵。
$f(\cdot) \text{is m-Strong Convex} \Leftrightarrow \nabla^2 f(x) \succcurlyeq m \cdot \mathcal I$
也就是说：要想 $\mathcal H = \nabla_{\theta}^2 \mathcal J(\theta_0)$ 正定，必然需要目标函数 $\mathcal J(\theta)$ 在 $\theta= \theta_0$ 处不仅是凸的，甚至是强凸的。

但在深度学习中，目标函数的表面由于特征较多，从而在局部呈现非凸的情况。例如鞍点，二阶梯度函数 $\nabla_{\theta}^2 \mathcal J(\theta)$ 在该处的特征值并不都是正的，也就是说：鞍点处的 $\text{Hessian Matrix}$ 可能不是正定的，从而可能导致在该点出迭代过程中选择的 $\theta$ ，使得更新方向 $\theta - \theta_0$ 是个错误的方向。

正则化 Hessian Matrix \text{Hessian Matrix} Hessian Matrix与相应问题

上述情况可以使用正则化 $\text{Hessian Matrix}$ 来避免。一种常用的正则化策略是 $\text{Hessian Matrix}$ 加上一个对角线元素均为 $\alpha$ 的对角阵：
$\theta = \theta_0 - \left[\underbrace{\nabla_{\theta}^2 \mathcal J(\theta_0)}_{\mathcal H} + \alpha \cdot \mathcal I\right]^{-1} \nabla_{\theta} \mathcal J(\theta_0)$
这种操作我们早在正则化与岭回归中就已介绍过。由于 $\text{Hessian Matrix} \Rightarrow \mathcal H$ 至少是实对称矩阵，那么必然有：
$\mathcal H = \mathcal Q\Lambda \mathcal Q^T \quad \mathcal Q\mathcal Q^T = \mathcal Q^T\mathcal Q = \mathcal I$
并且 $\lambda \mathcal I = \mathcal Q(\lambda \mathcal I) \mathcal Q^T$ ，从而 $\mathcal H + \lambda \cdot \mathcal I$ 可表示为：
$\begin{aligned} \mathcal H + \lambda \cdot \mathcal I & = \mathcal Q \Lambda\mathcal Q^T + \mathcal Q(\lambda \mathcal I) \mathcal Q^T \\ & = \mathcal Q(\Lambda + \lambda \mathcal I) \mathcal Q^T \end{aligned}$
这相当于：给 $\mathcal H$ 的所有特征值加上一个正值 $\alpha$ 。
相比于最小二乘法模型参数 $\mathcal W$ 的矩阵形式表达： $\mathcal W = (\mathcal X^T \mathcal X)^{-1} \mathcal X^T \mathcal Y$ , $\mathcal H$ 可能更不稳定。因为 $\mathcal X^T\mathcal X$ 必然是半正定的,但 $\mathcal H$ 中的特征值有可能是负的。

由于 $\mathcal H$ 中的特征值有可能是负的，甚至是负定矩阵。如果 $\mathcal H$ 中存在特征值负的很厉害的情况下(存在很强的负曲率)，我们需要增大 $\alpha$ 结果来抵消负特征值。如果 $\alpha$ 持续增大，对应特征值可能会被 $\alpha$ 主导。从而导致迭代步骤选择的方向收敛到 $\begin{aligned}\frac{1}{\alpha} \times\end{aligned}$ 普通梯度。

使用牛顿法训练大型的神经网络，更多还受限于计算负担。由于 $\mathcal H \in \mathbb R^{p \times p}$ ，其中 $p$ 表示样本特征维度，求解 $\mathcal H^{-1}$ 的时间复杂度是 $\mathcal O(k^3)$ 。并且由于迭代过程中随着 $\theta$ 的变化，因而需要每次迭代过程都要计算对应 $\mathcal H^{-1}$ 。因而，最终结果是：只有少量参数的神经网络，才能在实际中使用牛顿法进行训练。