更多深度文章，请关注：https://yq.aliyun.com/cloud
hackerearth，一家来自印度的创业公司，旨在帮助开发者通过线上编程竞赛获得工作机会。和github类似，它提供一个多种编程语言的代码交流平台。而hackerearth blog 上多刊登一些跟大数据、人工智能、机器学习、算法及编程竞赛相关的博文。
梯度下降法 (gradient descent algorithm，gd) 是为目标函数j(θ)，如代价函数(cost function), 求解全局最小值（global minimum）的一种迭代算法。本文会详细讨论按照准确性和耗费时间（accuracy and time consuming factor）将梯度下降法进行分类。这个算法在机器学习中被广泛用来最小化目标函数，如下图所示。
α表示学习速率（learning
rate）。
在本文中，考虑使用<b>线性回归</b>（linear
regression）作为算法实例，当然梯度下降法也可以应用到其他算法，如逻辑斯蒂回归（logistic
regression）和
神经网络（neural
networks）。在线性回归中，我们使用如下拟合函数（hypothesis
function）:
其中，
是参数，
<b>代价函数</b>(普通的最小平方差，ordinary
least square error)如下所示：
代价函数的梯度（gradient of cost function）：
参数与代价函数关系如下图所示：
下面的伪代码能够解释其详细原理：
1. 初始化参数值
2. 迭代更新这些参数使目标函数j(θ)不断变小。
基于如何使用数据计算代价函数的导数，梯度下降法可以被定义为不同的形式（various
variants）。确切地说，根据<b>使用数据量的大小</b>（the amount of data），<b>时间复杂度</b>（time complexity）和<b>算法的准确率</b>（accuracy of the algorithm），梯度下降法可分为：
1.
gradient descent, bgd）；
2.
<b>随机梯度下降法</b>（stochastic gradient descent, sgd）；
3.
<b>小批量梯度下降法</b>（mini-batch gradient descent, mbgd）。
这是梯度下降法的基本类型，这种方法<b>使用整个数据集（</b>the complete dataset<b>）去计算代价函数的梯度</b>。每次使用全部数据计算梯度去更新参数，<b>批量梯度下降法会很慢</b>，并且很难处理不能载入内存（don’t
fit in memory）的数据集。在随机初始化参数后，按如下方式计算代价函数的梯度：
其中，m是训练样本（training
examples）的数量。
note:
1. 如果训练集有3亿条数据，你需要从硬盘读取全部数据到内存中；
2. 每次一次计算完求和后，就进行参数更新；
3. 然后重复上面每一步；
4. 这意味着<b>需要较长的时间才能收敛</b>；
5. 特别是因为磁盘输入/输出（disk
i/o）是系统典型瓶颈，所以这种方法会不可避免地需要大量的读取。
上图是每次迭代后的等高线图，每个不同颜色的线表示代价函数不同的值。运用梯度下降会快速收敛到圆心，即唯一的一个全局最小值。
<b>批量梯度下降法不适合大数据集</b>。下面的python代码实现了批量梯度下降法：
批量梯度下降法被证明是一个较慢的算法，所以，我们可以选择随机梯度下降法达到更快的计算。随机梯度下降法的第一步是随机化整个数据集。在每次迭代仅选择一个训练样本去计算代价函数的梯度，然后更新参数。即使是大规模数据集，随机梯度下降法也会很快收敛。<b>随机梯度下降法得到结果的准确性可能不会是最好的，但是计算结果的速度很快</b>。在随机化初始参数之后，使用如下方法计算代价函数的梯度：
这里m表示训练样本的数量。
如下为随机梯度下降法的伪码：
1. 进入内循环（inner loop）;
2. 第一步：挑选第一个训练样本并更新参数，然后使用第二个实例；
3. 第二步：选第二个训练样本，继续更新参数；
4. 然后进行第三步…直到第n步；
5. 直到达到全局最小值
如下图所示，随机梯度下降法不像批量梯度下降法那样收敛，而是<b>游走到接近全局最小值的区域终止</b>。
小批量梯度下降法是最广泛使用的一种算法，该算法每次使用m个训练样本（称之为一批）进行训练，能够更快得出准确的答案。<b>小批量梯度下降法不是使用完整数据集，在每次迭代中仅使用</b><b>m</b><b>个训练样本去计算代价函数的梯度</b>。一般小批量梯度下降法所选取的样本数量在50到256个之间，视具体应用而定。
1.这种方法减少了参数更新时的变化，能够更加稳定地收敛。
2.同时，也能利用高度优化的矩阵，进行高效的梯度计算。
随机初始化参数后，按如下伪码计算代价函数的梯度：
这里b表示一批训练样本的个数，m是训练样本的总数。
<b>notes:</b>
1. 实现该算法时，<b>同时更新参数</b>。
3. 检查梯度下降法的工作过程。画出迭代次数与每次迭代后代价函数值的关系图，这能够帮助你了解梯度下降法是否取得了好的效果。每次迭代后j(θ)应该降低，多次迭代后应该趋于收敛。
4. 不同的学习速率在梯度下降法中的效果
以上为译文
文章原标题《3 types of gradient descent
algorithms for small & large data sets》，由hackerearth blog发布。
译者：李烽 ；审校：段志成-海棠