Simon S. Du等作者

烧脑!CMU、北大等合著论文真的找到了神经网络的全局最优解

一直以来,我们都不知道为什么深度神经网络的损失能降到零,降到零不代表着全局最优了么?这不是和一般 SGD 找到的都是局部极小点相矛盾么?最近 CMU、北大和 MIT 的研究者分析了深层全连接网络和残差网络,并表示使用梯度下降训练过参数化的深度神经网络真的能找到全局最优解。

用一阶方法训练的神经网络已经对很多应用产生了显著影响,但其理论特性却依然是个谜。一个经验观察是,即使优化目标函数是非凸和非平滑的,随机初始化的一阶方法(如随机梯度下降)仍然可以找到全局最小值(训练损失接近为零),这是训练中的第一个神秘现象。令人惊讶的是,这个特性与标签无关。在 Zhang 等人的论文 [2016] 中,作者用随机生成的标签取代了真正的标签,但仍发现随机初始化的一阶方法总能达到零训练损失。

人们普遍认为过参数化是导致该现象的主要原因,因为神经网络只有具备足够大的容量时才能拟合所有训练数据。实际上,很多神经网络架构都高度过参数化。例如,宽残差网络(Wide Residual Network)的参数量是训练数据的 100 倍。

训练深度神经网络的第二个神秘现象是「更深的网络更难训练。」为了解决这个问题,何恺明等人在 2016 年提出了深度残差网络(ResNet)架构,用随机梯度下降方法来训练显著具有更多层数的神经网络。理论上来说,Hardt 和 Ma [2016] 表明,线性网络中的残差连接可以阻止梯度消失为零,但使用非线性激活函数神经网络还无法利用残差连接的优势。

在本文中,作者将揭开这两个神秘现象的面纱。具体而言,作者们从理论上分析了损失函数梯度下降上的收敛情况,即采用全连接网络和残差网络架构下的损失函数收敛情况。作者关注根据欧式距离定义的损失函数,并假设激活函数是 Lipschitz 和平滑的。这种假设适用于很多激活函数,包括 soft-plus。本文贡献如下:

首先考虑全连接前馈网络。作者表明,如果层级的神经元数量,则随机初始化的梯度下降会以线性速率收敛到零训练损失。

接下来考虑 ResNet 架构。作者表明,只要中间层的宽度 m = Ω (poly(n, H)),则随机初始化的梯度下降会以线性速率收敛到零训练损失。与第一个结果相比,ResNet 对网络层数的依赖呈指数级上升。该理论阐明了利用残差连接的优势。

最后,作者利用同样的技术来分析卷积 ResNet。作者表明,如果 m = poly(n, p, H),其中 p 是图像块数量,则随机初始化的梯度下降会达到零训练损失。

本文的证明是基于以前关于双层神经网络梯度下降研究中的两个重要概念。第一个是 Du 等人 [2018b] 提出的概念,本文作者分析了神经网络预测的动力学特征,即其收敛性由格拉姆矩阵(Gram matrix)的最小特征值决定。为了降低最小特征值的下界,从初始化开始限制每个权重矩阵的距离就足够了。其次,作者利用了 Li 和 Liang [2018] 的观察结果,即如果神经网络参数化,则每个权重矩阵接近其初始化。与前两个研究不同,本文在分析深度神经网络时,需要构建更多深度神经网络的架构属性和新技术。在本文中,我们主要介绍了 ResNet 的分析结果,更详细的证明展示在原论文中的 29 页附录中。

论文:Gradient Descent Finds Global Minima of Deep Neural Networks

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

摘要:在训练深度神经网络时,即使目标函数是非凸的,梯度下降法也能找到全局最小值。本文证明了对于具有残差连接的深度超参数神经网络(ResNet),梯度下降可以在多项式时间内实现零训练损失。我们的分析依赖于神经网络架构引入的格拉姆矩阵的多项式结构。这种结构帮助我们证明格拉姆矩阵在训练过程中的稳定性,而且这种稳定性意味着梯度下降算法的全局最优性。我们的边界也揭示了使用 ResNet 优于全连接前馈架构的优点;对于前馈网络,我们的边界要求每层神经元的数量随深度进行指数缩放,而对于 ResNet,边界只要求每层神经元的数量随深度进行多项式缩放。我们还进一步将自己的分析扩展到深度残差卷积神经网络并得到了类似的收敛结果。

本文结构:第二节正式介绍了问题背景;第三节给出了在深度全连接神经网络上得到的主要结果;第四节给出了在 ResNet 上得到的主要结果;第五节给出了在卷积 ResNet 上得到的主要结果;第六节为以上三种架构提供了一个统一的证明策略。第 7 节为总结,证明见附录。

在论文的后面的章节中,大部分都在描述假设与推理。尤其在后面 29 页的附录中,作者给出了各推理的完整的证明。如果读者自信数学底子比较硬朗的话,可以查阅原论文了解详细推导过程,本文后面只简要介绍了 ResNet 的分析结果。

ResNet 的主要分析结果

在这一章节中,作者主要会考虑使用梯度下降训练 ResNet 的收敛性,并关注到底需要多大程度的过参数化才能确保梯度下降收敛到全局最优解。当然在这之前需要明确 ResNet 的形式化定义是什么样的。在这篇论文中,作者们主要分析了不同神经网络的经验风险最小化问题,其中损失函数由一般的欧式距离定义:

这个式子很容易理解,w 是神经网络所有的权重,x 为输入样本(如图像)、y 为样本的对应标注。在实践中,f(w, x_i) 表示的就是一个完整的残差网络(ResNet),我们希望利用梯度下降一步步调整 ResNet 中的权重 w,进而获得经过训练的 ResNet。从形式化上来说,ResNet 或 f(w, x_i) 函数可以表示为如下方程式:

