LionKing数据科学专栏

购买普通会员高级会员可以解锁网站精华内容且享受VIP服务的优惠

想要查看更多数据科学相关的内容请关注我们的微信公众号知乎专栏

随机梯度下降法(stochastic gradient descent)

随机梯度下降法

对于一个机器学习问题,最终往往会化为一个损失函数的最优化问题,形式为

$$\min_{\beta}L(\beta) = \sum_{i=1}^{n}L_i(\beta)$$

其中$L_i$是第$i$个样本对应的损失。

批量梯度下降法(batch gradient descent)的做法是把$L$当作一个整体,每次计算$$\nabla L(\beta) = \sum_{i=1}^{n}\nabla L_i(\beta)$$

并进行更新$$\beta \leftarrow \beta - \alpha \nabla L(\beta)$$

这个做法在学习速率$\alpha$适当的前提下可以保证收敛到局部极小值。缺点在于梯度的计算用到了$\nabla L_i(\beta)$中的每一项。如果$n$非常大,那么运算效率非常低。

在实际应用中的$n$往往非常大,因而我们希望在允许牺牲一部分收敛性能下,得到一个效率更高的算法。

随机梯度下降法是这样的一个方法,其思路是每次选取一个$L_i$并且以$\nabla L_i(\beta)$作为对$\nabla L(\beta)$的一个估计,从而无需计算所有的$\nabla L_j(\beta), j = 1, \ldots, n$。

$n\nabla L_i(\beta)$是对于$\nabla L(\beta)$的一个无偏估计(unbiased estimator)。

算法

随机梯度下降法的算法如下

一般来说$i$的选取方法是预先将数据打乱,然后滚动地选取$1, 2, \ldots, n, 1, 2, \ldots$。如果数据是在线数据(online data),即一直会有新的数据进入,则每次使用新进入的数据作为$i$即可。

随机梯度下降法的优缺点

相对于批量梯度下降法,随机梯度下降法每一步的迭代速度较快,对空间也比较节约。从准确度角度来说,随机梯度下降每次只有一个样本计算梯度,得到的学习曲线会急剧震荡,收敛速度较慢。

小批量梯度下降法可以结合两者的优点。

小批量梯度下降法

为了解决随机梯度下降过于不稳定的问题和批量梯度下降运算过慢的问题,可以使用小批量(Mini-batch)梯度下降法。

小批量梯度下降法的思路是每次选取全部$n$个样本的$k$个子样本(如$k = 10$),计算它们的梯度之和,并且更新参数。

算法如下:

大多数机器学习算法使用小批量梯度下降法求解优化问题。

线性回归实例

我们比较批量梯度下降法、随机梯度下降法、小批量梯度下降法在线性回归问题上的学习曲线。

可以看到随机梯度下降和小批量梯度下降的每一次迭代后的损失都非常接近批量梯度下降法。其中小批量梯度下降法相对更加稳定。

注意每一步迭代中,随机梯度下降需要的计算量略小于小批量梯度下降;而小批量梯度下降远快于批量梯度下降法。

更多最优化相关问题见本网站论坛最优化版面

更多面试问题见面试真题汇总

想要查看更多数据科学相关的内容请关注我们的微信公众号知乎专栏