批量算法

科技工作者之家  |   2020-11-17 18:14

机器学习算法和一般优化算法不同的一点是,机器学习算法的目标函数通常可以分解为训练样本上的求和。使用整个训练集的优化算法被称为批量(batch)或确定性(deterministic)算法,因为它们会在一个大批量中同时处理所有样本。这个术语可能有点令人困惑,因为这个词“批量”也经常被用来描述小批量随机梯度下降算法中用到的小批量样本。通常,术语 “批量梯度下降”指使用全部训练集,而术语“批量”单独出现时指一组样本。例如,我们普遍使用术语“批量大小”表示小批量的大小。

简介每次只使用单个样本的优化算法有时被称为随机(stochastic)或者在线(online)算法。术语“在线”通常是指从连续产生样本的数据流中抽取样本的情况,而不是从一个固定大小的训练集中遍历多次采样的情况。批量算法是指深度学习训练中,使用一个以上,而又不是全部的训练样本的优化算法,或指使用所有训练集的优化算法。在实际应用中,批量算法一般多指小批量算法,即使用部分训练样本的优化算法传统上,这些会被称为小批量(mini-batch)或小批量随机(mini-batch stochastic)方法,通常将它们简单地称为随机(stochastic)方法。

影响因素批量的大小通常由以下几个因素决定:

更大的批量会计算更精确的梯度估计,但是回报却是小于线性的。

极小批量通常难以充分利用多核架构。这促使我们使用一些绝对最小批量,低于这个值的小批量处理不会减少计算时间。

如果批量处理中的所有样本可以并行地处理(通常确是如此),那么内存消耗和批量大小会正比。对于很多硬件设施,这是批量大小的限制因素。

在某些硬件上使用特定大小的数组时,运行时间会更少。尤其是在使用GPU时,通常使用2的幂数作为批量大小可以获得更少的运行时间。一般,2的幂数的取值范围是32到256,16有时在尝试大模型时使用。

可能是由于小批量在学习过程中加入了噪声,它们会有一些正则化效果。泛化误差通常在批量大小为1时最好。因为梯度估计的高方差,小批量训练需要较小的学习率以保持稳定性。因为降低的学习率和消耗更多步骤来遍历整个训练集都会产生更多的步骤,所以会导致总的运行时间非常大。

不同的算法使用不同的方法从小批量中获取不同的信息。有些算法对采样误差比其他算法更敏感,这通常有两个可能原因。一个是它们使用了很难在少量样本上精确估计的信息,另一个是它们以放大采样误差的方式使用了信息。

小批量的优点小批量是随机抽取的这点也很重要。从一组样本中计算出梯度期望的无偏估计要求这些样本是独立的。我们也希望两个连续的梯度估计是互相独立的,因此两个连续的小批量样本也应该是彼此独立的。很多现实的数据集自然排列,从而使得连续的样本之间具有高度相关性。例如,假设我们有一个很长的血液样本测试结果清单。清单上的数据有可能是这样获取的,头五个血液样本于不同时间段取自第一个病人,接下来三个血液样本取自第二个病人,再随后的血液样本取自第三个病人,等等。如果我们从这个清单上顺序抽取样本,那么我们的每个小批量数据的偏差都很大,因为这个小批量很可能只代表着数据集上众多患者中的某一个患者。在这种数据集中的顺序有很大影响的情况下,很有必要在抽取小批量样本前打乱样本顺序。对于非常大的数据集,如数据中心含有几十亿样本的数据集,我们每次构建小批量样本时都将样本完全均匀地抽取出来是不太现实的。幸运的是,实践中通常将样本顺序打乱一次,然后按照这个顺序存储起来就足够了。之后训练模型时会用到的一组组小批量连续样本是固定的,每个独立的模型每次遍历训练数据时都会重复使用这个顺序。然而,这种偏离真实随机采样的方法并没有很严重的有害影响。不以某种方式打乱样本顺序才会极大地降低算法的性能。

批量梯度下降无约束优化问题是最优化理论的基础,通常采用迭代法求它的最优解。 经典的数值优化算法如梯度下降法(gradient descent method),牛顿法(Newton method)等都可求得其最优解。 梯度下降法早在 1847 年由大数学家 Cauchy 最先使用。它是最古老的一种解析方法,而其他解析方法大多承其衣钵,并构成最优化方法的基础。梯度下降法具有储存量小、结构简单、易于实现的优点。梯度下降法常作为机器学习领域内训练算法的核心算法,用来递归性地逼近最小偏差模型,如人工神经网络与 Logistic regression,广泛应用于数据挖掘、模式识别等领域。梯度下降法以负梯度方向作为极小化算法的下降方向,是无约束优化中最简单的方法。 在训练类的算法中(如神经网络、回归),通常使用梯度下降法最小化损失函数,这时学习率的设置对算法的性能很重要,已有许多研究致力于梯度下降法的分析与改进。20世纪 80 年代,Naym Shor研究发明了次梯度法(Subgradient Method), 它是解凸优化问题的一 种迭代算法,也适用于目 标 函数不 可微 的 情 形 。 牛顿法(Newton method)最初由艾萨克·牛顿发明,后于 1690 年由约瑟夫·拉弗森再次提出。 Bottou L提出在大数处理时,使用随机抽取的单个样本计算近似的平均梯度值,单次迭代计算量小,效率很高,特别适合大数据机器学习。郭跃东和宋旭东针对学习率对算法收敛速度的影响做了研究,提出了一种新的梯度下降法,通过求解线性回归问题分析了算法性能,结果表明,改进算法大大加快了算法的收敛速度

梯度下降法(Gradient descent)是一个一阶最优化算法,通常也称为最速下降法。 要使用梯度下降法找到一个函数的局部极小值,必须向函数上当前点对应梯度(或者是近似梯度)的反方向的规定步长距离点进行迭代搜索。如果相反地向梯度正方向迭代进行搜索,则会接近函数的局部极大值点;这个过程则被称为梯度上升法。批量梯度下降由若干样本计算得到,比单样本随机梯度下降更为可靠,同时大大降低了单样本梯度下降中批量梯度互相抵消的情况。其次,梯度下降有利于并行运算,能够在深度学习平台上高效运行1。

本词条内容贡献者为:

王慧维 - 副研究员 - 西南大学