我是靠谱客的博主 专注音响,最近开发中收集的这篇文章主要介绍【机器学习】梯度下降法与牛顿法【Ⅲ】拟牛顿法,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

参考了各路神仙的资料,包含自己的理解。
有任何的书写错误、排版错误、概念错误等,希望大家包含指正。

由于字数限制,分成三篇博客。
【机器学习】梯度下降法与牛顿法【Ⅰ】梯度下降法概述
【机器学习】梯度下降法与牛顿法【Ⅱ】牛顿法与修正牛顿法
【机器学习】梯度下降法与牛顿法【Ⅲ】拟牛顿法

2.4. 拟牛顿法

牛顿法在每次迭代时需要计算出黑塞矩阵 H t H_t Ht,然后求解一个以该矩阵为系数矩阵的线性方程组 H t d t = − g t H_td_t=-g_t Htdt=gt,这非常耗时,另外黑塞矩阵可能不可逆。为此提出了一些改进的方法,典型的代表是拟牛顿法(Quasi-Newton)。拟牛顿法是一类方法,其思想为不去计算黑塞矩阵及其逆矩阵,而是设法构造一个新矩阵来逼近黑塞矩阵或其逆矩阵。

拟牛顿法的算法实现为

输入:   初 始 值   x 0                                         精 度 阈 值   ε   初 始 矩 阵   B ^ 0 过程: begin{array}{ll} textbf{输入:}&space初始值space x_0 spacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespace \ &space精度阈值 space varepsilon \ &space 初始矩阵 space hat{B}_0\ textbf{过程:} end{array} 输入:过程:  x0                                       ε  B^0

1 : t = 0 ,   B 0 = B ^ 0 2 : while   true   do 3 :      计 算 梯 度   g t 4 :      if   ∣ ∣ g t ∣ ∣ 2   < ε   then 5 :          return   6 :      end   if 7 :      计 算 搜 索 方 向   d t = − B t − 1 g t 8 :      确 定 步 长   λ t 9 :      计 算 新 的 迭 代 点   x t + 1 = x t + λ t d t 10 :      确 定   B t + 1 11 :      t = t + 1 12 : end   while begin{array}{rl} 1:&t=0, space B_0=hat{B}_0\ 2:&textbf{while} space textbf{true} space textbf{do} \ 3:&spacespacespacespace 计算梯度space g_t \ 4:&spacespacespacespace textbf{if}space left|left|g_tright|right|_2space lt varepsilon space textbf{then}\ 5:&spacespacespacespace spacespacespacespace textbf{return } \ 6:&spacespacespacespace textbf{end}space textbf{if} \ 7:&spacespacespacespace 计算搜索方向 space d_t=-B^{-1}_tg_t \ 8:&spacespacespacespace 确定步长 space lambda_t \ 9:&spacespacespacespace 计算新的迭代点 space x_{t+1}=x_t+ lambda_td_t \ 10:&spacespacespacespace 确定 space B_{t+1} \ 11:&spacespacespacespace t=t+1 \ 12:&textbf{end}spacetextbf{while} end{array} 1:2:3:4:5:6:7:8:9:10:11:12:t=0, B0=B^0while true do     gt    if gt2 <ε then        return     end if     dt=Bt1gt     λt     xt+1=xt+λtdt     Bt+1    t=t+1end while

输出:   极 值 点   x t                                       begin{array}{ll} textbf{输出:} &space 极值点space x_t spacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespacespace end{array} 输出:  xt                                     

算法 4    拟牛顿法迭代算法

不同的具体拟牛顿法唯一的区别在于确定算法中 B t + 1 B_{t+1} Bt+1 的方法不同。

2.4.1. 拟牛顿方程

