Neural Architecture Search : A survey

Neural Architecture Search : A survey

http://www.jmlr.org/papers/volume20/18-598/18-598.pdf

Abstract

딥러닝이 image recognition, speech recognition, machine translation과 같은 다양한 task에 여러해동안 특출한 진보를 이루어냈다. 이 진보에 대해 중요한 하나의 요소는 새로운 neural architecture이다. 현재 사용되는 architectures들은 human experts가 manually 하게 디자인을 한 것임으로, 시간 소모가 크고, 오류가 발생하기 쉽다. 이런 이유 때문에, 자동적으로 neural architecture search를 하는 분야에 대해 관심이 생기고 있다. 저자는 이 field에 있는 연구들을 overview하고 세개의 dimension으로 카테고리를 나누고자 한다.

Introduction

딥러닝의 성공에도 불구하고, architecture engineering에 대한 수요는 증가하고 있는데, 이는 더 복잡한 neural architectures가 manually 디자인 되는 것을 의미한다. Neural Architecture Search (NAS)는 architecture engineering을 자동화 하는 것으로 automating machine learning (AutoML)안에서 다음 스텝이 된다. 지금까지, NAS 방법은 manually designed architecture에 비해서 image classification, object detection, semantic segmentation 등에서 더 나은 성능을 보여주었다. NAS는 autoML의 sub-field로 볼 수 있으며, hyper-parameter optimization과 meta-learning에 상당부분 겹친다. 

저자는 NAS를 세가지의 dimension으로 카테고리를 나누는데, 다음과 같다. search space, search strategy 과 performance estimation strategy.

1. Search Space : The search space defines which architectures can be represented in principle. Incorporating prior knowledge about typical properties of architectures well-suited for a task can reduce the size of the search space and simplify the search. However, this also introduces a human bias, which may prevent finding novel architectural building blocks that go beyond the current human knowledge.

2. Search Strategy : The search strategy details how to explore the search space (which is often exponentially large or even unbounded). It encompasses the classical exploration-exploitation trade-off since, on the other hand, it is desirable to find well-performing architectures quickly, while on the other hand, premature convergence to a region of suboptimal architectures should be avoided.

3. Performance Estimation Strategy : The objective of NAS is typically to find architectures that achieve high predictive performance on unseen data. Performance Estimation refers to the process of estimating this performance : the simplest option is to perform a standard training and validation of the architecture on dat,a but this is unfortunately computationally expensive and limits the number of architectures that can be explored. Much recent research therefore focuses on developing methods that reduce the cost of these performance estimations.

Search Space

Search space는 neural architectures를 정의한다. 몇가지 common search space를 소개한다. 가장 간단한 search space는 chain-structured neural networks로 밑의 그림과 같다.

A chain-structured neural network architecture A는 n layer의 sequence로 작성할 수 있으며 i 번째 layer는 i-1 번째로 부터 입력을 받고 i+1 번째 layer에 출력을 전달한다. Search space는 다음과 같이 parameterized 된다. (i) layer의 최대 개수, (ii) pooling, convolution과 같은 layer가 수행하는 operation의 종류, (iii) 이 operation과 관련된 hyper-parameter들 (필터의 개수, 필터의 크기 등) 혹은 fully-connected layer의 units 수. Parameter (iii)는 (ii)에 조건이 걸려있기 때문에 search space의 parameterization은 non fixed-length이다.

최근 NAS의 연구를 보면, hand-crafted architectures 즉, skip connections, multi-branch networks와 같은 디자인을 통합하였다. 이 경우 더 많은 degrees of freedom을 갖게 된다. 이러한, multi-branch architectures의 특수한 경우로, the chain-structured networks와 residual networks, 그리고 Dense net이 있다.

반복되는 motifs로 구성된 hand-crafted architectures로 부터 동기를 받아서, cell과 block과 같은 motifs를 찾는 연구가 있었다. (전체 구조를 찾는 것 대신에 말이다.) 하나의 스터디에서는 두개의 다른 cell을 최적화하였는데, normal cell은 input의 차원을 유지시키는 것이고, reduction cell은 spatial dimension을 축소시키는 것이다. 최종적인 구조는 이러한 cell을 정해진 방법으로 쌓는 것이고 이런 network의 구조는 밑의 그림에 나와있다.

이 방법은 매우 좋은 장점을 갖는데,

1. The size of the search space is drastically reduced since cells usually consist of significantly less layers than whole architectures.

2. Architectures built from cells can more easily be transferred or adapted to other data sets by simply varying the number of cells and filters used within a model.

3. Creating architectures by repeating building blocks has proven a useful design principle in general, such as repeating an LSTM block in RNNs or stacking a residual block.

