2019/08/29 14:29

王骏翔、禹富勋、陈翔、赵亮作者

KDD 2019 | 不用反向传播就能训练DL模型，ADMM效果可超梯度下降

随机梯度下降 (SGD) 是深度学习的标准算法，但是它存在着梯度消失和病态条件等问题。本文探索与反向传播（BP）完全不同的方向来优化深度学习模型，即非梯度优化算法，提出了「反向前向的交替方向乘子法」的深度模型优化算法，即 dlADMM。该方法解决了随机梯度下降存在的问题，在多个标准数据集上达到并超过梯度下降算法的效果，并且第一次给出了全局收敛的数学证明。同时增强了算法的可扩展性，为解决一些当前重要的瓶颈问题提供了全新视角，比如复杂不可导问题以及非常深的神经网络的高性能计算问题。目前，该论文已被数据挖掘领域顶会 KDD 2019 接收。

论文地址：https://arxiv.org/pdf/1905.13611.pdf
代码地址：https://github.com/xianggebenben/dlADMM

论文：ADMM for Efficient Deep Learning with Global Convergence

本文提出了一种基于交替方向乘子法的深度学习优化算法 dlADMM。该方法可以避免随机梯度下降算法的梯度消失和病态条件等问题，弥补了此前工作的不足。此外，该研究提出了先后向再前向的迭代次序加快了算法的收敛速度，并且对于大部分子问题采用二次近似的方式进行求解，避免了矩阵求逆的耗时操作。在基准数据集的实验结果表明，dlADMM 击败了大部分现有的优化算法，进一步证明了它的有效性和高效。

背景

深度学习已经在机器学习的各个领域受到广泛的应用，因为深度学习模型可以表征非线性特征的多层嵌套组合，所以相比传统的机器学习模型，它的表达性更丰富。由于深度学习通常用在大数据的应用场景中，所以需要一种优化算法可以在有限的时间内得到一个可用的解。

随机梯度下降算法 (SGD) 和它的许多变体如 ADAM 是深度学习领域广泛使用的优化算法，但是它存在着如梯度消失 (gradient vanishing) 和病态条件 (poor conditioning) 等问题；另一方面, 作为近年非常热门的优化框架，交替方向乘子算法 (ADMM) 可以解决 SGD 存在的问题: ADMM 的基本原理是把一个复杂的复合目标函数分解成若干个简单的子函数求解，这样不需要用链式法则求复合函数的导数，从而避免了梯度消失的问题，另外 ADMM 对输入不敏感，所以不存在病态条件的问题 [1]。除此之外 ADMM 还有诸多优点：它可以解决非光滑函数的优化问题；它在很多大规模的深度学习应用中展现了强大的可扩展性 (scalability) 等等。

经典反向传播算法 (BP)

一个典型的神经网络问题如下所示:

其中 W_l 和 b_l 是第 l 层的权重和截距, f_l (∙) 和 R(∙) 分别是激活函数和损失函数, L 是层数。经典的反向传播算法分前向传送梯度和后向更新参数两部分：每层的梯度按照链式法则向前传输，然后根据损失函数反向参数更新如下:

尽管反向传播非常实用，然而它存在一些问题，因为前面层级的梯度必须等后面层级的梯度算完，BP 的速度比较慢；因为 BP 需要保存前向传播的激活值，所以显存占用比较高；最常见的问题就是对于深度神经网络存在梯度消失, 这是因为根据链式法则如果, 那么随着层数的增加，梯度信号发生衰减直至消失。连提出 BP 的 Geoffrey Hinton 都对它充满了质疑。主要是因为反向传播机制实在是不像大脑。Hinton 在 2017 年的时候提出胶囊理论尝试替代标准神经网络。但是只要反向传播的机制不改变，梯度消失的问题就不会解决。因此目前有许多研究者尝试采用各种机制训练神经网络，早在 2016 年，Gavin Taylor[1] 等人就提出了 ADMM 的替代想法，ADMM 的原理如图 1 所示，一个神经网络按照不同的层被分解成若干个子问题，每个子问题可以并行求解，这样不需要求复合目标函数 R(∙) 的导数，解决了梯度下降的问题。按照 ADMM 的思路，神经网络问题被等价转换为如下问题 1:

问题 1:

其中 a_l 是辅助变量。

图 1. 基于 ADMM 的深度神经网络子问题分解示意图

挑战

