ENAS(Efficient Neural Architecture Search via Parameter Sharing)

2016년, 구글브레인에서 강화학습을 이용한 AutoML 방법론인 NAS(Neural Architecture Search with Reinforcement Learning)라는 논문을 발표합니다. 네트워크 구조가 수도 없이 많이 나왔지만, 사실 데이터에 맞는 구조를 디자인하는것은 매우 힘든 작업입니다. 만들고 나서 튜닝하는 것 까지 합치면 굉장히 많은 노력이 필요합니다. 심지어 내가 만들어놓은 구조가 최고의 구조라는 보장조차도 없습니다.

여기서 나온 아이디어가 “딥러닝으로 딥러닝 구조를 학습하자!”입니다. 2016년에 발표한 NAS 논문이 이쪽 분야에서는 가장 최초의 시도라고 할 수 있습니다. 하지만 처음 나온 방법론인 만큼 단점도 있었으니…가장 큰 단점은 어마어마한 연산량이었습니다. CIFAR-10을 실험 할 때도, 800개의 GPU를(!)사용했으며 그럼에도 불구하고 많은 시간이 걸렸다고 합니다. 시간이 나면 NAS에 대해서 포스팅도 따로 해보도록 하겠습니다.

그 이후로 연산량 문제를 해결하는 방법이 나왔으니, 그게 ENAS(Efficient Neural Architecture Search via Parameter Sharing)입니다.

Introduction

먼저 NAS의 기본 구조를 살펴보자면, RNN controller 부분이 있습니다. 이 controller는 네트워크 구조 후보군을 만들어주는 역할을 합니다. 그리고 이 구조를 학습시키고 성능을 측정합니다. 측정 결과는 하나의 guiding signal로 더 좋은 네트워크 구조를 찾는데 도움을 줍니다. 이렇게 RNN을 수렴하게 학습을 시키며, 강화학습이니까 각 네트워크 구조의 정확도가 reward signal로 쓰이게 됩니다. 하지만 위에서도 얘기했듯이, NAS는 좋은 성능을 보여주긴 했지만 계산복잡도가 매우 높고, 시간이 오래걸립니다. Task마다 다르긴 했지만, 450개의 GPU를 쓰고도 3~4일이 걸리기도 했습니다. 딥러닝이 아무리 좋은 성능을 내준다고 하더라도 일반적으로 이렇게 어마어마한 양의 리소스를 가용할 수 있는 곳은 얼마 없을 것입니다.

이 논문에서는 NAS의 계산복잡도의 주 원인이 child model(생성되는 구조들)이 학습한 weight들을 완전히 버려버리기 때문이라고 말합니다. 즉, 매번 모델을 만들어서 열심히 학습을 해도, 결국 다음 모델을 만들면 weight 재활용 따위는 없이 새로 학습을 해야하기 때문이란 겁니다. 그래서 이 논문의 가장 큰 contribution은 다음과 같습니다.

• Child model들이 weight를 공유하게 만들어서 밑바닥부터 학습하지 않게 만들자

즉, child model 간 parameter 공유 뿐만 아니라 좋은 성능까지 유도해서 계산 복잡도와 퍼포먼스 두 마리 토끼를 잡아보자 입니다.

Methods

ENAS의 아이디어는 쉽게 이렇게 생각하시면 됩니다. NAS의 각 iteration마다 생기는 모든 graph가 larger graph(전체 그래프)의 sub-graph(하위 그래프)입니다. 다시말해서, NAS의 search space를 directed acyclic graph(DAG)로 나타낼 수 있다는 말과 같습니다.

위 그래프가 DAG의 모습을 나타내고 있습니다. DAG를 직역하자면 방향성 비순환 그래프로 방향성을 가지면서 루프를 생성하지 않는 그래프를 말합니다 (루프는 자기 자신에게 돌아오는 경로). 전체 search space가 DAG 그래프 전부, 빨간 부분이 sub-graph라고 할 수 있습니다. 노드는 local computation이고 edge는 information flow를 뜻합니다. 각 노드의 local computation은 각자의 파라미터를 가지고 있으며 activate 될 때만 사용된다고 보면 됩니다. 이를 보면, NAS와는 다르게 ENAS는 search space에 있는 모든 child model들의 파라미터가 공유되게끔 만들어져 있습니다.

