Batch Gradient Descendent (BGD) Stochastic Gradient Descendent (SGD)

SGD, BGD初步描述（原文来自：http://blog.csdn.net/lilyth_lilyth/article/details/8973972，@熊均达@SJTU 做出解释及说明） 

 

梯度下降（GD）是最小化风险函数、损失函数（注意Risk Function和Cost Function在本文中其实指的一个意思，在不同应用领域里面可能叫法会有所不同。解释：@熊均达@SJTU）的一种常用方法，随机梯度下降和批量梯度下降是两种迭代求解思路，下面从公式和实现的角度对两者进行分析，如有哪个方面写的不对，希望网友纠正。

 

下面的h(x)是要拟合的函数，J(θ)损失函数，θ是参数，要迭代求解的值，theta求解出来了那最终要拟合的函数h(θ)就出来了。其中m是训练集的记录条数，j是参数的个数。

 

1、批量梯度下降(BGD)的求解思路如下：

（1）将J(θ)对θ求偏导，得到每个θ对应的的梯度

   

（2）由于是要最小化风险函数（注意这里用了风险函数，其实就是损失函数。解释：@熊均达@SJTU），所以按每个参数θ的梯度负方向，来更新每个θ

（3）从上面公式可以注意到，它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果m很大，那么可想而知这种方法的迭代速度！！所以，这就引入了另外一种方法，随机梯度下降。

 

2、随机梯度下降(SGD)的求解思路如下：

（1）上面的风险函数可以写成如下这种形式，损失函数对应的是训练集中每个样本的粒度（粒度相当于在每个样本点上的损失，因为SGD实际上对相应的Cost Function的偏导做了改动。解释：@熊均达@SJTU），而上面批量梯度下降对应的是所有的训练样本：

（2）每个样本的损失函数，对θ求偏导得到对应梯度，来更新θ

（3）随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况（例如几十万），那么可能只用其中几万条或者几千条的样本，就已经将θ迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。

@熊均达@SJTU附注1：在BGD中，你需要把所有的样本都考虑，求所有样本处的误差的平方和。而对于SGD,遍历到哪里就是哪里。

@熊均达@SJTU附注2：我现在倾向于在SGD不考虑什么是cost function，只考虑对θ的更新方法做改动。cost function应该在BGD中才存在，因为这个定义是严谨的，所谓cost function就是在所有样本点处的误差的平方和。

 

SGD BGD的深入比较描述（By: @熊均达@SJTU）

随机梯度下降和批量梯度下降不同点在于，批量梯度下降每一步更新θ值，都需要遍历全部的训练样本，而随机梯度下降在遇到每个训练样本时，更新θ之后继续处理下一个样本，每个样本只遍历一次，算法的学习时间比批量梯度下降快很多。但是，随机梯度下降可能永远不会收敛到全局最优值，而是在成本函数J(θ)最优值周围附近摇摆。但是在实际问题中，接近最优值的参数值可能已经是足够好的结果了，特别是对于数据量非常大的训练集来说，随机梯度下降是比批量梯度下降更好的选择。

在实际使用梯度下降算法时，将输入变量归一到同一取值范围，能够减少算法的迭代次数。这是因为在小的取值范围内会下降很快，但在大的取值范围内会下降较慢。并且当输入变量取值范围不够均衡时，更容易在最优值周围波动。采用特征缩放(feature scaling)和均值归一化(mean normalization)可以避免这些问题。选择学习率的值，要观察J(θ)值在每次迭代后的变化。已经证明了如果的取值足够小，则J(θ)每次迭代后的值都会减少。如果J(θ)在某次迭代后反而增加了，说明学习率的值应该减小，因为错过了最优值。Andrew Ng推荐的一个经验是每次将减少3倍。

 

批量梯度下降和随机梯度下降对比：

批量梯度下降	随机梯度下降
批量更新算法	在线算法
经验风险	泛化风险
可能陷入局部最优（初值选择敏感）	可能找到全局最优
对步长不敏感	对步长敏感
迭代次数少	迭代次数多
计算量大	计算量不大

 

对于线性回归问题，批量梯度下降和随机梯度下降是如何找到最优解的？

1. 批量梯度下降——最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小。
2. 随机梯度下降——最小化每条样本的成本函数，虽然不是每次迭代得到的成本函数都向着全局最优的方向，但是整体的方向还是向着全局最优解，最终结果往往是在全局最优解附近。具体证明参照【1】

 

全局最优问题和局部最优问题：

最优化问题对的分布是unimodal，即从图形上面看只有一个peak，所以梯度下降最终求得的是全局最优解。然而对于multimodal的问题，因为存在多个peak值，很有可能梯度下降的最终结果是局部最优。对于多个peak的问题，由于随机梯度下降每次更新方向的不确定性，所以SGD有可能使得从局部最优中跳出来而找到全局最优，相反的，这也可能使得SGD从全局最优跳到局部最优，但是对于一般的工程性凸问题，随机梯度下降都呈现了较好的运算复杂度（大概为）和收敛性。

 

最后附上带有大量干货的斯坦福CS229课程主页网址：http://cs229.stanford.edu/materials.html

有兴趣的同学可以自行查阅，其实网上大部分的资料都是根据这些资料翻译的，但是这些更权威。

 

 

参考资料：

1. https://hal.archives-ouvertes.fr/file/index/docid/359142/filename/ASCONVEXSET.BASIC.IJPAM.1.pdf
2. http://blog.csdn.net/lilyth_lilyth/article/details/8973972