批量减数更新方差缩减梯度下降算法BSUG

宋 杰，朱 勇，许 冰

安徽大学 计算机科学与技术学院，合肥230601

1 引言

机器学习中目标函数通常使用梯度下降（Gradient Descent，GD）或者随机梯度下降（Stochastic Gradient Descent，SGD）[1]算法进行求解。前者每次迭代都要计算所有样本的梯度来进行权重更新，后者每次随机选取一个训练数据来更新参数。随后出现改进的Mini-Batch SGD[2]算法，每次迭代通过在原始数据中随机选取m 个数据样本进行训练。SGD 的优点是每一步仅仅依赖于简单的随机样本梯度，因此计算消耗只有标准GD 的1/n。然而它的缺点是在随机性引入方差情况下，恒定的步长会导致收敛缓慢。

近年来，许多学者基于SGD 算法进行研究，其中Sutskever 等人提出Momentum 算法[3]，它是基于梯度动量累积的思想使用指数加权平均来减小梯度的摆动幅度。Duchi 等人提出AdaGrad（Adaptive Gradient）[4]算法，它是通过逐渐缩小步长来进行学习。Hinton在他的机器学习神经网络课程中提出RMSProp（Root Mean Square Prop）[5]，其使用微分平方加权平均数进一步优化损失函数摆幅过大的问题。而针对SGD随机性引入方差问题，文献[6]提出了随机方差缩减梯度法（Stochastic Variance Reduction Gradient，SVRG），其核心思想是利用全局梯度信息对每次用于模型更新的梯度进行修正[7]。理论分析和实验证明，SVRG 在方差降低的情况下产生了线性收敛。随后依据方差缩减思想产生了新型的SAGA（Stochastic Average Gradient Average）[8]、

SCSG（Stochastically Controlled Stochastic Gradient）[9]、Mini-Batch SCSG[10]、b-NICE SAGA[11-12]等一系列算法[13-15]。其中SAGA是通过保留每个样本梯度，在计算过程中更新全局梯度平均值来缩减方差，这个过程需要储存所有样本梯度，为计算机带来很大的存储困难。SCSG 则是通过随机抽取一部分样本梯度作为全局梯度来计算平均梯度，但是在进行权重更新时，随机选取更新次数会让计算更加多变与繁琐，计算量大。

本文提出一种新的方差缩减算法BSUG（Batch Subtraction Update Gradient），通过随机抽取小样本来代替计算全局样本梯度，同时在参数更新同时对全局平均梯度进行更新。通过理论分析和实验证明了BSUG算法在收敛速度以及检测精度方面不弱于其他算法，并且具有较强的稳定性。

2 当前研究现状

给定n 个训练数据(x1,y1),(x2,y2),…,(xn,yn)，其中xi∈Rd表示输入数据，yi∈R 表示对应的训练标签，求解目标函数[16]使得每个输入数据训练得到的输出与已知训练标签误差最小。

其中，fi表示目标函数，w 表示目标函数中的参数，w*是最优参数。

机器学习中目标函数通常使用梯度下降（GD）或者随机梯度下降（SGD）算法进行求解，其中SGD 算法更新如下：

GD 提供了最终收敛的保证，而SGD 在收敛速度、可扩展性和实现简便方面具有优势。随后出现使用式（3）进行更新改进的算法Mini-Batch SGD。

针对恒定步长，AdaGrad 是将每次更新的梯度累加，从而在训练过程中为权重调整步长。

变量h 保存了所有梯度值的平方和，ε 防止分母为0。然后在更新参数时，通过乘以调节学习的尺度。但是AdaGrad在迭代后期由于步长过小，可能很难找到一个最优解。

为了解决AdaGrad的问题，RMSProp使用了加权平均数。

其中，β 是梯度累积权重，s 保存了所有梯度值的加权平方和，它并不会因为迭代一直累加，这样也就不会出现后期收敛缓慢的问题。

SVRG 的提出主要是用来解决由于方差而导致SGD不能快速收敛的问题，其核心思想是利用全局的梯度信息对每次用于模型更新的梯度进行修正。算法中每次的迭代都是通过以下公式进行更新：

其中，w ∈Rd表示模型参数，η 表示更新步长，=是使用上一轮模型参数计算出的全局平均梯度，表示函数f 在样本点ij的梯度，是梯度的偏差，是经过修正后的无偏估计，使用来更新wj。

