【FairNAS】2019-arxiv-FairNAS Rethinking Evaluation Fairness of Weight Sharing Neural Architecture Search-论文阅读

FairNAS

2019-arxiv-FairNAS Rethinking Evaluation Fairness of Weight Sharing Neural Architecture Search

来源：ChenBong 博客园

Institute：Xiaomi AI Lab
Author：Xiangxiang Chu，Bo Zhang，etc.
GitHub：https://github.com/xiaomi-automl/FairNAS 【280+】
Citation：50+

Introduction

NAS总体上就是跑n个模型，找到最好的模型。

一般可以分为2个stage：

搜索阶段，（生成器）生成不同的模型
评估阶段，（评估器）评估这些模型的性能

NAS方法分类

基于强化学习的方法

使用controller（LSTM/RNN）生成候选模型描述，训练完将性能作为reward，更新controller，使 controller 可以生成越来越好的模型。
可以看出，基于RL的方法是将搜索阶段（生成模型）和评估阶段（评估模型的性能）轮流进行，目的是使得生成器（controller）的生成的模型性能越来越好。
缺点：由于要完全训练很多候选模型，效率极低。

基于梯度下降的方法（DARTS-like）

将生成和评估整合到一个阶段，在一个网络中给每个算子op都附加一个可微分的强度系数（α），初始的时候每个算子op的强度都是平等的，在训练过程中对网络性能提升更大的算子会被加强，即在训练中自动调整网络中算子op的强度
优点：最大的贡献在于 用连续的空间来表示离散的网络结构，使得离散的结构变得连续可微分（例如）
缺点：
1. 计算开销问题：每次前向反向都要经过所有的算子，计算开销很大，因此无法直接在大数据集上进行搜索，只能使用代理（在小数据集上搜索再迁移到大数据集上）
2. 公平性问题 - 马太效应：一个优秀的算子只是因为训练过程中分配到的资源多，而不是因为本身优秀。一开始每个算子强度相同，随机选择一些算子开始优化，这些算子在前期被优化得多，导致其强度（α）越来越大，而强度大又导致更新它对整个网络的性能提升更明显。有限的训练资源，给谁越多，谁就越强。即初始值敏感和强者越强，弱者越弱，而陷入局部最优。
3. 公平性问题 - “前期英雄”：有些算子可能是“前期英雄”，而有些算子是“后期英雄”，而DARTS倾向于去找那些“前期英雄”的算子，而陷入局部最优。
4. 搜索阶段和推理阶段的差异问题：即搜索时使用全部算子的加权，而最后只保留最高的或top-k
5. 理论基础问题：DARTS认为在训练过程中，根据梯度可以自动判断算子的好坏，但这是一种偏直觉的排序策略，没有数学的理论基础。

one-shot 的基于参数共享的方法

Pipeline：
- Stage 1：训练一个超网（评估器）；
- Stage 2： （生成）使用一些策略（如Random，EA）从超网中采样候选网络
- Stage 3： （评估）候选网络从超网中继承权重进行推理，推理性能即作为该候选网络的性能估计。即将超网作为不同候选网络的性能评估器。
- Stage 4：选择评估阶段Stage 3中的 top-k 进行 train from scratch
优点：one-shot 可以概括为 “一次训练，多次推理” Train Only Once to Evaluate All Submodels，即只要训练一个超网，就可以评估多个子网
缺点：
1. 计算开销问题：超网要包含足够的搜索空间，导致网络太大，计算开销大（改进：SPOS中每次选择single path进行训练，而不是每次训练整个网络）
2. 相关性问题：或者叫一致性问题，即超网中子网性能（One-shot acc）和retrain后的性能（stand-along acc）相关性不强（而且往往比较低），即搜出来的优秀子网并不一定是最优秀的子网，甚至可能还比较差，而相关性正是 one-shot 方法的基础，如果没有这个基础假设，one-shot 这个方法就没有意义了。
对于每次 uniform sample 一两条路径进行训练的one-shot（如SPOS等），还有以下问题：
1. 公平性问题 - 马太效应： 对于某一个优秀的op，我们不知道它是真的天生优秀（适合位于网络的这个位置），还是被训练的次数多被优化的好，尽管是 uniform 采样，但是实际过程中肯定是会存在该问题的，FairNAS里的证明就说了这个事，即每个op都均等采样是基本不存在的。
2. 公平性问题 - 顺序问题： ** 就算假设某一层有4个op，然后4次采样也很幸运，每个都采样了一遍，但是因为每采样一次会更新一次超网，所以后来的采样一定会受到之前更新的影响，即所谓采样顺序不同**也会带来公平性的问题。（ABCD不等于DBCA)。

