机器学习笔记之优化算法(十九)牛顿法与正则化

引言

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

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

经典牛顿法自身是一个典型的线搜索方法$(\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{array}{l}\begin{array}{rl}{x}_{k+1}& =x_k+\mathcal{P}\\ {\mathcal{P}}_k& =\underset{\mathcal{P}}{\mathrm{argmin}}f(x_{k+1})\\ & =\underset{\mathcal{P}}{\mathrm{argmin}}f(x_k+\mathcal{P})\end{array}\end{array}$$
• 关于目标函数$f(\cdot )$，我们对其要求是：$f(\cdot )$至少二阶可微。这意味着$\text{Hessian Matrix}\Rightarrow {\nabla }^{2}f(\cdot )$存在。因此对目标函数$f(x_k+\mathcal{P})$进行二阶泰勒展开：
  $$f(x_k+\mathcal{P})=\varphi (\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}(\Vert \mathcal{P}{\Vert }^2)$$
  忽略掉高阶无穷小$\mathcal{O}(\Vert \mathcal{P}{\Vert }^2)$，通过令$\nabla \varphi (\mathcal{P})\triangleq 0$来求解${\mathcal{P}}_k$，使$\varphi ({\mathcal{P}}_k)$取得最小值：
  $$\nabla \varphi (\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$，使$\varphi ({\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{array}{rl}\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{array}{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{array}{rl}\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{array}$$
假设$\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{array}{rl}{\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{array}$$
  • 计算${\theta }_0$位置的$\text{Hessian Matrix}\Rightarrow \mathcal{H}$：
    该公式同样也是书上描述。
    $$\begin{array}{rl}\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{array}$$
  • 计算$\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}\iff {\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$是个错误的方向。

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

上述情况可以使用正则化$\text{Hessian Matrix}$来避免。一种常用的正则化策略是$\text{Hessian Matrix}$加上一个对角线元素均为$\alpha$的对角阵：
$$\theta ={\theta }_0-{\left[\underset{\mathcal{H}}{\underbrace{{\nabla }_{\theta }^2\mathcal{J}({\theta }_0)}}+\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\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{array}{rl}\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{array}$$
这相当于：给$\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{array}{r}\frac{1}{\alpha }\times \end{array}$普通梯度。

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

相关参考：
《深度学习》(花书)P190 - 8.6 二阶近似方法