결과적으로, 이런 cell-based search space는 많은 연구에서 성공적으로 적용되었다. 하지만, cell-based search space를 쓸 때, macro-architectures를 어떻게 선택할 것인지에 대한 새로운 design 선택이 제시된다. 이상적으로, macro-architectures와 micro-architecture (cell 구조)는 하나만 optimized되기 보다는 동시에 optimized가 되어야한다. 그렇지 않는다면, 잘 동작하는 cell을 찾은 이후에는 macro-architectures engineering을 manually하게 진행을 해야하기 때문이다. 한 가지 방법은 hierarchical search space를 사용하는 방법으로, 각 level에서 만들어지는 motifs들을 갖고 다른 조합을 만들어내서 다음 level로 연결시키는 방법이다.

Search space의 선택은 optimization problem의 어려움을 크게 결정한다. Fixed macro-architectures에서 single cell을 기반한 search space의 경우라도 optimization problem은 (i) non-continuous 하며 (ii) relatively high dimensional 하다. (더 복잡한 모델이 더 나은 성능을 보임으로, 더 디자인 고려요소가 많아진다.)

Many search space의 architectures가 fixed-length vectors로 표현된다는 점을 주의해야한다.

Search Strategy

많은 서로 다른 search strategies가 neural architectures 공간에서 사용될 수 있다. (Random search, Bayesian optimization, evolutionary methods, reinforcement learning (RL), and gradient-based methods.) 역사적으로, evolutionary algorithm은 neural architectures를 진화시키기 위해서 이미 사용되었다. Bayesian optimization은 2013년 이후로 몇차례의 성공을 이룩했는데, state-of-the-art vision architectures, state-of-the-art performance for CIFAR-10 without data augmentation을 성취해냈다. 또한, the first automatically-tuned neural network를 갖고 human experts를 대상으로 competition dataset에서 승리하였다.

RL로서의 NAS에서는, neural architectures를 생성하는 것은 agent의 action이라고 고려하고, action space는 search space와 동일하다. Agent의 reward는 validation set에 대한 trained network의 성능을 기반으로 한다. 다른 RL 접근방법들이 어떻게 agent의 policy를 표현하고 이를 최적화 할지에 따라서 다르다. 예로, Neural network architectures를 encoding하는 string을 sample하는 RNN policy가 있다. RNN은 policy gardient algorithm을 사용해서 최적화를 시키고, 그 다음 연구로 proximal policy optimization이 사용되었다. 다른 예로는 Q-learning을 사용하여 hyper-parameter와 layer의 type을 연속적으로 선택하는 policy를 학습하였다.

이러한 접근 법의 다른 견해는 policy가 순차적으로 architecture를 생성하기 위한 action을 sampling하고, 환경의 state에 지금까지 sampling된 action의 summary를 포함하며, 보상은 순차적인 process 동안 환경과의 상호 작용이 발생하지 않기때문에, architecture sampling process를 단일 동작의 순차적 생성으로 해석하는 것보다 직관적이다는 것이다. 이것은 RL 문제를 stateless multi-armed bandit problem으로 단순화 시킨다.

관련된 연구의 접근 방식은 현재 상태는 architecture이고, reward는 architecture의 성능을 추정한 것이며, action은 function-preserving mutations에 대응된다. 또한, variable-length network architecture를 처리하기 위해서, LSTM을 사용하여 architecture를 fixed-length로 encoding 한다. 이 encoding된 것을 바탕으로 actor network는 sampling 작업을 결정한다. 이 두 구성 요소의 조합은 policy를 구성하며 Reinforcement policy gradient algorithm을 사용하여 end-to-end learning을 가능하게 한다. 이 방법은 똑같은 state를 방문하지 않게 된다.

RL을 사용하는 것 외에 다른 방법은 neuro-evolutionary 접근 방법이다. Neural network를 디자인 하는 첫번째 접근 방법은 30년 전으로 거슬러 올라간다. Miller는 genetic algorithm을 사용하여 architecture를 제안하고, 역전파를 사용하여 가중치를 최적화 하였다. 그 이후로 많은 neuro-evolutionary 접근 방법은 architecture structure와 가중치에 genetic algorithm을 사용하여 최적화를 하였다. 그러나, supervised learning을 진행할 때, 수백만개의 가중치를 갖는 modern neural network로 scaling할 때, SGD 기반의 가중치 최적화 방법은 evolutionary 방법보다 우세하다. 최근의 neuro-evolutionary 접근법은 gradient-based 방법으로 가중치를 최적하고 neural architecture 자체에만 evolutionary algorithm을 사용한다. Evolutionary algorithm은 model의 population 즉, 학습된 network의 집합을 진화시킨다. 모든 evolution step에서, 적어도 하나의 model을 population에서 선택하고, parent로 사용하여 돌연변이를 적용하여 child를 만들도록 한다. NAS의 관점에서, mutation은 layer의 추가, 제거, hyper-parameter 변경, skip connection 추가 등을 변경하는 작업이다. child를 학습한 후에 validation set으로 그들의 fitness를 평가하고 population에 추가한다.

