基于强化学习的自动搜索

导读：神经架构自动搜索的另一个常用策略是强化学习，强化学习把架构的生成看成一个智能体 ( agent ) 在选择动作 ( action ) 的过程，通过在测试集上测试网络性能来获取奖励值 ( reward )，从而指导架构的生成。近年来，基于强化学习的神经网络架构搜索已经取得了很多突破性的进展，涵盖各种策略函数和优化方法，下面将从搜索单元、搜索方法和搜索输出等多个方面对这些先进算法进行分类介绍。

图1 基于强化学习的网络架构搜索示示意图

1. 基本搜索方法

1.1 基于层的搜索

神经网络架构的自动搜索是从对 layer 的搜索开始的，经典算法有 NASNet 和 MetaQNN。NASNet 是由 Google 团队在 NAS 搜索方法见的基础上提出的，即直接在感兴趣的数据集上学习构建神经网络模型。NASNet 搜索空间定义了神经网络结构搜索的基本单元，它的设计灵感来源于卷积神经网络的设计通常是由卷积滤波器组 ( 卷积、池化等 )、非线性激活函数和连接方式等重复主题 ( 如 Inception 和 ResNet 模型中出现的重复模块 ) 所定义。基于以上观察发现，RNN 控制器可以预测出以这些主题为基础的一般卷积单元，然后，多个单元按顺序堆叠，来处理任意空间维度和过滤深度的输入，其中每个卷积单元具有相同的结构，但是权重不同。

为了轻松的为任意大小的图像构建可扩展的神经网络结构，当使用某个特征图作为输入时，作者设计了两种类型的卷积单元：(1) Normal Cell，不改变特征图的大小；(2) Reduction Cell，将特征图的长宽各减少为原来的一半。需要注意的是，NASNet 使用强化学习的方法不断迭代更新 RNN 控制器，从而搜索到的不同的 Normal Cell 和 Reduction Cell 堆叠结构。如图2所示，是 NASNet 在 cifar 数据集和 ImageNet 数据集上额搜索结果示例。

图2 NASNet 搜索结果示例

NasNet 使用一种常见的启发式方法，每当空间激活大小减小时，输出中的过滤器数量就会增加一倍，以保持大致稳定的隐藏状态维度。更重要的是，就像 Inception 和 ResNet 模型一样，作者将修正重复单元的数量 N 和初始卷积滤波器的数量作为根据图像分类问题的规模设定的自由参数。因此，NASNet 网络中变化的是 RNN 控制器搜索到的 Normal Cell 和 Reduction Cell 结构。

在 NASNet 的搜索空间中，每个 cell 接收两个初始隐藏状态 hi 和 hi-1 作为输入，它们是前两个较低层中的两个 cell 的输出或输入图像。在给定这两个初始隐藏状态的情况下，RNN 控制器循环预测卷积单元的其余结构。控制器为每个单元的预测结果组成 B blocks，每个 block 由5个不同的 softmax 分类器进行5个预测步骤，对应于 block 元素的离散选择：

Step1：从 hi 和 hi-1 或者前面的 block 中创建的隐藏状态集中选择一个隐藏状态。

Step2：从与 step1 相同的选项中选择第二个隐藏状态。

Step3：选择要应用于步骤1中选择的隐藏状态的操作。

Step4：选择要应用于步骤2中选择的隐藏状态的操作。

Step5：选择一个方法来组合步骤3和步骤4的输出，以创建一个新的隐藏状态。

搜索过程如下图所示：

图3 NASNet 搜索过程

该算法将新创建的隐藏状态附加到现有隐藏状态集合作为后续块中的潜在输入。RNN 控制器重复上述5个预测步骤 B 次，对应于卷积单元中的 B 块。

MetaQNN 是一种基于强化学习的元建模算法，即通过一个基于 Q-Learning 的元建模过程实现 CNN 结构选择过程的自动化。在这个过程中，构建了一个基于 Q-Learning 算法的智能体，其目标是主动发现在给定的机器学习任务中表现良好的 CNN 结构。智能体的任务是顺序选择 CNN 模型的层，通过离散化所选择的层参数，为智能体提供一个大而有限的搜索空间。智能体通过随机策略和 ϵ-greedy 策略来选择性能良好的模型，然后使用得到的网络结构验证精度作为奖励值，指导智能体进行学习，并且使用了经验回放策略来加速学习过程。算法流程如图4所示。

