8.1.3 批量算法和小批量算法

批量梯度算法的问题

机器学习算法和一般优化算法不同的一点是，机器学习算法的目标函数通常可以分解为训练样本上的求和。

[success] 关于代价函数的两个假设 机器学习优化算法通常使用整个代价函数中的一部分项去更新其参数。

机器学习中的优化算法在计算参数的每一次更新时通常仅使用整个代价函数中一部分项来估计代价函数的期望值。

例如，最大似然估计问题可以在对数空间中分解成各个样本的总和：

$$\begin{aligned} \theta_{\text{ML}} = {\arg\max}_{\theta} \sum_{i=1}^m \log p_{\text{model}} (x^{(i)}, y^{(i)}; \theta) . \end{aligned}$$

最大化这个总和等价于最大化训练集在经验分布上的期望：

$$\begin{aligned} J(\theta) = \Bbb E_{x, y \sim\hat{p}_\text{data}} \log p_{\text{model}} (x,y ; \theta) . \end{aligned}$$

优化算法用到的目标函数$J$中的大多数属性也是训练集上的期望。 例如，最常用的属性是梯度：

$$\begin{aligned} \nabla_{\theta} J(\theta) = \Bbb E_{x, y \sim\hat{p}_{\text{data}}} \nabla_{\theta} \log p_{\text{model}} (x,y; \theta) . \end{aligned}$$

准确计算这个期望的计算代价非常大，因为我们需要在整个数据集上的每个样本上评估模型。 在实践中，我们可以从数据集中随机采样少量的样本，然后计算这些样本上的平均值。

[success] Ng补充 [l]：神经网络的第l层 {t}：第t上mini-batch (i)：batch的第i个样本

为什么使用小批量算法

[success] 原因一：快速地计算出梯度估计值，而不是缓慢地计算准确值，那么收敛会更快

回想一下，$n$个样本均值的标准差（\eqn?）是$\sigma/\sqrt{n}$，其中$\sigma$是样本值真实的标准差。 分母$\sqrt{n}$表明使用更多样本来估计梯度的方法的回报是低于线性的。 比较两个假想的梯度计算，一个基于$100$个样本，另一个基于$10,000$个样本。 后者需要的计算量是前者的$100$倍，但却只降低了$10$倍的均值标准差。 如果能够快速地计算出梯度估计值，而不是缓慢地计算准确值，那么大多数优化算法会收敛地更快（就总的计算量而言，而不是指更新次数）。

[success] 原因二：大量样本都对梯度做出了非常相似的贡献

另一个促使我们从小数目样本中获得梯度的统计估计的动机是训练集的冗余。 在最坏的情况下，训练集中所有的$m$个样本都是彼此相同的拷贝。 基于采样的梯度估计可以使用单个样本计算出正确的梯度，而比原来的做法少花了$m$倍时间。 实践中，我们不太可能真的遇到这种最坏情况，但我们可能会发现大量样本都对梯度做出了非常相似的贡献。

[success] 原因三：可以并行计算

术语

[success] 选择不同的size得到的算法各有名字。

size的大小	算法的名字
size=样本数	批量（batch）或确定性（deterministic）梯度算法
size=1	随机（stochastic）或者在线（on-line）算法
size $\in$ (1, 样本数)	为小批量（minibatch）或小批量随机（minibatch stochastic）方法

使用整个训练集的优化算法被称为批量或确定性梯度算法，因为它们会在一个大批量中同时处理所有样本。 这个术语可能有点令人困惑，因为这个词"批量"也经常被用来描述小批量随机梯度下降算法中用到的小批量样本。 通常，术语"批量梯度下降"指使用全部训练集，而术语"批量"单独出现时指一组样本。 例如，我们普遍使用术语"批量大小"表示小批量的大小。

每次只使用单个样本的优化算法有时被称为随机或者在线算法。 术语"在线"通常是指从连续产生样本的数据流中抽取样本的情况，而不是从一个固定大小的训练集中遍历多次采样的情况。

大多数用于深度学习的算法介于以上两者之间，使用一个以上，而又不是全部的训练样本。 传统上，这些会被称为小批量或小批量随机, %小批方法 ，现在通常将它们简单地称为随机方法。

随机方法的典型示例是随机梯度下降，这将在\sec?中详细描述。

如果决定批量的size

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

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

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

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

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

• 可能是由于小批量在学习过程中加入了噪声，它们会有一些正则化效果~{cite?}。

  泛化误差通常在批量大小为$1$时最好。

  因为梯度估计的高方差，小批量训练需要较小的学习率以保持稳定性。

  因为降低的学习率和消耗更多步骤来遍历整个训练集都会产生更多的步骤，所以会导致总的运行时间非常大。

[success] 关于size，Ng有几点补充： (1)如果样本总数m比较小（m < 2000），则令size=m (2)常用的size有：64、128、256、512 (3)fit in CPU/GPU memory SGD算法的目标是使计算高效，而不是对准确率的优化。

