全局最优解？为什么 SGD 能令神经网络的损失降到零
source link: https://www.jiqizhixin.com/articles/100703?amp%3Butm_medium=referral
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.
昨日，reddit 上一篇帖子引发热议，该帖介绍了一篇关于梯度下降对过参数化神经网络影响的论文，该论文只用单个非常宽的隐藏层，并证明了在一定条件下神经网络能收敛到非凸优化的全局最优解。这是对深度学习的复古？到底是否有效？社区中很多人对此发表了看法。机器之心简要介绍了该论文，更详细的推导过程与方法请查看原论文，不过这样的证明读者们都 Hold 住吗。
用一阶方法训练的神经网络已经对很多应用产生了显著影响，但其理论特性却依然成谜。一个经验观察是，即使优化目标函数是非凸和非平滑的，随机初始化的一阶方法（如 随机梯度下降 ）仍然可以找到全局最小值（训练损失接近为零）。令人惊讶的是，这个特性与标签无关。在 Zhang 等人的论文 [2016] 中，作者用随机生成的标签取代了真正的标签，但仍发现随机初始化的一阶方法总能达到零训练损失。
关于神经网络为什么能适应所有训练标签，人们普遍认为是因为神经网络过参数化了。例如，Wide ResNet [Zagoruyko and Komodakis] 使用的参数数量是训练数据的 100 倍，因此必须存在一个这种架构的神经网络，能够适应所有训练数据。然而，这并不能说明为什么由随机初始化的一阶方法找到的神经网络能够适应所有数据。目标函数是非凸和非平滑的，这使得传统的凸优化分析技术在这种情况下没有用。据我们所知，理论只能保证现有的方法收敛到一个驻点 [Davis et al., 2018]。
在本文中，作者将解释这一令人惊讶的现象，即带有修正线性单元（ReLU）激活函数的两层神经网络能收敛到全局最优解。形式化的，我们可以考虑有以下形式的神经网络：
其中 x ∈ R^d 为 d 维实数向量输入，w_r ∈ R^d 为第一层的权重向量，a_r ∈ R 为输出权重。此外，σ (·) 表示 ReLU激活函数：σ (z) = z if z ≥ 0、 σ (z) = 0 if z < 0。
随后我们可以根据二次损失函数（欧式距离）定义经验风险最小化问题，若给定 n 笔数据的训练集 {(x_1, y_1), ..., (x_i, y_i), ..., (x_n, y_n) }，我们希望最小化：
为了实现经验风险最小化，我们需要修正第二层并针对第一层的权重矩阵应用梯度下降（GD）：
其中η > 0 为学习率（在本论文中为步长），因此每一个权重向量的梯度计算式可以表示为：
尽管这只是一个浅层全连接网络，但由于使用了 ReLU激活函数，目标函数仍然是非凸和不平滑的。不过即使针对这样简单的目标函数，为什么随机初始化的一阶梯度方法能实现零的训练误差仍然不太清楚。实际上，许多先前的研究工作都在尝试回答这个问题。他们尝试的方法包括损失函数面貌分析、偏微分方程、算法动力学分析或最优传输理论等。这些方法或研究结果通常都依赖于标签和输入分布的强假设，或者并没有明示为什么随机初始化的一阶方法能实现零的训练损失。
在这一篇论文中，作者们严格证明了只要 m 足够大，且数据是非退化的，那么使用适当随机初始化的 a 和 W(0)，梯度下降能收敛到全局最优解，且收敛速度对于二次损失函数是线性的。线性速率也就是说模型能在 K = O(log (1/ε)) 次迭代内搜索到最优解 W(k)，它能令 L(W(K)) ≤ ε。因此，作者理论结果并不仅仅展示了全局收敛性，同时还为达到期望的准确率提供了量化的收敛率。
分析技术概览：
-
首先作者直接分析了每一次独立预测的动力学特征，即 f(W, a, x_i) for i = 1, . . . , n。他们发现预测空间的动力学是由格拉姆矩阵（Gram matrix）谱属性决定的，且只要格拉姆矩阵的最小特征值是下界，那么梯度下降就服从线性收敛速度。
-
其次作者观察到格拉姆矩阵仅和激活模式相关（ReLU 输入大于零的情况），因此他们就能使用矩阵微扰分析探索是否大多数的模式并没有改变，因此格拉姆矩阵仍然接近于初始化状态。
-
最后作者发现过参数化、随机初始化和线性收敛联合限制了权重向量 w_r 仍然接近于初始值。
最后作者根据这三个观察结果与方法严格证明了他们的论点，此外他们还表示整个证明仅使用了线性代数与标准概率边界，因此能推广到其它深度神经网络。以下我们展示了他们证明出的两个定理（Theorem 3.1 和 Theorem 4.1），证明过程请查阅原论文。
论文：Gradient DescentProvably Optimizes Over-parameterizedNeural Networks
论文链接：https://arxiv.org/abs/1810.02054
摘要：神经网络一个最神秘的地方是梯度下降等随机初始化的一阶优化方法能实现零的训练损失，即使目标函数是非凸和不平滑的。本论文揭秘了这一现象，即带有 ReLU激活函数的两层全连接网络为什么能实现零的训练损失。对于有 m 个隐藏神经元的浅层神经网络（ReLU激活函数）和 n 项训练数据，我们的实验表示只要 m 足够大，且数据是非退化的，那么随机初始化的梯度下降能收敛到全局最优解，且收敛速度对于二次损失函数是线性的。
我们的分析基于以下观察：过参数化和随机初始化联合限制了每一个权重向量在所有迭代中都接近于它的初始值，这令我们可以利用比较强的类凸属性，并展示梯度下降能以全局线性的速率收敛到全局最优解。我们相信这些观点同样能用于分析深度模型和其它一阶梯度优化方法。
3 连续型时间分析
本章展示了分析梯度流（gradient flow）的结果，即将步长设置为无穷小量的梯度下降。在后一部分的离散型时间分析中，我们将进一步修正这一部分的证明，并为带正下降步长的梯度下降设定一个定量边界。
形式化而言，我们考虑常微分方程，公式如下所示：
其中 r 属于 1 到 m。我们将 u_i(t) = f(W(t), a, x_i) 指定为输入 x_i 在时间 t 上的预测，u(t) = (u_1(t), . . . , u_n(t)) ∈ R^n 指定为时间 t 上的预测向量。本章的主要结果见以下定理：
4 离散型时间分析
本章展示了具有正常数项步长的随机初始化梯度下降以线性速率收敛到全局最小值。我们首先介绍主要定理：
定理 4.1 表明，即使目标函数是非平滑和非凸的，具有正常数步长的梯度下降仍然具有线性收敛速度。我们对最小特征值和隐藏节点数的假设与梯度流定理完全相同。值得注意的是，与之前的研究 [Li and Liang, 2018] 相比，我们对步长的选择与隐藏节点 m 的数量无关。
理论 优化算法 SGD 论文
相关数据
Activation function
在 计算网络中， 一个节点的激活函数定义了该节点在给定的输入或输入的集合下的输出。标准的计算机芯片电路可以看作是根据输入得到"开"(1)或"关"(0)输出的数字网络激活函数。这与神经网络中的线性感知机的行为类似。 一种函数（例如 ReLU 或 S 型函数），用于对上一层的所有输入求加权和，然后生成一个输出值（通常为非线性值），并将其传递给下一层。
Neural Network
（人工）神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型，那时候研究者构想了「感知器（perceptron）」的想法。这一领域的研究者通常被称为「联结主义者（Connectionist）」，因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型，它们都是前馈神经网络：卷积神经网络（CNN）和循环神经网络（RNN），其中 RNN 又包含长短期记忆（LSTM）、门控循环单元（GRU）等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习，但也有一些为无监督学习设计的变体，比如自动编码器和生成对抗网络（GAN）。
来源：机器之心
Convex optimization
凸优化，或叫做凸最优化，凸最小化，是数学最优化的一个子领域，研究定义于凸集中的凸函数最小化的问题。凸优化在某种意义上说较一般情形的数学最优化问题要简单，譬如在凸优化中局部最优值必定是全局最优值。凸函数的凸性使得凸分析中的有力工具在最优化问题中得以应用，如次导数等。 凸优化应用于很多学科领域，诸如自动控制系统，信号处理，通讯和网络，电子电路设计，数据分析和建模，统计学（最优化设计），以及金融。在近来运算能力提高和最优化理论发展的背景下，一般的凸优化已经接近简单的线性规划一样直捷易行。许多最优化问题都可以转化成凸优化（凸最小化）问题，例如求凹函数f最大值的问题就等同于求凸函数 -f最小值的问题。
来源： 维基百科
Deep neural network
深度神经网络（DNN）是深度学习的一种框架，它是一种具备至少一个隐层的神经网络。与浅层神经网络类似，深度神经网络也能够为复杂非线性系统提供建模，但多出的层次为模型提供了更高的抽象层次，因而提高了模型的能力。
来源：机器之心 Techopedia
Convergence
在数学，计算机科学和逻辑学中，收敛指的是不同的变换序列在有限的时间内达到一个结论（变换终止），并且得出的结论是独立于达到它的路径（他们是融合的）。 通俗来说，收敛通常是指在训练期间达到的一种状态，即经过一定次数的迭代之后，训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说，如果采用当前数据进行额外的训练将无法改进模型，模型即达到收敛状态。在深度学习中，损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变，暂时形成收敛的假象。
Learning rate
在使用不同优化器（例如随机梯度下降，Adam）神经网络相关训练中，学习速率作为一个超参数控制了权重更新的幅度，以及训练的速度和精度。学习速率太大容易导致目标（代价）函数波动较大从而难以找到最优，而弱学习速率设置太小，则会导致收敛过慢耗时太长
来源：Liu, T. Y. (2009). Learning to rank for information retrieval. Foundations and Trends® in Information Retrieval, 3(3), 225-331. Wikipedia
Gradient Descent
梯度下降是用于查找函数最小值的一阶迭代优化算法。 要使用梯度下降找到函数的局部最小值，可以采用与当前点的函数梯度（或近似梯度）的负值成比例的步骤。 如果采取的步骤与梯度的正值成比例，则接近该函数的局部最大值，被称为梯度上升。
来源：Vapnik V. N. (2000). The Nature of Statistical Learning Theory. Information Science and Statistics. Springer-Verlag. Wikipedia
Loss function
在数学优化，统计学，计量经济学，决策理论，机器学习和计算神经科学等领域，损失函数或成本函数是将一或多个变量的一个事件或值映射为可以直观地表示某种与之相关“成本”的实数的函数。
来源： Wikipedia
neurons
（人工）神经元是一个类比于生物神经元的数学计算模型，是神经网络的基本组成单元。 对于生物神经网络，每个神经元与其他神经元相连，当它“兴奋”时会向相连的神经元发送化学物质，从而改变这些神经元的电位；神经元的“兴奋”由其电位决定，当它的电位超过一个“阈值”（threshold）便会被激活，亦即“兴奋”。 目前最常见的神经元模型是基于1943年 Warren McCulloch 和 Walter Pitts提出的“M-P 神经元模型”。 在这个模型中，神经元通过带权重的连接接处理来自n个其他神经元的输入信号，其总输入值将与神经元的阈值进行比较，最后通过“激活函数”（activation function）产生神经元的输出。
来源： Overview of Artificial Neural Networks and its Applications. (2018). medium.com.
Objective function
目标函数f(x)就是用设计变量来表示的所追求的目标形式，所以目标函数就是设计变量的函数，是一个标量。从工程意义讲，目标函数是系统的性能标准，比如，一个结构的最轻重量、最低造价、最合理形式；一件产品的最短生产时间、最小能量消耗；一个实验的最佳配方等等，建立目标函数的过程就是寻找设计变量与目标的关系的过程，目标函数和设计变量的关系可用曲线、曲面或超曲面表示。
来源： 百度百科
Stochastic gradient descent
梯度下降（Gradient Descent）是遵循成本函数的梯度来最小化一个函数的过程。这个过程涉及到对成本形式以及其衍生形式的认知，使得我们可以从已知的给定点朝既定方向移动。比如向下朝最小值移动。 在机器学习中，我们可以利用随机梯度下降的方法来最小化训练模型中的误差，即每次迭代时完成一次评估和更新。 这种优化算法的工作原理是模型每看到一个训练实例，就对其作出预测，并重复迭代该过程到一定的次数。这个流程可以用于找出能导致训练数据最小误差的模型的系数。
来源： 机器之心
Weight
线性模型中特征的系数，或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0，则相应的特征对模型来说没有任何贡献。
来源：Google AI Glossary
Accuracy
分类模型的正确预测所占的比例。在多类别分类中，准确率的定义为：正确的预测数/样本总数。 在二元分类中，准确率的定义为：(真正例数+真负例数)/样本总数
机器之心是国内领先的前沿科技媒体和产业服务平台,关注人工智能、机器人和神经认知科学,坚持为从业者提供高质量内容和多项产业服务。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK