机器学习 学习笔记(4)牛顿法 拟牛顿法

牛顿法

考虑无约束最优化问题

其中

为目标函数的极小点。

假设f(x)有二阶连续偏导数,若第k次迭代值为

,则可将f(x)在

附近进行二阶泰勒展开:

这里

是f(x)的梯度向量在点

的值,

是f(x)的海塞矩阵:

在点

的值,函数f(x)有极值的必要条件是在极值点处一阶导数为0,即梯度向量为0.特别是当

是正定矩阵时,函数f(x)的极值为极小值。

牛顿法利用极小点的必要条件

,每次迭代从

开始,求目标函数的极小点,作为第k+1次迭代值

,具体地,假设

满足

,则有

(解释为:当x接近于xk时,

,则

,可以得出:

牛顿法步骤如下:

输入:目标函数f(x),梯度

,海塞矩阵H(x),精度要求

输出:f(x)的极小值点

(1)取初始点

,置k=0

(2)计算

(3)若

,则停止计算,得近似解

(4)计算

,并求

(5)置

(6)置k=k+1,转(2)

拟牛顿法

牛顿法计算海塞矩阵的逆矩阵开销太多,拟牛顿法用一个近似的矩阵代替海塞矩阵的逆矩阵。

满足条件

,则

,或

拟牛顿法将

作为

的近似

DFP(Davidon-Fletcher-Powell)算法:

DFP选择

的方法是,假设每一步迭代中矩阵

是由

加上两个附加项构成的,即

是待定矩阵,这时

,为了使得

满足拟牛顿条件,可以使得

满足条件:

,当

时,满足上述条件,则可以得到

。如果初始

是正定的,那么迭代过程中的每个矩阵

都是正定的。

DFP算法步骤如下:

输入:目标函数f(x),梯度

,精度要求

输出:f(x)的极小值点

(1)选定初始点

,取

为正定矩阵,置k=0

(2)计算

,若

,则停止计算,得近似解

,否则转(3)

(3)置

(4)一维搜索:求

使得

(5)置

(6)计算

,若

,则停止计算,的近似解

,否则,按照

计算

(7)置k=k+1,转(3)

BFGS(Broyden-Fletcher-Goldfarb-Shanno)算法

BFGS算法是最流行的拟牛顿算法,可以考虑用

逼近海塞矩阵的逆矩阵

,也可以考虑用

逼近海塞矩阵H。这时候,相应的拟牛顿条件是

,则迭代公式

,则

满足

,最终得到

的迭代公式

BFGS算法步骤为:

输入:目标函数f(x),梯度

,精度要求

输出:f(x)的极小值点

(1)选定初始点

,取

为正定矩阵,置k=0

(2)计算

,若

,则停止计算,得近似解

,否则转(3)

(3)由

,求出

(4)一维搜索,求

使得

(5)置

(6)计算

,若

,则停止计算,的近似解

,否则,按照

计算

(7)置k=k+1,转(3)

关于牛顿法和梯度下降法的效率对比:

  从本质上去看,牛顿法是二阶收敛,梯度下降是一阶收敛,所以牛顿法就更快。如果更通俗地说的话,比如你想找一条最短的路径走到一个盆地的最底部,梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步,牛顿法在选择方向时,不仅会考虑坡度是否够大,还会考虑你走了一步之后,坡度是否会变得更大。所以,可以说牛顿法比梯度下降法看得更远一点,能更快地走到最底部。(牛顿法目光更加长远,所以少走弯路;相对而言,梯度下降法只考虑了局部的最优,没有全局思想。)

  根据wiki上的解释,从几何上说,牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面,而梯度下降法是用一个平面去拟合当前的局部曲面,通常情况下,二次曲面的拟合会比平面更好,所以牛顿法选择的下降路径会更符合真实的最优下降路径。

参考:

  1. 《机器学习》
  2. 《统计学习方法》
  3. 常见的几种最优化方法(梯度下降法、牛顿法、拟牛顿法、共轭梯度法等)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉战队

稀疏&集成的卷积神经网络学习

今天主要和大家说的是分类检测过程中,一些稀疏和集成学习的相关知识,首先和大家说下图像目标定位与检测的方法分类。 众所周知,当前是信息时代,信息的获得、加工、处理...

39450
来自专栏SIGAI学习与实践平台

【技术短文】基于深度负相关学习的人群计数方法

原创声明:本文为 SIGAI 原创文章,仅供个人学习使用,未经允许,不得转载,不能用于商业目的。

20360
来自专栏机器学习算法工程师

《机器学习》笔记-贝叶斯分类器(7)

作者:刘才权 编辑:陈人和 前 言 如今机器学习和深度学习如此火热,相信很多像我一样的普通程序猿或者还在大学校园中的同学,一定也想参与其中。不管是出于好奇,还...

40460
来自专栏用户2442861的专栏

支持向量机学习笔记:数学过程及经典Tutorial

http://blog.csdn.net/linj_m/article/details/18322149   ( SVM系列 )

11310
来自专栏UAI人工智能

OpenAI 首个研究成果 生成式模型系列

17440
来自专栏企鹅号快讯

如何利用深度学习识别千万张图片?

首先我们来谈一下什么是卷积神经网络,相信在深度学习中这是最重要的概念,首先你可以把卷积想象成一种混合信息的手段。想象一下装满信息的两个桶,我们把它们倒入一个桶中...

26950
来自专栏机器学习算法与理论

【一文读懂】机器学习

      看到很多人都有写博客的习惯,现在开始实习了,也把之前写过的东西整理整理,发在这里,有兴趣的同学可以一起交流交流。文笔稚嫩,希望大家宽容以待!   ...

36260
来自专栏计算机视觉战队

CVPR 2018 论文简单笔记(部分,待更新)

计算机视觉最具影响力的学术会议之一的 CVPR 将于 2018 年 6 月 18 日 - 22 日在美国盐湖城召开举行。据 CVPR 官网显示,今年大会有超过 ...

19420
来自专栏人工智能

机器学习基础之模型评估(四)

标题: 损失函数与风险 正则化 这次,我们来介绍一下机器学习模型中常用到的一种对付模型过拟合问题的方法,也是许多模型常用的优化模型的一个方法:正则化。 正则化是...

21280
来自专栏前沿技墅

猫工智能:卷积神经网络层的实现

23850

扫码关注云+社区

领取腾讯云代金券