算法伪代码如下：

算法1 SVRG

从算法1 中可以看出，算法的主要计算在步骤2 和步骤6 中。步骤2 是计算平均梯度，步骤6 是计算修正后的梯度无偏估计，从到一轮迭代计算成本为n+2m 。随后SAGA 和SCSG 也主要是从这两个步骤进行修改从而优化算法。

在SAGA算法中，利用一块内存存储所有样本的原始梯度，计算出以当前新权重为模型的新梯度∇fij(wj-1),通过从而达到更新的目的，但是算法内存占用过大。而SCSG算法主要是通过在数据集中随机抽取B 个小样本数据进行全局平均梯度的估计，并且对于梯度的无偏估计迭代次数k 主要是从服从几何分布的数列{1,2,…,m}中随机抽取，计算成本为B+2k,小于SVRG的n+2m。

Lei等人提出了Mini-Batch SCSG，一种小批量样本无偏估计算法。该方法基于SCSG的小样本平均梯度，在计算梯度的无偏估计时，使用小批量样本的平均梯度来代替原有单个样本梯度，即：

Gower等人提出了b-NICE SAGA，一种针对SAGA单样本更新平均梯度缓慢问题而提出的新算法。该方法在更新平均梯度时使用小批量样本梯度同时替换更新，在计算梯度无偏估计时也是使用小批量样本的平均梯度来进行计算。它通过平滑度系数设置了最优批量大小，从而总复杂度线性降低，但计算成本和内存消耗有所增加，小批量样本梯度的计算与更新加大了整个算法的计算消耗。

Allen-Zhu 等人提出了Natasha[17]，一种新的参数更新方法。该方法主要是对参数随机抽样更新。通过每轮参数抽样对部分参数进行更新，同时使用小批量样本进行梯度计算。

Zou 等人提出的SVR-HMC[18]则是在迭代过程中对参数利用哈密尔顿蒙特卡罗方法进行错位更新，但其本质也是一种比较复杂的无偏估计计算方式。

3 BSUG算法

3.1 算法介绍

SCSG算法中的小批量平均梯度以及SAGA算法中的无偏估计更新为本文的算法带来灵感。这里使用更新的平均梯度是由SCSG计算出的小批量平均梯度，即n →B，这样可以减少存储成本。同时改变SAGA 平均梯度的更新形式，由原来的改为，即将过去模型计算出的样本梯度直接舍去，通过直接舍去样本梯度来减少梯度方差。不可避免的，计算梯度无偏估计的迭代次数也要相应地减少为小于B，间接地减少计算成本。

算法伪代码如算法2。

算法2 BSUG

BSUG算法主要包括以下部分：

（1）从n 个样本中随机抽取样本Ht,| Ht|=B，如步骤2所示；

（2）计算Ht中所有样本梯度并保存，如步骤3～6所示；

（3）计算每次更新的平均梯度，如步骤9所示；

（4）随机从B 中选取一个样本进行梯度无偏估计计算，如步骤10、11所示；

（5）将选取样本所在的梯度删除，重新计算平均梯度，如步骤12、9所示。

从步骤12可以看出，∇fij(w[ij])是有限的，且删除后不再拥有，为避免错误重复删除，在程序编程时会将B中的样本随机排序后依次抽取。

3.2 算法收敛性分析

为了简单起见，本文只考虑每个fi(w)的情况是凸面平滑，P(w)是强凸问题。下面的假设将在本文的各种情况下使用。

假设1 fi是具有L-Lipschitz梯度的凸函数：

假设2 P(w)是强凸函数：

由文献[6]可知：

通过对j=1,2,…,k 阶段的累加可得：

第二个不等式使用了强凸性质（12），因此获得：

从而有BSUG的收敛性：

由BSUG算法的收敛性可以看出，算法的收敛速度与参数B 和k 的选取有关。关于参数B 和k 的选取对算法的稳定性以及收敛速度探究将在实验部分详细说明。

4 实验

本文算法是由Python3.6 完成，整体网络架构参考文献[19]完成。对于算法的实现，本文使用的设备为CPU：AMD A6-3400M APU with RadeonTMHD Graphics 1.40 GHz，内存6.00 GB。使用的是主流数据集MNIST[20]，参与训练样本是从MNIST数据中随机抽取的10 000个训练样本，测试样本是MNIST 自带的10 000 个测试样本。本文所有程序网络结构全部为728×40×10，即输入层728个神经元，隐含层40个神经元，输出层为10个神经元的Softmax-with-Loss层。

