6

优化算法系列（2）：深入讨论SGD及其改进思路

 3 years ago
source link: https://allenwind.github.io/blog/8336/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

优化算法系列（2）：深入讨论SGD及其改进思路

从机器学习角度来看，一个完整的任务包括模型、评估、优化，本系列谈的就是优化。机器学习模型的训练其实就是参数学习，通常是通过一定的优化算法来寻找一组可以最小化结构风险的参数。而最常见的优化算法是梯度下降算法（SGD），基于SGD可以引申出很大的优化算法。本系列打算探讨优化算法的改进与变化逻辑。

首先来说说最基本的梯度下降（GD）算法。

简单回顾一下上篇说的梯度下降算法。假设有训练样本集D=(x1,y1),…,(xn,yn)D=(x1,y1),…,(xn,yn)，单个样本可以用 x=(x,y)x=(x,y)来表示，模型fθ(x)fθ(x)的优化参数为 θθ ，那么整个训练样本集上的损失函数为

L(θ)=1|D|∑(x,y)∈DL(y,fθ(x))L(θ)=1|D|∑(x,y)∈DL(y,fθ(x))

为完成优化目标，GD的做法是

θn+1=θn−γ∇θL(θn)θn+1=θn−γ∇θL(θn)

我们这里不讨论起导出。其中0<γ≪10<γ≪1称为学习率。注意到，每次迭代时，GD都要运用整个训练集D来进行梯度计算，对于数据量小的情况可以接受，但是在训练神经网络时，这个计算量就十分巨大。

于是随机梯度下降（SGD）就来解决这个问题，每次随机采样一个批量来替代全批量作为梯度计算的数据。

随机梯度下降

随机梯度下降的随机来自哪里？那就是随机采样定量样本来估计梯度替代全量数据的梯度。

SGD的随机性

与GD每次都用全量的数据不同，SGD每次只取其子集Ri⊆DRi⊆D来计算梯度，于是有

LRi(θ)=1|D|∑(x,y)∈RiL(y,fθ(x))LRi(θ)=1|D|∑(x,y)∈RiL(y,fθ(x))

子集RiRi称为批，其大小称为批量，就是我们训练神经网络常用的参数batch_size。由于RiRi是随机采样自DD，因此LRi(θ)LRi(θ)也是一个随机变量。

SGD迭代过程，

θn+1=θn−γ∇θLRi(θn)θn+1=θn−γ∇θLRi(θn)

由于LRi(θ)LRi(θ)是一个随机变量，所以∇θLRi(θn)∇θLRi(θn)也是一个随机变量，是原来真是梯度∇θL(θn)∇θL(θn)​的估计。因此，可以看到，随机梯度下降的随机就体现在对梯度的计算的随机性上。不严格来说，在实践中，学习率会随着模型的训练进度而调整，因此学习率γγ本身也是SGD中随机的来源。

原来我们是用整个训练集来计算梯度，现在我们是在训练集的子集上计算（估算）梯度，那么它们之间的差肯定为一个随机数，即

∇θL(θ)−∇θLRi(θ)=ξi∇θL(θ)−∇θLRi(θ)=ξi

ξiξi 表示批次ii在子集样本RiRi​上的梯度误差，这个误差我们可以从方差的角度来衡量，

Var(ξi)=σ2iVar⁡(ξi)=σi2

如果要把γ∇θLRi(θn)γ∇θLRi(θn)当做一个正态考虑，那么

Var(ξi)=γ2σ2iVar⁡(ξi)=γ2σi2

尽管随机采样带来梯度计算的误差，但从优化角度看也带来一个好处。梯度下降（GD）在鞍点处梯度为0，一点陷入鞍点难以逃离，而随机梯度下降（SGD）相比与梯度下降（GD）引入随机性能够有利于逃离鞍点。

批量大小的选择

不难理解，假定学习率不变的情况下，当集样本RiRi的数量越大，梯度误差ξξ的方差越小，引入的噪声越小，反之则相反。我们可以想象两个极端，当集样本RiRi为整个训练集时，GD和SGD的梯度没有差别，当集样本RiRi每次只取一个样本时，GD和SGD的差别是最大的。

这个思考给我们的启示是，在训练模型时，假定学习率不变的情况下，当选择更小的批量时，计算效率快，但梯度误差的方差更大，训练不稳定，更难收敛，当选择更大的批量时，梯度误差的方差更小，有利于训练稳定，有利于快速收敛（不能保证收敛得更好），但需要的计算资源更大。