Kendall Tau(τ) （Kendall相关系数）

one-shot acc 高的模型，stand-alone acc 不一定是最高的，甚至可能表现很差。因此一种用的比较多的就是Kendall Tau (τ) metric，它会评估两个阶段模型性能的相关性，相关性越高则表示算法越有效。τ 的范围在-1到1之间：

τ= 1：one-shot acc 的排序和 stand-alone acc 的排序完全一致
τ= -1：one-shot acc 的排序和 stand-alone acc 的排序完全反序
τ = 0：one-shot acc 的排序和 stand-alone acc 的排序完全没有关系

可以看出，我们希望 τ 的值越大越好。

e.g.

A method based on time-consuming incomplete training only reaches an average τ of 0.474. 【2019-ICCV-Multinomial Distribution Learning for Effective Neural Architecture Search, X Zheng】
SPOS（Single Paht One-Shot)，τ = 0.6153
FairNAS(ours)， τ = 0.9487

FairNAS 介绍

FairNAS 可以总结为：

不放回的子网采样，多子网梯度统一更新。

Motivation

作者从one-shot方法中存在的两阶段性能（one-shot acc VS stand-alone acc） **存在很大的gap (30%-90% vs. 92%-94.5%) **，还有两阶段性能 相关性不强 的现象出发，发现当前NAS方法（包括DARTS和one-shot）中普遍存在的 unfair training 导致的 unfair evaluation 的问题，提出了一种称为 Strict Fairness（FairNAS）的公平训练方法，使得两阶段性能强正相关，达到了SOTA的 Kendall Tau(τ) of 0.9487。

Contribution

提出了 Strict Fairness（FairNAS）的公平训练方法使得两阶段性能呈现强烈的正相关，τ = 0.9487
证明了在 uniform sample 下，采样次数趋于无穷时，每个算子op被采样的次数 Y 不可能都相同
Single-Path supernet training 有效性的原因：同一层的不同choice block学到了相似的特征
实验说明在 fairness condition 下对超网中的子网进行评估时，无需重新计算BN层（与 EagleEye 的结论相反）

Method

Formally, we discuss fairness in a common supernet that consists of L layers, each with several choice blocks.

Without loss of generality, we suppose each layer has an equal number of choices, say m.

The weights are updated for n times in total.

Therefore, we can describe the training process as P(m, n, L).

L = 19 layers, m = 6 ops（不同的层有相同的op数m）

sample / update n times

Define2. Expectation Fairness（EF约束）

L = 19 layers, m = 6 ops（不同的层有相同的op数m）

sample / update (n) times

Define 2. Expectation Fairness (EF)

a natural way is to guarantee all choices blocks have equal expectations after n steps

Definition 2. Expectation Fairness.

(Ω) be the sampling space containing m basic events ({l_1, l_2, ..., l_m}),

Let (Y_{l_i}) be the number of times that outcome (l_i) is observed(updated) over n trails.

Then the expectation fairness is that for (P(m, n, L), E(Y_{l_1}) = E(Y_{l_2}) =...= E(Y_{l_m}) holds, ∀l∈L)

即同一层的不同算子op要选中（更新）同样的次数

An EF Example: Uniform Sampling（SPOS）

(egin{aligned} Eleft(Y_{l_{i}} ight) &=n * p_{l_{i}}=n / m \ operatorname{Var}left(Y_{l_{i}} ight) &=n * p_{l_{i}}left(1-p_{l_{i}} ight)=frac{n(m-1)}{m^{2}} end{aligned} qquad (1))

即所有的算子op被选中的次数Y的期望和方差都相同。

但存在一个ordering issue：即子网的选择顺序会影响最后的结果，（M1，M2，M3）和（M1，M3，M2）不同