图4 使用 Q-Learning 设计 CNN 架构

在整个训练过程中，维护了一个回放字典，该字典存储 (i) 网络拓扑和 (ii) 所有采样模型的验证集上的预测性能。如果已经训练过的模型被重新采样，则不会对其进行重新训练，而是将先前找到的验证准确性呈现给 agent。在对每个模型进行采样和训练之后，agent 从回放字典中随机采样90个模型，并对每个采样序列中的所有转换应用 Q 值更新。Q 值更新应用于时间上相反顺序的转换，该方法可以加速 Q 值收敛。

1.2 基于块的搜索

NASNet 和 MetaQNN 都是针对特定数据集基于 layer 的搜索算法，在很大程度上解决了人工构建神经网络对专业知识和经验的依赖性，但是依然存在几个问题：(1) 现代神经网络一般是由数百个卷积层组成，每个卷积层在类型和超参数上都有众多的选择，这大大增加了网络架构的搜索空间和计算成本。(2) 一个经典的神经网络通常局限于某个特定的数据集或任务，泛化能力较差。针对以上问题，基于 block 的设计方法被不断提出。

与以往直接生成整个网络的神经网络自动设计的研究不同，Block-QNN 的目标是设计块结构。采用分块设计，网络不仅具有较高的性能，而且对不同的数据集和任务具有较强的泛化能力。由于 CNN 包含一个前馈计算过程，作者用一个有向无环图 ( DAG ) 来表示，其中每个节点对应于 CNN 中的一个层，而有向边表示数据从一个层流向另一个层。为了将这种图转化为统一的表示形式，提出了一种新的层表示形式，称为网络结构代码 ( Network Structure Code，NSC )，如表1所示。每个块由一组5维的 NSC 向量表示。在 NSC 中，前三个数字代表层索引、操作类型和内核大小。最后两个是前驱参数，它们指的是结构代码中层的前驱层的位置。设置第二个前驱 ( Pred2 ) 为拥有两个前驱的层，对于只有一个前驱的层，将 Pred2 设置为0。

表1 网络结构代码空间

NSC 可以对复杂体系结构进行编码，如图5所示。此外，块中没有后续层的所有层都连接在一起以提供最终输出。

图5 具有代表性的块示例及其网络结构代码 ( NSC )。具有多分支连接的块 (左) 和具有快捷连接的块 (右)

虽然 BlockQNN 专注于构建网络块来压缩整个网络设计的搜索空间，但仍然有大量可能的结构需要寻找，因此使用具有 ϵ-greedy 搜索策略的 Q-Learning 算法自动设计。Agent 首先对一组 NSC 进行采样以构建块结构，基于该结构，通过顺序堆叠这些块来构建整个网络。然后，我们在特定任务上训练生成的网络，并且验证准确性被视为更新 Q-value 的奖励。然后，agent 选择另一组 NSC 以获得更好的块结构。

最佳网络块由 learning agent 构建，该 learning agent 通过训练顺序选择组件层，然后堆叠块来构建整个自动生成的网络。为了加速生成过程，该方法还使用了分布式异步框架和早期停止策略。为了进一步加快学习过程，该算法还引入了早期停止策略和分布式异步框架。

分布式异步框架，如图6所示。它由三部分组成：主节点，控制器节点和计算节点。Agent 首先在主节点中对一批块结构进行采样。然后，我们将它们存储在一个控制器节点中，该节点使用块结构来构建整个网络并将这些网络分配给计算节点。它可以被视为简化的参数服务器。具体地，在每个计算节点上并行地训练网络，并且将验证准确性作为控制器节点的奖励返回给更新 agent。有了这个框架，我们就可以在具有多个 GPU 的多台机器上高效地生成网络。

图6 BlockQNN 的分布式架构

与 BlockQNN 相比，Faster BlockQNN 做了两个方面的改进。首先提出了一种新的块间连接方式，通过搜索自动设计特定块之间的连接取代了传统的堆叠连接；其次提出在训练之前预测网络性能，以此进一步加快 block 搜索过程。关于块间连接的搜索我们将在下一节中介绍。

