从NAS到Apollo，优化方法如何助力设计空间探索

摘要

不管是AutoML中的自动化调参和神经架构搜索（Neural Architecture Search, NAS），还是Google在硬件架构设计方面的最新研究工作[1]，优化方法都在空间设计探索中扮演着非常重要的角色。优化方法种类繁多，适用场景也可能会不同。本文借助当前热门研究方向NAS的空间设计问题，开展了对主流优化方法的研究，主要内容包括优化方法类别（黑盒子优化、可微分方法以及其他加速方法）、NAS公开数据集、拓展思考等。

因篇幅较长，此次研究分为两部分。本篇为第一部分，主要研究和分析了黑盒子优化(Black-box optimization, BBO)，以及用于NAS空间设计的三种主流黑盒子优化方法，即进化算法(Evolutionary algorithm)、强化学习（Reinforcement learning）、贝叶斯优化(Bayesian optimization)。在后续的第二部分中，将研究基于可微分的非黑盒子方法DARTS（Darts : Differentiable architecture search），以及避免重复从零开始训练的“weight sharing”等优化加速思想，并对现有优化方法进行评述。

黑盒子优化

黑盒子优化方法的一个显著特征是“derivative-free”。如图1所示，该方法只关注盒子两端的输入

和输出

，而从输入到输出之间的映射关系

却不给予明确的形式化表示，因此也无法计算函数

的derivative。在BBO中，函数

又称为目标函数，求解目标是找到输入

使得函数

最大化，函数

可能是Apollo硬件架构探索中的加权平均的运行时间或者是NAS中的探索模型在测试数据上的准确率。

黑盒子方法适用于很多复杂、难解的优化问题，尤其当计算和获取函数值

在实际问题中非常困难的时候，这也是NAS和Apollo经常遇到的挑战。例如，在硬件架构探索的过程中，评估一次硬件配置的性能是一个漫长耗时的过程，导致不可能在实际应用中收集足够的输入

和输出数据

。同样的问题也出现在NAS中，尤其是训练超大规模模型，如参数量达数万亿的Switch Transformer。这种表达目标函数所需要的数据不足经常在优化过程中遇到，在架构探索中表现地尤为突出。

图1：黑盒子优化

进化算法(Evolutionary algorithm，EA)

进化算法的灵感来源于大自然的生物进化，是基于自然选择和遗传等生物机制的一种搜索方法，与传统的基于微积分的方法相比，该方法不依赖于空间是否具有可导性质，具有自适应、自学习、自组织地进行全局探索的特点。

图2：进化方法流程图

进化算法的基本思想是，从给定群体中选择适应性较强的子种群作为进化的样本，通过基因遗传等方式产生新个体，然后根据某种评估标准对新旧个体进行筛选，从而得到具有多样性、适应能力更强的新种群。图2包含了进化算法的四个主要步骤：选择(Selection)、交叉（Crossover）、变异（Mutation）、更新（Update），很多变种方法都是在其中一个或者多个步骤进行调整，如文[2]在update时引入”age”属性，使新种群中最大程度地保留新个体。在上述步骤中，交叉、变异是两个比较重要的基因遗传操作，现做简单介绍如下：

交叉：针对两个配体的基因序列，在每个序列上选择一定数量（可以是1个或者是多个）的交叉点，并进行相应位置的基因互换。在图3(a)中，分别对双亲基因在第三个基因座的基因值进行了互换。交叉方式有多种方式，根据交叉位置的数量可分为单点交叉、两点交叉、多点交叉；如果两个配对个体的每个基因座上都以相同的交叉概率进行交叉，则称之为均匀交叉；如果两个配体随机产生两个交叉点，然后按照随机产生的整数进行基因互换，则称为均匀两点交叉。
变异：针对单个个体的基因序列的某些基因值做出修改。一般的流程是，对种群内的所有个体以事先设定的变异概率判断是否进行变异，然后对进行变异的个体随机选择基因座进行变异。在图3(b)中，将第三个基因座的基因值0替换成1。

图3：两种基因遗传操作

在使用进化算法时，需要先完成相关优化问题到基因式编码的处理。例如，在将进化算法用于NAS时，首先需要对神经网络结构进行编码。文[3]采用二进制编码（如图4中的1-00-111）来描述一个神经网络结构，其中节点表示对输入数据或者前一层输出数据的操作，如卷积核大小为3x3的卷积操作 conv 3x3。然后，根据操作的先后顺序绘制相应的有向图，其中连接节点的边表示前后紧邻的两个操作。文[3]按照图中两个节点之间是否有边定义二进制序列，1代表相邻两个节点有边连接；反之，则无。如果将这个二进制序列中的1变异为0，表示对应的两个卷积操作失去现有的操作顺序。在完成二进制编码之后，进化方法中的交叉、变异等基因遗传操作同样适用于NAS中的二进制序列，不同基因值的序列对应于不同的神经网络结构。

图4：神经网络结构表示方法(来源[3])

强化学习(Reinforcement learning)

与进化算法中以卷积核操作为基本单元来定义神经网络结构类似，文[4]将决定每层卷积相关的参数（如卷积核宽度、高度、卷积核数量等）选择看成字符串序列的生成问题，从而转化为适用强化学习的序列决策问题。该文的思路是通过基于RNN控制器生成字符串序列，字符串的长度由RNN决定，如图5所示。从整体上来看，为了优化由该字符串描述的神经网络结构，作者将每次新生成的字符串作为反馈重新用于训练RNN，如图6所示。其中，输出的一系列字符串看成是强化学习中的action，由字符串描述的神经网络在测试集上的准确率作为reward。可以看出，强化学习只是用于训练控制器，而不直接参与字符串序列的生成过程。除了NAS，强化学习也用于软硬件架构协同设计[5]。进化算法是现在NAS问题的主流设计思想，也可以与迁移学习进行完美结合[1，8]。

图5：基于RNN的神经网络卷积核生成器(来源[4])

图6：基于RNN的控制器(来源[4])

贝叶斯优化(Bayesian optimization)

贝叶斯优化通过基于目标函数

的过去评估结果来搜索更优的设计点

，包含代理函数（surrogate function）和采集函数(acquisition function)两个重要函数的设计和选择。其中，前者用于近似目标函数

，后者用于评估和筛选下一个设计点，并将之与当前所有设计点一起来更新代理函数。贝叶斯方法与其他随机采样方法的不同之处在于，在尝试下一个设计点时，通过贝叶斯公式使得先验与后验分布进行关联，从而更好地利用现有设计点，来避免之后的无效探索，算法流程如图7所示。首先，在观察到数据

，其中

为已经尝试过的设计点的数量，通过采集函数寻找下一个可能使目标函数更优的设计点

，形象化表示如图8(a)所示，其中红色下三角

是根据采集函数选择出来的下一个设计点，黑色实圈

是当前已经选择的设计点。常用的采集函数有Probability of improvement (PI)、Expected improvement(EI)，其中EI能解决PI面对的局部最优问题。根据最新的观察数据

，更新目标函数分布

，也就是目标函数的后验分布。

图7：贝叶斯优化流程（来源文[6]）

在贝叶斯优化中，高斯进程(Gaussian process, GP)是常用的代理函数。简单来说，高斯进程是一个描述高斯函数的函数。例如，在图8(b)中，在给定设计点

，通过代理函数计算得到的是在该点的均值为

、方差为

高斯分布，而不是单个值。在选择下一个设计点时，通常会在当前均值的利用(Exploitation)以及由均值和方差确定的范围内进行的探索（Exploration）之间进行权衡。有关贝叶斯优化的更多细节请参考文[6]。

（a）采取函数与近似函数的设计点选取

(b)高斯进程

图8：基于高斯进程的贝叶斯优化示意图（来源文[6]）

与进化算法、强化学习方法类似，在使用贝叶斯方法之前也需要对NAS进行编码，常见做法是采用有向图的处理方式，如文[7]。贝叶斯优化方法中的一个要素是描述高斯进程的核函数，文[7]根据有向图重新定义了两个变量，用于描述和更新核函数。

总结

空间设计探索是NAS和Apollo的重要研究内容，本文从优化方法在空间设计探索中的助力作用，深入研究了进化算法、强化学习和贝叶斯优化这三种主流的黑盒子优化方法，希望能帮助相关研究人员更快速地了解这些方法的精髓。

由于水平有限，文中存在不足的地方，请各位读者批评指正，也欢迎大家参与我们的讨论。

参考文献

[1]Yazdanbakhsh, Amir,et al."Apollo:Transferable Architecture Exploration." arXiv: 2102.01723.

[2]Real,Esteban,et al."Regularized evolution for image classifier architecture search." AAAI, 2019.

[3]Xie,Lingxi,et al."Genetic CNN.", ICCV 2017.

[4]Zoph,Barret,et al."Neural architecture search with reinforcement learning." ICLR, 2017.

[5]Zhou,Yanqi, et al."Rethinking co-design of neural architectures and hardware accelerators." arXiv:2102.08619.

[6]Brochu,Eric, et al."A tutorial on Bayesian optimization of expensive cost functions,with application to active user modeling and hierarchical reinforcement learning." arXiv:1012.2599.

[7]Kandasamy,Kirthevasan,et al."Neural architecture search with Bayesian optimisation and optimal transport.", NeurIPS 2018.

[8]Wong,Catherine,et al."Transfer learning with neural AutoML.", NeurIPS 2018.

往期推荐

1、贝叶斯方法与深度学习的结合及应用（1）

2、贝叶斯方法与深度学习的结合及应用（2）

3、概率图模型在深度学习的应用