SGD过程中的噪声如何帮助避免局部极小值和鞍点?

来自 UC Berkeley RISELab 的本科研究员 Noah Golmant 发表博客,从理论的角度分析了损失函数的结构,并据此解释随机梯度下降(SGD)中的噪声如何帮助避免局部极小值和鞍点,为设计和改良深度学习架构提供了很有用的参考视角。

当我们着手训练一个很酷的机器学习模型时,最常用的方法是随机梯度下降法(SGD)。随机梯度下降在高度非凸的损失表面上远远超越了朴素梯度下降法。这种简单的爬山法技术已经主导了现代的非凸优化。然而,假的局部最小值和鞍点的存在使得分析工作更加复杂。理解当去除经典的凸性假设时,我们关于随机梯度下降(SGD)动态的直觉会怎样变化是十分关键的。向非凸环境的转变催生了对于像动态系统理论、随机微分方程等框架的使用,这为在优化解空间中考虑长期动态和短期随机性提供了模型。

在这里,我将讨论在梯度下降的世界中首先出现的一个麻烦:噪声随机梯度下降和朴素梯度下降之间唯一的区别是:前者使用了梯度的噪声近似。这个噪声结构最终成为了在背后驱动针对非凸问题的随机梯度下降算法进行「探索」的动力。

mini-batch 噪声的协方差结构

介绍一下我们的问题设定背景。假设我想要最小化一个包含 N 个样本的有限数据集上的损失函数 f:R^n→R。对于参数 x∈R^n,我们称第 i 个样本上的损失为 f_i(x)。现在,N 很可能是个很大的数,因此,我们将通过一个小批量估计(mini-batch estimate)g_B: 来估计数据集的梯度 g_N:。其中,B⊆{1,2,…,N} 是一个大小为 m 的 mini-batch。尽管 g_N 本身就是一个关于梯度 ∇f(x) 的带噪声估计,结果表明,mini-batch 抽样可以生成带有有趣的协方差结构的估计。 

