引言

　　最近读了一篇 WWW2020 的论文[1]，它在协同过滤中应用 NAS，其中提出的 SIF 算法本文就不做介绍了。本文介绍 SIF 里用到的 NAS 算法 NASP [2]，这两篇文章的作者都是第四范式的一个大佬，NASP 发表在 AAAI2020，本文对它作一个简单的笔记。

1. Darts 的缺陷

　　NASP 针对的主要是 DARTS 的一些缺陷，作者在论文中列出了 DARTS 的一些缺陷：

• Search efficiency：DARTS 的 supernet 和 softmax 的计算方式导致 search space 里的所有 operations 都需要在计算 w 的时候做 forward 和 backward-propagated，而且还涉及到一些二阶梯度的计算，这是非常大的一个开销。
• Architecture performance：因为 architecture 是通过 softmax 后的概率得到的，所以各个 operation 之间可能存在一些 correlation，就比如针对一条边上有三个候选 operation，它们的概率分别是 0.3，0.3 和 0.4，你很难说这三个 operation 的性能差距很大，甚至概率小的 operation 会有更好的性能。
• Model complexity：DARTS 在损失函数上并不能有效限制模型的大小。

2 NASP

　　针对 DARTS 的缺陷，NASP 提出一些改进方法，下面分别介绍下。

2.1 Proximal Algorithm (PA)

　　作者在论文中说，NASP 是在 NAS 领域中首先应用 PA 算法的，也就是近端梯度算法。PA 算法的关键步骤是：

mathbf{x}=operatorname{prox}_{mathcal{S}}(mathbf{z})=arg min _{mathbf{y}} 1 / 2|mathbf{y}-mathbf{z}|_{2}^{2} text { s.t. } mathbf{y} in mathcal{S}

　　然后不断迭代：

mathbf{x}_{t+1}=operatorname{prox}_{mathcal{S}}left(mathbf{x}_{t}-varepsilon nabla fleft(mathbf{x}_{t}right)right)

　　PA 算法也有一种变种叫做 lazy proximal step：

overline{mathbf{x}}_{t}=operatorname{prox}_{mathcal{S}}left(mathbf{x}_{t}right), quad mathbf{x}_{t+1}=mathbf{x}_{t}-varepsilon nabla fleft(overline{mathbf{x}}_{t}right)

　　NASP 中应用 PA 的目的主要是为了处理后面加的 discrete 的限制，利用 PA 可以进行相应的优化。

2.2 Search Objective

　　NASP 有一个很重要的思想就是在 search 的时候保持 search space 是 differentiable，但是训练模型的时候又让 architecture 是 discrete 的，其实做法也很简单，也就是在训练时把每条 edge 上的所有 op 的 logits 取一个 argmax，这个 op 的权重赋值成 1，其它 op 的权重赋值成 0，这就是一个 discrete 的过程，这样在训练 child model 的时候，每条 edge 就只会用到一个 op 了，在训练完 child model 后再把 edge 上所有 op 的权重恢复成取 argmax 之前的数值，再做梯度下降。论文中也画了一张图来表现 NASP 与其它算法的区别：

　　具体来说，discrete 的限制可以写成：

begin{aligned} &bar{O}^{(i, j)}left(x^{(i)}right)=sum_{k=1}^{|mathcal{O}|} a_{k}^{(i, j)} mathcal{O}_{k}left(x^{(j)}right)/ &text { s.t. } mathbf{a}^{(i, j)} in mathcal{C} end{aligned}

mathcal{C} 的限制也很简单 left{mathbf{a} mid|mathbf{a}|_{0}=1, text { and } 0 leq a_{k} leq 1right} ，它通过 0 范数保证了只能有一个 op 的权重大于 0。

　　为了控制模型的复杂度，NASP 又设计了一个正则项：