众所周知，网络生成中最耗时的部分是对采样网络进行训练，以获得验证准确性作为奖励。为了降低这一成本，作者提出投入资源进行训练之前，定量评估网络架构。网络性能预测模型可以形式化为一个函数，用 f 表示。函数 f 取网络架构 x 和 epoch 索引 t 两个参数，得到标量值 f(x,t) 作为第 t 个时期的精度预测。通过这种方式，它可以很快的提供反馈，因此特别适合大规模的网络设计搜索。

1.3 基于连接的搜索

传统的神经网络模型都是由多种卷积单元顺序堆叠在一起的，这种连接方式限制了网络的深度，后来 ResNet 和 Inception 等带有特殊连接的网络模型被提出，不仅可以构造很深的网络，而且可以改善过拟合的问题。因此，研究者们自然而然的想到，通过强化学习的方法，让网络自动学习生成特殊的连接。

Faster BlockQNN 提出了一种新的块间连接方式，通过搜索自动设计特定块之间的连接取代了传统的堆叠连接。基于这一改进，可以将 Faster BlockQNN 视为两阶段的框架：(1) 找到最优块网络；(2) 找到最优块的最佳连接。BlockQNN 中已经阐述了搜索最优块的方法，搜索最优块连接与搜索最优块的区别仅在于 NSC 的定义：使用块结构来代替卷积层，卷积运算的核大小由通道数代替。由于块结构是顺序连接的，作者使用前面的参数来表示不同块之间的附加连接。我们仅使用步幅为 2的池化层进行下采样，并使用1x1的卷积核来匹配连接不同维度的层。

由于网络结构代码 ( NSC ) 在获取层的关键信息时，离散表示不适合复杂的数值计算和深度模式识别，因此开发了一种将证书编码转化为统一实向量表示的层嵌入方案，如图7所示。嵌入是通过查找表完成的，以整数编码为输入，通过查表将其分别映射到嵌入的向量，最后将其串接成一个真实的向量表示。注意 Pred1 和 Pred2 共享同一个查找表。

图7 图层嵌入组件

如下图所示为 Faster BlockQNN 框架的整体流水线。给定块结构，它首先通过整数编码和层嵌入将每个层编码为向量。随后，它应用具有长短期记忆 ( LSTM ) 单元的循环网络，将网络拓扑下各层的信息整合成结构特征。该结构特征和 epoch 索引 ( 也嵌入到向量中 ) 将最终被输入到多层感知器 ( MLP ) 以预测相应时间点的准确度，即给定 epoch 的结束时间。注意，蓝色表示的块，包括嵌入，LSTM 和 MLP，是以端到端的方式联合学习的。

图8 Faster BlockQNN 框架的整体流水线

MaskConnect 是另一种基于 Connect 的搜索算法，由于很多神经网络结构依赖于简单的连接规则，例如，将每个模块仅连接到紧接在前的模块或者可能连接到所有先前的模块。这种简单的连接规则不太可能产生给定问题的最佳架构。在 MaskConnect 中，删除了一些预先设定的选项，通过直接优化模块与给定任务的连接来学习组合和聚合神经网络的构建块。虽然原则上这涉及搜索指数数量的连通性配置，但该方法可以使用反向传播的变体有效地优化关于连通性的训练损失。这是通过连通性掩码实现的，即学习二进制参数，作为“开关”确定我们网络中的最终连接。该掩码与网络的卷积权值一起学习，作为针对问题给定损失函数的联合优化的一部分。

人工设计的网络在拓扑结构中具有快速的推理速度，但是大多数现有的架构搜索方法完全忽略了架构的拓扑特征，商汤科技提出了逆强化学习方法 ( IRLAS )。该方法中引入了一种镜像激励函数，此函数奖励拓扑结构与专家设计的网络 ( 如 ResNet ) 相似的架构，以提取专家人类设计网络的抽象拓扑知识，从而生成具有理想架构的网络。为了避免在搜索空间上引起过强的先验，该算法引入逆强化学习来训练镜像刺激函数并将其用作架构搜索的启发式指导。镜像激励函数是通用的，与搜索空间和策略设计是正交的，因此，它可以很容易地推广到不同的搜索算法中。

