没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
理解牛顿法
作者:SIGAI
2018.5.31
原创声明:本文为 SIGAI 原创文章,仅供个人学习使用,未经允许,不能用于
商业目的。
导言
牛顿法是数值优化算法中的大家族,她和她的改进型在很多实际问题中得到了应用。在
机器学习中,牛顿法是和梯度下降法地位相当的的主要优化算法。在本文中,SIGAI 将为大
家深入浅出的系统讲述牛顿法的原理与应用。
牛顿法的起源
牛顿法以伟大的英国科学家牛顿命名,牛顿不仅是伟大的物理学家,是近代物理的奠基
人,还是伟大的数学家,他和德国数学家莱布尼兹并列发明了微积分,这是数学历史上最有
划时代意义的成果之一,奠定了近代和现代数学的基石。在数学中,也有很多以牛顿命名的
公式和定理,牛顿法就是其中之一。
牛顿法不仅可以用来求解函数的极值问题,还可以用来求解方程的根,二者在本质上是
一个问题,因为求解函数极值的思路是寻找导数为 0 的点,这就是求解方程。在本文中,我
们介绍的是求解函数极值的牛顿法。
在 SIGAI 之前关于最优方法的系列文章“理解梯度下降法”,“理解凸优化”中,我们
介绍了最优化的基本概念和原理,以及迭代法的思想,如果对这些概念还不清楚,请先阅读
这两篇文章。和梯度下降法一样,牛顿法也是寻找导数为 0 的点,同样是一种迭代法。核心
思想是在某点处用二次函数来近似目标函数,得到导数为 0 的方程,求解该方程,得到下一
个迭代点。因为是用二次函数近似,因此可能会有误差,需要反复这样迭代,直到到达导数
为 0 的点处。下面我们开始具体的推导,先考虑一元函数的情况,然后推广到多元函数。
一元函数的情况
为了能让大家更好的理解推导过程的原理,首先考虑一元函数的情况。根据一元函数的
泰勒展开公式,我们对目标函数在 x0 点处做泰勒展开,有:
( ) ( ) ( )( ) ( )( )
( )
( )( )
2
' ''
0 0 0 0 0 0 0
11
... ...
2!
n
n
f x f x f x x x f x x x f x x x
n
= + − + − + + −
如果忽略 2 次以上的项,则有:
( ) ( ) ( )( ) ( )( )
2
' ''
0 0 0 0 0
1
2
f x f x f x x x f x x x= + − + −
现在我们在 x0 点处,要以它为基础,找到导数为 0 的点,即导数为 0。对上面等式两
边同时求导,并令导数为 0,可以得到下面的方程:
( ) ( ) ( )( )
' ' ''
0 0 0
0f x f x f x x x= + − =
可以解得:
( )
( )
'
0
0
''
0
fx
xx
fx
=−
这样我们就得到了下一点的位置,从而走到 x1。接下来重复这个过程,直到到达导数
为 0 的点,由此得到牛顿法的迭代公式:
( )
( )
'
1
''
t
tt
t
fx
xx
fx
+
=−
给定初始迭代点 x0,反复用上面的公式进行迭代,直到达到导数为 0 的点或者达到最
大迭代次数。
多元函数的情况
下面推广到多元函数的情况,如果读者对梯度,Hessian 的概念还不清楚,请先去看微
积分教材,或者阅读 SIGAI 之前关于最优化的公众号文章。根据多元函数的泰勒展开公式,
我们对目标函数在 x0 点处做泰勒展开,有:
( ) ( ) ( ) ( ) ( ) ( )( ) ( )
( )
T T 2
2
0 0 0 0 0 0 0
1
x x x x x x x x x x x x
2
f f f f
= + − + − − + −
忽略二次及以上的项,并对上式两边同时求梯度,得到函数的导数(梯度向量)为:
( ) ( ) ( )( )
2
0 0 0
x x x x xff = + −
其中
( )
2
0
xf
即为 Hessian 矩阵,在后面我们写成 H。令函数的梯度为 0,则有:
( ) ( )( ) ( )
( )
( )
1
22
0 0 0 0 0 0
x x x x 0 x x x xf f f f
−
+ − = = −
这是一个线性方程组的解。如果将梯度向量简写为 g,上面的公式可以简写为:
1
0
x x H g
−
=−
从初始点 x0 处开始,反复计算函数在处的 Hessian 矩阵和梯度向量,然后用下述公式
进行迭代:
1
1
x x H g
k k k k
−
+
=−
最终会到达函数的驻点处。其中
1
Hg
−
−
称为牛顿方向。迭代终止的条件是梯度的模接
近于 0,或者函数值下降小于指定阈值。
实现细节
根据上面的推导,我们可以得到牛顿法的完整流程为:
1.给定初始值
0
x
和精度阈值
,设置 k = 0
2.计算梯度
g
k
和矩阵
H
k
3.如果
g
k
即在此点处梯度的值接近于 0,则达到极值点处,停止迭代
4.计算搜索方向
1
d H g
k k k
−
=−
5.计算新的迭代点
1
x x d
k k k
+
=+
剩余14页未读,继续阅读
资源评论
SIGAI_csdn
- 粉丝: 2349
- 资源: 45
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功