美文网首页
2019-04-08

2019-04-08

作者: sea_monster | 来源:发表于2019-04-08 16:45 被阅读0次

Line Search,BGFS,LBGFS

Line Search

line search方法：
1.首先找到一个下降方向;
2.然后计算目标函数f将沿着这个方向减小的一个步骤大小。
3.最后确定X应该沿着这个方向移动的距离。

下降方向的计算方法有梯度下降法、牛顿法等。

例子：
下面是一个使用行搜索的梯度方法示例。

1.设置迭代计数器k=0，并初始猜测X_0的最小重复次数。
2.Repeat：
3.计算下降方向P_k
4.选择\alpha_k去不精确的最小化h(\alpha)=f(X_k+\alpha P_k)
5.更新X_{k+1}=X_k+\alpha_k P_k和k=k+1
6.直到\|\nabla f(X_k)\| < \epsilon

在行搜索步骤(4)中，该算法可以通过求解h'(\alpha _k)=0来精确地最小化h，也可以通过让h有足够的减少量来不精确地最小化h。

前者称为精确行搜索,例如共轭梯度法。
后者称为不精确行搜索，例如回溯行搜索或者使用Wolfe条件。

Wholfe Condition

在无约束最小化问题中，Wolfe条件是一组执行不精确线搜索的不等式，特别是在准牛顿方法中,

由Philip Wolfe于1969年首次发表。

对于连续光滑的函数f:\mathbb R^n \to \mathbb R，为了求解f(X)的最小值，可将问题转化为求解多个子问题：\underset{\alpha}{min}f(X_k+\alpha p_k)。

其中X_k是当前最好的猜测，p_k \in \mathbb R^n是一个搜索方向，以及\alpha \in \mathbb R是步长。

当前最好的猜测意思是指当前的X_k是最接近argmin f(X)的一个值。

不精确的线搜索提供了计算可接受的步长\alpha的有效方式，这样就可以“充分”降低目标函数，而不是精确地最小化目标函数。

在线搜索中，还没有找到新的搜索方向p_k的时候，对\alpha的估计都可以使用Wolfe条件。

Armijo规则和曲率：
如果有以下两个不等式成立：

  1. f(X_k+\alpha_k p_k) \le f(X_k)+c_1\alpha_kp_k^T\nabla f(X_k)
  2. -p_k^T\nabla f(X_k+\alpha_k p_k)\le -c_2p_k^T\nabla f(X_k)

那么说明在梯度下降的方向p_k上，步长\alpha_k满足了沃尔夫的条件。

不等式1被称为Armijo规则而不等式2作为曲率的条件;不等式1确保步长\alpha能使f充分地减少，不等式2确保梯度充分地减小，可以分别解释步长值的上限和下限。

c_1通常取一个较小的值而c_2通常取一个较大的值，且满足0<c_1<c_2<1。

Nocedal建议{c_1=10^{-４}}，而c_2在牛顿或拟牛顿方法中为0.9，在非线性共轭梯度中为0.1。

曲率强的Wolfe条件
\varphi(a)=f(X_k+\alpha p_k)表示关于\alpha的单变量函数\varphi限制在方向p_k。

Wolfe条件可能导致步长的值不接近最小值\varphi。所以我们可以将曲率条件(即不等式2)修改为以下形式：

  1. {\displaystyle| p_k^T\nabla f(X_k+\alpha_k p_k)|\le c_2|p_k^T\nabla f(x_k)|}

然后1和3形成强沃尔夫条件，使\alpha接近临界点的\varphi。

原理
在一个优化算法中强加Wolfe条件X_{k+1}=X_k+\alpha p_k是为了确保梯度收敛到零。具体来说，如果p_k和梯度所成角度的cos值：
{\displaystyle cos\theta_k=\frac{\nabla f(X_k)^Tp_k}{\|\nabla f(X_k)\|\|p_k\|}}
被限制大于0，并且有不等式1和不等式2成立，那么\nabla f(X_k)\to 0。

BFGS

本文参考：
wiki百科
割线法求方程根
Broyden–Fletcher–Goldfarb–Shanno algorithm

