Neural GPUs and Extended Neural GPUs

Title:

Neural GPUs Learn Algorithms

Can Active Memory Replace Attention?

Overview:

Google Brain 팀에서 ICLR 2016, NIPS 2016에서 발표한 두 개의 논문, Neural GPU와 그 extension에 관한 소개를 드리려고 합니다.  이 전 포스팅 Learning To Remember Rare Events에서 (key, value) 타입의 memory module을 기존의 다양한 supervised neural network model에 적용했었는데요, 그 중 하나의 model이 extended neural GPU 이고, 이를 이해하기 위해서는 그 이전 work인 neural GPU를 알아야 합니다.

Algorithm을 배우는 최근의 다양한 연구들이 있었죠. 대표적으로 DeepMind에서 발표한 Neural Turing Machine (NTM)이 있습니다. NTM은 neural network model에 computer의 DRAM과 같은 memory module을 추가하고, memory read/write operation을 differentiable하게 구성함으로써, neural network model이 주어진 example로부터 generalized algorithm을 배울 수 있다는 것을 실험적으로 검증한 센세이셔널한 연구죠!

이 논문에서는 training example들로부터 algorithm을 배우는 기존의 다양한 연구들의 sequential한 특성을 문제점으로 지적합니다. 즉, sequence data로부터 algorithm을 배울 때, parallel하게 학습할 수는 없을까? 라는 의문으로부터 연구가 시작됐습니다. 그래서 GPU라는 이름을 붙였죠;; 아시다시피 복잡한 control flow를 갖는 out-of-order execution에 특화된 CPU대비, GPU는 단순하지만 병렬화가 유리한 stream processing에 특화된 하드웨어 구조를 갖고 있습니다. 그냥 conceptually GPU라는 이름을 붙인것 같습니다;;

언급한 문제점 (sequential processing)을 극복하기 위해 neural GPU라는 concept을 제안하고, 다양한 sequence learning문제에 제안하는 architecture를 적용해봅니다. 하지만 대표적인 sequence learning 문제 (machine translation)에 적용했더니 성능이 그닥 좋지 않죠;; 그래서 NMT에서 잘 동작하는 model을 만들기위해 extended neural GPU라는 것을 제안합니다. 그리고 이 extended neural GPU model을 baseline으로, 지난 포스팅 Learning To Remember Rare Events에서 one-shot learning을 위한 memory augmentation을 추가하죠! 아래에서 좀 더 자세히 살펴보도록 합시다.

Introduction:

우리가 원하는 건, 복잡한 algorithm을 학습할 수 있는 neural network model을 얻는 것입니다. NTM이 이를 해결해주었죠! 하지만, NTM에서도 sequential program 학습을 병렬화하진 못했습니다. 이게 왜 문제가 되냐면, 학습과정의 단일 step 연산하는데만해도 soft attention mechanism으로 전체 memory를 최소 한 번씩은 읽고 쓰는 과정이 필요한데, 이 모든 과정을 sequential 하게 진행하면 학습이 엄청 느려진다는 단점이 있기 때문입니다. 이를 일부 해결해보기 위해 soft attention을 hard attention으로 바꿔 볼 수 있지만, non-differentiable한 hard attention model은 학습이 잘 안된다는 단점(gradient flow path가 끊기기 때문에 reinforcement learning 방식으로 학습합니다)이 있죠;;

이 연구에서는 algorithm learning의 sequential nature를 극복하고자, neural GPU라는 model을 제안합니다. Neural GPU model은 이론적으로는 다양한 복잡한 algorithm들을 학습할 수 있는 turing-complete model이라고 합니다. 근데 실험은 binary addition/multiplication에 대한 generalization performance를 보여주죠;; 실험은 많이 빈약하지만, 새로운 concept이기때문에, 제안하는 idea에 집중하시면 좋을 것 같습니다.

풀고자 하는 문제를 조금 살펴보면, binary addition (left-most bit이 LSB입니다)인데요, 9+5=14 를 푸는 문제 입니다. 첫번째 그림처럼 9와 5가 aligned 4bit number일 경우, 문제가 상대적으로 쉬워집니다. 각 bit에 대해 (1,1,0), (0,0,1), (0,1,1), (1,0,1) 이러한 aligned pattern을 다양한 example들로부터 학습하면 됩니다. 물론 올림 내림 이런 것들도 당연히 학습해야 하구요.

스크린샷 2017-03-28 오후 2.32.46

저자들은 이러한 쉬운 문제로는 generalization (e.g., 학습은 1~20bit number로만 수행하고, test는 2000bit number에서 수행) 성능이 안좋을 것이라 언급하며, non-aligned numbers에 대한 연산을 general하게 푸는 문제로 re-formulation 합니다. 이렇게요!