在牛顿法中,对二阶泰勒展开式两侧求导,有
∇ f ( x t + 1 ) = ∇ f ( x t ) + H t ( x t + 1 − x t ) nabla f(x_{t+1})=nabla f(x_t)+H_t(x_{t+1}-x_t) f(xt+1)=f(xt)+Ht(xt+1xt)
用于逼近黑塞矩阵 H H H 的近似矩阵 B B B 也要满足类似上式的关系。因此存在拟牛顿方程
∇ f ( x t + 1 ) − ∇ f ( x t ) = B t + 1 ( x t + 1 − x t ) nabla f(x_{t+1})-nabla f(x_t)=B_{t+1}(x_{t+1}-x_t) f(xt+1)f(xt)=Bt+1(xt+1xt)

有些人可能有疑问,为什么式 7 7 7 B t + 1 B_{t+1} Bt+1 对应 H t H_t Ht

根据算法 3 3 3 的描述,确定 B t + 1 B_{t+1} Bt+1 这步紧跟在第 t t t 轮迭代计算完 x t + 1 x_{t+1} xt+1 之后,其实是提前计算出了下一次迭代中的近似矩阵 B B B ,这样在第 t ′ = t + 1 t'=t+1 t=t+1 轮迭代时就可以直接使用 B t ′ B_{t'} Bt ,根据 d t ′ = − B t ′ − 1 g t ′ d_{t'}=-B^{-1}_{t'}g_{t'} dt=Bt1gt 更新迭代方向,再根据 x t ′ + 1 = x t ′ + λ t ′ d t ′ x_{t'+1}=x_{t'}+lambda_{t'}d_{t'} xt+1=xt+λtdt 计算新迭代点,此时, B t ′ B_{t'} Bt 依然与 H t ′ H_{t'} Ht 对应。

理解了算法过程,这里也就理解了,不再赘述。

y t = ∇ f ( x t + 1 ) − ∇ f ( x t ) y_t=nabla f(x_{t+1})-nabla f(x_t) yt=f(xt+1)f(xt) s t = x t + 1 − x t s_t=x_{t+1}-x_t st=xt+1xt,拟牛顿方程可以简记为
y t = B t + 1 s t (7) y_t=B_{t+1}s_t tag{7} yt=Bt+1st(7)

还可以从拉格朗日中值定理的角度去理解拟牛顿方程,比较容易理解,不再赘述。

另外,如果我们直接逼近的是 H t − 1 H^{-1}_t Ht1 而不是 H t H_t Ht ,规定 C t C_t Ct 是对 H t − 1 H_t^{-1} Ht1 的近似,那么对应地满足
s t = C t + 1 y t (8) s_t=C_{t+1}y_t tag{8} st=Ct+1yt(8)
两个拟牛顿方程对应了两种具体的实现思想,即通过 B t B_t Bt 逼近 H t H_t Ht 和通过 C t C_t Ct 逼近 H t − 1 H_{t}^{-1} Ht1

大体上,基于已有信息 y t y_t yt s t s_t st B t B_t Bt 来确定 B t + 1 B_{t+1} Bt+1(或基于已有信息 y t y_t yt s t s_t st C t C_t Ct 来确定 C t + 1 C_{t+1} Ct+1 )的方法分为两大类。

第一类方法是选择满足拟牛顿方程且与 B t B_t Bt 近似的矩阵,即要求满足
min ⁡ ∣ ∣ B t + 1 − B t ∣ ∣ ,    s . t .   y t = B t + 1 s t , B = B T min ||B_{t+1}-B_t||,spacespace {rm s.t.}space y_t=B_{t+1}s_t,B=B^T minBt+1Bt,  s.t. yt=Bt+1st,B=BT
同理,如果是选择与 C t C_t Ct 近似的矩阵,即需要满足
min ⁡ ∣ ∣ C t + 1 − C t ∣ ∣ ,    s . t .   s t = C t + 1 y t , C = C T min ||C_{t+1}-C_t||,spacespace {rm s.t.}space s_t=C_{t+1}y_t,C=C^T minCt+1Ct,  s.t. st=Ct+1yt,C=CT

这部分具体求解方法过于数学,不进行讲解。

第二类方法是在满足拟牛顿方程的基础上,对 B t B_t Bt(或 C t C_t Ct)进行校正,令 B t + 1 = B t + Δ B t B_{t+1}=B_t+Delta B_t Bt+1=Bt+ΔBt(或 C t + 1 = C t + Δ C t ) C_{t+1}=C_t+Delta C_t) Ct+1=Ct+ΔCt) 。根据对矩阵 Δ B t Delta B_t ΔBt(或 Δ C t Delta C_t ΔCt)的秩要求不同,分为“rank-2 校正”和“rank-1 校正”,“rank-2 校正”要求 Δ B t Delta B_t ΔBt(或 Δ C t Delta C_t ΔCt)的秩为 2 2 2 ,这类方法包括 DFP 方法和 BFGS 方法;“rank-1 校正”要求 Δ B t Delta B_t ΔBt(或 Δ C t Delta C_t ΔCt)的秩为 1 1 1 ,这类方法包括 SR-1 方法。之所以对 Δ B t Delta B_t ΔBt(或 Δ C t Delta C_t ΔCt)的秩进行限制,是因为可以避免 Δ B t Delta B_t ΔBt(或 Δ C t Delta C_t ΔCt)过于复杂,一方面导致计算难度上升,另一方面引入过多无关信息。

