宁波市高等级公路建设指挥部网站,西安小程序开发哪家好,wordpress 删除小工具栏,石家庄响应式模板建站机器学习笔记之优化算法——再回首:牛顿法与正则化 引言回顾#xff1a;经典牛顿法及其弊端牛顿法#xff1a;算法步骤迭代过程中可能出现的问题正则化 Hessian Matrix \text{Hessian Matrix} Hessian Matrix与相应问题 引言
本节我们介绍经典牛顿法在训练神经网络过程中的迭… 机器学习笔记之优化算法——再回首:牛顿法与正则化 引言回顾经典牛顿法及其弊端牛顿法算法步骤迭代过程中可能出现的问题正则化 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_{k1} x_k \alpha_k \cdot \mathcal P_k xk1xkαk⋅Pk 其中标量 α k \alpha_k αk表示当前第 k k k次迭代情况下的更新步长向量 P k \mathcal P_k Pk表示当前迭代步骤的更新方向。与梯度下降法区分的是在经典牛顿法中
步长并不是我们关注的信息我们通常设置 α k 1 ( k 1 , 2 , 3 , ⋯ ) \alpha_k 1(k1,2,3,\cdots) αk1(k1,2,3,⋯)从而迭代结果 x k 1 x_{k1} xk1可看作是关于方向变量 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_{k1} x_k \mathcal P \\ \mathcal P_k \mathop{\arg\min}\limits_{\mathcal P} f(x_{k1}) \\ \mathop{\arg\min}\limits_{\mathcal P} f(x_k \mathcal P) \end{aligned} \end{cases} ⎩ ⎨ ⎧xk1PkxkPPargminf(xk1)Pargminf(xkP)关于目标函数 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(xkP)进行二阶泰勒展开 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(xkP)ϕ(P)f(xk)1!1[∇f(xk)]TP2!1PT[∇2f(xk)]⋅PO(∥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_{i1}^N \mathcal L [\mathcal G(x^{(i)};\theta),y^{(i)}] \end{aligned}\quad P_{data} \{(x^{(i)},y^{(i)})\}_{i1}^N J(θ)EPdata{L[G(x(i);θ),y(i)]}N1i1∑NL[G(x(i);θ),y(i)]Pdata{(x(i),y(i))}i1N 其中 θ \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_{i1}^N \mathcal L[\mathcal G(x^{(i)};\theta_0),y^{(i)}]\right\} \\ \frac{1}{N} \nabla_{\theta} \sum_{i1}^N \mathcal L[\mathcal G(x^{(i)};\theta_0),y^{(i)}] \end{aligned} ∇θJ(θ0)∇θ{N1i1∑NL[G(x(i);θ0),y(i)]}N1∇θi1∑NL[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_{i1}^N \mathcal L[\mathcal G(x^{(i)};\theta_0),y^{(i)}]\right\} \\ \frac{1}{N} \nabla_{\theta}^2 \sum_{i1}^N \mathcal L[\mathcal G(x^{(i)};\theta_0),y^{(i)}] \end{aligned} H∇θ2J(θ0)∇θ2{N1i1∑NL[G(x(i);θ0),y(i)]}N1∇θ2i1∑NL[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∇θ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 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 HQΛQTQQTQTQI 并且 λ I Q ( λ I ) Q T \lambda \mathcal I \mathcal Q(\lambda \mathcal I) \mathcal Q^T λIQ(λ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λ⋅IQΛQTQ(λI)QTQ(Λλ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 二阶近似方法
