首页 > 其他 > 详细

梯度下降以及牛顿法

时间:2014-06-12 15:19:32      阅读:498      评论:0      收藏:0      [点我收藏+]

回顾一些参数估计的方法,包括梯度下降算法和牛顿法及其扩展

梯度下降算法(Gradient Descent, GD)

目的是优化参数,使得估计值与真实值的误差最小。试用于优化目标形式为:

bubuko.com,布布扣

其中bubuko.com,布布扣表示特征权重,bubuko.com,布布扣表示样本的以bubuko.com,布布扣维特征描述,bubuko.com,布布扣为样本。

1, 批梯度下降算法(batch gradient decent, BGD)

样本集合损失函数为

 

bubuko.com,布布扣

其中bubuko.com,布布扣为样本个数,bubuko.com,布布扣为正确输出。分别对每维的参数bubuko.com,布布扣求导得

bubuko.com,布布扣

因此每次按照负梯度的方向更新参数

bubuko.com,布布扣

 

2, 随机梯度下降算法(stochastic gradient descent, SGD)

唯一不同于BGD,SGD每次迭代随机选取一个样本,更新参数。

对于单个样本j的损失函数为

bubuko.com,布布扣

由此可以看出,BGD中样本集合的损失函数为单个样本损失函数的和

SGD中,针对单个样本损失函数,对每维的参数求导得

bubuko.com,布布扣

更新参数为

bubuko.com,布布扣

每轮迭代的过程中,SGD比BGD计算量至少缩减了bubuko.com,布布扣倍,SGD的前提是保证了样本的随机性,同一个样本可能被选取多次。

 

L-BFGS 算法

1,牛顿法

首先将目标函数用Taylor公式在某点展开。Taylor展开式所表示的意义为:

已知函数某点的各个阶导数,可以拟合出函数在这个点周围的值,因此如果某点为极小值附近的点,则可以估算出函数的极小值。

用Taylor公式将函数bubuko.com,布布扣在某点展开,将此Taylor展开式求导估计可能的极小值

一维:

bubuko.com,布布扣

bubuko.com,布布扣

多维:

bubuko.com,布布扣

bubuko.com,布布扣

对于凸函数一定收敛;而对于非凸函数,是否收敛取决于初始选取的点是否为极小值周围的点。如果远离极小值点则不收敛。因此提出阻尼牛顿法,确定某点的搜索方向做一维搜索,找到当前极小值,然后再重新找搜索方向。

2,阻尼牛顿法

即在更新时先确定搜索方向

bubuko.com,布布扣

然后在此方向上找到可更新的极小值

bubuko.com,布布扣

牛顿法使用的限制条件为二阶导矩阵(Hesse)正定,因此复杂的目标函数很难保证Hesse矩阵可逆,因此导致牛顿法失效,因此提出拟牛顿法

 

3,拟牛顿法 (BFGS)

用方法近似计算Hesse矩阵,用bubuko.com,布布扣表示近似构造的Hesse矩阵。bubuko.com,布布扣为单位矩阵,然后同过DFP公式或者BFGS公式计算之后的Hesse矩阵 bubuko.com,布布扣

首先规定bubuko.com,布布扣bubuko.com,布布扣 

不加证明地给出DFP公式

bubuko.com,布布扣

BFGS公式为其DFP的对偶公式

bubuko.com,布布扣

在BFGS迭代过程中需要设置中断条件,因此具体算法过程为

a) 初始化 bubuko.com,布布扣,k=0,收敛依据e

b) 令为bubuko.com,布布扣单位矩阵

c) 计算一阶导数矩阵(梯度)bubuko.com,布布扣,确定优化方向bubuko.com,布布扣

d) 使用一维搜索极小值bubuko.com,布布扣

e) 判断是否收敛,否则继续6

f) 利用BFGS公式计算bubuko.com,布布扣,   k=k+1继续c

由于BFGS每次迭代过程都需要记录H(N*N)维矩阵,存储空间至少为N(N+1)/2。优化计算存储空间,则提出L-BFGS

 

4,限域拟牛顿法(Limited Storege BFGS,L-BFGS)

根据BFGS重写H矩阵的修正公式

bubuko.com,布布扣

其中bubuko.com,布布扣,则

BFGS中H的修正过程为

bubuko.com,布布扣

L-BFGS中H 的修正过程为(只记录最近的m次)

bubuko.com,布布扣

用于限制存储空间,用于BFGS每次迭代过程都需要记录H(N*N)维矩阵,存储空间至少为N(N+1)/2,用于H是由单位矩阵(存储空间为N)一步步修正得来一次,只需记录修正的过程。假设L-BFGS只记录修正前m步修正,则只需记录2m+1个N维向量。

梯度下降以及牛顿法,布布扣,bubuko.com

梯度下降以及牛顿法

原文:http://www.cnblogs.com/jmliunlp/p/3781841.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!