找到神经网络的全局最小值到底有多难?

数天前,机器之心发布了 Simon S. Du 等人的论文Gradient Descent Finds Global Minima of Deep Neural Networks》引起了大家激烈的讨论。对此论文,读者们褒贬不一。此外,机器之心通过读者留言了解到微软研究院 Zeyuan Allen-Zhu、斯坦福 Yuanzhi Li、德州大学奥斯汀分校 Zhao Song(共同一作)稍微早些时候也发布了一篇类似的论文,但有更好的结果。后经沟通联系,机器之心对微软的这篇论文进行了跟进报道,希望能为读者提供更全面的内容参考,更好的理解两篇论文。

在细致解读微软研究院的这篇论文之前,读者们可以先了解下微软这篇论文与 Simon S. Du 等人论文的对比(详见微软这篇论文的第二页)。

最重要的区别是,Simon Du 等人证明了全连接深度网络(非 ResNet)的收敛时间关于层数 L 的依赖是不超过指数级别 2^O(L) 的,而残差网络(ResNet)是多项式级别 poly(L) 的。Simon Du 等人因此给出理论依据,判断 ResNet 的收敛性更好。本文作者指出,这样的推断是逻辑错误的,因为本文证明了全连接网络也同样在多项式级别 poly(L) 时间内收敛(所以 Simon Du 等人文中的「不超过指数」,其实是和残差网络一样的多项式)。也就是说,ResNet 相对于非 ResNet 的优势,实际上有更深层的原因,而不是像 Simons Du 文章里声称的,是指数和多项式的区别。两篇文章的其它的区别包括,Simon Du 等的人的结果,隐藏了其它的可能指数级别的参数,以及 Simon Du 的结果不能处理最常用的 ReLU 激活函数,等等。

微软的这篇论文是基于 [Li-Liang 2018] 在今年 NIPS 2018 上发表的一个深度延伸。Li 和 Liang 证明了只有一个隐藏层的神经网络,在过参数化的情况下可以找到全局最优。至于多层网络,需要开发更多的理论技术。一个具体的例子是这样的。假设训练数据不退化(相对距离为δ),那么如何证明数据传递到了最后一层,也不会发生退化?这篇论文证明了,只要过参数化(引理 4.5),那么样本传递到最后一层,相对距离依然可以有δ\/2。

下面是对微软研究院这篇论文的技术介绍:

论文:A Convergence Theory for Deep Learning via Over-Parameterization

论文地址:https://arxiv.org/pdf/1811.03962.pdf

摘要:深层神经网络(DNN)已在许多领域表现出主导性能;自 AlexNet 以来,实践中使用的神经网络越来越深,越来越宽。然而在理论方面,前人大部分的工作在关注为什么我们可以训练只有一个隐藏层的神经网络。多层网络的理论仍然不明确。

在这项工作中,我们证明了为什么常用的算法,比如随机梯度下降(SGD),可以在多项式时间内找到 DNN 训练的全局最优解。我们只做两个假设:输入数据不退化,和网络过参数化。前者意味着输入不存在两个相同的数据点有矛盾的标签;后者意味着隐藏神经元的数量足够多,也就是关于层数 L,以及样本数量 n 都是多项式级别。

作为一个具体示例,在训练集上从随机初始的权重开始,我们证明了在关于 n 和 L 的多项式时间内,SGD 就可以在分类任务中达到了 100%的准确率,也就是找到全局最优解。我们的理论可适用于最常用的 ReLU 激活函数,适用于任何光滑甚至非凸的损失函数。在网络架构方面,我们的理论至少可以适用于全连接网络,卷积网络(CNN)和残差网络(ResNet)。

神经网络在众多机器学习任务中取得了巨大成功。其中一项实验结果表明,通过随机初始化的一阶方法训练的神经网络,具有非常强的拟合训练数据的能力。从容量的角度来看,拟合训练数据的能力可能并不令人惊讶:现代神经网络总是过参数化,它们具有远多于训练样本总数的参数。因此,理论上,只要数据不退化,总会存在实现零训练误差的参数选择。

然而,从优化的角度来看,一阶方法可以在训练数据上找到全局最优解这事情「非常不简单」。大家常用的神经网络通常配备 ReLU 激活函数,这使得神经网络不仅是非凸的,甚至非光滑。与之相对的是,优化理论中,如何找到非凸、非平滑函数的哪怕是一阶、二阶临界点的收敛性也是不明确的 [Burke, 2005],更不用提全局最优解。那么,实际训练中,随机梯度下降法(SGD)是如何在含有 ReLU 的深度神经网络中,收敛到全局最小值的呢?


这篇文章证明了,不管是全连接的深度前馈网络,是深度卷积网络 (CNN),还是深度残差网络 (ResNet),假设深度为 L,假设训练样本有 n 个,只要样本不退化——也就是任意两个样本之间的相对距离超过δ——那么只要神经元数量超过,随机初始化后的 SGD 算法就可以在多项式时间内找到全局最优解。这里「找到全局最优解」的定义取决于具体任务,如果是分类问题,那么就是在 多项式时间内得到 100% 正确率;如果是拟合问题,就是在 多项式时间内找到拟合残差为ε的解。后者被称为线性收敛速率。

细节

这篇文章的细节其实可以由如下两个简单的定理和图片概括(文中 Sec 3.1)。假设损失函数是平方拟合(l_2 regression loss)

文中定理 3(没有马鞍点):在一定条件下(比如 SGD 的移动路径上),神经网络目标函数的梯度模长的平方,大于目标函数值本身,除以一个多项式因子:

定理 3 说了一件很简单的事情,就是只要没有达到全局最优,那么函数梯度就一定大于零,并且函数越大,梯度的模长就越大。换言之,在 SGD 的移动路径上,只要训练损失 (training loss) 不到 0,就不会出现马鞍点,更不会出现局部最小值。这个结果本身就很特殊,因为大部分的非凸问题不满足这个性质,而过度参数化的神经网络,用 SGD 进行训练,却可以保证得到这个性质!

有了定理 3,就可以证明 SGD 收敛了么?并没有,因为如果 SGD 向梯度的反方向移动,为什么函数值会下降?「函数值会下降」在优化理论中对应了光滑性 (smoothness)。传统的优化理论中有很多关于光滑性的定义,但都需要函数至少二阶可导(可惜 ReLU 激活函数并不存在二阶导数)。这篇文章的另一个精髓,在于证明了过度参数化的神经网络满足以下的一个「半光滑性」。

文中定理 4(半光滑性):在一定条件下(比如 SGD 的移动路径上),神经网络目标函数和其一阶近似之间的距离「很小」:

与传统光滑性不同的是,这里不等式的右边有一个关于‖ΔW‖的一阶项,文中说明,这个一阶项会随着神经元数量越来越多,变得越来越小。也就是网络参数越多,会越「光滑」,也就越容易做训练。

为了理解定理 3 和定理 4,我们可以参见文中的图片。当目标函数值在 1.3(并没有到全局最优)的时候,函数的梯度很大(定理 3),并且向梯度方向走,的确可以有效地降低目标函数值(定理 4)。

延伸