IRLAS 将网络拓扑的设计过程视为可变长度决策序列，用于选择操作。并且这个顺序过程可以表示为马尔可夫决策过程 ( MDP )。为了编码网络架构以提取抽象拓扑知识作为 agent 的可用输入，为网络架构定义一个状态特征函数，包括：操作类型，内核大小和当前层的两个前驱索引 ( 对于只有一个前驱的层，其中一个索引设置为零 )。尽管简单，但该状态特征函数提供了网络架构的完整表征，包括有关各个层执行的计算信息以及层的连接方式。然后进一步利用特征计数来统一每个状态特征的信息，以获得整个架构的特征嵌入。

2. 进阶搜索方法

在前四节中，我们介绍了多种基于传统强化学习的神经网络搜索算法，在本节中，我们将介绍几种不同的搜索方法，包括逆强化学习、蒙特卡罗树搜索、图超网络和教师网络等。

2.1 逆强化学习

在1.3节中已经提到了 IRLAS 算法，IRLAS 方法试图生成拓扑上与人类设计网络相似的架构，因此 agent 的学习涉及模仿学习问题。模仿学习 ( IL ) 使 agent 能够从专家的演示中学习，独立于所提议任务中的任何特定知识。IL 有两个不同的领域：策略模仿和逆向强化学习。策略模仿 ( 也称为行为克隆 ) 的目标是直接学习从感知环境或预处理功能到 agent 操作的策略映射。逆向强化学习 ( IRL ) 是指从观察到的行为中获得奖励函数的问题。在神经网络领域，由于人为设计网络的数量有限，很难获得足够数量的专家状态动作元组进行监督学习。因此，直接策略模仿方法不可行。逆向强化学习 ( IRL ) 是指从观察到的专家行为中获得奖励函数的问题。由于奖励函数是一项简洁，强大且可迁移的任务定义，因此 IRL 提供了一种比策略模仿更有效的 IL 形式。如图9所示，是逆强化学习的过程。这一过程可以描述为首先随机生成一个初始策略，通过比较专家样本和自己样本的，来获得奖励函数，利用奖励函数进行强化学习，更新策略。逆强化学习是一个庞大的分支，有很多子方法，在这里我们不展开赘述，感兴趣的读者可自行研究。

图9 逆强化学习

需要注意的是，在学习专家拓扑知识的过程中有两个关键问题，第一个问题是如何编码网络提取抽象的拓扑知识作为 agent 的输入？针对这一问题，使用了一种状态特征函数

，该函数中包括操作类型、内核大小以及当前层的两个前驱索引。然后利用特征计数来统一每个状态的特征信息，以获得整个网络结构的特征嵌入。

第二个问题就是如何利用这些知识对架构搜索进行有效的引导。在这一问题中，就用到了逆强化学习。首先我们需要有一个基础共识，就是人都是有模仿能力的，在我们不太擅长的领域，会无意识的将自己的行动和别人的行动作比较，从而纠正自己的不正确的行为。基于这一观察，提出了镜像激励函数，将 agent 采样得到的网络与专家网络作为输入，镜像激励函数会输出一个信号来判断这两个网络的拓扑相似性，输出的结果越高说明越接近专家网络。

下图就是 IRLAS 的方法流程图，首先将专家网络拓扑结构和 agent 采样得到的拓扑结构转换为状态特征码作为镜像激励函数的输入。在 agent 进行搜索的过程中，利用镜像激励函数进行启发式引导，生成类似于专家设计的网络。然后对生成的网络进行训练，得到验证集的准确率。将该准确率与镜像激励函数的输出值相结合作为奖励，用于对镜像激励函数的更新。

图10 IRLAS 算法流程

2.2 图超网络

神经架构搜索可以看做一个嵌套优化问题，内循环用于查找给定架构的训练损失的最优参数，外循环用于查找验证损失的最优架构。针对神经网络架构搜索计算成本过高的问题，有研究者提出了一种图超网络 ( GHN ) 来分摊搜索成本：即给定一个架构，它通过在图神经网络上运行推理直接生成权值。可以看出，该方法的重点是优化内循环，即推断给定网络的参数。