Designing Recurrent Cells

Recurrent cell을 정해주기 위하여, 일단 N개의 노드를 가지고 있는 DAG를 생각해봅시다. ENAS의 controller는 RNN이고 어떤 edge를 activate할지(빨간색으로 만들지), 그리고 어떤 노드를 쓸지(local computation) 정해줍니다. NAS에서는 노드의 배치 등등을 사용자가 정해주고, 각 노드의 operation만 학습을 했습니다. 반면에, ENAS에서는 RNN cell의 노드 배치와 operation을 모두 같이 학습합니다. 따라서 더 유연한 학습이 가능합니다.

Recurrent cell을 생성하기 위해서, 먼저 $N=4$ 일 때 ENAS의 과정을 간단한 recurrent cell을 가지고 보여드리겠습니다. 아래 Figure 1이 이 과정을 묘사한 그림입니다. $x_t$는 recurrent cell에 입력되는 input signal로, 텍스트 데이터를 예로 들자면 word embedding vector가 될 수 있습니다. $h_{t-1}$은 이전 time step의 output입니다.

1. Node 1 : 먼저 controller가 activation function을 sample합니다. 아래 그림에서 가장 오른쪽 그림을 보면, 여기서는 tanh를 선택합니다. 이를 식으로 나타내면 다음과 같습니다. \({ h }_{ 1 }=tanh({ x }_{ t }\cdot { W }^{ (x) }+{ h }_{ t-1 }\cdot { W }_{ 1 }^{ (h) })\)
2. Node 2 : 이제 이전 index와 activation function을 sample합니다. 여기서는 바로 직전 index 1과 ReLU가 나왔습니다. \({ h }_{ 2 }=ReLU({ h }_{ 1 }\cdot { W }_{ 2,1 }^{ (h) })\)
3. Node 3 : 다시 한번 더 이전 index와 activation function을 sample합니다. 이번에는 index 2와 ReLU가 나왔습니다. \({ h }_{ 3 }=ReLU({ h }_{ 2 }\cdot { W }_{ 3,2 }^{ (h) })\)
4. Node 4 : 여기서는 index 1과 tanh가 나왔습니다. \({ h }_{ 4 }=tanh({ h }_{ 1 }\cdot { W }_{ 4,1 }^{ (h) })\)
5. 결과물 산출을 위해서 어떤 다른 노드의 입력으로 쓰이지 않는 노드들의 평균을 구합니다. 예를 들자면 그림에서 노드 3,4는 다른 노드의 input으로 사용되지 않았습니다. 그렇기 때문에 recurrent cell의 output은 다음과 같습니다. \({ h }_{ t }=({ h }_{ 3 }+{ h }_{ 4 })/2\)

각 노드와 엣지마다 파라미터 행렬 ${ W }_{ l,j }^{ (h) }$이 존재합니다. 여기서 $l$과 $j$는 각각 노드와 인덱스를 뜻합니다. 이전 index를 선택함에 따라 controller도 어떤 파라미터 행렬을 사용할지 결정합니다. ENAS는 이러한 방식으로 작동하기 때문에 전체 search space에서 파라미터를 공유한다고 말할 수 있습니다.

만약 activation function을 4개(tanh, ReLU, identity, sigmoid) , 노드를 $N$개 사용한다면 search space에는 총 ${ 4 }^{ N }\times N!$개의 구조가 존재하게됩니다.

Training ENAS and Deriving Architectures

논문에서는 hidden cell이 100개인 LSTM을 controller 네트워크로 사용했다고 합니다.