牛顿法需要计算Hessian矩阵的逆矩阵，运算复杂度太高。在动辄百亿、千亿量级特征的大数据时代，模型训练耗时太久。因此，很多牛顿算法的变形出现了，这类变形统称拟牛顿算法。拟牛顿算法的核心思想用一个近似矩阵B替代逆Hessian矩阵H^{-1}。不同算法的矩阵B的计算有差异，但大多算法都是采用迭代更新的思想在tranning的每一轮更新矩阵B。

由于BFGS涉及割线等式(secant equation)，所以先介绍一下割线法。
割线法：

方法：


optimization图20.png

割线法的最初两个迭代。红色曲线表示函数f，蓝色曲线表示割线。
割线法由以下的递推关系定义：

{\displaystyle x_{n+1}=x_n-\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}f(x_n)}

从上式中可以看出，割线法的初始值x0和x1，离函数的根越近越好。

方法的推导：

给定x_{n-1}和x_n，我们通过作点(x_{n−1}, f(x_{n−1}))和(x_n, f(x_n))的直线，得到函数f的割线。这条割线的点斜式直线方程为：

{\displaystyle y-f(x_n)=\frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}}(x-x_n)}

当y=0时，求解x即为求解x_{n+1}，此时有方程：

{\displaystyle x_{n+1}=x_n-\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}f(x_n)}

收敛:

如果初始值x_0和x_1离根足够近，那么割线会在第n次迭代后将x收敛于f的一个根。收敛速率为α，其中：

{\displaystyle \alpha = \frac{1+\sqrt{5}}{2} \approx 1.618}
是黄金比。特别地，收敛速率是超线性的。

这个结果只在某些条件下才成立，例如f是连续的二阶可导函数，且函数的根不是重根。

如果初始值离根太远，则不能保证割线法收敛。

BGFS原理：
优化问题是最小化f(X)，其中X是\mathbb{R}^n中的向量，并且f是一个可微分的标量函数。X可以采用的值没有限制。 该算法从最佳值X_0的初始估计开始，并迭代地进行以在每个阶段获得更好的估计。

可由牛顿方程的模拟解给出阶段k的搜索方向p_k：
B_k p_k=-\nabla f(X_k)

其中B_k是Hessian矩阵的近似值，在每个阶段迭代更新，\nabla f(X_k)是函数的梯度在X_k评估。然后通过使用最小化f(X_k+\alpha p_k)的p_k方向的线搜索来查找下一个点X_{k+1}（\alpha>0)。

对B_k的更新施加的拟牛顿条件是：
B_{k+1}(X_{k+1}-X_k)=\nabla f(X_{k+1})-\nabla f(X_k)

设y_k=\nabla f(X_{k+1})-\nabla f(X_k)和s_k=X_{k+1}-X_k，然后化为B_{k+1}s_k=y_k（割线方程）。当B_{k+1}为正定时，曲率条件s^T_k y_k>0。

为了使函数为强凸，通过在阶段k处添加两个矩阵使B_{k+1}近似Hessian矩阵：
B_{k+1}=B_k+U_k+V_k

(其中U_k和V_k都是秩为1的对称的矩阵，但它们的和是秩为2更新矩阵。)

另一种更简单的使秩为一的方法称为对称秩一方法。由于对称秩一方法不保证正定性，所以为了保持B_{k+1}的对称性和正定性，选择B_{k+1}=B_k+\alpha uu^T+\beta vv^T作为更新形式，又加入之前提到的割线条件：B_{k+1}s_k=y_k。此时让u=y_k和v=B_k s_k，我们可以获得：
{\displaystyle \alpha = \frac{1}{y^T_k s_k}}
{\displaystyle \beta = \frac{1}{s_k^T B_k s_k}}

最后，将B_{k+1}=B_k+\alpha uu^T+\beta vv^T的\alpha和\beta替换，得到B_{k+1}更新等式：

{\displaystyle B_{k+1} = B_k+\frac{y_ky_k^T}{y^T_k s_k}-\frac{B_k s_k s_K^T B_k^T}{s_k^T B_k s_k}}