图超网络 ( GHN ) 是一种由图神经网络 ( GNN ) 和超网络 ( HyperNetwork ) 组成的网络。它接收计算图 ( CG ) 作为输入，并在图中生成所有节点的自由参数。在评估期间，生成的参数用于评估随机采样架构的适用性，然后根据验证集的准确率选择性能最好的架构。

图神经网络是节点和边的集合，其中每个节点都是一个递归神经网络 ( RNN )，它分别沿边发送和接收消息，跨越消息传递的范围。超网络是生成另一个网络参数的神经网络，通过连接固定大小的多个内核，可以为不同内核大小的层预测权重，从而指导神经网络架构的搜索工作，可以看做是一种宽松的权重共享机制。

图11 GHN 流程图

GHN 具体流程如上图所示：首先在 A 阶段对神经网络结构进行随机采样，形成图形超网络；然后在 B 阶段经过图传播，图形超网络中的每个节点都会生成自己的权重参数；最后在 C 阶段利用生成的权值对样本网络进行训练，使训练损失最小化。其中为了简单起见，使用了多层感知器 ( MLP ) 来实现超网络。

此外，GHN 算法可以推广和应用于 anytime prediction 领域，这是 NAS 程序以前从未探索过的，它的性能优于现有的手动设计的最先进的模型。

2.3 蒙特卡洛树搜索

AlphaX 算法是一种改善计算成本的算法，它结合了蒙特卡罗树搜索 ( Monte Carlo Tree Search ，MCTS ) 和元深度神经网络来探索搜索空间 ( Meta-DNN )。AlphaX 是第一个为 NAS 扩展 MCTS 的，同时也是第一个在 CIFAR-10 和 ImageNet 实现准确性高的 MCTS 代理。

对于传统的搜索算法来说，在搜索空间较小，树的层数较浅的情况下，可以通过穷举法计算所有子树的价值，从而选择最优的策略。但是当搜索空间过大的时候，搜索整棵树会花费大量的时间和计算资源，例如围棋，显然是不符合实际的。

MCTS 是一种结合了随机取样和树搜索的算法。MCTS 在给定的决策空间中随机抽取样本，并根据样本建立搜索树，并寻找最优策略。MCTS 也可以解决搜索空间过大的问题，在不能搜索全部子树的情况下，可以做到高效且避免陷入局部最优解。其基本概述：可以用随机模拟来近似真实值，再用这些值调整策略，使之朝向最优解的方向发展。

MCTS 是基于迭代搜索策略来构建搜索树，逐渐构建部分树，搜索树中的节点表示一个状态，到子节点的链接表示后续的动作，当达到设定时间或者迭代到最大次数时搜索结束，根据先前的树的结果，返回最优的动作。

MCTS 的算法流程图如下：

图12 MCTS 算法流程图

每轮迭代 MCTS 包含四步，如图13所示：

(1) 选择 ( Selection )：从根节点开始，使用树策略找到最紧急的可扩展的节点，这个节点可以是未被探索的部分行动中的中间节点。一个节点如果不是终端状态，且还有未被访问的子节点，则这个节点是可扩展的。由图可知，从根节点0开始搜索，到节点6的时候，由于节点6不是终端状态，只有一个子节点，且还存在其他的动作节点，所以节点6是可扩展的节点。

(2) 扩展 ( Expansion )：根据可以使用的动作，将一个或者多个子节点添加来扩展树。图中的节点6的子节点9就被添加到搜索树中。

(3) 模拟 ( Simulation )：根据默认的策略从这个新的节点模拟运行到终端状态，并计算出奖励。从节点9开始执行模拟的动作，根据默认的策略最后会得到一个奖励值。

(4) 奖励回传 ( Backpropagation )：通过选择的节点将模拟得到的奖励值反向传播，更新每一个经过的节点的统计信息，回传的奖励值会影响树策略。从节点9开始，将奖励值经选择的节点，回传到根节点，并更新每一个节点的奖励信息。

图13 MCTS 基本步骤演示

以上的这四个步骤被分为两个不同的策略：

(1) 树策略 ( Tree Policy )：在选择和扩展这两步中，树策略会从搜索树中已经包含的节点中选择和创建叶子节点。

(2) 默认策略 ( Default Policy )：在模拟阶段，从选定的非终端状态的节点开始，模拟动作直到终端状态，生成估计奖励值。

