Question

1. 机器学习算法和一般最优化算法不同的一点：机器学习算法的目标函数通常可以分解为每个训练样本上的损失函数的求和。如： $ \vec\theta_{ML}=\arg\max_{\vec\theta}\sum_{i=1}^{N}\log p_{model}(\mathbf{\vec x}_i,y_i;\vec\theta) $ 。

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

   $ J(\vec\theta)=\mathbb E_{(\mathbf{\vec x},y)\sim \hat p_{data}}\log p_{model}(\mathbf{\vec x} ,y ;\vec\theta) $

2. 当使用基于梯度的优化算法求解时，需要用到梯度：

   $ \nabla_\vec\theta J(\vec\theta)=\nabla_\vec\theta [\mathbb E_{(\mathbf{\vec x},y)\sim \hat p_{data}}\log p_{model}(\mathbf{\vec x} ,y ;\vec\theta)] = \mathbb E_{(\mathbf{\vec x},y)\sim \hat p_{data}} \nabla_\vec\theta\log p_{model}(\mathbf{\vec x} ,y ;\vec\theta) $

   这个梯度本质上也是一个期望，要准确的求解这个期望的计算量非常大，因为需要计算整个数据集上的每一个样本。

   实践中，可以从数据集中随机采样少量的样本，然后计算这些样本上的梯度的均值，将这个均值作为该期望的一个估计。

3. 使用小批量样本来估计梯度的原因：

   • 使用更多样本来估计梯度的方法的收益是低于线性的。

     独立同分布的 $ n $ 个样本的均值 $ \bar X $ 是个随机变量，其标准差为 $ \frac{\sigma}{\sqrt{n}} $ ，其中 $ \sigma $ 为样本的真实标准差。

   • 如果能够快速计算出梯度的估计值（而不是费时地计算准确值），则大多数优化算法会更快收敛。

     大多数优化算法基于梯度下降，如果每一步中计算梯度的时间大大缩短，则它们会更快收敛。

   • 训练集存在冗余。

     实践中可能发现：大量样本都对梯度做出了非常相似的贡献。

     最坏情况下， 训练集中的 $ N $ 个样本都是相同的拷贝。此时基于小批量样本估计梯度的策略也能够计算正确的梯度，但是节省了大量时间。

4. 使用整个训练集的优化算法被称作batch梯度算法（或者确定性deterministic梯度算法）。

   每次只使用单个样本的优化算法被称作随机stochastic算法（或者在线online算法）。

   大多数深度学习的优化算法介于两者之间：使用一个以上、又不是采用全部的训练样本，称作mini-batch或者mini-batch随机算法。

5. 当使用小批量样本来估计梯度时，由于估计的梯度往往会偏离真实的梯度，这可以视作在学习过程中加入了噪声扰动。这种扰动会带来一些正则化效果。

3.1 mini-batch 大小

1. mini-batch的大小由下列因素决定：

   • 不能太大。更大的batch会使得训练更快，但是可能导致泛化能力下降。

     • 训练更快是因为：

       • 更大的batch size 只需要更少的迭代步数就可以使得训练误差收敛。

         因为batch size 越大，则小批量样本来估计总体梯度越可靠，则每次参数更新沿着总体梯度的负方向的概率越大。

         另外，训练误差收敛速度快，并不意味着模型的泛化性能强。

       • 更大的batch size 可以利用大规模数据并行的优势。

     • 泛化能力下降是因为：更大的batch size 计算的梯度估计更精确，它带来更小的梯度噪声。此时噪声的力量太小，不足以将参数推出一个尖锐极小值的吸引区域。

       解决方案为：提高学习率，从而放大梯度噪声的贡献。

   • 不能太小。因为对于多核架构来讲，太小的batch并不会相应地减少计算时间（考虑到多核之间的同步开销）。

   • 如果batch中所有样本可以并行地预处理，则内存消耗和batch大小成正比。

     对于许多硬件设备来说，这就是batch大小的限制因素。

   • 在有些硬件上，特定大小的效果更好。

     在使用GPU时，通常使用 2 的幂作为batch大小。

2. 泛化误差通常在batch大小为 1 时最好，但此时梯度估计值的方差非常大，因此需要非常小的学习速率以维持稳定性。如果学习速率过大，则导致步长的变化剧烈。

   由于需要降低学习速率，因此需要消耗更多的迭代次数来训练。虽然每一轮迭代中，计算梯度估计值的时间大幅度降低了（batch size为 1），但是总的运行时间还是非常大。

3. 某些算法对采样误差非常敏感，此时mini-batch效果较差。原因可能有两个：

   • 这些算法需要用到全部样本的一些精确信息，但是这些信息难以在少量样本上估计到。
   • 这些算法会放大采样误差，导致误差积累越来越严重。

4. 通常仅仅基于梯度 $ \mathbf{\vec g} $ 的更新方法相对更稳定，它能够处理更小的batch（如100）。

   如果使用了黑塞矩阵 $ \mathbf H $ （如需要计算 $ \mathbf H^{-1}\mathbf{\vec g} $ 的二阶方法） 通常需要更大的 batch（如 10000）。

   • 即使 $ \mathbf H $ 被精确估计，但是它的条件数很差，那么乘以 $ \mathbf H $ 或者 $ \mathbf H^{-1} $ 会放大之前存在的误差。这就导致 $ \mathbf{\vec g} $ 的一个非常小的变化也会导致 $ \mathbf H^{-1}\mathbf{\vec g} $ 的一个非常大的变化。因此 batch需要更大从而降低梯度估计的方差。
   • 通常只是近似地估计 $ \mathbf H $ ，因此只会引入更多的误差。

3.2 随机抽样

1. mini-batch是随机抽样的也非常重要。从一组样本中计算出梯度期望的无偏估计要求：组内的样本是独立的。

   另外，也希望两个连续的梯度估计也是相互独立的。这要求：两个连续的mini-batch样本集合也应该是彼此独立的。

2. 实际应用中，采集的数据样本很可能出现这样的情况：连续的样本之间具有高度相关性。

   如：统计人群的偏好，很可能连续的样本就是同一个家庭、同一个职业、同一个地域...。

   解决方法是：将样本随机混洗之后存储，训练时按照混洗之后的顺序读取。

   这种打乱顺序不会对mini-batch产生严重的影响，不打乱顺序的mini-batch才会极大降低算法泛化能力。

3. mini-batch可以异步并行分布式更新：在计算mini-batch样本集合 $ \mathbb X_i $ 上梯度更新时，也可以同时计算其他mini-batch样本集合 $ \mathbb X_j $ 上的更新。

3.3 重复样本

1. 当 $ \mathbf{\vec x},y $ 都是离散时，泛化误差的期望：

   $ J^{*}(\vec\theta)=\mathbb E_{(\mathbf{\vec x},y)\sim p_{data}} L(f(\mathbf{\vec x};\vec\theta),y) =\sum_{(\mathbf{\vec x},y)} p_{data}(\mathbf{\vec x},y) L(f(\mathbf{\vec x};\vec\theta),y) $

   其梯度为：

   $ \mathbf{\vec g}=\nabla_{\vec\theta}J^{*}(\vec\theta)=\sum_{(\mathbf{\vec x},y)} p_{data}(\mathbf{\vec x},y) \nabla_{\vec\theta}L(f(\mathbf{\vec x};\vec\theta),y) $

   泛化误差的梯度的无偏估计可以通过从数据生成分布 $ p_{data} $ 抽取 mini-batch样本 $ \{\mathbf{\vec x}_1,\mathbf{\vec x}_2,\cdots,\mathbf{\vec x}_m\} $ 以及对应的标签 $ \{y_1,y_2,\cdots,y_m\} $ ，然后计算mini-batch上的损失函数对于 $ \vec\theta $ 的梯度：

   $ \hat{\mathbf{\vec g}}= \frac 1m \nabla_{\vec\theta}\sum_{i=1}^{m}L(f(\mathbf{\vec x}_i;\vec\theta),y_i) $

   它就是 $ \mathbf{\vec g} $ 的无偏估计。

   因此，mini-batch随机梯度下降中，只要没有重复使用样本，它就是真实泛化误差梯度的无偏估计。

2. 如果是在线学习，则每个样本或者mini-batch都不会重复。每次更新都是独立地从真实分布 $ p_{data} $ 中采样获得。

3. 如果训练集不大，通常需要多次遍历训练集，此时只有第一遍满足泛化误差的梯度的无偏估计。

   后续的遍历中，泛化误差的梯度估计不再是无偏的。但是后续的遍历会减小训练误差，从而抵消了训练误差和测试误差之间gap的增加。最终效果是：减小了测试误差。

4. 随着数据集规模的爆炸性增长，超过了计算能力的增长速度，现在普遍地对每个样本只使用一次，甚至不完整地使用训练集。

   此时过拟合不再是问题，欠拟合以及计算效率成为主要问题。