机器学习笔记之优化算法——再回首:牛顿法与正则化
- 引言
- 回顾:经典牛顿法及其弊端
- 牛顿法:算法步骤
- 迭代过程中可能出现的问题
- 正则化 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+α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+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 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!1PT[∇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的解。
- 如果
∇
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)达到最小值:
牛顿法:算法步骤
在训练神经网络的方法中,牛顿法是二阶近似方法的代表。这里为了简单表述,将上面提到的目标函数
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=1∑NL[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)=∇θ{N1i=1∑NL[G(x(i);θ0),y(i)]}=N1∇θi=1∑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_{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=1∑NL[G(x(i);θ0),y(i)]}=N1∇θ2i=1∑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+Δθ
- 计算
∇
θ
J
(
θ
0
)
\nabla_{\theta} \mathcal J(\theta_0)
∇θJ(θ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
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。因而,最终结果是:只有少量参数的神经网络,才能在实际中使用牛顿法进行训练。文章来源:https://www.uudwc.com/A/8pj9Y/
相关参考:
《深度学习》(花书)P190 - 8.6 二阶近似方法文章来源地址https://www.uudwc.com/A/8pj9Y/