引理 1 (Chaudhari & Soatto 定理:https://arxiv.org/abs/1710.11029):在回置抽样(有放回的抽样)中,大小为 m 的 mini-batch 的方差等于 Var(g_B)=1/mD(x),其中

该结果意味着什么呢?在许多优化问题中,我们根本的目标是最大化一些参数配置的似然。因此,我们的损失是一个负对数似然。对于分类问题来说,这就是一个交叉熵。在这个例子中,第一项  是对于(负)对数似然的梯度的协方差的估计。这就是观测到的 Fisher 信息。当 N 趋近于正无穷时,它就趋向于一个 Fisher 信息矩阵,即相对熵(KL 散度)的 Hessian 矩阵。但是 KL 散度是一个与我们想要最小化的交叉熵损失(负对数似然)相差甚远的常数因子。

因此,mini-batch 噪声的协方差与我们损失的 Hessian 矩阵渐进相关。事实上,当 x 接近一个局部最小值时,协方差就趋向于 Hessian 的缩放版本。

绕道 Fisher 信息

在我们继续详细的随机梯度下降分析之前,让我们花点时间考虑 Fisher 信息矩阵 I(x) 和 Hessian 矩阵 ∇^2f(x) 之间的关系。I(x) 是对数似然梯度的方差。方差与损失表面的曲率有什么关系呢?假设我们处在一个严格函数 f 的局部最小值,换句话说,I(x∗)=∇^2f(x∗) 是正定的。I(x) 引入了一个 x∗附近的被称为「Fisher-Rao metric」的度量指标: d(x,y)=√[(x−y)^TI(x∗)(x−y) ]。有趣的是,参数的 Fisher-Rao 范数提供了泛化误差的上界(https://arxiv.org/abs/1711.01530)。这意味着我们可以对平坦极小值的泛化能力更有信心。

回到这个故事中来

接下来我们介绍一些关于随机梯度下降动态的有趣猜想。让我们做一个类似中心极限定理的假设,并且假设我们可以将估计出的 g_B 分解成「真实」的数据集梯度和噪声项:g_B=g_N+(1√B)n(x),其中 n(x)∼N(0,D(x))。此外,为了简单起见,假设我们已经接近了极小值,因此 D(x)≈∇^2f(x)。n(x) 在指数参数中有一个二次形式的密度ρ(z):

这表明,Hessian 矩阵的特征值在决定被随机梯度下降认为是「稳定」的最小值时起重要的作用。当损失处在一个非常「尖锐」(二阶导很大)的最小值,并且此处有许多绝对值大的、正的特征值时,我很可能会加入一些把损失从朴素梯度下降的吸引域中「推出来」的噪声。类似地,对于平坦极小值,损失更有可能「稳定下来」。我们可以用下面的技巧做到这一点:

引理 2:令 v∈R^n 为一个均值为 0 并且协方差为 D 的随机向量。那么,E[||v||^2]=Tr(D)。

通过使用这一条引理以及马尔可夫不等式,我们可以看到,当 Hessian 具有大曲率时,更大扰动的可能性越高。我们还可以考虑一个在局部最小值 x∗ 周围的「稳定半径」:对于给定的 ϵ∈(0,1),存在一些 r(x∗)>0,使得如果我们的起点 x_0 满足 ||x_0−x∗||<r(x∗),第 t 次迭代满足 ||x_t−x∗||<r(对于所有的 t≥0)的概率至少为 1−ϵ。在这种情况下,我们可以说 x∗ 是在半径 r(x∗) 内随机稳定的。将这种稳定性的概念与我们之前的非正式论证结合起来,我们得到以下结论:

定理 1: 一个严格的局部最小值 x∗ 的稳定性半径 r(x∗) 与 ∇^2f(x∗) 的谱半径成反比。

让我们把这个结论和我们所知道的 Fisher 信息结合起来。如果在随机梯度下降的动态下,平坦极小值更加稳定,这就意味着随机梯度下降隐式地提供了一种正则化的形式。它通过注入各项异性的噪声使我们摆脱了 Fisher-Rao 范数所带来的不利泛化条件。

深度学习的启示:Hessian 矩阵的退化和「wide valleys」

深度学习中,一个有趣的现象是过度参数化。我们经常有比做示例运算时更多的参数(d>>N)。这时,D(x) 是高度退化的,即它有许多零(或者接近零)的特征值。这意味着损失函数在很多方向上都是局部不变的。这为这些网络描绘了一个有趣的优化解空间中的场景:随机梯度下降大部分时间都在穿越很宽的「峡谷」(wide valleys)。噪声沿着几个有大曲率的方向传播,这抵消了 g_N 朝着这个「峡谷」的底部(损失表面的最小值)推进的趋势。

当前关注点:批量大小、学习率、泛化性能下降

由于我们在将 n(x) 加到梯度之前,按照 1/√m 的因子将其进行缩放,因此增加了批处理的规模,降低了小批量估计的整体方差。这是一个值得解决的问题,因为大的批量尺寸可以使模型训练得更快。它在两个重要的方面使得训练更快:训练误差在更少的梯度更新中易于收敛,并且大的批量尺寸使得我们能利用大规模数据并行的优势。但是,不使用任何技巧就增大批量尺寸会导致测试误差增大。这个现象被称为泛化能力下降(generalization gap),并且目前还存在一些为什么会出现这种情况的假说。一个流行的解释是,我们的「探索性噪声」不再有足够的力量将我们推出一个尖锐最小值的吸引域。一种解决办法是简单地提高学习率,以增加这种噪声的贡献。这种缩放规则非常成功(https://arxiv.org/abs/1706.02677)。

长期关注点:逃离鞍点

虽然泛化能力下降「generalization gap」最近已经成为了一个热门话题,但之前仍有很多工作研究鞍点的影响。虽然不会渐进收敛到鞍点(http://noahgolmant.com/avoiding-saddle-points.html),我们仍然可能附近停留相当长的一段时间(https://arxiv.org/abs/1705.10412)。而且尽管大的批量尺寸似乎会更易于产生更尖锐的最小值,但真正大的批量尺寸会将我们引导到确定的轨迹上,这个轨迹被固定在鞍点附近。一项研究(https://arxiv.org/abs/1503.02101)表明,注入足够大的各项同性噪声可以帮助我们逃离鞍点。我敢打赌,如果噪声有足够的「放大」能力,小批量的随机梯度下降(mini-batch SGD)会在造成训练困难的维度上提供足够的噪声,并且帮助我们逃离它们。

一旦我们解决了「尖锐的最小值」的问题,鞍点可能是下一个大规模优化的主要障碍。例如,我在 CIFAR-10 数据集上用普通的随机梯度下降算法训练了 ResNet34。当我将批量尺寸增大到 4096 时,泛化能力下降的现象出现了。在这一点之后(我最高测试了大小为 32K 的批量尺寸,有 50K 个训练样本),性能显著降低:训练误差和测试误差都仅仅在少数几个 epoch 中比较平稳,并且网络无法收敛到一个有效解上。以下是这些结果的初步学习曲线(即看起来比较丑、还有待改进):

进一步的工作

目前提出的大多数处理尖锐的最小值/鞍点的解决方案都是围绕(a)注入各向同性噪声,或(b)保持特定的「学习率和批量尺寸」。我认为从长远来看,这还不够。各向同性噪声在包含「wide valley」结构的解空间中做的并不好。增加学习率也增大了对梯度的更新,这使得权重更新得更大。我认为正确的方法应该是想出一种有效的方法来模拟小批量噪声的各向异性,这种方法从学习率和批处理大小的组合中「解耦」出来。存在能够使用子采样梯度信息和 Hessian 向量乘积去做到这一点的方法,我正在进行这个实验。我很希望听听其它的关于如何解决这个问题的想法。与此同时,我们还需要做大量的理论工作来更详细地理解这种动态,特别是在一个深度学习环境中。


原文链接:http://noahgolmant.com/sgd-noise.html

理论随机梯度下降鞍点
2
相关数据
深度学习技术

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

范数技术

范数(norm),是具有“长度”概念的函数。在线性代数、泛函分析及相关的数学领域,是一个函数,其为向量空间内的所有向量赋予非零的正长度或大小。半范数反而可以为非零的向量赋予零长度。

权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

交叉熵技术

交叉熵(Cross Entropy)是Loss函数的一种(也称为损失函数或代价函数),用于描述模型预测值与真实值的差距大小

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

学习曲线技术

在机器学习领域,学习曲线通常是表现学习准确率随着训练次数/时长/数据量的增长而变化的曲线

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

凸优化技术

凸优化,或叫做凸最优化,凸最小化,是数学最优化的一个子领域,研究定义于凸集中的凸函数最小化的问题。凸优化在某种意义上说较一般情形的数学最优化问题要简单,譬如在凸优化中局部最优值必定是全局最优值。凸函数的凸性使得凸分析中的有力工具在最优化问题中得以应用,如次导数等。 凸优化应用于很多学科领域,诸如自动控制系统,信号处理,通讯和网络,电子电路设计,数据分析和建模,统计学(最优化设计),以及金融。在近来运算能力提高和最优化理论发展的背景下,一般的凸优化已经接近简单的线性规划一样直捷易行。许多最优化问题都可以转化成凸优化(凸最小化)问题,例如求凹函数f最大值的问题就等同于求凸函数 -f最小值的问题。

学习率技术

在使用不同优化器(例如随机梯度下降,Adam)神经网络相关训练中,学习速率作为一个超参数控制了权重更新的幅度,以及训练的速度和精度。学习速率太大容易导致目标(代价)函数波动较大从而难以找到最优,而弱学习速率设置太小,则会导致收敛过慢耗时太长

损失函数技术

在数学优化,统计学,计量经济学,决策理论,机器学习和计算神经科学等领域,损失函数或成本函数是将一或多个变量的一个事件或值映射为可以直观地表示某种与之相关“成本”的实数的函数。

梯度下降技术

梯度下降是用于查找函数最小值的一阶迭代优化算法。 要使用梯度下降找到函数的局部最小值,可以采用与当前点的函数梯度(或近似梯度)的负值成比例的步骤。 如果采取的步骤与梯度的正值成比例,则接近该函数的局部最大值,被称为梯度上升。

随机梯度下降技术

梯度下降(Gradient Descent)是遵循成本函数的梯度来最小化一个函数的过程。这个过程涉及到对成本形式以及其衍生形式的认知,使得我们可以从已知的给定点朝既定方向移动。比如向下朝最小值移动。 在机器学习中,我们可以利用随机梯度下降的方法来最小化训练模型中的误差,即每次迭代时完成一次评估和更新。 这种优化算法的工作原理是模型每看到一个训练实例,就对其作出预测,并重复迭代该过程到一定的次数。这个流程可以用于找出能导致训练数据最小误差的模型的系数。

噪音技术

噪音是一个随机误差或观测变量的方差。在拟合数据的过程中,我们常见的公式$y=f(x)+\epsilon$中$\epsilon$即为噪音。 数据通常包含噪音,错误,例外或不确定性,或者不完整。 错误和噪音可能会混淆数据挖掘过程,从而导致错误模式的衍生。去除噪音是数据挖掘(data mining)或知识发现(Knowledge Discovery in Database,KDD)的一个重要步骤。

中心极限定理技术

中心极限定理是概率论中的一组定理。中心极限定理说明,在适当的条件下,大量相互独立随机变量的均值经适当标准化后依分布收敛于正态分布。这组定理是数理统计学和误差分析的理论基础,指出了大量随机变量之和近似服从正态分布的条件。

分类问题技术

分类问题是数据挖掘处理的一个重要组成部分,在机器学习领域,分类问题通常被认为属于监督式学习(supervised learning),也就是说,分类问题的目标是根据已知样本的某些特征,判断一个新的样本属于哪种已知的样本类。根据类别的数量还可以进一步将分类问题划分为二元分类(binary classification)和多元分类(multiclass classification)。

规范化技术

规范化:将属性数据按比例缩放,使之落入一个小的特定区间,如-1.0 到1.0 或0.0 到1.0。 通过将属性数据按比例缩放,使之落入一个小的特定区间,如0.0到1.0,对属性规范化。对于距离度量分类算法,如涉及神经网络或诸如最临近分类和聚类的分类算法,规范化特别有用。如果使用神经网络后向传播算法进行分类挖掘,对于训练样本属性输入值规范化将有助于加快学习阶段的速度。对于基于距离的方法,规范化可以帮助防止具有较大初始值域的属性与具有较小初始值域的属相相比,权重过大。有许多数据规范化的方法,包括最小-最大规范化、z-score规范化和按小数定标规范化。

相对熵技术

相对熵(relative entropy)又称为KL散度(Kullback–Leibler divergence,简称KLD)[1],信息散度(information divergence),信息增益(information gain)。 KL散度是两个概率分布P和Q差别的非对称性的度量。 KL散度是用来 度量使用基于Q的编码来编码来自P的样本平均所需的额外的位元数。 典型情况下,P表示数据的真实分布,Q表示数据的理论分布,模型分布,或P的近似分布。

推荐文章
暂无评论
暂无评论~