在奖励回传阶段虽然没有用到策略，但是是根据树策略选择的节点进行统计值更新。

2.4 知识提炼（教师网络）

在实际应用中，为了让模型的学习能力和性能增加，我们通常会增加神经网络的深度和广度，但是网络结构的增加会受限于硬件的性能和计算的速度。在实时应用中，减少存储和计算成本，安全的压缩模型而不影响模型的性能也变得至关重要。将大型的神经网络框架在轻量级的设备上使用属于知识精炼的压缩技术，现有的知识精炼技术已经以将大的网络压缩成一个小的网络，但是都需要手工设计小网络的架构，并且很难通过该过程得到的网络性能是否是最佳的。传统的模型压缩技术是通过人工修改网络架构，但是在深度神经网络中，网络的架构过大使得人工修改变得异常困难。

为了解决这些问题，研究者们提出了 N2N Learning 的算法，这个算法可以通过强化学习来学习一种最优的压缩策略，将较大的“教师”网络作为输入，将压缩过后的“学生”网络输出，如图14所示。将“教师”网络转换成“学生”网络的过程作为马尔科夫决策过程 ( Markov Decision Process，MDP )。

图14 N2N Learning 模型图

这个过程可以被定义为 ${\mathcal M}={{\mathcal S},{\mathcal A},T,r,\gamma}$。其中：

（1）状态 ${\mathcal S}$：

状态空间，是由“教师”网络可以导出的所有可能的简化网络的集合。这个状态空间会非常大，因为包含了所有可能减少的系统结构。

（2）动作 ${\mathcal A}$：

一系列的转换动作，可以将网络转换成另一种网络。在模型压缩中有两种操作：层移除操作和层收缩操作。

对于层移除操作来说，是一个决定将选定的层数移除或者保留的操作，根据双向 LSTM 的策略来决定，以此来观察隐藏状态，判断该层与前后层数的关系，从而决定是否要移除该层。

对于层收缩来说，这个操作与层移除操作类似，也需要通过 LSTM 的策略来判断该层的参数与上下的联系，从而对层数进行缩减。

（3）转换函数 T：

确定性转换函数，通过状态和动作，每个动作会将原网络转换成另一个网络。

（4）折现系数 $\gamma$：

始终为1，保证所有的奖励。

（5）奖励函数 r：

强化学习学习一个最优策略使得奖励函数最大，压缩算法的奖励函数要基于模型的压缩率以及准确率。使得模型在保持高精度的同时最大程度的进行压缩。对于某些高压缩而精度低的模型，肯定会比低压缩而精度高的模型得到更严厉的惩罚，因为精度降低的压缩是没有意义的。

该算法首先通过“教师”模型来标记数据，再用这些标记的数据来判断“学生”模型的性能，从而得到最优的压缩策略。N2N Learning 算法在不同数据集上压缩模型的准确率和压缩率都比传统的手工设计模型的效果要好。虽然对于每个“学生”模型可能都要重新训练，会带来一定的开销，但是可以选择超网络和选择训练等方法来对此进行优化。

文章摘自：《 深入理解 AutoML 和 AutoDL 》 机械工业出版社.2019.9

作者介绍：

王健宗，大型金融集团科技公司深度学习平台和 AutoML 平台负责人，中国人工智能开源软件发展联盟副理事长，美国佛罗里达大学人工智能博士后，曾任美国莱斯大学电子与计算机工程系研究员，专注于联邦学习和人工智能在金融、保险、投资、银行和医疗等领域的研发工作，发表联邦学习、深度学习、云计算和大数据等领域国际论文30余篇，以及发明专利200余项。多届国内知名大数据、人工智能、金融科技和联邦学习会议/论坛主席和出品人。

瞿晓阳，华中科技大学计算机系统结构博士，美国中佛罗里达大学访问学者，大型金融集团科技公司资深算法工程师，一直从事机器学习、大数据、体系结构方面的研究工作，在 AutoML 平台、面向 AI 的云原生架构、高性能计算、高效能存储系统等方面经验丰富。近几年，在国际会议和期刊发表过多篇文章，担任过多个国际期刊的评委。

本文来自 DataFun 社区