其中 x^(1) 表示输入图像 x 经第一个卷积层得出的特征图(feature map),c_σ为初始化阶段中归一化输入的缩放因子,这里并没有详细展示 c_σ的表达式,详情可查看原论文。此外,σ表示一般的激活函数,且作者假设算出来的中间层(x)都是方阵。在 x^(h) 中,作者形式化定义了残差第 h 个残差模块的输出,它会通过残差连接将 h-1 层的输出加上当前层的输出。x^(h) 后面σ左边比较复杂的表达式展示了这一层级的缩放因子,它们具体是什么可以查阅原论文。

最后的 f_res(x, w) 则表示了残差网络的最终表达式,即最后一个残差模块的输出做一个简单的反射变换。因此为了分析 ResNet 的收敛情况,作者定义了总体格莱姆矩阵,即对于所有 (i, j) ∈ [n] × [n],我们有:

直观上而言,K^(h) 表示了在经过复合 h 次核函数后所得到的格莱姆矩阵(Gram matrix),其中核函数都是由激活函数σ所定义。此外,当权重矩阵的长和宽 m 趋向于无穷大时,它们会渐进格莱姆矩阵。因此作者做了以下假设以决定收敛率和过参数化总量:

注意 λ 在这里仅依赖于 K^(0),因此它的定义与全连接网络中的不太一样。一般而言,除非两个数据点是平行的,否则λ通常都是正数。在有了这个假设以后,作者给出了他们对 ResNet 的主要定理:

与全连接网络中得出的定理不同,定理 4.1 完全是多项式形式的,因为神经元数量和收敛率都是关于 n 和 H 的多项式,所以作者根据分析结果表明经典多层全连接架构和 ResNet 架构是有显著差别的。作者在这里并没有使用任何指数因子,其主要原因是残差连接块使得整个架构在初始化阶段和训练阶段都更加稳定。

以上只是 ResNet 分析所获得的结果,更多分析和推导过程都在原论文中。作者最后表示过参数化网络上实现的梯度下降能获得零训练损失,且证明的关键技术是表明格莱姆矩阵在过参数化的情况下会越来越稳定,因此下降的每一步都会以几何速率减少损失,并最终收敛到全局最优解。

理论最优化MIT北京大学CMU神经网络
62
相关数据
何恺明人物

Facebook AI Research研究科学家。Residual Net提出者。

激活函数技术

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

权重技术

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

核函数技术

核函数包括线性核函数、多项式核函数、高斯核函数等,其中高斯核函数最常用,可以将数据映射到无穷维,也叫做径向基函数(Radial Basis Function 简称 RBF),是某种沿径向对称的标量函数。最常应用于SVM支持向量机中

参数技术

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

收敛技术

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

损失函数技术

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

超参数技术

在机器学习中,超参数是在学习过程开始之前设置其值的参数。 相反,其他参数的值是通过训练得出的。 不同的模型训练算法需要不同的超参数,一些简单的算法(如普通最小二乘回归)不需要。 给定这些超参数,训练算法从数据中学习参数。相同种类的机器学习模型可能需要不同的超参数来适应不同的数据模式,并且必须对其进行调整以便模型能够最优地解决机器学习问题。 在实际应用中一般需要对超参数进行优化,以找到一个超参数元组(tuple),由这些超参数元组形成一个最优化模型,该模型可以将在给定的独立数据上预定义的损失函数最小化。

神经网络技术

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

深度残差网络技术

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

梯度下降技术

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

卷积神经网络技术

卷积神经网路(Convolutional Neural Network, CNN)是一种前馈神经网络,它的人工神经元可以响应一部分覆盖范围内的周围单元,对于大型图像处理有出色表现。卷积神经网路由一个或多个卷积层和顶端的全连通层(对应经典的神经网路)组成,同时也包括关联权重和池化层(pooling layer)。这一结构使得卷积神经网路能够利用输入数据的二维结构。与其他深度学习结构相比,卷积神经网路在图像和语音识别方面能够给出更好的结果。这一模型也可以使用反向传播算法进行训练。相比较其他深度、前馈神经网路,卷积神经网路需要考量的参数更少,使之成为一种颇具吸引力的深度学习结构。 卷积网络是一种专门用于处理具有已知的、网格状拓扑的数据的神经网络。例如时间序列数据,它可以被认为是以一定时间间隔采样的一维网格,又如图像数据,其可以被认为是二维像素网格。

随机梯度下降技术

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

目标函数技术

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

神经元技术

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

深度神经网络技术

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

推荐文章
机器之心・CEO
读者匿名评论:读者参数超过数据量的情况下,本来优化就容易(注:有更强的理论结果),而本文要求的参数远超过必须的量;条件3.1极其的强,一个gram矩阵当然是半正定,但很难保证正定,本文直接就假设其成立,证明就没那么难了。本文做出了一定贡献,但结果不强,离解决问题还很远,容易误导。
这篇文章是11月才出的,但是实际上微软的朱泽园他们10月就有更好的的结果了。 这是微软他们10月文章的link:https://arxiv.org/pdf/1810.12065.pdf 这是微软他们11月文章link:https://arxiv.org/pdf/1811.03962.pdf 10月那篇文章主要是处理RNN。11月那篇文章就是处理一般的DNN。11月这篇相对10那篇简单很多,听说他们本来不打算写的,但是好像很多人觉得RNN不是多层的,所以他们就又写了一篇。 简单总结下微软组和这篇文章的区别。 如果L是number of layers, m 是number of hidden nodes, 微软组证明的只要m>poly(L), 用SGD就可以把模型train到global optimal。而杜的这篇文章做出了相似的结果,但是需要m>2^O(L),跟微软的结果相比是trivial的。
1