스크린샷 2017-03-28 오후 2.32.55

이제 input은 완전한 sequence가 되었습니다. 이런 문제를 풀 때, 보통 recurrent model을 써서 각 time-step에 sequence의 각 element를 입력해주면서 학습하죠. 하지만, 앞서 언급한대로 학습이 느려지는 단점이 생깁니다. 그래서 neural GPU를 제안합니다.

Neural GPUs (model architecture):

스크린샷 2017-03-28 오후 2.43.58

그림과 함께 살펴봅시다. 그림의 예시는 2-layers 3-width neural GPU model입니다. state-to-state 가 2개의 convolutional GRU (CGRU) iteration을 거치고, 각 state는 3개의 column으로 구성되어 있어 2-layer 3-width model이 됩니다.

먼저 GRU에 대해 살펴보죠. GPU는 입력 vector x와 current state s를 입력으로 받아 다음과 같은 연산을 수행합니다.

스크린샷 2017-03-28 오후 2.48.57

여기서 r은 reset gate로 current state s에 element-wise multiplication을 통해 얼마나 reset해줄지를 학습하는 gate이며, update gate u를 사용하여 current state s와 현재의 입력 x로 부터 얻어지는 representation을 출력에 얼마나 반영할지 결정해주는 역할을 합니다.

Neural GPU는 CGRU로 구성됩니다. 기본적인 연산은 GRU와 비슷하지만, 재밌는 것이 입력으로 current state s만을 취합니다. 아래 보시다시피 input x와 관련된 term들이 모두 사라졌습니다. 즉, current state에 모든 입력 sequence를 다 넣어버리고, CGRU로 recurrent하게 학습을 하는 거죠! 그래서 GPU입니다. 즉, sequence data의 모든 element가 time step-0에 모두 사용됩니다.

스크린샷 2017-03-28 오후 2.50.00

다시 제일 위의 그림을 보시죠. 각 state는 [w,h,m] shape을 갖는 mental image (그림에서 각 state의 width, height가 w-dimension, h-dimension이 되고, (w,h) 로 정해지는 가장 작은 네모(?)가 m-dimension vector라고 생각하면 됩니다)이며, [k_w, k_h, m, m]의 filter로 이 mental image를 convolve합니다. 아래와 같이요!

스크린샷 2017-03-28 오후 2.47.21

이렇게 convolution을 하면, 출력 sate의 shape은 입력 state의 shape과 동일해집니다 (보통의 convolution처럼 input-output shape을 맞춰주기 위해 boundary padding option으로 “SAME”을 줍니다).

Sequence i = (i_1, ... , i_n)가 주어졌을 때 (각 sequence element는 n개의 discrete symbol {0, ... , I}로부터 정해집니다), 먼저 이 전체 sequence i가 mental image의 initial state s_0의 첫 번째 column에 embedding 됩니다. 이 때, [I,m] shape의 embedding matrix E를 통해 각 element는 m-dimension으로 embedding 됩니다. s_0 [0,k,:] = E[i_k] 처럼요. s_0의 나머지 column들은 zero로 채웁니다. 아마도 이 나머지 column들은 연산을 진행해나감에 있어서 temporal한 momory로 사용되길 바라고 설계한 것 같습니다. 그럼 이제 s_0가 준비됐습니다. 이제 l-layer의 CGRU를 거쳐 next state로 transition하면 되고, 이를 sequence length만큼 반복해서 얻게되는 s_n이 최종 output state s_{fin}이 됩니다. 아래처럼요.

스크린샷 2017-03-28 오후 2.47.45

Neural GPU의 결과값은, s_{fin}에 output matrix O를 곱한 l_k = O s_{fin} [0,k,:]로 부터 o_k = \arg\max (l_k)로 얻어지게 됩니다. 학습은, logit l_k의 softmax와 target label사이의 negative log-likelihood loss로 진행하구요.

실제 실험에서는 2-layer CGRU, 4-width state, 24-dimensional embedding (m), 3×3 convolutional kernel을 사용했다고 하네요.

Neural GPUs (experiments):

1) long binary addition/multiplication 과 2) copying, sequence reversing, duplicating, counting 등의 elementary function에 대한 algorithm learning 실험을 수행했습니다.

  • binary addition / multiplication