实验总共包括两部分：第一部分主要是本文算法与当前主流算法之间的评测对比；第二部分主要是对本文算法参数关系的探究。

4.1 算法对比

使用Python3.6编程实现BSUG算法，将其与主流的Mini-Batch SGD、AdaGrad、RMSProp、SVRG 和SCSG算法进行对比评测。

从表1和图1中可以看出以下几点：

（1）BSUG、RMSProp 与SCSG 迭代到第一个epoch时，精度都达到了65%，而SVRG、Mini-Batch SGD 和AdaGrad只达到40%。随着迭代进行，BSUG、RMSProp与SCSG只需7个epoch精度就达到80%，而SVRG达到65%，Mini-Batch SGD 和AdaGrad 只达到50%，可见BSUG 在收敛速度上与RMSProp、SCSG 相当，并优于SVRG、Mini-Batch SGD和AdaGrad。

（2）BSUG、RMSProp 与SCSG 都平稳快速地达到高精准度。在准确度上BSUG 与SCSG 相差0.26 个百分点，与RMSProp 相差1.13 个百分点，SVRG 的检测准确率略低于前面三种算法，但仍然比Mini-Batch SGD和AdaGrad优秀。

（3）Mini-Batch SGD 和AdaGrad 没有达到高准确率要求，合理猜测是由于训练样本不足导致的，这也间接说明Mini-Batch SGD和AdaGrad存在不能更深入学习样本特征的缺点。

表1 算法对比结果

图1 算法精度对比

4.2 稳定性探究

本文算法的稳定性主要受到批大小B 以及内迭代次数k 两个因素影响。本文主要从训练样本数B 与n比例关系和B 与k 比例关系两方面进行实验探究。

4.2.1 B 与n 比例探究

在探究B 与n 比例关系对算法的影响实验中，将从MNIST 数据中逐一抽取10 000、8 000、4 000 个样本进行训练，并且B ∈{n/2,n/4,n/8,n/16,n/32}，设置k=B-1 进行实验。

表2 B 与n 比例探究结果

表3 B 与k 比例探究结果

从表2和图2中可以看出以下几点：

（1）B 与n 之间的比例关系与算法效果有一定的关系，B 越大训练精度越小，同时因为k 的设置导致替代次数变多，训练的时间也会越长。

（3）实验样本数过少，当样本数更多时应该设置适当的B 来适应数据集。

图2 B 与n 比例探究结果

4.2.2 B 与k 比例探究

探究B 与k 比例关系对算法的影响实验中，将从MNIST 数据中抽取8 000 个样本进行训练。同时让B分别为250、500、1 000，设置k ∈{B-1,0.8×B,0.6×B,0.4×B,0.2×B}进行实验。

从表3和图3中可以看出以下几点：

（1）k 与B 的大小关系对算法效果有直接影响，k越接近于B，算法的测试精度越高，反之，精度下降，且这种现象不随B 的增加发生变化。

（2）由数据的交叉观测可知，当k 为常数(k=200)时，精度会随着B 的增加而降低，更加证实上述观点。

4.3 实验总结

图3 B 与k 比例探究结果

通过4.1节可以发现BSUG算法相比于Mini-Batch SGD、AdaGrad和SVRG等算法在收敛速度和精度上效果突出，并和RMSProp、SCSG效果相当。通过4.2节可以知道BSUG算法是一个相对稳定的算法，以及参数对算法精度影响的趋势。

5 结束语

本文采用小样本平均梯度代替全局平均梯度的思想，设计了选取小样本进行训练，同时更新平均梯度来实现方差缩减的算法BSUG，基于Python平台进行算法实现，并理论证明了算法的收敛性。通过实验证明了BSUG算法优于Mini-Batch SGD、AdaGrad和SVRG算法，与RMSProp、SCSG 算法效果相当。并且通过对超参数的探究证明了BSUG算法具有一定的稳定性，在批量较低的情况下也能达到足够的精度。

本文由于设备原因，导致无法对更大数据集进行实验，同时对于批大小的最低下限没有进行更深入的讨论，这将是以后继续完善的方向。