mathcal{R}(mathbf{A})=sum_{k=1}^{|mathcal{O}|} p_{k} / bar{p}left|mathbf{dot { a }}_{k}right|_{2}^{2} / bar{p}=sum_{i=1}^{|mathcal{O}|} p_{i}

mathbf{dot { a }}_{k} 是 mathbf{A} 里的第 k 列， p_j 表示第 i 个 op 的参数量，思想其实很简单，就是针对每个 op 的参数量做一个加权。

　　所以整个 search objective 可以写成：

min _{mathbf{A}} mathcal{F}left(w^{*}, mathbf{A}right), mathbf{s . t .}left{begin{array}{l} w^{*}=arg min mathcal{L}_{text {train }}(w, mathbf{A}) / mathbf{a}^{(i, j)} in mathcal{C} end{array}right. / mathcal{F}(w, mathbf{A})=mathcal{L}_{mathrm{val}}(w, mathbf{A})+eta mathcal{R}(mathbf{A})

　　越大的 eta 往往意味 search 到一个越小的 architecture。

2.3 Search Algorithm

　　如果我们在搜索的过程里应用 PA 算法：

mathbf{A}_{t+1}=operatorname{prox}_{mathcal{C}}left(mathbf{A}_{t}-varepsilon nabla_{overline{mathbf{A}}_{t}} mathcal{F}left(wleft(mathbf{A}_{t}right), mathbf{A}_{t}right)right)

　　可以看出依然需要计算二阶梯度，开销依然很大，或者应用 lazy proximal step：

begin{aligned} overline{mathbf{A}}_{t} &=operatorname{prox}_{mathcal{C}}left(mathbf{A}_{t}right) / mathbf{A}_{t+1} &=mathbf{A}_{t}-varepsilon nabla_{overline{mathbf{A}}_{t}} mathcal{F}left(wleft(overline{mathbf{A}}_{t}right), overline{mathbf{A}}_{t}right) end{aligned}

　　然而依然不可行，以为这并不能保证 mathbf{A}_t 是在 [0,1] 之间的。

　　因此作者提出了 NASP 算法，伪代码如下：

　　NASP 主要基于一个发现 operatorname{prox}_{mathcal{C}}(mathbf{a})=operatorname{prox}_{mathcal{C}_{1}}left(operatorname{prox}_{mathcal{C}_{2}}(mathbf{a})right) ，其中 mathcal{C}_{1}=left{mathbf{a} mid|mathbf{a}|_{0}=1right} （作者开源的源码里主要就是通过 argmax 得到，然后二值化） 和 mathcal{C}_{2}=left{mathbf{a} mid 0 leq a_{k} leq 1right} （作者开源的源码里主要就是通过硬剪裁得到），这个发现具体的证明如下：

　　同时，我们可以发现 NASP 是没有计算二阶梯度的，论文中给出的解释这样的：

　　大致意思就是 discrete 的 architecture 要比 continuous 的 architecture 更加稳定，不需要在更新 w 的时候再更新 architecture，因此去掉二阶梯度并不会带来精度上的过大损失，反而能大大加速模型的搜索过程。论文中给出 NASP 要比 STOA 有着 10 倍以上的加速。

总结

　　阅读完 NASP，还是挺有启发的，特别是 search space 之间 discrete 和 continuous 的转换，除此之外作者还应有了 PA 算法，但是我不太懂这一个应用的创新，阅读了作者开源的源码，感觉也就是在做梯度下降，作者开源的 NASP 源码包括 SIF 的源码和 DARTS 的源码有大部分基本是一样的，可以看作是在 DARTS 工作上的一个拓展吧。

Refer

• [1] Q. Yao, X. Chen, J. T. Kwok, Y. Li, and C.-J. Hsieh, “Efficient Neural Interaction Function Search for Collaborative Filtering,” in Proceedings of The Web Conference 2020, 2020, pp. 1660–1670.
• [2] Q. Yao, J. Xu, W.-W. Tu, and Z. Zhu, “Efficient Neural Architecture Search via Proximal Iterations,” 2020.