梯度下降法,牛顿法,拟牛顿法

最优化是一种数学方法,它是研究在给定约束之下如何寻求某些因素,以使某一些指标达到最优的一些学科的总称.在机器学习中,大部分的机器学习算法的本质都是建立优化模型,通过最优化方法对目标函数(损失函数)进行优化,从而训练出最好的模型.梯度下降法,牛顿法和拟牛顿法是求解无约束最优化问题的常用方法.

梯度下降法

梯度下降法实现简单,当目标函数为凸函数时,梯度下降法的解是全局最优解.

梯度

梯度的定义: 函数在某一点的梯度是这样一个向量,它的方向与取得最大方向导数的方向一致(即函数沿梯度方向有最大的变化率),而它的摸为方向导数的最大值.
1.梯度是一个向量
2.梯度的方向是最大方向导数的方向
3.梯度的值是最大方向导数的值

梯度下降法

梯度下降法的优化思想: 用当前位置负梯度方向作为搜索方向,因为该方向为当前位置的最快下降方向.梯度下降法越接近目标值步长越小,前进越慢.
梯度下降法过程如下:

缺点:
梯度下降法越靠近极小值,下降变慢;对于学习率(步长的选择不当)可能会造成’之’字形下降.

牛顿法

方程的根

牛顿法最经典的应用就是来求解方程根的问题,因为并不是所有的方程都有求根公式,或者比较复杂求解起来比较困难.
首先利用泰勒公式,在$x_0$出一阶展开:

那么我们要求解$f(x) = 0$等价于:

进而有:

注意这里因为是使用泰勒公式一阶展开,所以$f(x) = f(x_0) + f’(x_0)(x-x_0)$并不是完全相等,而是近似相等,所以这里我们求得的$x$并不一定能使得$f(x) = 0$只是相比于$f(x_0)$的值更接近0.
所以我们可以得到迭代求解法:

已经证明,如果$f’$是连续的,并且待求的零点x孤立,那么在零点x周围存在一个区域,只要初始值$x_0$在这个区域内,那么牛顿法必定收敛.
过程如下:

最优化

在最优化问题中,目标函数$f(x)$存在极值的条件是极值点处一阶导数为0,即$f’(x_0) = 0$.这时候就发现其实还是用到上面说到的那种方法.
我们可以将$f’(x)$使用泰勒公式进行一阶展开,得到:

同样的令$f’(x) = 0$,那么有迭代公式:

一般认为牛顿法可以利用曲线本身的信息,比梯度下降法更容易收敛.(因为还考虑了二阶导数的信息),如下图是一个最小化一个目标方程的例子, 红色曲线是利用牛顿法迭代求解, 绿色曲线是利用梯度下降法求解.

牛顿法一般公式

上面我们讨论的都是2维的情况,高维情况的牛顿法迭代公式为:

其中$H$是hessian矩阵,$\nabla f({x_n})$是$f(x)$的梯度向量在$x_n$处的值.
$f(x)$有极值的必要条件: 它的一阶导在极值点处取值为0,若是极小值点,则要求Hessian矩阵为正定矩阵.

hessian矩阵和# Jacobian矩阵

jacobian矩阵

jacobian矩阵是一阶偏导数以一定方式排列成的矩阵,其行列式成为jacabian行列式,jacabian类似于多元函数的导数.

Hessian矩阵

在数学中,hessian矩阵是一个自变量为向量的实值函数的二阶偏导数组成的方块矩阵,此函数如下:

如果所有的二阶导数都存在,那么$f$的Hessian矩阵为$H(f)$:

牛顿法优缺点

从本质上看牛顿法是二阶收敛(最优化时,),而梯度下降法是一阶收敛.如果通俗的说就是,梯度下降法每次从你当前所处的位置选一个坡度最大的方向走一步,牛顿法在选择方向时不仅会考虑坡度是否够大,还会考虑你走了一步之后坡度是否会变得更大.所以,可以说牛顿法比梯度下降法看得更远一点,能更快地走到最底部。(牛顿法目光更加长远,所以少走弯路;相对而言,梯度下降法只考虑了局部的最优,没有全局思想。)
缺点: 可以上面每一次迭代都需要求解Hessian矩阵及其逆矩阵,计算复杂.
这就引出了拟牛顿法

拟牛顿法

在牛顿法的迭代中,需要计算Hessian矩阵及其逆矩阵,计算过程比较复杂,考虑使用一个n阶矩阵$G_k = G(x_k)$来代替Hessian矩阵$H_k^{-1} = H^{-1}(x_k)$,这是牛顿法的基本思想.
那么满足什么条件的$G_k$才能用来代替$H_k^{-1}$呢?我们先来看一下$H_k$满足的条件,又叫拟牛顿条件.

拟牛顿条件

从而有:

记:
$y_k = g_{k + 1} - g_k= \nabla f(x_{k + 1}) -\nabla f(x_k)$;
$\delta_k = x_{k + 1} - x_k$
此外如果$H_k$是正定的($H^{-1}_k$也是正定的),那么可以保证牛顿法搜索方向
$-H^{-1}_k \nabla f(x_k)$是下降方向,所以$G_k$要扮演$H^{-1}_k$的角色,应当满足同样的条件,即:
1)替代矩阵$G_k$正定,只有正定才能保证牛顿法的搜索方向是向下搜索的.
2)替代矩阵$G_k$满足拟牛顿条件,$G_k(\nabla f(x_{k + 1}) - \nabla f(x_k)) = x_{k + 1} - x_k$
显然$G_K$的选择并不是唯一的,因为每次迭代都需要更新替代矩阵$G_k$,$G_{k + 1} = G_k + \Delta G_k$
这里对DFP算法和DFGS算法做简单的介绍.

DFP算法

DFP算法选择$G_{k + 1}$的方法是: 假设每一步迭代中矩阵$G_{k + 1}$是由$G_k$ 加上两个附加项构成的,即$G_{k + 1} = G_k + P_k + Q_k$
其中$P_k,Q_k$是待定矩阵.此时有: $G_{k+ 1}y_k = G_ky_k + P_ky_k + Q_ky_k$
为使$G_{k + 1}$满足拟牛顿条件,那么可使$P_K,Q_k$满足:

事实上,不难找出满足条件的$P_k,Q_k$,例如取:

称为DEP算法。可以证明,如果初始矩阵 $G_0$ 是正定的,则迭代过程中每个矩阵 $G_k$都是正定的。

BFPS算法

DFP算法考虑用$G_k$逼近Hessian矩阵的逆$H^{-1}$,而BFPS算法考虑用$B_k$去逼近Hessian矩阵$H_k$.此时对应的拟牛顿条件为:

可以证明,如果初始矩阵$B_0$是正定的,则迭代过程中每个矩阵$B_k$都是正定的.


-------------本文结束感谢您的阅读-------------


本文标题:梯度下降法,牛顿法,拟牛顿法

文章作者:Statusrank

CSDN博客欢迎来访!

发布时间:2019年01月16日 - 16:01

最后更新:2019年01月16日 - 18:01

原始链接:https://statusrank.xyz/articles/667ed989.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

万水千山总是情,就给五毛行不行!

相关文章: