学习和纯优化异同

用于深度模型训练的优化算法与传统的优化算法在几个方面有所不同。机器学习通常是间接作用的。在大多数机器学习问题中，我们关注某些性能度量 $P$ ，其定义于测试集上并且可能是不可解的。因此，我们只是间接地优化 $P$ 。我们希望通过降低代价函数 $J(\theta)$ 来提高 $P$ 。这一点与纯优化不同，纯优化最小化目标 $J$ 本身。训练深度模型的优化算法通常也会包括一些针对机器学习目标函数的特定结构进行的特化。

通常，代价函数可写为训练集上的平均，如

$J(\theta)=\mathbb{E}_{(x,y)\sim\hat{p}_{data}}L(f(x;\theta),y)$

其中 $L$ 是每个样本的损失函数， $f(x;\theta)$ 是输入 $x$ 时所预测的输出， $\hat{p}_{data}$ 是经验分布。监督学习中， $y$ 是目标输出。在本章中，我们会介绍不带正则化的监督学习， $L$ 的变量是 $f(x;\theta)$ 和 $y$ 。不难将这种监督学习扩展成其他形式，如包括 $\theta$ 或者 $x$ 作为参数，或是去掉参数 $y$ ，以发展不同形式的正则化或是无监督学习。

$J(\theta)=\mathbb{E}_{(x,y)\sim\hat{p}_{data}}L(f(x;\theta),y)$定义了训练集上的目标函数。通常，我们更希望最小化取自数据生成分布 $p_{data}$ 的期望，而不仅仅是有限训练集上的对应目标函数：

$J^*(\theta)=\mathbb{E}_{(x,y)\sim p_{data}}L(f(x;\theta),y)$

经验风险最小化

机器学习算法的目标是降低 $J^*(\theta)=\mathbb{E}_{(x,y)\sim p_{data}}L(f(x;\theta),y)$ 所示的期望泛化误差。这个数据量被称为风险。在这里，我们强调该期望取自真实的潜在分布 $p_{data}$ 。如果我们知道了真实分布 $p_{data}(x,y)$，那么最小化风险变成了一个可以被优化算法解决的优化问题。然而，我们遇到的机器学习问题，通常是不知道 $p_{data}$ ，只知道训练集中的样本。

将机器学习问题转化回一个优化问题的最简单方法是最小化训练集上的期望损失。这意味着用训练集上的经验分布 $\hat{p}(x,y)$ 替代真是分布 $p(x,y)$ 。现在，我们将最小化经验风险：

$\mathbb{E}_{x,y\sim\hat{p}_{data}}[L(f(x;\theta),y)]=\frac{1}{m}\sum\limits_{i=1}^mL(f(x^{(i)};\theta),y^{(i)})$

其中 $m$ 表示训练样本的数目。

基于最小化这种平均训练误差的训练过程被称为经验风险最小化。在这种情况下，机器学习仍然和传统的直接优化很相似。我们并不直接最优化风险，而是最优化经验风险，希望也能够很大地降低风险。一系列不同的理论构造了一些条件，使得这些条件下真实风险的期望可以下降不同的量。

然而，经验风险最小化很容易导致过拟合。高容量的模型会简单地记住训练集。在很多情况下，经验风险最小化并非真的可行。最有效的现代优化算法是基于梯度下降的，但是很多有用的损失函数，如 $0-1$ 损失，没有有效的导数（导数要么为零，要么处处未定义）。这两个问题说明，在深度学习中我们很少使用经验风险最小化。反之，我们会使用一个稍有不同的方法，我们真正优化的目标会更加不同于我们希望优化的目标。

代理损失函数和提前终止

有时，我们真正关心的损失函数（比如分类误差）并不能被高效地优化。例如，即使对于线性分类器而言，精确地最小化 $0-1$ 损失通常是不可解的（复杂度是输入维数的指数级别）。在这种情况下，我们通常会优化代理损失函数。代理损失函数作为原目标的代理，还具备一些优点。例如，正确类别的负对数似然通常用作 $0-1$ 损失的替代。负对数似然允许模型估计给定样本类别的条件概率，如果该模型效果好，那么它能够输出期望最小分类误差所对应的类别。

在某些情况下，代理损失函数比原函数学到的更多。例如，使用对数似然替代函数时，在训练集上的 $0-1$ 损失达到 $0$ 之后，测试集上的 $0-1$ 损失还能持续下降很长一段时间。这是因为即使 $0-1$ 损失期望是零时，我们还能拉开不同类别的距离以改进分类器的鲁棒性，获得一个更强壮的、更值得信赖的分类器，从而，相对于简单地最小化训练集上的平均 $0-1$ 损失，它能够从训练数据中抽取更多信息。

一般地优化和我们用于训练算法的优化有一个重要不同：训练算法通常不会停止在局部极小点。反之，机器学习通常优化代理损失函数，但是在基于提前终止的收敛条件满足时停止。通常，提前终止使用真实潜在损失函数，如验证集上的 $0-1$ 损失，并设计为在过拟合发生之前终止。与纯优化不同的是，提前终止时代理损失函数仍然有较大的导数，而纯优化终止时导数较小。

批量算法和小批量算法

机器学习算法和一般优化算法不同的一点是，机器学习算法的目标函数通常可以分解为训练样本上的求和。机器学习中的优化算法在计算参数的每一次更新时通常仅使用整个代价函数中一部分来估计代价函数的期望值。

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

$\theta_{ML}=\mathop{\arg\max}\limits_\theta\sum\limits_{i=1}^m\log p_{model}(x^{(i)},y^{(i)};\theta)$

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

$J(\theta)=\mathbb{E}_{x,y\sim\hat{p}_{data}}\log p_{model}(x,y;\theta)$

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

$\nabla_\theta J(\theta)=\mathbb{E}_{x,y\sim\hat{p}_{data}}\nabla_\theta \log p_{model}(x,y;\theta)$

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

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

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

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

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

大多数用于深度学习的算法介于以上两者之间，使用一个以上，而又不是全部的训练样本。传统上，这些会被称为小批量（minibatch）或小批量随机（minibatch stochastic）方法，现在通常将它们简单地称为随机方法。随机方法的典型示例是随机梯度下降，小批量的大小通常由以下几个因素决定：

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

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

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

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

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

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

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

很多机器学习上的优化问题都可以分解成并行地计算不同样本上单独的更新。 换言之，我们在计算小批量样本 $X$ 上最小化 $J(X)$ 的更新时，同时可以计算其他小批量样本上的更新。

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

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

在 $x$ 和 $y$ 是离散时，以上的等价性很容易得到。在这种情况下，泛化误差 $J^*(\theta)=\mathbb{E}_{(x,y)\sim p_{data}}L(f(x;\theta),y)$ 可以表示为

$J^*(\theta) = \sum\limits_{x} \sum\limits_y p_{\text{data}}(x, y) L(f(x; \theta),y)$

上式的准确梯度为

$g = \nabla_{\theta} J^*(\theta) = \sum\limits_{x} \sum\limits_y p_{\text{data}} (x, y) \nabla_{\theta} L(f(x;\theta),y)$

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

因此，我们可以从数据生成分布 $p_{\text{data}}$ 抽取小批量样本 $\{x^{(1)},\dots,x^{(m)}\}$ 以及对应的目标 $y^{(i)}$ ，然后计算该小批量上损失函数关于对应参数的梯度

$\hat{g} = \frac{1}{m} \nabla_{\theta} \sum\limits_i L(f(x^{(i)};\theta),y^{(i)} )$

以此获得泛化误差准确梯度的无偏估计。最后，在泛化误差上使用随机梯度下降方法在方向 $\hat{g}$ 上更新 $\theta$

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

随着数据集的规模迅速增长，超越了计算能力的增速， 机器学习应用每个样本只使用一次的情况变得越来越常见，甚至是不完整地使用训练集。 在使用一个非常大的训练集时，过拟合不再是问题，而欠拟合和计算效率变成了主要的顾虑。