但是batch size参数的随意增加会加大计算成本，同时也考虑到Var(ξi)=γ2σ2iVar⁡(ξi)=γ2σi2，从调整学习率的角度来调整梯度误差的方差更合理。从实践的角度来看，批量大小一般是增加都一定大小后就不再增加，如32，64， 128，然后把关注点转向对学习率的调整。

学习率调整与warm-up

直观上看，随着SGD的迭代，

θn+1=θn−γ∇θLRi(θn)θn+1=θn−γ∇θLRi(θn)

靠近极小值时，∇θLRi(θn)∇θLRi(θn)​取值很小，导致更新速度减慢，这个时候学习率γγ也应该相应的减小，避免θθ在一个狭小的区间内反复横条，影响收敛速度。

此外，我们还有考虑学习率与batch_size同步的问题，根据Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour，学习率在批量大小比较小的时候，按线性缩放。就是说在一定范围的批量大小内，当批量翻倍时，学习率也应该翻倍。

SGD的简单分析

与其他的数值优化算法一样，随机梯度下降往往收敛都局部最优甚至是鞍点，如何保证泛化能力？我们来分析一下，假设在某一维度上的梯度为零的概率为p，那么局部最小的概率为pnpn，这里假设参数的个数为nn，因此，优化时找到局部最优点也是很难。也就是说更多的时候是收敛到鞍点。那么该如何保证泛化能力？

我认为这里有一个认知上的误区，就是收敛到最优点才能保证泛化能力。事实上，纯粹的数值优化问题与基于统计学习的优化在目标上不同。我们训练的目标并不是loss最优，它只不过是给我们的模型提供一个优化方向。我们的模型的实用性关注的是在测试集上某个性能指标表现很好。

因此，这个疑问在神经网络没有多大的讨论价值，当然在凸优化中有。因为在神经网络中，我们是面向测试集的某个优化指标去。另外还要考虑测试集和训练集的概念漂移以及迁移学习，从工程上看，“差不多”的就是最好的。

随机梯度下降的改进思路

以上我们获得随机梯度下降，

θn+1=θn−γ∇θLRi(θn)θn+1=θn−γ∇θLRi(θn)

可以看到，影响 SGD 有四个因素，因此可以从这些因素上改进：

  • 学习率 γγ 的调整
  • 参数更新方向 （不止梯度方向）
  • 批量 RiRi 的大小batch_size与梯度估计
  • 提高价数（即止于计算梯度）

也就是说, 优化 SGD 可以从以上四点入手，如果调整点能让算法收敛更快、更好、更稳定, 那么就是有效的。后续我们会依据这一思路来展开讨论。

对于第四点，提高价数，考虑多元极值，Hessian矩阵

Hij=∂2f∂xi∂xjHij=∂2f∂xi∂xj

考虑到函数的nn次连续性，

∂2f∂xi∂xj=∂2f∂xj∂xi∂2f∂xi∂xj=∂2f∂xj∂xi

那么Hessian矩阵是n×nn×n的对称矩阵。驻点为极值点要求Hessian矩阵为正定矩阵，即满足x⊤Hx>0x⊤Hx>0​​。但是这个计算太难了，计算效率不高，因此高价数的优化算法在深度学习中很少使用。因此在接下来的文章中不考虑提高价数这一改进思路。此外，模拟退火、遗传算法、蚁群算法等，它们不能在深度学习上流行的大概率原因还是计算效率。

SGD优化器对神经网络参数更新时可以简单写成，

wi+1=wi+εwi+1=wi+ε

所有其他的优化算法都是这种形式。这种形式其实就是类似随机漫步（随机游走），也就是说参数的更新过程可以看做是带约束的随机游走。那么，神经网络的优化是否可以使用随机过程刻画，并利用随机过程的一些性质探索神经网络训练的特点呢？

作为一个问题留作思考。

抛开机器学习来看，在应用数学上有很大的优化算法，如粒子群优化算法、模拟退火算法，然而这类算法在训练模型上不常使用，我个人的理解是效率问题。往往工程落地和纯粹的理论之间是有一定的差别的，工程落地考虑到业务本身的约束会愿意在理论上作妥协。本篇讲述SGD，是训练神经网络最常用的优化算法，效率高，因而在工程上大量使用。

[1] 《数值分析》


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK