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

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

  • 引言
    • 回顾:经典牛顿法及其弊端
    • 牛顿法:算法步骤
    • 迭代过程中可能出现的问题
    • 正则化 Hessian Matrix \text{Hessian Matrix} Hessian Matrix与相应问题

引言

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

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

经典牛顿法自身是一个典型的线搜索方法 ( 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+αkPk
其中标量 α 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+1Pk=xk+P=Pargminf(xk+1)=Pargminf(xk+P)
  • 关于目标函数 f ( ⋅ ) f(\cdot) f(),我们对其要求是: f ( ⋅ ) f(\cdot) f()至少二阶可微。这意味着 Hessian Matrix ⇒ ∇ 2 f ( ⋅ ) \text{Hessian Matrix} \Rightarrow \nabla^2 f(\cdot) Hessian Matrix2f()存在。因此对目标函数 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!1PT[2f(xk)]P+O(P2)
    忽略掉高阶无穷小 O ( ∥ P ∥ 2 ) \mathcal O(\|\mathcal P\|^2) O(P2),通过 ∇ ϕ ( 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)02f(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 Matrix2f(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)]1f(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)]}=N1i=1NL[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 Matrix2J(θ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(θ)=(10)Jθ(θ0)+212(θθ0)H0H(θθ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) θ=θ0H1θ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)=θ{N1i=1NL[G(x(i);θ0),y(i)]}=N1θi=1NL[G(x(i);θ0),y(i)]
    • 计算 θ 0 \theta_0 θ0位置的 Hessian Matrix ⇒ H \text{Hessian Matrix} \Rightarrow \mathcal H Hessian MatrixH
      该公式同样也是书上描述。
      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=θ2J(θ0)=θ2{N1i=1NL[G(x(i);θ0),y(i)]}=N1θ2i=1NL[G(x(i);θ0),y(i)]
    • 计算 Hessian Matrix \text{Hessian Matrix} Hessian Matrix的逆: H − 1 \mathcal H^{-1} H1
    • 计算变量 θ \theta θ变化量 Δ θ \Delta \theta Δθ
      Δ θ = − H − 1 ∇ θ J ( θ 0 ) \Delta \theta = -\mathcal H^{-1} \nabla_{\theta} \mathcal J(\theta_0) Δθ=H1θ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} H1无法求解。在凸函数 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 Convex2f(x)mI
也就是说:要想 H = ∇ θ 2 J ( θ 0 ) \mathcal H = \nabla_{\theta}^2 \mathcal J(\theta_0) H=θ2J(θ0)正定,必然需要目标函数 J ( θ ) \mathcal J(\theta) J(θ) θ = θ 0 \theta= \theta_0 θ=θ0不仅是凸的,甚至是强凸

但在深度学习中,目标函数的表面由于特征较多,从而在局部呈现非凸的情况。例如鞍点二阶梯度函数 ∇ θ 2 J ( θ ) \nabla_{\theta}^2 \mathcal J(\theta) θ2J(θ)在该处的特征值并不都是正的,也就是说:鞍点处的 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 θ2J(θ0)+αI 1θJ(θ0)
这种操作我们早在正则化与岭回归中就已介绍过。由于 Hessian Matrix ⇒ H \text{Hessian Matrix} \Rightarrow \mathcal H Hessian MatrixH至少是实对称矩阵,那么必然有:
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} HRp×p,其中 p p p表示样本特征维度,求解 H − 1 \mathcal H^{-1} H1时间复杂度 O ( k 3 ) \mathcal O(k^3) O(k3)。并且由于迭代过程中随着 θ \theta θ的变化,因而需要每次迭代过程都要计算对应 H − 1 \mathcal H^{-1} H1。因而,最终结果是:只有少量参数的神经网络,才能在实际中使用牛顿法进行训练。

相关参考:
《深度学习》(花书)P190 - 8.6 二阶近似方法文章来源地址https://www.uudwc.com/A/8pj9Y/

原文地址:https://blog.csdn.net/qq_34758157/article/details/132500004

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

h
上一篇 2023年08月26日 12:09
下一篇 2023年08月26日 12:09