ENAS에는 총 2개의 학습 가능한 파라미터 셋이 있습니다. 하나는 controller LSTM 파라미터 $\theta$이고 child models의 공유 파라미터인 $w$가 있습니다. 먼저 트레이닝 데이터를 $w$를 학습시킵니다. Penn Treebank 데이터셋 기준으로, $w$는 배치사이즈 64 기준 400번 돌렸다고합니다. 두 번째로는 controller 파라미터인 $\theta$를 학습시킵니다. 이렇게 두 단계를 차례대로 반복 학습을 시키면 됩니다.

Training the shared parameters $w$

$w$를 학습시킬 때, 먼저 controller의 policy인 $\pi (m;\theta)$를 고정합니다. 여기서 $m$은 모델을 뜻합니다. 그리고 우리가 일반적으로 아는 SGD(Stochastic Gradient Descent)로 ${ E }_{ m\sim \pi }\left| L(m;w) \right| $를 최소화합니다. Cross-entropy loss를 사용하며 그래디언트는 다음과 같이 몬테 카를로(Monte Carlo estimate)방법을 써서 추정합니다. $${ \triangledown }_{ w }{ E }_{ m \sim \pi (m;\theta ) }\left[ L(m;w) \right] \approx \frac { 1 }{ M } \sum _{ u-1 }^{ M }{ { \triangledown }_{ w }L({ m }_{ i },w) } $$ 위 식 ${ \triangledown }_{ w }{ E }_{ m\sim \pi (m;\theta ) }\left[ L(m;w) \right] $은 그래디언트에 대한 불편추정치(unbiased estimate)입니다. 그러나 $m$이 고정되어있을 때, 이 추정치는 일반적인 SGD보다 저 높은 분산치를 가지고 있습니다. 즉, 불안정한 값을 가지게 됩니다. 그런데, 논문 저자들은 신기하게도 $M=1$일 때 $w$ 파라미터 업데이트가 잘 된다는 것을 확인했다고 합니다. 즉, 어떤 단일 모델 $m$ 하나를 사용한다면 전혀 상관없다는 것이죠.

Training the controller parameter $\theta$

$w$를 학습시켰으니 이제 child parameter $w$를 고정시키고 policy parameter $\theta$를 학습시킬 차례입니다. Reward ${ E }_{ m\sim \pi (m;\theta ) }\left[ R(m;w) \right] $ 를 최대화하는 방향으로 학습시켜야 합니다. Reward $R(m;w)$ 는 검증 데이터(validation set)를 사용해서 측정합니다. 이는 당연히 ENAS가 overfit 되지 않고 좀 더 generalize 되게끔 학습시키기 위함입니다.

Deriving Architectures

전체적인 과정을 정리해보면 다음과 같습니다. 먼저 policy $\pi (m;\theta)$를 통해 몇 개의 모델을 뽑습니다. 다음으로는 각 모델에 대한 reward(validation set에 대한 성능)을 측정합니다. 그리고 가장 높은 reward가 나온 하나의 모델만 가져갑니다. 이는 NAS와의 가장 큰 차이점이라고도 할 수 있습니다. NAS에서는 여러 개의 모델을 밑바닥부터 학습시켜서(이게 가장 계산 복잡도가 높은 이유입니다) 가장 높은 성능을 보여주는 모델을 선택합니다. 그러나 ENAS에서처럼 파라미터를 공유한다면 훨씬 더 계산복잡도를 낮출 수 있습니다.

Designing Convolutional Networks

이제 CNN(Convolutional Neural Network) 구조를 만들기 controller에 대해 알아보겠습니다. 위에서 recurrent cell search space에서는 1) 어떤 노드를 연결할 것인지 그리고 2) 어떤 activation function을 사용할 것인지 정해줬습니다. 이번에 convolutional models search space에서도 마찬가지로 어떤 노드와 연결할 것인지, 어떤 computation operation을 적용할 것인지 정해줍니다.

위 그림은 CNN 구조가 생성되는 과정을 보여주고 있습니다. Controller에서는 다음과 같이 총 6가지의 operation이 나옵니다.

• 3 x 3 or 5 x 5 conv filters
• 3 x 3 or 5 x 5 depthwise-separable conv filters
• Average or max pooling with 3 x 3 kernal size