算法实现：
从初始的X_0和近似Hessian矩阵B_0开始，重复以下步骤，直到X_k收敛：

  1. 通过解B_k p_k=-\nabla f(X_k)获得方向p_k；
  2. 执行一维的最优化（线搜索）以在p_k的方向找到一个可接受的步长\alpha_k，对\alpha_k有：\alpha_k=argmin f(X_k+\alpha p_k)。
  3. 设s_k=\alpha_k p_k(步长和方向)，然后更新X_{k+1}=X_{k}+s_k
  4. 设y_k=\nabla f(X_{k+1})-\nabla f(X_k)
  5. {\displaystyle B_{k+1} = B_k+\frac{y_ky_k^T}{y^T_k s_k}-\frac{B_k s_k s_K^T B_k^T}{s_k^T B_k s_k}}

其中f(X)表示要最小化的目标函数。可以通过观察梯度的范数\|\nabla f(X_k)\|来检查是否收敛。如果B_0被初始化B_0=I，则第一步将等同于梯度下降，但随着步骤加深，B_k近似于Hessian。

该算法的第一步需要使用矩阵B_k的逆，它可以有效地通过Sherman-Morrison公式在第5步来获得:
{\displaystyle B_{k+1}^{-1} =\Big(I-\frac{s_k y_k^T}{y_k^T s_k} \Big) B_k^{-1}\Big(I-\frac{y_k s_k^T}{y_k^T s_k} \Big)+\frac{s_k s_k^T}{y^T_k s_k}}

这可以在没有临时矩阵的情况下有效地计算。

由于B_k^{-1}是对称的，并且y_k^T B^{-1}_k y_k和s^T_k y_k是标量，可以使用变式:
{\displaystyle B_{k+1}^{-1}=B_k^{-1}+\frac{(s_k^T y_k+y_k^TB_k^{-1}y_k)(s_ks_k^T)}{(s^T_ky_k)^2}-\frac{B_k^{-1}y_ks_k^T+s_ky_k^TB_k^{-1}}{s_k^Ty_k}}

Limited-memory BFGS(存储受限的BFGS)

参考：
牛顿法与拟牛顿法学习笔记（五）L-BFGS 算法
wiki Limited-memory BFGS

BFGS的优点是其花费较少的时间改进每个线搜索。在另一方面，BFGS 算法必须存储 Hessian逆矩阵B，需要O(n^2)的存储空间，使BFGS不适用于大多数具有百万级参数的现代深度学习模型。而LBFGS通过避免存储完整的Hessian逆近似B，使算法的存储代价可以显著降低。

该算法基于Hessian逆矩阵的BFGS递推算法：
H_{k+1}=(I-\rho_k s_k y_k^T)H_k(I-\rho_k y_k s_k^T)+ \rho_k s_k s_k^T

推导递归算法的性质：

定义{\displaystyle \rho_k = \frac{1}{y_k^T s_k}}，V_k=I-\rho y_ks_k^T，等式可以改为：
H_{k+1}=V_k^TH_kV_k+\rho_k s_ks_k^T
从最初的H_0计算到H_{k+1}有：
H_1=V_0^TH_0V_0+\rho_0 s_0s_0^T
H_2=V_1^TH_1V_1+\rho_1 s_1s_1^T
\quad \;\; = V_1^TV_0^TH_0V_0V_1+V_1^T\rho s_0s_0^T V_1+\rho_1 s_1 s_1^T
\cdots
H_{k+1}=(V_k^TV_{k-1}^T\cdots V_1^TV_0^T)H_0 (V_0V_1\cdots V_{k-1}V_k)
\qquad \;\;+(V_k^TV_{k-1}^T\cdots V_2^TV_1^T)(\rho_0 s_0 s_0^T) (V_1V_2\cdots V_{k-1}V_k)
\qquad \;\;+(V_k^TV_{k-1}^T\cdots V_3^TV_2^T)(\rho_1 s_1 s_1^T) (V_2V_3\cdots V_{k-1}V_k)
\qquad \;\;+\cdots
\qquad \;\;+(V_k^TV_{k-1}^T)(\rho_{k-2} s_{k-2} s_{k-2}^T) (V_{k-1}V_k)
\qquad \;\;+V_k^T(\rho_{k-1} s_{k-1} s_{k-1}^T) V_k
\qquad \;\;+\rho_k s_k s_k^T

由上式可知，如果要计算H_{k+1}需要储存\{s_i,y_i\}^k_{i=0}个数据，这与我们的低存储的期望不符，于是我们只存储m个数据进行近似计算：

H_{k+1}=(V_k^TV_{k-1}^T\cdots V_{k-m+2}^TV_{k-m+1}^T)H_0 (V_{k-m+1}V_{k-m+2}\cdots V_{k-1}V_k)
\qquad \;\;+(V_k^TV_{k-1}^T\cdots V_{k-m+3}^TV_{k-m+2}^T)(\rho_0 s_0 s_0^T) (V_{k-m+2}V_{k-m+3}\cdots V_{k-1}V_k)
\qquad \;\;+(V_k^TV_{k-1}^T\cdots V_{k-m+4}^TV_{k-m+3}^T)(\rho_1 s_1 s_1^T) (V_{k-m+3}V_{k-m+4}\cdots V_{k-1}V_k)
\qquad \;\;+\cdots
\qquad \;\;+(V_k^TV_{k-1}^T)(\rho_{k-2} s_{k-2} s_{k-2}^T) (V_{k-1}V_k)
\qquad \;\;+V_k^T(\rho_{k-1} s_{k-1} s_{k-1}^T) V_k
\qquad \;\;+\rho_k s_k s_k^T

算法实现：
首先定义{\displaystyle \rho_k = \frac{1}{y_k^T s_k}}，然后固定的k，我们又定义了一个向量序列q_{k-m},\cdots,q_k，其中q_k＝g_k和q_i=(I-\rho_iy_is_i^T)q_{i+1}=V_iq_{i+1}。然后定义\alpha_i=\rho_is_i^Tq_{i+1}，那么对q_i有q_i=q_{i+1}-\alpha_iy_i。接下来我们还定义了另一个向量序列z_{k-m},\cdots,z_k，其中z_{i+1}=(I-\rho_is_iy_i^T)z_i+\alpha_is_i=V_i^Tz_i+\alpha_is_i，然后定义\beta_i=\rho_iy_i^Tz_i，那么对z_{i+1}有z_{i+1}=z_i+(\alpha_i-\beta_i)s_i，初始化z_{k-m}=-H^0_kq_{k-m}，然后递归地使用。最后得到的z_k就是梯度下降方向。

按以下方式计算梯度下降方向：

(其中：s_i = x_{i+1}-x_i,y_i = g_{i+1}-g_i,{\displaystyle \rho_i = \frac{1}{y_i^T s_i}})

q_k=g_k
For\; i=k-1,k-2,\cdots,k-m:
\quad\,\; \alpha_i=\rho_is_i^Tq_{i+1}
\qquad q_i=q_{i+1}-\alpha_i y_i
{\displaystyle \gamma_k = \frac{s^T_{k-1}y_{k-1}}{y^T_{k-1} y_{k-1}}}
H^0_k=\gamma_kI
(使用\gamma_k对I进行缩放，可以得到一个合适步长。)
z_{k-m}=-H^0_kq_{k-m}
For\;i=k-m,k-m+1,\cdots,k-1:
\quad\;\;\beta_i=\rho_iy_i^Tz_i
\quad\;\, z_{i+1}=z_i+(\alpha_i-\beta_i)s_i

第一个循环计算并存储\alpha_i=\rho_is_iV_i \cdots V_{k-2}V_{k-1}，第二个循环请注意V_i^T\cdots V_{k-m+1}^TV_{k-m}^T\rho_is_is_i^TV_i \cdots V_{k-2}V_{k-1}在其中的变化。

无论是最小化还是最大化，这个公式都是有效的。注意，如果我们最大化，搜索方向将是z的负数(因为z是“下坡”)，并且H_k^0应该是负定的，而不是正定的。对于最小化，Hessian矩阵逆H_k^0必须是正定的。因此，矩阵通常表示为对角线矩阵，另外还有一个好处，即最初设置z只需要逐个元素的乘法。

相关文章

网友评论

      本文标题：2019-04-08

      本文链接：https://www.haomeiwen.com/subject/nydpiqtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|2019-04-08|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！