2.4.2. DFP

DFP 方法的基本思想是使用矩阵 C t C_t Ct 来逼近黑塞矩阵的逆矩阵 H t − 1 H_t^{-1} Ht1 。在 DFP 方法中 C t + 1 C_{t+1} Ct+1 { y t , s t , C t } {y_t,s_t,C_t} {yt,st,Ct} 满足如下关系
C t + 1 = C t − C t y t y t T C t y t T C t y t + s t s t T y t T s t (9) C_{t+1}=C_t-frac{C_ty_ty_t^TC_t}{y_t^TC_ty_t}+frac{s_ts_t^T}{y_t^Ts_t} tag{9} Ct+1=CtytTCtytCtytytTCt+ytTstststT(9)
推导过程如下。

上文提到 C t + 1 = C t + Δ C t C_{t+1}=C_t+Delta C_t Ct+1=Ct+ΔCt ,其中要求 Δ C t Delta C_t ΔCt 秩为 2 2 2 ,那么不妨假设 Δ C t = a u u T + b v v T Delta C_t=auu^T+bvv^T ΔCt=auuT+bvvT,即
C t + 1 = C t + a u u T + b v v T (10) C_{t+1}=C_t+auu^T+bvv^T tag{10} Ct+1=Ct+auuT+bvvT(10)
其中 u u u v v v n n n 维向量, a a a b b b 为标量。

可以证明只有当 u u u v v v 线性无关时, r ( a u u T + b v v T ) = 2 r(auu^T+bvv^T)=2 r(auuT+bvvT)=2,其他情况下 a u u T + b v v T auu^T+bvv^T auuT+bvvT 的秩均不为 2 2 2,所以我认为更准确地来说, Δ C t Delta C_t ΔCt 的秩最大为 2 2 2

将拟牛顿方程式 ( 8 ) (8) (8) 代入式 ( 10 ) (10) (10) 中,变形后得
C t y t + a u u T y t + b v v T y t − s t = 0 (11) C_ty_t+auu^Ty_t+bvv^Ty_t-s_t=0 tag{11} Ctyt+auuTyt+bvvTytst=0(11)
u = C t y t u=C_ty_t u=Ctyt,则式 ( 11 ) (11) (11) 的前两项可以合并为 C t y t + a u u T y t = u ( 1 + a u T y t ) C_ty_t+auu^Ty_t=u(1+au^Ty_t) Ctyt+auuTyt=u(1+auTyt) ;令 v = s t v=s_t v=st,则式 ( 11 ) (11) (11) 的后两项可以合并为 b v v T y t − s t = s t ( b v T y t − 1 ) bvv^Ty_t-s_t=s_t(bv^Ty_t-1) bvvTytst=st(bvTyt1) 。由于方程就式 ( 11 ) (11) (11) 一个,但是未知数却有 u u u v v v 两个,因此方程存在多组解,我们不妨认为 1 + a u T y t = 0 1+au^Ty_t=0 1+auTyt=0 b v T y t − 1 = 0 bv^Ty_t-1=0 bvTyt1=0,可以解得