本文中关于 SGD 收敛性的证明,停留在了前馈网络(包括 CNN,ResNet 等),那么是否可以扩展到其它的更复杂的深度学习网络呢?例如在自然语言处理应用中广泛使用的递归神经网络(RNN)?作者强调了 RNN 其实是一个比 DNN 更难的问题(第三页)。在两周前,本文的作者将这个问题单独成稿,发表在了 arXiv 上(链接:https://arxiv.org/abs/1810.12065)。

目前提到的多层网络收敛性都是针对训练数据找全局最优。那么如何推广到测试数据集呢?这篇文章并没有涉及,但是在第三页援引了一个同样是这周传到 arXiv 的重要工作 [Allen-Zhu, Li, Liang 2018]:证明了过度参数化的三层神经网络的训练集最优解可以推广到测试集!具体而言,如果数据是由一个未知的三层神经网络产生的,那么使用过参数化的三层神经网络,和 SGD 进行训练,只要多项式级别那么多样本,就可以学出能在测试集上完成比如分类、拟合问题的未知网络。这个结果是对本文的一个很好的补充(链接:https://arxiv.org/abs/1811.04918)。 

理论SGDCNNarXiv
2
相关数据
深度学习技术

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

激活函数技术

在 计算网络中, 一个节点的激活函数定义了该节点在给定的输入或输入的集合下的输出。标准的计算机芯片电路可以看作是根据输入得到"开"(1)或"关"(0)输出的数字网络激活函数。这与神经网络中的线性感知机的行为类似。 一种函数(例如 ReLU 或 S 型函数),用于对上一层的所有输入求加权和,然后生成一个输出值(通常为非线性值),并将其传递给下一层。

权重技术

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

机器学习技术

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

参数技术

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

收敛技术

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

损失函数技术

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

导数技术

导数(Derivative)是微积分中的重要基础概念。当函数y=f(x)的自变量x在一点x_0上产生一个增量Δx时,函数输出值的增量Δy与自变量增量Δx的比值在Δx趋于0时的极限a如果存在,a即为在x0处的导数,记作f'(x_0) 或 df(x_0)/dx。

神经网络技术

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

深度残差网络技术

残差网络是为了解决深度神经网络(DNN)隐藏层过多时的网络退化问题而提出。退化(degradation)问题是指:当网络隐藏层变多时,网络的准确度达到饱和然后急剧退化,而且这个退化不是由于过拟合引起的。

梯度下降技术

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

准确率技术

分类模型的正确预测所占的比例。在多类别分类中,准确率的定义为:正确的预测数/样本总数。 在二元分类中,准确率的定义为:(真正例数+真负例数)/样本总数

随机梯度下降技术

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

逻辑技术

人工智能领域用逻辑来理解智能推理问题;它可以提供用于分析编程语言的技术,也可用作分析、表征知识或编程的工具。目前人们常用的逻辑分支有命题逻辑(Propositional Logic )以及一阶逻辑(FOL)等谓词逻辑。

Alex网络技术

AlexNet是一个卷积神经网络的名字,最初是与CUDA一起使用GPU支持运行的,AlexNet是2012年ImageNet竞赛冠军获得者Alex Krizhevsky设计的。该网络达错误率大大减小了15.3%,比亚军高出10.8个百分点。AlexNet是由SuperVision组设计的,由Alex Krizhevsky, Geoffrey Hinton和Ilya Sutskever组成。

目标函数技术

目标函数f(x)就是用设计变量来表示的所追求的目标形式,所以目标函数就是设计变量的函数,是一个标量。从工程意义讲,目标函数是系统的性能标准,比如,一个结构的最轻重量、最低造价、最合理形式;一件产品的最短生产时间、最小能量消耗;一个实验的最佳配方等等,建立目标函数的过程就是寻找设计变量与目标的关系的过程,目标函数和设计变量的关系可用曲线、曲面或超曲面表示。

分类问题技术

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

神经元技术

(人工)神经元是一个类比于生物神经元的数学计算模型,是神经网络的基本组成单元。 对于生物神经网络,每个神经元与其他神经元相连,当它“兴奋”时会向相连的神经元发送化学物质,从而改变这些神经元的电位;神经元的“兴奋”由其电位决定,当它的电位超过一个“阈值”(threshold)便会被激活,亦即“兴奋”。 目前最常见的神经元模型是基于1943年 Warren McCulloch 和 Walter Pitts提出的“M-P 神经元模型”。 在这个模型中,神经元通过带权重的连接接处理来自n个其他神经元的输入信号,其总输入值将与神经元的阈值进行比较,最后通过“激活函数”(activation function)产生神经元的输出。

自然语言处理技术

自然语言处理(英语:natural language processing,缩写作 NLP)是人工智能和语言学领域的分支学科。此领域探讨如何处理及运用自然语言;自然语言认知则是指让电脑“懂”人类的语言。自然语言生成系统把计算机数据转化为自然语言。自然语言理解系统把自然语言转化为计算机程序更易于处理的形式。

深度神经网络技术

深度神经网络(DNN)是深度学习的一种框架,它是一种具备至少一个隐层的神经网络。与浅层神经网络类似,深度神经网络也能够为复杂非线性系统提供建模,但多出的层次为模型提供了更高的抽象层次,因而提高了模型的能力。

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