随机平均梯度法(Stochasitc Average Gradient)和随机梯度下降(SGD)有什么区别

  数学 数值计算 最优化    浏览次数:13106        分享
16

我看到很多封装好的ML算法里都在用这个随机平均梯度法(Stochasitc Average Gradient),但是网上对于这个算法的资料非常非常少。可能是因为这个算法太新了。

有人具体了解过这个算法吗?这个和普通的随机梯度下降有什么改进之处?

 

MrMath   2017-03-27 11:15



   3个回答 
24

是的,这个算法的确很新,论文是两年前的。Minimizing Finite Sums with the Stochastic Average Gradient,2015.1.19。

可以看论文第3页的公式(5)和(6)。我截图贴下面。

我们知道sgd是当前权重减去步长乘以梯度,得到新的权重。sag中的a,就是平均的意思,具体说,就是在第k步迭代的时候,我考虑的这一步和前面n-1个梯度的平均值,当前权重减去步长乘以最近n个梯度的平均值。n是自己设置的,当n=1的时候,就是普通的sgd。


这个想法非常的简单,在随机中又增加了确定性,类似于mini-batch sgd的作用,但不同的是,sag又没有去计算更多的样本,只是利用了之前计算出来的梯度,所以每次迭代的计算成本远小于mini-batch sgd,和sgd相当。效果而言,sag相对于sgd,收敛速度快了很多。这一点上面的论文中有具体的描述和证明。




SofaSofa数据科学社区DS面试题库 DS面经

清风   2017-05-27 11:32

你好,我最近在看python,觉得你比较厉害,能否留个联系方式发到我的邮箱cp20133808@163.com - 陈十一   2017-09-05 14:50
经常在一些package里看到sag,现在看了你的解释终于搞懂了! - NextPage   2017-09-13 13:53
学习了 - wlk1993   2017-11-18 09:43
7

其实SAG就是SGD with momentum(带动量的随机梯度下降)的姊妹版本。

SAG是对过去k次的梯度求均值。

SGD with momentum是对过去所有的梯度求加权平均(权重成指数衰减)。


SofaSofa数据科学社区DS面试题库 DS面经

染盘   2017-11-17 13:35

4

随机梯度下降被发明出来的原因是因为它的下降速度快,可以减少迭代的次数,但是不容易收敛是它的缺点。

在有些特定的情况下呢,需要更多的迭代(更多的计算复杂度)才能达到收敛条件,反而可能不如正常的梯度下降来得好。

为了避免这个情况呢,随机平均梯度法就诞生啦,保证了随机梯度下降原汁原味的优点(下降快),同时又利用平均的特性,让梯度下降能更快达到收敛条件,减少迭代次数。

综上,这个方法呢,以后估计还会改进吧,毕竟平均这个特性太“low”了,不过思想倒是可取的,跟马尔科夫链有点异曲同工,说不定下一个算法就是“马尔科夫链随机梯度下降”呢。


SofaSofa数据科学社区DS面试题库 DS面经

天晴   2017-12-26 17:55

“跟马尔科夫链有点异曲同工”这个想法不错 哈哈 - dzzxjl   2018-03-07 20:31


  相关讨论

对于小批量随机剃度下降法(mini-batch SGD),如何选择每批样本的数量?

Adam优化算法

学习率不当会导致sgd不收敛吗?

nesterov’s momentum和momentum的区别?

最速下降法与梯度下降法

为什么梯度的反方向是函数下降最快的方向?

随机梯度下降(sgd)的收敛问题

牛顿法到底是一阶优化算法还是二阶优化算法?

Newton–Raphson和牛顿法区别?

RMSProp的直白解释

  随便看看

matplotlib.pyplot做折线图的时候,显示为虚线,或者点划线?

pandas.DataFrame里的loc和iloc什么区别?

逻辑回归的损失函数是怎么来的

行数很多的pandas DataFrame如何在jupyter中完整显示?

条件概率证明P(a,b|c) > P(a,b)