从另一个角度来说,如果 u u u v v v 线性无关,那么想要式 ( 11 ) (11) (11) 成立就必须保证 u u u 的系数 1 + a u T y t 1+au^Ty_t 1+auTyt v v v 的系数 b v T y t − 1 bv^Ty_t-1 bvTyt1 均为零。

a = − 1 u T y t = − 1 y t T C t y t b = 1 v T y t = 1 s t T y t a=-frac{1}{u^Ty_t}=-frac{1}{y_t^TC_ty_t} \ b=frac{1}{v^Ty_t}=frac{1}{s_t^Ty_t} a=uTyt1=ytTCtyt1b=vTyt1=stTyt1

u = C t y t u=C_ty_t u=Ctyt v = s t v=s_t v=st 以及上面的结果代回式 ( 10 ) (10) (10) 中可得式 ( 9 ) (9) (9)

2.4.3. BFGS

BFPS 方法的基本思想是使用矩阵 B t B_t Bt 来逼近黑塞矩阵 H t H_t Ht 。在 BFPS 方法中 B t + 1 B_{t+1} Bt+1 { y t , s t , B t } {y_t,s_t,B_t} {yt,st,Bt} 满足如下关系
B t + 1 = B t − B t s t s t T B t s t T B t s t + y t y t T y t T s t (12) B_{t+1}=B_t-frac{B_ts_ts_t^TB_t}{s_t^TB_ts_t}+frac{y_ty_t^T}{y_t^Ts_t} tag{12} Bt+1=BtstTBtstBtststTBt+ytTstytytT(12)
推导过程与 DFP 相似,由于 BFGS 对应的拟牛顿方程式 ( 7 ) (7) (7)与 BFP 的拟牛顿方程式 ( 8 ) (8) (8) 是对偶的,所以只需要将式 ( 9 ) (9) (9) 中的 y t y_t yt s t s_t st 调换即可。

在根据 d t = − B t − 1 g t d_t=-B^{-1}_tg_t dt=Bt1gt 获取迭代方向时,需要用到 B − 1 B^{-1} B1,虽然又出现了计算逆矩阵的步骤,直观上来看与引入拟牛顿法的目的相违背,但是其实可以通过 Sherman-Morrison 公式将式 ( 12 ) (12) (12) 关于 B B B 的递推公式转换为关于 B − 1 B^{-1} B1 的递推公式。

Sherman-Morrison公式以 Jack Sherman 和 Winifred J. Morrison命名,在线性代数中,是求解逆矩阵的一种方法。对于任意非奇异方阵 A A A n n n 维向量 u , v ∈ R n u,vin mathbb{R}^n u,vRn,若 1 + v T A − 1 u ≠ 0 1+v^TA^{-1}une 0 1+vTA1u=0,则
( A + u v T ) − 1 = A − 1 − ( A − 1 u ) ( v T A − 1 ) 1 + v T A − 1 u (13) (A+uv^T)^{-1}=A^{-1}-frac{(A^{-1}u)(v^TA^{-1})}{1+v^TA^{-1}u}tag{13} (A+uvT)1=A11+vTA1u(A1u)(vTA1)(13)
通过式 ( 13 ) (13) (13) 最终得到
B t + 1 − 1 = ( I − s t y t T s t T y t ) B t − 1 ( I − y t s t T s t T y t ) + s t s t T s t T y t (14) B_{t+1}^{-1}=left(I-frac{s_ty^T_t}{s^T_ty_t}right)B_t^{-1}left(I-frac{y_ts_t^T}{s^T_ty_t}right)+frac{s_ts^T_t}{s^T_ty_t} tag{14} Bt+11=(IstTytstytT)Bt1(IstTytytstT)+stTytststT(14)
我们一般初始化 B 0 = I B_0=I B0=I,所以 B 0 − 1 = I B^{-1}_0=I B01=I,之后根据式 ( 14 ) (14) (14) 进行递推即可。