尽管 ADMM 具备很多优点，但是把它应用在深度学习的问题中的效果较当前最优算法入 SGD 和 ADAM 还有很大差距，很多技术和理论问题仍亟待解决：1) 收敛慢。即使最简单的目标函数，通常 ADMM 需要很多次迭代才能达到最优解。2) 对于特征维度的三次时间复杂度。在 Taylor 等人的实验中，他们使用了超过 9000 核 CPU 来让 ADMM 训练了仅仅 300 个神经元 [1]。其中 ADMM 最耗时的地方在于求解逆矩阵, 它的时间复杂度大概在 O(n^3 ), 其中 n 是神经元的个数。3) 缺乏收敛保证。尽管很多实验证明了 ADMM 在深度学习中是收敛的，然而它的理论收敛行为依然未知。主要原因是因为神经网络是线性和非线性映射和组合体，因而是高度非凸优化问题。

基于这些问题，最新的一期 KDD2019 论文提出了 ADMM 的改进版本 dlADMM，第一次使基于 ADMM 的算法在多个标准数据集上达到当前最佳效果，并且在收敛性理论证明得到重要突破。

dlADMM 相比 ADMM 的优势:

加快收敛。文章提出了一种新的迭代方式加强了训练参数的信息交换，从而加快了 dlADMM 的收敛过程。
加快运行速度。作者通过二次近似的技术避免了求解逆矩阵，把时间复杂度从 O(n^3 ) 降低到 O(n^2 )，即与梯度下降相同的复杂度。从而大幅提高 ADMM 的运行速度。
具备收敛保证。本文第一次证明了 dlADMM 可以全局收敛到问题的一个驻点（该点导数为 0）。

下面具体讨论提出算法的这些优势：

1). 加快收敛

直接用 ADMM 解问题 1 并不能保证收敛，所以作者把问题 1 放松成如下的问题 2。在问题 2 中，当ν→+∞ 时，问题 2 无线逼近问题 1。

问题 2：

在问题 2 中，ν>0 是一个参数, z_l 是一个辅助变量。在解问题 2 的过程中，通过增大ν可以使其理论上无限逼近问题 1。

问题 2 的增广拉格朗日 [2] 形式如下:

其中是 dlADMM 中的一个超参数。

为了加快收敛过程，作者提出了一种新的迭代方式：先后向更新再前向更新，如图 2 所示。具体来讲，参数从最后一层开始更新，然后向前更新直到第一层，接着参数从第一层开始向后更新直到最后最后一层。这样更新的好处在于最后一层的参数信息可以层层传递到第一层，而第一层的参数信息可以层层传递到最后一层，加强参数信息交换，从而帮助参数更快地收敛。

图 2. dlADMM 原理图

2). 加快运行速度

对于求解 dlADMM 产生的子问题，大部分都需要耗时的矩阵求逆操作。为此，作者使用了二次近似的技术，如图 3 所示。在每一次迭代的时候对目标函数做二次近似函数展开，由于变量的二次项是一个常数，因此不需要求解逆矩阵，从而提高了算法的运行效率。

图 3. 二次近似

3.) 收敛保证

作者证明了无论参数 (W,b,z,a) 如何初始化，当ρ 足够大的时候，dlADMM 全局收敛于问题 2 的一个驻点上。

具体来说，是基于如下两条假设：

a. 求解 z 的子问题存在显式解。

b. F 是强制的 (coercive),R(∙) 是莱布尼茨可导 (Lipschitz differentiable)。

对于假设 a, 常用的激活函数如 Relu 和 Leaky Relu 满足条件；对于假设 b，常用的交叉熵和最小二乘损失函数都满足条件。

在此基础之上, 本文证明了三条收敛性质：

是有界的，L_ρ是有下界的。
L_ρ是单调下降的。
L_ρ的次梯度趋向于 0。

同时文章也证明了 dlADMM 的收敛率是 o(1/k).

实验结果

该论文在两个基准数据集 MNIST 和 Fashion MNIST 上进行了实验。

1. 收敛验证

作者画出了当ρ=1 和 ρ=〖10〗^(-6) 的收敛曲线，验证了当 ρ 足够大的时候，dlADMM 是收敛的（Figure 2），反之，dlADMM 不停地振荡（Figure 3)。

2. 效果比较

作者把 dlADMM 和当前公认的算法进行了比较。比较的方法包括：

a. 随机梯度下降 (SGD). b. 自适应性梯度算法 (Adagrad). c. 自适应性学习率算法 (Adadelta).

d. 自适应动量估计 (Adam). e. 交替方向乘子算法 (ADMM).

Figure 4 和 Figure 5 展示了所有算法在 MNIST 和 Fashion MNIST 的训练集和测试集的正确率，可以看到开始的时候 dlADMM 上升最快，并且在二十次迭代之内迅速达到非常高的精度并且击败所有算法。在 80 次迭代之后虽被 ADAM 反超，但是仍然优于其他算法。文中提出的改进版 dlADMM 显著提高了 ADMM 的表现，使之充分发挥 ADMM 在迭代初期进展迅速的优点，同时在后期保证较高收敛率。

3. 时间分析

