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

机器学习笔记之优化算法——再回首:牛顿法与正则化

• 引言

引言

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

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

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

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

牛顿法：算法步骤

在训练神经网络的方法中，牛顿法是二阶近似方法的代表。这里为了简单表述，将上面提到的目标函数 f ( ⋅ ) f(\cdot) f(⋅)具象化为经验风险 ( Empirical Risk ) (\text{Empirical Risk}) (Empirical Risk)：
J ( θ ) = E P d a t a { L [ G ( x ( i ) ; θ ) , y ( i ) ] } = 1 N ∑ i = 1 N L [ G ( x ( i ) ; θ ) , y ( i ) ] P d a t a = { ( x ( i ) , y ( i ) ) } i = 1 N \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 J(θ)​=EPdata​​{L[G(x(i);θ),y(i)]}=N1​i=1∑N​L[G(x(i);θ),y(i)]​Pdata​={(x(i),y(i))}i=1N​
其中 θ \theta θ可看作是需要学习的模型参数； G ( ⋅ ) \mathcal G(\cdot) G(⋅)可看作是模型关于 x x x的预测函数； L ( ⋅ ) \mathcal L(\cdot) L(⋅)可看作是损失函数，描述预测结果与真实标签的差异性信息。

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

• 实际上，书中 θ − θ 0 \theta - \theta_0 θ−θ0​本身就将步长 α = 1 \alpha = 1 α=1包含在内。
• 这里关于 J ( θ ) \mathcal J(\theta) J(θ)高于二阶的高阶无穷小直接省略掉了~
• 关于 Hessian Matrix ⇒ ∇ 2 J ( θ 0 ) \text{Hessian Matrix} \Rightarrow \nabla^2 \mathcal J(\theta_0) Hessian Matrix⇒∇2J(θ0​)直接使用 H \mathcal H H进行表示。
  J ( θ ) ≈ J ( θ 0 ) + 1 1 ! ( θ − θ 0 ) T ∇ θ J ( θ 0 ) + 1 2 ! ( θ − θ 0 ) T H ( θ − θ 0 ) \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) J(θ)≈J(θ0​)+1!1​(θ−θ0​)T∇θ​J(θ0​)+2!1​(θ−θ0​)TH(θ−θ0​)

依然令 ∇ J ( θ ) ≜ 0 \nabla \mathcal J(\theta) \triangleq 0 ∇J(θ)≜0，有：
∇ J ( θ ) = ( 1 − 0 ) ⋅ ∇ J θ ( θ 0 ) + 1 2 ⋅ 2 ( θ − θ 0 ) ⋅ H ≜ 0 ⇒ H ( θ − θ 0 ) = − ∇ J θ ( θ 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} ∇J(θ)​=(1−0)⋅∇Jθ​(θ0​)+21​⋅2(θ−θ0​)⋅H≜0⇒H(θ−θ0​)=−∇Jθ​(θ0​)​
假设 H \mathcal H H是正定的条件下，关于 θ \theta θ与 θ 0 \theta_0 θ0​的递推关系表示如下：
θ = θ 0 − H − 1 ∇ θ J ( θ 0 ) \theta = \theta_0 - \mathcal H^{-1} \nabla_{\theta} \mathcal J(\theta_0) θ=θ0​−H−1∇θ​J(θ0​)

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

• 初始化：初始参数 θ s t a r t \theta_{start} θstart​以及包含 N N N个样本的训练数据集；

