NAS 学习笔记(九)- FairNAS

  |     |   本文总阅读量:

版权声明:本文原创,转载请留意文尾,如有侵权请留言, 谢谢

引言

  本文分享一篇小米 2020 年的关于 NAS 的论文 [1],它和我们上文介绍的 SPOS 非常像,不同的只是将其中的 uniform sampling 改成了公平采样,本文对它做简单的笔记。

Fairness

  本文主要要解决的问题是训练 child architecture 时产生的 unfairness 的问题,ENAS 和 DARTS 之类的算法都是偏向于初始性能好的 child architecture,在后面的训练中它们更可能被采样,这便是 unfair bias,因此如果 supernet 因为 unfair bias 错误估计了 child architecture 的性能,也就是对 candidate child architecture 的 rank 出现问题时,会大大影响我们的搜索过程,造成 unfairness,难以搜索出真正最优的 child architecture。
  作者为了缓解这个问题,提出两种 fairness 的机制,Expectation Fairness 和 Strict Fairness。
  FairNas 的 supernet 结构和 SPOS 是类似的,都是 single path,每层 里采样一个 choice block,我们定义训练过程为 \(P(m, n, L)\),其中 \(m\) 指的每层里 choice block 的个数,\(n\) 指的是 weights 被更新的次数,\(L\) 指的是 supernet 的层数。

Expectation Fairness

  顾名思义,Expectation Fairness 要保证的就是,所有的 m 种 choice block 在更新 \(n\) 次后都能有相同的期望,它的定义如下:

  SPOS 中采用的 uniform sampling 是满足这个约束的,且:

\[ \begin{aligned} E\left(Y_{l_{i}}\right) &=n * p_{l_{i}}=n / m \\ \operatorname{Var}\left(Y_{l_{i}}\right) &=n * p_{l_{i}}\left(1-p_{l_{i}}\right)=\frac{n(m-1)}{m^{2}} \end{aligned} \tag{1} \]

  但即使如此,SPOS 中也存在 unfairness,它主要是一个 order issue,即如果 我们在训练 supernet 时采样了一组 architecture \(\{M_1, M_2, M_3\}\),训练 \(M_2\) 的时候,已经用到了受到了训练完 \(M_1\) 造成的影响了,并且如果学习率还不同的话,会产生更复杂的情况。   这里作者还指出了一个反逻辑的事实,也就是 \(n\) 趋近无穷时时,每个 choice block 的采样数不可能一样,数学化就是:

\[ \operatorname{Regarding} P(m, n, L), \forall n \in\left\{x: x \% m=0, x \in N_{+}\right\}, \lim _{n \rightarrow+\infty} p\left(Y_{l 1}=\right.$ $\left.Y_{l 2}=\ldots=Y_{l m}\right)=0$ \]

  它的证明如下:

\[ Let \quad f(m, n)=p\left(Y_{l 1}=Y_{l 2}=\ldots=Y_{l m}\right) \\ f(m, n)=C_{n}^{\frac{n}{n}} C_{\frac{n(m-1)}{m}}^{\frac{n}{m}} \ldots C \frac{\frac{n}{m}}{\frac{n}{m}} \frac{1}{m^{n}}=\frac{n !}{\left(\frac{n}{m} !\right)^{m}} \frac{1}{m^{n}} \\ \begin{aligned} \lim _{n \rightarrow+\infty} f(m, n) &=\lim _{n \rightarrow+\infty} \frac{n !}{\left(\frac{n}{m} !\right)^{m} \times m^{n}} \\ &=\lim _{n \rightarrow+\infty} \frac{\sqrt{2 \pi n}\left(\frac{n}{e}\right)^{n}}{\sqrt{2 \pi \frac{n}{m}}^{m}\left(\frac{n}{e}\right)^{n}} \\ &=\lim _{n \rightarrow+\infty} \frac{\sqrt{m}}{\frac{2 \pi n}{m} \frac{m-1}{2}} \\ &=0 \end{aligned} \]

  证明中用到了 Stirling’s approximation。

Strict Fairness

  针对 Expectation Fairness 的问题,作者提出了 Strict Fairness:

  它可以保证 \(P(Y_{l_1}=Y_{l_2}=...=Y_{l_m})=1\) 随时都成立。

FairNAS

  FairNas 和 SPOS 一样,也是一个 two-stage 的 One-Shot 算法,第一个 stage 训练 train supernet,第二个 stage 搜索最优的 architecture。

Train Supernet with Strict Fairness

  FairNAS 是支持 Strict Fairness 的,它实际上是在 uniform sampling 的基础上加了一个公平采样,就是每次 update weights 时同时采样出 \(m\) 个 architecture,并且是不放回的,所以每层的每个 choice block 都有被采样的机会,然后分别训练这 \(m\) 个 architecture,然后分别做 BP,将梯度累加起来在 supernet 中做一次 update weights,论文中称这个为一次 supernet step,论文中的图把这个思想解释的很清楚:

  并且这样做符合了: \[ \begin{aligned} E\left(Y_{l_{i}}^{\prime}\right) &=n / m \\ \operatorname{Var}\left(Y_{l_{i}}^{\prime}\right) &=0 \end{aligned} \]

  方差相比 uniform sampling 来说还减小了。伪代码如下:

Searching with Supernet as an Evaluator

  搜索的过程依然使用了 evolutionary algorithm,它基于 MoreMNAS,使用 Proximal Policy Optimization 作为强化算法, 称为 NSGA-II,这个我还没研究过,伪代码如下:

Conclusion

  综合来说,FairNAS 的思想是很简单的,感觉相比 SPOS 就是多做了一个公平采样,类似于一个 trick,不过关于概率推导那段还是很反逻辑的,值得学习。

Refer

  • [1] X. Chu, B. Zhang, R. Xu, and J. Li, “FairNAS: Rethinking Evaluation Fairness of Weight Sharing Neural Architecture Search,” 2020.

相关内容


坚持原创技术分享,您的支持将鼓励我继续创作,π(3.14)元就够啦!



文章目录
  1. 1. 引言
  2. 2. Fairness
    1. 2.1. Expectation Fairness
    2. 2.2. Strict Fairness
  3. 3. FairNAS
    1. 3.1. Train Supernet with Strict Fairness
    2. 3.2. Searching with Supernet as an Evaluator
  4. 4. Conclusion
  5. 5. Refer
  6. 6. 相关内容
您是第 位小伙伴 | 本站总访问量 | 已经写了 680.3k 字啦

载入天数...载入时分秒...