文章作者分析了 dlADMM 的运行时间和数据集数量，神经元个数以及和 ρ的选取上面的关系。

如 table 2 和 table 3 所示，当数据集数量, 神经元个数和ρ的值越大的时候, dlADMM 的运行时间越长。具体来说, 运行时间和神经元个数和数据集数量成线性关系。这个结果体现了 dlADMM 强大的可扩展性 ( scalability)。

本文提出的 dlADMM 代码已经公开, 欢迎使用。链接如下: https://github.com/xianggebenben/dlADMM。欢迎邮件联系 jwang40@gmu.edu 或者 lzhao9@gmu.edu。

文献：

[1]. Taylor, Gavin, et al. "Training neural networks without gradients: A scalable admm approach". International conference on machine learning. 2016.

[2]. Boyd, Stephen, et al. "Distributed optimization and statistical learning via the alternating direction method of multipliers." Foundations and Trends® in Machine learning 3.1 (2011): 1-122.

理论反向传播算法梯度下降

相关数据

深度学习技术

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

来源：LeCun, Y., Bengio, Y., & Hinton, G. (2015). Deep learning. nature, 521(7553), 436.

激活函数技术

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

来源：维基百科 Google ML glossary

权重技术

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

来源：Google AI Glossary

交叉熵技术

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

来源：维基百科

机器学习技术

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

来源：Mitchell, T. (1997). Machine Learning. McGraw Hill.

基准技术

一种简单的模型或启发法，用作比较模型效果时的参考点。基准有助于模型开发者针对特定问题量化最低预期效果。

来源：Google ML Glossary

参数技术

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

来源：维基百科

时间复杂度技术

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 n （必须比 n0 大）的输入，它至多需要 5n3 + 3n 的时间运行完毕，那么它的渐近时间复杂度是 O(n3)。

来源：维基百科

收敛技术

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

来源：Wikipedia Google ML glossary

凸优化技术

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

来源：维基百科

学习率技术

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

来源：Liu, T. Y. (2009). Learning to rank for information retrieval. Foundations and Trends® in Information Retrieval, 3(3), 225-331. Wikipedia

损失函数技术

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

来源：Wikipedia

超参数技术

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

来源：Wikipedia

导数技术

导数（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）。

来源：机器之心

反向传播算法技术

反向传播（英语：Backpropagation，缩写为BP）是“误差反向传播”的简称，是一种与最优化方法（如梯度下降法）结合使用的，用来训练人工神经网络的常见方法。该方法计算对网络中所有权重计算损失函数的梯度。这个梯度会反馈给最优化方法，用来更新权值以最小化损失函数。在神经网络上执行梯度下降法的主要算法。该算法会先按前向传播方式计算（并缓存）每个节点的输出值，然后再按反向传播遍历图的方式计算损失函数值相对于每个参数的偏导数。

来源：维基百科 Google ML glossary

数据挖掘技术

数据挖掘（英语：data mining）是一个跨学科的计算机科学分支它是用人工智能、机器学习、统计学和数据库的交叉方法在相對較大型的数据集中发现模式的计算过程。数据挖掘过程的总体目标是从一个数据集中提取信息，并将其转换成可理解的结构，以进一步使用。

来源：维基百科

梯度下降技术

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

来源：Vapnik V. N. (2000). The Nature of Statistical Learning Theory. Information Science and Statistics. Springer-Verlag.Wikipedia

映射技术

映射指的是具有某种特殊结构的函数，或泛指类函数思想的范畴论中的态射。逻辑和图论中也有一些不太常规的用法。其数学定义为：两个非空集合A与B间存在着对应关系f，而且对于A中的每一个元素x，B中总有有唯一的一个元素y与它对应，就这种对应为从A到B的映射，记作f：A→B。其中，y称为元素x在映射f下的象，记作：y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域，记作f(A)。同样的，在机器学习中，映射就是输入与输出之间的对应关系。

来源：Wikipedia

随机梯度下降技术

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

来源：机器之心

目标函数技术

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

来源：百度百科

神经元技术

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

来源：Overview of Artificial Neural Networks and its Applications. (2018). medium.com.

链式法则技术

是求复合函数导数的一个法则, 是微积分中最重要的法则之一。

来源：Wikipedia

深度神经网络技术

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

来源：机器之心 Techopedia

模型优化技术

像卷积神经网络（CNN）这样的深度学习模型具有大量的参数；实际上，我们可以调用这些超参数，因为它们原本在模型中并没有被优化。你可以网格搜索这些超参数的最优值，但需要大量硬件计算和时间。改进模型的最佳方法之一是基于在你的领域进行过深入研究的专家的设计和体系结构，他们通常拥有强大的硬件可供使用。常见的简单模型优化技巧包括迁移学习、dropout、学习率调整等

来源：机器之心