d-bit numbers에 대한 덧셈, 곱셈 입니다. 입력은 2개의 d-bit binary number와 addition (or multiplication) operator 1-bit을 포한한 2d+1 bit sequence입니다. binary addition은 {0,1,+,PAD} symbols로 구성되고, binary mul은 {0,1,\cdot,PAD}로 구성됩니다. 아래는 binary addition, multiplication에 대한 예제입니다.

스크린샷 2017-03-28 오후 3.24.12

스크린샷 2017-03-28 오후 3.24.19

curriculum training, gradient noise 등을 사용하여 학습했고, 총 6개의 hyperparams set에 대해 각각 3가지 configuration으로 총 729가지 경우의 수에 대해 random seed로 부터 training을 진행했다고 합니다. d-bit number의 d는 max 20bit까지의 데이터로 학습을 진행했고, 아래 표와 같이 20~2000bit data에 대한 성능을 측정해 봄으로써 학습된 model이 algorithm을 잘 학습하여 generalization이 잘 됐는지 확인합니다.

스크린샷 2017-03-28 오후 3.24.26

보시는 것과 같이, 기존의 work들 대비 제안하는 neural GPU는 모든 경우에서 좋은 성능을 보여주고 있는 것을 확인할 수 있습니다.

  • other algorithmic tasks

copying sequences, reversing sequences, duplicating sequences, counting by sorting bits의 다양한 task에 대해서 완벽하게 algorithm을 학습하는 것을 확인했다고 하네요.

학습 성공을 위해, 몇몇 training technique들이 필요했다고 합니다. 위에서 언급한대로, learning rate, initial param scale, relaxation pull factor, curriculum progress threshold, gradient noise scale, dropout rate 이렇게 총 6개의 hyperparams에 대해 총 3^6 = 729 instances를 생성해 실험했습니다. 200-bit 실험에 대해서는 729번 중 대부분이 올바르게 동작을 했지만, 2000-bit 실험에서는 성공한 instance가 매우 적었다고 하네요. 논문에서 따로 언급한 training technique들을 몇 개 소개하면,

>> curriculum learning: 원활한 학습을 위해 curriculum learning을 사용했습니다. 예를들어 7-digit number에 대한 학습을 수행하기 전에 6-digit number에 대한 accuracy가 90%이상 나올 때 까지 학습을 하고, 다음 curriculum으로 넘어가는 거죠. 전체의 20%정도는 1~20-digit number 에서 random 하게 골라서 학습을 하고, 나머지 80%에 대해 curriculum learning을 합니다.

>> gradient noise: 각 training step마다 gradient에 noise를 추가하여, 학습속도 향상 및 안정적인 학습을 이룰 수 있었다고 하구요, 이 때 3- step의 noise scale을 사용했다고 합니다.

>> gate cutoff:  CGRU의 gate는 sigmoid function대신 1.2 \sigma (x) - 0.1 function을 사용했고, [0.0, 1.0]에서 clipping하여 hard threshold 버전의 sigmoid function을 사용했더니, 학습에 좀 더 효과적이 었다고 합니다.

>> dropout: 보통 recurrent network에서는 dropout이 효과적이지 않다는 연구가 있었는데, 본 연구에서는 낮은 dropout rate (6%, 9%, 13.5%)을 적용하여 성능 향상(dropout이 없으면 729 instance들 중 성공하는 instance가 거의 없었다고 하네요..)을 봤다고 합니다.

>> parameter sharing relaxation: 학습성능 향상을 위해 recurrent unit의 shared parameter를 relaxation하는 technique을 사용합니다. 즉, r개의 non-shared parameter set을 두고, 매 time-step t마다 t ~ mod ~ r = i에 대해 i-th parameter set을 사용하는 거죠. 단, r개의 parameter set 사이의 distance로 loss penalty를 줘서, 나중에 이 parameter set들을 하나로 unifying할 때 서로 비슷한 range를 갖도록 합니다. 이 distance penalty에 scalar값을 곱해서 loss에 반영했는데요, scalar값이 0이면 penalty는 없는것이고, scalar값이 커지면 parameter set들 간의 distance가 작게 유지됩니다. 이 scalar값을 relaxation pull 이라고 부르고요. 학습을 진행하면서 이 relaxation pull값을 점차 증가시킵니다. 그리고 마지막에 모든 parameter set들을 averaging해서 fine-tuning하고 학습을 마무리합니다. 이 technique은 제안하는 neural GPU training에 있어서 반드시 필요한 technique이었다고 합니다.

이렇게 어렵게어렵게(;;) 학습한 neural GPU는 학습속도 및 generalization performance 측면에서 좋은 결과를 보여주었고, NMT같은 좀 더 practical한 application에 적용해보는 것을 future work으로 이야기 하며 논문을 마칩니다. (바로 아래 논문이죠! 이 논문은 concept에 대해서만 간단히 설명드리겠습니다.)

