Probabilistic Neural Architecture Search

Motivation

Most existing methods of NAS cannot be directly applied to large scale problems because of their prohibitive computational complexity or high memory usage.

This paper proposes a Probabilistic approach to NAS (PARSEC) that drastically reduces memory requirements while maintaining SOTA computational complexity, making it possible to directly search over more complex architectures and larger datasets.

• a memory-efficient sampling procedure wherein we learn a probability distribution over high-performing neural network architectures.

• Importantly, this framework enables us to transfer the distribution of architectures learnt on smaller problems to larger ones, further reducing the computational cost.

Importance-weighted Monte Carlo empirical Bayes

• $p(\alpha|\pi):$ a prior on the choices of inputs and operations that define the cell, where hyper-parameters $\pi$ are the probabilities corresponding to the different choices.
• $y: \text{target}$
• $\mathbf{X}: \text{input}$
• $v:$ network weights

Given the estimator:

From equation (7):

$\nabla_{v, \pi} \log p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\pi})\\ =\frac{1}{p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\pi})} \int \nabla_{\boldsymbol{v}, \pi} \log p(\boldsymbol{y}, \boldsymbol{\alpha} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\pi}) p(\boldsymbol{y}, \boldsymbol{\alpha} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\pi}) \mathrm{d} \alpha \\ = \frac{1}{p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\pi})} {\color{red}\int} \nabla_{\boldsymbol{v}, \pi} \log p(\boldsymbol{y}, \boldsymbol{\alpha} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\pi}) p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\alpha}) {\color{red}p(\boldsymbol{\alpha} \mid \boldsymbol{\pi}) \mathrm{d} \alpha} \\ = \frac{1}{p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\pi})} {\color{red}\sum_{k=1}^K} \nabla_{\boldsymbol{v}, \pi} \log p(\boldsymbol{y}, {\color{red}\boldsymbol{\alpha}_k} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\pi}) p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{v}, {\color{red}\boldsymbol{\alpha}_k}) \\ = \frac{1}{p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\pi})} \sum_{k=1}^K \nabla_{\boldsymbol{v}, \pi} (\log p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\alpha}_k)+\log p(\boldsymbol{\alpha}_k|\boldsymbol{\pi})) p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\alpha}_k) \\$

$= \frac{1}{p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\pi})} \sum_{k=1}^K \nabla_{\boldsymbol{v}} (\log p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\alpha}_k)p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\alpha}_k))+\nabla_{\boldsymbol\pi}\log p(\boldsymbol{\alpha}_k|\boldsymbol{\pi}) p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\alpha}_k) \\$

$= \sum_{k=1}^K \frac{p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\alpha}_k)}{p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\pi})}\nabla_{\boldsymbol{v}} \log p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\alpha}_k)+\sum_{k=1}^{K}\frac{p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\alpha}_k)}{p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{v}, \boldsymbol{\pi})}\nabla_{\boldsymbol\pi}\log p(\boldsymbol{\alpha}_k|\boldsymbol{\pi}) \\$

Reference

• https://arxiv.org/pdf/1902.05116.pdf