• While \text{While} While：

  • 计算 ∇ θ J ( θ 0 ) \nabla_{\theta} \mathcal J(\theta_0) ∇θ​J(θ0​)：
    牛顿-莱布尼兹公式~,这是书上的表达。详细位置见末尾~
    ∇ θ J ( θ 0 ) = ∇ θ { 1 N ∑ i = 1 N L [ G ( x ( i ) ; θ 0 ) , y ( i ) ] } = 1 N ∇ θ ∑ i = 1 N L [ G ( x ( i ) ; θ 0 ) , y ( i ) ] \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} ∇θ​J(θ0​)​=∇θ​{N1​i=1∑N​L[G(x(i);θ0​),y(i)]}=N1​∇θ​i=1∑N​L[G(x(i);θ0​),y(i)]​
  • 计算 θ 0 \theta_0 θ0​位置的 Hessian Matrix ⇒ H \text{Hessian Matrix} \Rightarrow \mathcal H Hessian Matrix⇒H：
    该公式同样也是书上描述。
    H = ∇ θ 2 J ( θ 0 ) = ∇ θ 2 { 1 N ∑ i = 1 N L [ G ( x ( i ) ; θ 0 ) , y ( i ) ] } = 1 N ∇ θ 2 ∑ i = 1 N L [ G ( x ( i ) ; θ 0 ) , y ( i ) ] \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} H​=∇θ2​J(θ0​)=∇θ2​{N1​i=1∑N​L[G(x(i);θ0​),y(i)]}=N1​∇θ2​i=1∑N​L[G(x(i);θ0​),y(i)]​
  • 计算 Hessian Matrix \text{Hessian Matrix} Hessian Matrix的逆： H − 1 \mathcal H^{-1} H−1；
  • 计算变量 θ \theta θ的变化量 Δ θ \Delta \theta Δθ：
    Δ θ = − H − 1 ∇ θ J ( θ 0 ) \Delta \theta = -\mathcal H^{-1} \nabla_{\theta} \mathcal J(\theta_0) Δθ=−H−1∇θ​J(θ0​)
  • 对变量 θ \theta θ进行更新：
    θ = θ 0 + Δ θ \theta = \theta_0 + \Delta \theta θ=θ0​+Δθ

• End While \text{End While} End While

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

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

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

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

上述情况可以使用正则化 Hessian Matrix \text{Hessian Matrix} Hessian Matrix来避免。一种常用的正则化策略是 Hessian Matrix \text{Hessian Matrix} Hessian Matrix加上一个对角线元素均为 α \alpha α的对角阵：
θ = θ 0 − [ ∇ θ 2 J ( θ 0 ) ⏟ H + α ⋅ I ] − 1 ∇ θ J ( θ 0 ) \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) θ=θ0​− ​H ∇θ2​J(θ0​)​​+α⋅I ​−1∇θ​J(θ0​)
这种操作我们早在正则化与岭回归中就已介绍过。由于 Hessian Matrix ⇒ H \text{Hessian Matrix} \Rightarrow \mathcal H Hessian Matrix⇒H至少是实对称矩阵，那么必然有：
H = Q Λ Q T Q Q T = Q T Q = I \mathcal H = \mathcal Q\Lambda \mathcal Q^T \quad \mathcal Q\mathcal Q^T = \mathcal Q^T\mathcal Q = \mathcal I H=QΛQTQQT=QTQ=I
并且 λ I = Q ( λ I ) Q T \lambda \mathcal I = \mathcal Q(\lambda \mathcal I) \mathcal Q^T λI=Q(λI)QT，从而 H + λ ⋅ I \mathcal H + \lambda \cdot \mathcal I H+λ⋅I可表示为：
H + λ ⋅ I = Q Λ Q T + Q ( λ I ) Q T = Q ( Λ + λ I ) Q T \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} H+λ⋅I​=QΛQT+Q(λI)QT=Q(Λ+λI)QT​
这相当于：给 H \mathcal H H的所有特征值加上一个正值 α \alpha α。
相比于最小二乘法模型参数 W \mathcal W W的矩阵形式表达： W = ( X T X ) − 1 X T Y \mathcal W = (\mathcal X^T \mathcal X)^{-1} \mathcal X^T \mathcal Y W=(XTX)−1XTY, H \mathcal H H可能更不稳定。因为 X T X \mathcal X^T\mathcal X XTX必然是半正定的,但 H \mathcal H H中的特征值有可能是负的。

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

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

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