Neuro-evolutionary 방법은 parent를 sampling하고, population을 update하고, child를 생성하는지에 관련된 것이다. 여러가지 방법이 있겠지만, (i) population중 가장 안좋은 individual을 제거하는 방법 (ii) 가장 오래된 individual을 제거하는 방법 (iii) individual을 전혀 제거하지 않는 방법이 있다. child를 생성하기 위해서, 대부분의 접근 방법은 child network를 무작위로 초기화하지만, 최근에는 lamarckain inheritance를 사용하여, 부모에서 학습된 weight이 child에게 넘어가도록 하였다. 또한, mutation에 영향을 받지 않는 모든 parameter를 상속받는 방법을 사용했는데, 이 방법은 무작위 초기화 방법에 비해서 학습 속도가 빠르다는 장점을 갖는다. 또한, NAS는 learning rate schedule을 최적화 하는 방법에도 사용 될 수 있다.

Real은 RL과 evolution, random search를 비교한 연구를 수행하여, RL과 evolution 방법이 언제나 더 나은 성능을 보여주며, 작은 모델을 찾아내거나 정확하게 수행된다는 것을 확인하였다. 두가지 방법 모두 random search 보다 일관되게 우수한 성능을 보여주었다.

Bayesian optimization (BO)는 hyper-parameter를 최적화하기 위한 가장 보편적인 방법이지만, 일반적인 BO toolbox는 Gaussian process를 기반으로 하고 낮은 차원의 continuous optimization problem에 중점을 두어, 많은 group에서 NAS에 적용되지 않았다. 최근 연구는 고전적인 GP-based BO 방법을 사용하기 위해서 architecture search space에 kernel function을 끌어냈다. 대조적으로, 몇몇 연구에서는 high dimensional conditional space을 효율적으로 탐색하기 위해서 tree 기반 model 또는 random forest를 사용하여 neural architecture와 그 hyper-parameter를 공동으로 최적화하여 광범위한 문제에 대해 state-of-the-art 성능을 보였다. 완전한 비교가 부족하지만, 이러한 접근 방법이 evolutionary algorithm보다 우월할 수 있다는 증거들이 있다.

Negrinho와 Gordon, Wistuba는 search space의 tree structure를 이용하고, Monte Carlo Tree Search를 사용한다. Elsken은 보다 정교한 search mechanism을 요구하지 않고, 더 나은 성능을 애는 architecture의 방향으로 greedily moving하여 high quality architecture를 발견하는 간단하면서도 우수한 hill climbing algorithm을 제안하였다.

Performance Estimation Strategy

앞에서 보듯이, search strategy는 validation set에서의 정확도와 같은 성능 측정을 최대화하는 neural architecture A를 찾는 것을 목표로 한다. Search process를 진행하기 위해서, 이 strategy는 주어진 architecture A를 평가해야한다. 이를 수행하는 가장 간단한 방법은 A를 training set에서 학습시키고, validation set에서 성능을 평가하는 것이다. 그러나 모든 architecture를 학습시킨다고 본다면, NAS의 경우 수천 GPU days 계산 요구가 발생한다. 이것은 자연스럽게 성능 추정을 가속화하는 방법을 개발하도록 하였다. 밑의 표는 NAS에서 performance estimation의 속도를 향상시키는데 사용된 방법들을 보여준다.

Performance은 전체 training 이후 실제 성능의 low fidelity를 기준으로 성능을 예측할 수 있다. 이는 더 짧은 training step, data의 subset으로 학습, 낮은 해상도 이미지를 사용하거나, 적은 수의 layer와 cell을 사용하는 방법을 포함한다. 이 방법은 computation cost를 줄이지만, 성능이 일반적으로 과소 평가되기 때문에 추정치에서 편차가 발생한다. 이는 search strategy가 다른 architecture의 순위 지정에만 의존하고 상대적 순위가 안정적으로 유지되는 한 문제가 되지 않을 수 있다. 그러나, 최근 연구 결과에 따르면, 근사값과 평가 값 사이의 차이가 크면, 이 상대적 순위는 극적으로 변할 수 있다.