$L$개의 layer를 가진 CNN 구조를 만든다고 할 때, 네트워크는 총 $6^L \times 2^{L(L-1)/2}$개 생성될 수 있습니다. 실험에서는 $L$값을 12로 설정해서 $1.6 \times 10^{29}$개의 네트워크 후보군이 있었다고 합니다.

Designing Convolutional Cells

전체적으로 네트워크를 구성하기보다는, 작은 여러개의 모듈로 나눠서 합칠 수 있습니다. 위 그림은 이러한 방식을 사용할 경우 convolution cell을 어떻게 구성하는지 보여주고 있습니다.

Figure 5를 기준으로(노트가 총 4개이므로 $B=4$) 설명드리면, 먼저 input으로 node 1과 2가 들어갑니다. 이는 Figure 4의 이전 conv cell을 거친 결과물입니다. 이제 남은 2개의 노드에 대해서는 controller RNN을 통해서 두 가지 결정을 합니다. 먼저 어떤 노드와 연결시킬지 결정하고 그 다음으로 어떤 operation을 적용시킬지 결정합니다. 총 5가지의 operation(identity, 3 x 3 or 5 x 5 conv filter, 3 3 x 3 average pooling or max pooling) 중에 하나를 선택합니다. Figure 5 기준으로 자세한 과정은 다음과 같습니다.

1. 노드 1과 2는 input 노드이기 때문에 아무런 과정을 거치지 않습니다.
2. Node 3 : controller를 통해 나온 연결 노드가 2번 노드이므로, 2번 노드를 operation A와 operation B(sep 5x5, id)로 연결해줍니다.
3. Node 4 : controller에서 node 3과 node 1, 그리고 avg 3x3과 sep 3x3이 나왔기 때문에 output은 다음과 같습니다. \(h_4 = avg\_pool\_3\times3(h_3)+sep\_conv\_3\times3(h_1)\)
4. 최종적으로 4번 노드에서만 결과물이 나오므로 $h_4$만 output으로 취급합니다. 만약 여러 개의 노드가 output이라면 자동적으로 concatenate 과정을 거쳐 하나로 통일해줍니다.

Reduction cell에서는 똑같은 방식으로 cell 하나를 뽑되, stride를 2로 줍니다. 이를 통해 spatial dimension이 2만큼 줄어듭니다. RNN controller로 뽑는 블럭은 총 $2(B-2)$개가 됩니다.

노드 $i(3<=i<=B)$에서, 총 $(5\times(B-2)!)^2$ 종류의 cell 생성이 가능합니다. Convolutional cell과 reduction cell 두 개가 있으므로, search space의 최종 크기는 $(5\times(B-2)!)^4$가 됩니다. 논문에서는 $B=7$로 두어 search space가 $1.3\times10^{11}$의 크기가 됩니다.

Experiments

논문에서는 Penn Treebank dataset와 CIFAR-10 dataset을 사용하여 실험을 진행합니다.

Language Model with Penn Treebank

Penn Treebank는 벤치마크용 텍스트 데이터로 자주 쓰이는 데이터입니다. 실험에 대한 구체적인 설계는 논문에 상세하게 설명되어있으니(Adam optimizer 썼고 등등…) 자세한 내용은 논문을 참고해주시기 바랍니다. 특이할만한 점으로는 premature convergence를 방지하기 위해서 tanh constant, temperature for the sampling logits, controller’s sample entropy 등 여러가지 제한을 걸어두었습니다. 여기에 노드 간 transformation에서 highway connection을 적용해줬다고 합니다.

학습에는 GTX 1080TI를 사용했다고 하며 모델을 찾는데 10시간 정도 걸렸다고 합니다. 최종적인 모델은 위 그림과 같습니다. 재미있는 점으로는 활성 함수로 sigmoid나 identity가 쓰이지 않았다는 점입니다. 그리고 활성 함수 cell들이 local optimum이라고 추측하고 있습니다. 이는 무작위로 비선형 활성함수를 가지고 있는 노드들을 선택해서 identity나 sigmoid로 바꿔주면 perplexity값이 8만큼 증가하는 것을 관찰 할 수 있었기 때문입니다. 이런 식으로 ReLU 노드를 tanh 등으로 바꿔주면 perplexity가 최대 3만큼 증가하는 것도 확인할 수 있었습니다.