Extended Neural GPUs:

위에서 언급한 것 처럼, neural GPU 그 자체만으로는 NMT와 같은 practical application에서 좋은 성능을 얻지 못한다고 합니다. 이는, sequence element간의 dependency가 강하게 존재하는 language model에서 각 output element를 독립적으로 prediction하는 구조 때문이라고 하는데요, 저자들은 이를 극복하기 위해 특정 output element를 prediction할 때 이 전 output을 conditionally 사용할 수 있도록 구조를 변경할 필요가 있다고 합니다. 아래와 같이 말이죠.

스크린샷 2017-03-29 오전 1.04.18

이렇게 명시적으로 output을 conditioning했더니 성능이 아주 약간 좋아졌습니다. 여전히 기존의 work들 대비 훨씬 낮은 성능을 보였고, 궁극적으로는 encoder-decoder network을 구성해서 extended neural GPU를 제안합니다. 매 decoding time-step마다 해당 시점의 output element를 출력하도록 하는데요, 이 때 이전 output element에 대한 prediction을 현재 output element prediction에 직접 사용할 수 있도록 해주었습니다.

스크린샷 2017-03-29 오전 1.04.26

여기서 추가적으로 tape memory p라는 것이 등장하는데요, 이 memory는 각 state와 동일한 shape을 갖는 memory 입니다. 이 memory의 사용법을 o_2 prediction시점을 예로들어 설명해보죠. o_2 prediction을 위해 d_1p_1이 사용됩니다. d_1은 이 전 decoding stage의 prediction결과 o_1을 담고 있는 state이고, p_1p_0o_1의 값을 (해당 위치에) 덮어씌워 만든 memory 입니다 (p_0는 all-zero로 initialize 합니다). o_2 prediction에 d_1만을 사용한 것이 아니라, 굳이 중복된 정보를 담고 있는 p_1을 사용하는 이유는 아마도 attention 효과를 줄 수 있기 때문이 아닌가 싶습니다. 즉, zero-initialized tape memory를 기반으로, 현재 decoding stage관점에서 바로 직전 prediction까지의 결과들만을 담고 있으니, 현재 prediction에 conditionally사용될 수 있는 정보들에 대해서 attention을 줄 수 있을 것 같습니다.

Tape memory p의 추가로 decoding stage CGRU는 아래와 같이 표현됩니다.

스크린샷 2017-03-29 오전 1.16.51

결과를 살펴볼까요? 첫 번째가 neural GPU, 두 번째가 output conditioning, 세 번째가 tape memory를 활용한 Extended Neural GPU이죠. 성능을 보시는 것처럼 매우 좋습니다.

스크린샷 2017-03-29 오전 1.19.27

근데, 원래 neural GPU취지가 sequence data를 parallel하게 학습하고, output을 parallel하게 prediction하는 게 아니었나요?;; NMT를 위해서 output prediction을 sequential decoder를 바탕으로 학습했으니 다시 neural “GPU”의 본래 취지에 어긋나는게 아닌가 싶네요. 뭐 그래도 최종 성능을 보면 attention-based GRU보다 훨씬 좋은 성능을 보이고 있습니다.

Discussion:

사실 neural GPU의 핵심 중 하나로 state의 width를 생각했었습니다. state-0의 1st column에 data를 입력해주고, final state의 1st column으로부터 data를 출력하는데, 그 중간 연산 과정에서 width-dimension은 CPU의 register-file 역할을 해줄거라고 생각했습니다. 다시말해서, 연산을 위해 필요한 temporal memory 공간을 width-dimension으로 추가해주고, 학습이 진행되는 동안 이 공간이 implicit하게 사용되도록 함으로써 algorithm을 잘 학습하는 거죠! 아마도 이러한 효과를 기대하고 architecture를 설계한 것 같은데, 실제로 w개의 m-dimension data element로 구성된 각 state를 1개의 (w \times m)-dimension data element 공간으로 구성해도 성능에 큰 차이가 없었다고 하는군요…;; 단지 parameter수 증가없이도 동일한 성능을 얻을 수 있었다는 점만을 어필했습니다만, 좀 더 복잡한 task에서는 이 temporal memory공간이 유용하게 활용되지 않을까 싶습니다.

전체적으로 부족한 점이 많아보이기는 하지만, 새롭게 제안된 concept이라 다른 application에도 적용해 볼 수 있지 않을까 싶어서 소개드렸습니다.

One thought on “Neural GPUs and Extended Neural GPUs

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s