Architecture의 성능을 평가할 수 있는 또 다른 방법은 learning curve extrapolation이다. 초기 learning curve를 extrapolation 하여 수행 능력이 떨어지는 것으로 보이는 것들은 예측을 중단시켜 architecture search process의 속도를 높인다. 다른 방법으로, 새로운 architecture의 성능을 예측하는 surrogate model을 사용한다. Learning curve extrapolation을 사용하지 않지만, architecture/cell property를 기반으로 성능을 예측하고, 학습 중에 보이는 것보다 큰 크기의 architecture/cell에 extrapolation을 적용한다.  Neural architecture 의 성능을 예측하기 위한 주요 어려운 점은 search process의 속도를 높이기 위해서 상대적으로 적은 search space에서 좋은 예측이 상대적으로 적은 평가를 기반으로 만들어 져야 한다는 것이다.

성능 평가 속도를 높이기 위한 다른 방법으로 이전에 trained된 다른 architecture의 weights을 기반으로 새로운 architecture의 weight을 초기화 하는 것이다. 이 방법은 network morphisms이며, network에 의해서 대표되는 기능은 그대로 두고 architecture를 수정할 수 있기 때문에 빠르다. 따라서, 처음부터 training을 하지 않아도, network의 용량을 지속적으로 늘리면서 고성능을 유지할 수 있다. 적은 수의 epochs에 대한 계속적인 학습은 network morphisms에 의해 도입된 추가적인 용량을 사용할 수도 있게 한다. 이러한 접근 방식의 장점은 architecture의 크기에 상한 경계가 없는 search space를 허용한다는 것이다. 반면에, 엄격한 network morphisms은 architecture를 더 크게 만들 수 있으며, 지나치게 복잡한 architecture로 이어질 수 있다. 이런 문제는 shrinking architectures를 허용하는 approximate network morphisms을 사용함으로써 약화될 수 있다.

One-shot architecture search는 모든 architecture를 super graph의 다른 sub graph로 취급하고, 이 super graph의 가장자리가 공통인 architecture간의 weights을 공유한다. 하나의 one-shot model의 weight만 학습해야 하며, architectures는 별도의 training 없이 평가할 수 있다. One-shot model은 교육이 필요없기 때문에, architectures의 성능 평가 속도를 크게 높여주며 GPU days가 몇 시간 밖에 걸리지 않는 method를 생성해낸다. One-shot model 은 일반적으로 최상의 architecture의 실제 성능을 심각하게 과소 평가함으로 큰 bias가 있다. 밑의 그림은 One-shot architecture search을 보여준다.

ENAS는 search space에서 architecture를 sampling하고 reinforcement를 통해 얻은 대략적인 gradient를 기반으로 one-shot model을 교육하는 RNN controller를 학습한다. DARTS는 one-shot model의 각 edge에 candidate operation을 혼합하여 search space의 연속적인 relaxation과 함께 one-shot model의 모든 가중치를 공동으로 최적화한다. DARTS와 같이 연산에 대한 실수 가중치를 최적화하는 대신 SNAS는 candidate operations에 대한 distribution을 최적화 한다. 이 저자는 불연속 distribution을 relaxation하고 이를 구별할 수 있도록, gradient descent를 통한 최적화를 가능하게 하기 위해서 concrete distribution과 reparametrization을 사용한다. GPU memory에 전체 one-shot model을 유지할 필요성을 극복하기 위해서 ProxylessNAS도 제안이 되었다.

One-shot NAS의 한계는 priori으로 정의된 super graph가 search space를 sub graph로 제한한다는 것이다. 더욱이, architecture searching 동안 전체 super graph가 GPU memory에 존재할 것을 요구하는 접근법은 상대적으로 작은 super graph와 search space로 제한 될 것이고, 따라서, 일반적으로 cell-based search space와 함께 사용된다. Weight sharing에 기반한 접근 방식이 NAS에 필요한 계산 자원을 (수천에서 수 GPU)로 크게 감소시켰지만, 현재 architecture의 sampling 분포는 이를 고정하지 않고 one-shot model과 함께 최적화 된다. 예를 들어, search space이 다른 것보다 많으면, 이러한 architecture에 더 적절하게 적용되는 one-shot model의 weights으로 이어질 수 있으며 search space의 이러한 부분에 대한 검색의 bias를 강화할 수 있다. 이것은 NAS의 premature convergence를 가져오거나, architecture의 one-shot과 실제 성능 사이의 상관 관계를 거의 만들지 않을 수 있다. 

Future Directions(Skip, 꼭 읽어보길 바란다.)

Neural architecture search, NAS, Deep learning