如何基于一个批量更新参数

[success] 基于一阶梯度的更新和基于二阶Hessian的更新 后者需要更大的batch size

不同的算法使用不同的方法从小批量中获取不同的信息。 有些算法对采样误差比其他算法更敏感，这通常有两个可能原因。 一个是它们使用了很难在少量样本上精确估计的信息，另一个是它们以放大采样误差的方式使用了信息。 仅基于梯度$g$的更新方法通常相对鲁棒，并能使用较小的批量获得成功，如$100$。 使用Hessian矩阵$H$，计算如$H^{-1}g$更新的二阶方法通常需要更大的批量，如$10,000$。 这些大批量需要最小化估计$H^{-1}g$的波动。 假设$H$被精确估计，但是有病态条件数。 乘以$H$或是其逆会放大之前存在的误差（这个示例中是指$g$的估计误差）。

[warning] 病态问题是怎么影响参数更新的误差的？

即使$H$被精确估计，$g$中非常小的变化也会导致更新值$H^{-1}g$中非常大的变化。 当然，我们通常只会近似地估计$H$，因此相对于我们使用具有较差条件数的操作去估计$g$，更新$H^{-1}g$会含有更多的误差。

如何选取一个批量

[success] 两个连续的小批量样本应该是独立的。 先全部打乱样本，然后按照打乱后的顺序依次取样本。 不打乱样本可能是有害的。

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

小批量算法的理论分析

很多机器学习上的优化问题都可以分解成并行地计算不同样本上单独的更新。 换言之，我们在计算小批量样本$X$上最小化$J(X)$的更新时，同时可以计算其他小批量样本上的更新。 这类异步并行分布式方法将在\sec?中进一步讨论。

小批量随机梯度下降的一个有趣动机是，只要没有重复使用样本， 它将遵循着真实\emph{泛化误差}（\eqn?）的梯度。 很多小批量随机梯度下降方法的实现都会打乱数据顺序一次，然后多次遍历数据来更新参数。 第一次遍历时，每个小批量样本都用来计算真实泛化误差的无偏估计。 第二次遍历时，估计将会是有偏的，因为它重新抽取了已经用过的样本，而不是从和原先样本相同的数据生成分布中获取新的无偏的样本。

[warning] 不太懂

从在线学习的情况中我们最容易看出随机梯度下降最小化的是真实的泛化误差的原因。 这时样本或者说（单个样本的）小批量都是从数据流中抽取出来的。 换言之，学习器好像是一个每次看到新样本的人， 每个样本$(x,y)$都来自数据生成分布~$p{\text{data}}(x,y)$，而不是使用大小固定的训练集。 这种情况下，样本永远不会重复；每次更新的样本是从分布$p\text{data}$中采样获得的无偏样本。

在$x$和$y$是离散时，以上的等价性最容易被看出来。 在这种情况下，泛化误差（\eqn?）可以表示为

$$\begin{aligned} J^*(\theta) = \sum_{x} \sum_y p_{\text{data}}(x, y) L(f(x; \theta),y), \end{aligned}$$

上式的准确梯度为

$$\begin{aligned} g = \nabla_{\theta} J^*(\theta) = \sum_{x} \sum_y p_{\text{data}} (x, y) \nabla_{\theta} L(f(x;\theta),y) . \end{aligned}$$

在\eqn?和\eqn?中，我们已经在对数似然中看到了同样的结果；现在我们发现这一点在似然之外的其他函数$L$上也是成立的。 在一些关于$p_\text{data}$和$L$的温和假设下，在$x$和$y$是连续时也能得到类似的结果。

因此，我们可以从数据生成分布~$p\text{data}$抽取小批量样本${ x^{(1)}, \cdots,x^{(m)} }$以及对应的目标$y^{(i)}$，然后计算该小批量上损失函数关于对应参数的梯度 \begin{aligned} \hat{g} = \frac{1}{m} \nabla{\theta} \sum_i L(f(x^{(i)};\theta),y^{(i)} ). \end{aligned} 以此获得泛化误差准确梯度的无偏估计。 最后，在方向$\hat{g}$上更新$\theta$也就意味着以（真实）泛化误差为目标进行\,SGD\,。

当然，这个解释只能用于样本没有重复使用的情况。 然而，除非训练集特别大，通常最好是多次遍历训练集。 当多次遍历数据集更新时，只有第一遍满足泛化误差梯度的无偏估计。 但是，额外的遍历更新当然会由于减小训练误差而得到足够的好处，以抵消其带来的训练误差和测试误差间差距的增加。

随着数据集的规模迅速增长，超越了计算能力的增速， 机器学习应用每个样本只使用一次的情况变得越来越常见，甚至是不完整地使用训练集。 在使用一个非常大的训练集时，过拟合不再是问题，而欠拟合和计算效率变成了主要的顾虑。 读者也可以参考~{bottou-bousquet-2008}中关于训练样本数目增长时，泛化误差上计算瓶颈影响的讨论。