下面是推导式 ( 14 ) (14) (14) 的过程。

为了方便叙述,省略下标。令 D = B + y y T y T s D=B+frac{yy^T}{y^Ts} D=B+yTsyyT ,可知 − B s s T B s T B s = − 1 s T B s ( B s ) ( B s ) T -frac{Bss^TB}{s^TBs}=-frac{1}{s^TBs}(Bs)(Bs)^T sTBsBssTB=sTBs1(Bs)(Bs)T s T B s s^TBs sTBs 为标量(二次型形式)。

对式 ( 12 ) (12) (12) 两侧取逆,利用Sherman-Morrison公式有
KaTeX parse error: No such environment: align at position 8: begin{̲a̲l̲i̲g̲n̲}̲ B_{t+1}^{-1}&=…
D − 1 D^{-1} D1 再次利用Sherman-Morrison公式有
KaTeX parse error: No such environment: align at position 8: begin{̲a̲l̲i̲g̲n̲}̲ D^{-1}&=left(…
注意到 y T s y^Ts yTs y T B − 1 y y^TB^{-1}y yTB1y 都是常数,令 Q = y T s + y T B − 1 y Q=y^Ts+y^TB^{-1}y Q=yTs+yTB1y,将式 ( 16 ) (16) (16) 代回式 ( 15 ) (15) (15) 中,其中第二项
KaTeX parse error: No such environment: align at position 8: begin{̲a̲l̲i̲g̲n̲}̲ D^{-1}frac{Bs…
将第二项代回,有
KaTeX parse error: No such environment: align at position 8: begin{̲a̲l̲i̲g̲n̲}̲ B_{t+1}^{-1} &…
k = s T y k=s^Ty k=sTy 代回式 ( 17 ) (17) (17) ,加上下标得到式 ( 14 ) (14) (14) 。推导完毕。

一定注意 B t − 1 ≠ C t B_t^{-1} ne C_t Bt1=Ct !虽然根据拟牛顿公式很容易得到 B B B C C C 满足互逆的关系,但本质上二者是不互逆的,通过对比式 ( 9 ) (9) (9) 和式 ( 14 ) (14) (14) 可以很清楚地看到二者是不同的。直观上理解, B t − 1 B_t^{-1} Bt1 是我们通过对 B t B_t Bt 迭代再取逆得到的,而 C t C_t Ct 通过迭代可以直接得到,除了 B 0 B_0 B0 C 0 C_0 C0 一般取 I I I 所以互逆外,其他迭代中 B B B C C C 无法满足时刻互逆,因此最终也无法保证二者互逆。

另一个角度考虑,如果二者满足互逆关系,那么 BFGS 方法完全没有必要存在,相比于 DFP 方法甚至还多了一步求逆的过程。相反,实践表明 BFGS 方法往往比 DFP 方法更加有效,被认为是最有效的拟牛顿法。

2.4.4. SR-1

有别于 DFP 方法和 BFGS 方法,SR-1 方法是一种 rank-1 校正方法。其基本思想也是用 B t B_t Bt(或 C t C_t Ct)来逼近黑塞矩阵 H t H_t Ht(或其逆矩阵 H t − 1 H^{-1}_t Ht1),这里仅大概描述一下 SR-1 采用 B t B_t Bt 逼近黑塞矩阵 H t H_t Ht 时公式,采用新的矩阵逼近黑塞矩阵的逆矩阵的公式类似。在 SR-1 方法中 B t + 1 B_{t+1} Bt+1 { y t , s t , B t } {y_t,s_t,B_t} {yt,st,Bt} 满足如下关系
B t + 1 = B t + ( y t − B t s t ) ( y t − B t s t ) T ( y t − B t s t ) T s t (18) B_{t+1}=B_t+frac{(y_t-B_ts_t)(y_t-B_ts_t)^T}{(y_t-B_ts_t)^Ts_t} tag{18} Bt+1=Bt+(ytBtst)Tst(ytBtst)(ytBtst)T(18)
推导过程与 BFGS 方法类似。只不过因为是 rank-1 校正,所以只要求 Δ B t = a u u T Delta B_t=auu^T ΔBt=auuT 。将拟牛顿方程式 ( 7 ) (7) (7) 代入 B t + 1 = B t + a u u T B_{t+1}=B_t+auu^T Bt+1=Bt+auuT 中得
a u u T s t = y t − B t s t auu^Ts_t=y_t-B_ts_t auuTst=ytBtst
u = y t − B t s t u=y_t-B_ts_t u=ytBtst ,得 a u T s t = 1 au^Ts_t=1 auTst=1,即 a = 1 u T s t = 1 ( y t − B t s t ) T s t a=frac{1}{u^Ts_t}=frac{1}{(y_t-B_ts_t)^Ts_t} a=uTst1=(ytBtst)Tst1 。将 u u u a a a 代回 B t + 1 = B t + a u u T B_{t+1}=B_t+auu^T Bt+1=Bt+auuT 中得到式 ( 18 ) (18) (18)

SR-1 方法的迭代公式相较于 DFP 方法和 BFGS 方法更加简单,但是 DFP 方法和 BFGS 方法可以保证 B B B (或 C C C)正定,而 SR-1 方法不行。

3. 梯度下降法与牛顿法的对比

牛顿法属于高阶优化算法,梯度下降法属于低阶优化算法,因为相较而言高阶算法看得更远,在做出某一步点移动的选择时候,会考虑之后的更多步,因此下降路径更符合真实的最快下降路径,低阶算法所考虑的下降路径则更局部,因此牛顿法的收敛速度会比梯度下降法更快。

假设目标函数是个二元函数,那么牛顿法相当于用一个曲面来拟合局部区域,而梯度下降法相当于用一个平面拟合局部区域,显然曲面拟合会更加真实,更加相似。

二者都存在陷入局部极值点的问题。可以通过设置不同的初始迭代点多次执行,或者规定约束条件以保证结果正确。

原始牛顿法主要存在三个缺点:

  1. 局部极值点或鞍点
  2. 迭代不能保证目标函数值减小
  3. 获取黑塞矩阵的计算量过大,且不一定可逆

缺点2可以由修正牛顿法解决,缺点2和缺点3可以由拟牛顿法解决。

另外需要注意,在深度学习中,往往采用梯度下降法,而很少采用牛顿法,主要是因为神经网络常常是非凸的,牛顿法难以收敛,即使收敛也很容易陷入鞍点。

REF

[1] 牛顿法 - 博客园

[2] 黑塞矩阵 - 百度百科

[3] 牛顿法和拟牛顿法 - 知乎

[4] 【最优化】无约束优化方法- 知乎

[5] (一)牛顿法与阻尼牛顿法 - 博客园

[6] 线搜索(line search)方法 - 博客园

[7] 最优化理论与方法-第六讲-无约束优化问题(二)- 哔哩哔哩

[8] 拟牛顿法(DFP、BFGS、L-BFGS)- CSDN博客

[9] Sherman-Morrison公式在BFGS算法的应用 - 简书

[10] 逻辑回归模型及LBFGS的Sherman Morrison(SM) 公式推导 - CSDN博客

[11] 最优化算法数学详解之——梯度下降法和牛顿迭代法 - CSDN博客

最后

以上就是专注音响为你收集整理的【机器学习】梯度下降法与牛顿法【Ⅲ】拟牛顿法的全部内容,希望文章能够帮你解决【机器学习】梯度下降法与牛顿法【Ⅲ】拟牛顿法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(73)

评论列表共有 0 条评论

立即
投稿
返回
顶部