Image Classification on CIFAR-10

역시나 이미지 분야도 벤치마크 데이터로 많이 쓰이는 CIFAR-10을 사용했습니다. 먼저 search space를 두 개로 나눠서 적용했습니다. 위에서 설명한 두 가지 방법 -네트워크 구조 전체를 구성하기(macro search space), convolution cell 하나씩 구성하기(micro search)- 을 사용해서 구조를 찾았습니다. CNN 구조 생성에서도 마찬가지로 premature convergence를 방지하기 위한 여러가지 제한을 걸어두었습니다. 추가적으로 네트워크 전체를 구성할 때(macro search space)는 skip connection가 너무 많이 생기지 않게 하기 위하여 두 레이어 사이에 skip connection이 걸릴 확률과 skip connection이 생성될 사전 확률($\rho =0.4$) 사이에 KL divergence를 reward에 더해줍니다.

Table 2에서 Shake-Shake는 정규화 기법이고 CutOut은 augumentation 기법입니다. ENAS를 통해서 찾은 네트워크 구조가 NAS를 통해 찾은 결과보다는 에러율이 더 높지만, 계산량을 생각해본다면 굉장히 좋은 결과물이 나온 것을 확인할 수 있습니다. CNN 전체 구조를 찾는 경우는 7시간, Conv cell을 하나씩 찾을때는 11.5시간밖에 걸리지 않았다고 하며 이는 NAS와 비교했을 때 5만배 가량 더 빠르다고 합니다. 또한 텍스트 데이터에 대해 실험했을 때와 마찬가지로 이 결과물들은 여전히 local optimum에 빠져있는것을 확인할 수 있습니다. Macro search space에서 모든 seperable convolution을 normal convolution으로 바꾸고 파라미터 수를 고정시키고 모델 사이즈를 조금 조정하면 테스트 에러가 1.7%정도 줄었다고 합니다. 마찬가지로 micro search space에서도 무작위로 convolution cell 몇 개를 바꿔주면 성능이 조금 더 떨어졌다고 합니다. 이는 ENAS로 찾은 모델 구조가 매우 좋은 성능을 보여주고 있음을 뜻합니다. 아래 사진은 각각 macro search space와 micro search space에서 최종적으로 나온 네트워크 구조입니다.

Conclusion

NAS는 최초로 신경망으로 신경망 구조를 만드는 방법을 제안했습니다. 하지만 어마어마한 연산량이 문제였으며 이를 사용하기 위해선 수백개의 GPU를 필요로합니다. GPU를 수백개씩 운용할 수 있는 곳은 그리 많지 않습니다. 이런 상황에서 sub graph들의 파라미터를 공유하는 방법으로 효율적으로 파라미터를 줄이는 방법을 제안한게 ENAS입니다. 실제 실험 결과를 보아도 NAS보다는 약간 부족하지만 좋은 성능을 보여주고 있습니다.

요즘 논문만 읽고 정리를 못하다가 근 한달만에 포스팅 해봤습니다. 2017년에 GAN 논문들이 큰 관심을 받았다면, 이제는 AutoML 관련 논문들이 크게 발전하지 않을까 하는 생각이 들었습니다. 나름 논문들을 열심히 읽었다고 생각했는데, 중간 중간 Recurrent Highway Network에서 쓰인 highway connection을 걸었다는 등 잘 모르는 부분들이 나와서 반성(…)도 하고 있습니다.

Reference

• Pham, H., Guan, M. Y., Zoph, B., Le, Q. V., & Dean, J. (2018). Efficient Neural Architecture Search via Parameter Sharing. arXiv preprint arXiv:1802.03268.