Neural GPUs Learn Algorithms

Łukasz Kaiser; Ilya Sutskever

Source-linked AI summary

Neural GPUs Learn Algorithms

Łukasz Kaiser, Ilya Sutskever

arXiv:1511.08228v32015년 11월 25일cs.LGcs.NE

TL;DR

신경망으로 예제에서 알고리즘을 학습하는 일은 여전히 어렵다. Neural GPU는 병렬적이고 얕으며 Turing-complete한 아키텍처로 이를 해결하고, 오류 없이 훨씬 긴 입력에도 일반화하는 비자명한 초선형 시간 알고리즘을 학습한다.

문제
신경망으로 예제에서 알고리즘을 학습하는 일은 여전히 미해결 연구 과제다.
방법
Neural GPU는 알고리즘 학습을 위해 병렬 convolutional gated recurrent unit을 사용하는 얕고 Turing-complete한 아키텍처다.
결과
최대 20비트 수로 학습한 Neural GPU는 테스트한 최대 2000비트 입력에서 오류 없이 binary multiplication을 학습했으며, addition과 기타 알고리즘 과제도 학습했다.
시사점 및 한계
이 결과는 이산 상태 없이 symbolic algorithms와 잠재적으로 program synthesis에 신경망을 활용할 가능성을 뒷받침한다.
시사점 및 한계
729개 모델 grid search 중 소수의 모델만 2000비트 수에 오류 없이 일반화했지만, dropout과 gradient noise는 신뢰도를 향상시켰다.

Abstract

from arXiv · show

Learning an algorithm from examples is a fundamental problem that has been widely studied. Recently it has been addressed using neural networks, in particular by Neural Turing Machines (NTMs). These are fully differentiable computers that use backpropagation to learn their own programming. Despite their appeal NTMs have a weakness that is caused by their sequential nature: they are not parallel and are are hard to train due to their large depth when unfolded. We present a neural network architecture to address this problem: the Neural GPU. It is based on a type of convolutional gated recurrent unit and, like the NTM, is computationally universal. Unlike the NTM, the Neural GPU is highly parallel which makes it easier to train and efficient to run. An essential property of algorithms is their ability to handle inputs of arbitrary size. We show that the Neural GPU can be trained on short instances of an algorithmic task and successfully generalize to long instances. We verified it on a number of tasks including long addition and long multiplication of numbers represented in binary. We train the Neural GPU on numbers with upto 20 bits and observe no errors whatsoever while testing it, even on much longer numbers. To achieve these results we introduce a technique for training deep recurrent networks: parameter sharing relaxation. We also found a small amount of dropout and gradient noise to have a large positive effect on learning and generalization.

1 서론

Neural GPU는 Neural Turing Machines의 효율성과 최적화 문제를 극복하기 위해 알고리즘 학습을 위한 병렬적이고 얕은 Turing-complete 아키텍처로 제시된다. 예제로부터 긴 이진 곱셈, 덧셈 및 기타 알고리즘 과제를 학습하며, 학습 길이를 훨씬 넘어 일반화한다.

Sequence-to-sequence 모델은 고정 크기 인코딩으로 제한되지만, attention은 이러한 병목을 제거해도 남은 모든 문제를 해결하지는 못한다.Neural Turing Machines는 이론적으로 임의의 알고리즘을 다루지만, soft attention, 상당한 깊이, 어려운 최적화, 낮은 병렬화 가능성 때문에 계산 효율성과 학습이 저해된다.
Neural GPU는 원리적으로 Turing-complete이며, Neural Turing Machines의 깊은 순차 처리 대신 고도로 병렬적인 얕은 계산을 사용하도록 설계된다.이 설계는 복잡한 알고리즘의 최적화를 쉽게 학습하고 실행을 더 효율적으로 만드는 것을 목표로 한다.
최대 20비트 수로 학습한 Neural GPU는 최대 2000비트까지의 테스트된 이진 곱셈에서 오류를 전혀 내지 않았다.논문은 이를 입력 크기에 대해 초선형 실행 시간을 갖는 알고리즘을 학습한 최초의 neural network라고 설명한다.
동일한 아키텍처는 긴 이진 덧셈, 세기, 복사, sequence reversal, sequence duplication도 학습한다.
Stack-augmented RNNs는 최대 20비트 수로 학습한 덧셈을 약 100비트 수까지는 일반화하지만, 200비트 수에는 결코 일반화하지 못하며 오류 없이 일반화한 적도 없다.논문은 이를 Neural GPU 없이 얻은 가장 강력한 일반화라고 부른다.

2 Neural GPU

Neural GPU는 임베딩된 입력을 2차원 mental image에 저장하고, stacked convolutional gated recurrent unit으로 그 상태를 갱신한다. 최종 상태에 학습된 output matrix를 적용해 출력을 생성하며, differentiable optimization으로 end-to-end 학습된다.

2 Neural GPU: CGRU는 convolutional kernel banks로 구현된 선형 변환을 갖는 update and reset gates를 사용해 mental image의 각 위치를 갱신한다.convolution은 mental image의 형태를 보존하며 [k_w, k_h, m, m] 형태의 kernel을 사용한다.
2 Neural GPU: convolution은 zero padding and stride 1을 사용하므로, 표준 최적화 convolution 구현으로 Neural GPU 연산을 지원할 수 있다.저자들은 더 빠른 convolution 방법도 직접 사용할 수 있다고 언급한다.
2 Neural GPU: Neural GPU는 입력 sequence를 tensor 형태의 starting state 첫 번째 column에 임베딩한 뒤, n recurrent steps 동안 l개의 stacked CGRU layers를 적용한다.상태의 형태는 [w, h, m]이며, 최종 상태는 s_fin = s_n이다.
2 Neural GPU: model은 최종 상태에서 대응하는 첫 번째 column vector에 학습된 matrix O를 적용하고 maximal logit을 선택해 각 output을 예측한다.학습에는 logits에 대한 softmax cross-entropy를 사용한다.
2 Neural GPU: All Neural GPU components are differentiable하므로 stochastic-gradient training이 가능하다. 보고된 configuration은 Adam, gradient clipping, l = 2, w = 4, m = 24, 3 × 3 kernels를 사용한다.Adam은 ε = 10^-4를 사용하며, gradient는 norm 1로 clipping된다.

3 실험

Neural GPU는 긴 이진 덧셈과 곱셈을 학습하고 학습 길이를 넘어 일반화한다. 또한 더 단순한 알고리즘 과제를 훨씬 긴 시퀀스 길이에서도 해결하며, parameter-sharing relaxation과 소량의 dropout은 학습과 일반화를 향상한다.

실험 범위: 실험은 Neural GPU가 알고리즘 과제를 학습하고 학습에 사용된 시퀀스 길이를 훨씬 넘어 잘 일반화하는지를 검증하도록 설계되었다.연구는 긴 이진 덧셈과 곱셈으로 시작한 뒤, 몇 가지 추가 알고리즘 과제를 평가한다.
핵심 과제: 핵심 실험에서는 긴 이진 덧셈과 곱셈을 다루며, 입력과 출력을 과제별 산술 기호 및 padding 기호를 포함한 이산 기호 시퀀스로 인코딩한다.덧셈에는 {0, 1, +, PAD}를 사용하고, 곱셈에는 {0, 1, ·, PAD}를 사용한다. 덧셈은 길이가 같고 하위 비트부터 나열된 이진수에 대해 수행된다.
기타 알고리즘 과제: 최대 길이 41인 시퀀스로 학습한 뒤, Neural GPU는 최대 길이 4001에서 평가한 더 단순한 과제에서 오류를 전혀 보이지 않았다.평가한 과제에는 비트 시퀀스 복사, 역순 배열, 복제, 정렬이 포함되었다.
학습 방법: 소량의 dropout은 일반화를 향상해 더 높은 길이로 일반화하는 모델을 늘렸고, 곱셈 모델이 2000비트까지 일반화할 수 있게 했다.dropout 비율은 6%, 9%, 13.5%에서 탐색했으며, dropout은 recurrent connection이 아니라 전체 mental image에 적용했다.
학습 방법: Parameter-sharing relaxation은 곱셈에 결정적이었다. 이를 사용하지 않으면 모델은 학습 데이터에 맞추는 데 어려움을 겪고 일반화에 실패했지만, relaxation을 적용한 729회 실행 중 거의 모두가 학습 세트에 맞았다.이 방법은 일시적으로 r개의 비공유 parameter set을 사용한 뒤, 이를 평균으로 점진적으로 끌어당긴다. r = 6이 자주 사용되었다.

4 논의

논의에서는 Neural GPU의 계산 효율성과 데이터 효율성을 강조하는 한편, 십진수 입력에서 성능이 저하되고 장거리 일반화가 일관되지 않음을 지적한다. 또한 파라미터 수를 늘리지 않고도 width를 키워 hidden-state capacity를 높이는 방식을 설명한다.

시각화: 학습된 계산은 state evolution을 통해 시각화할 수 있으며, duplication의 경우 모델은 각 단계에서 embedding의 일부를 아래쪽으로 이동시킨다.시각화에서는 −1을 흰색, 1을 검은색, 그 외의 값은 회색으로 인코딩한다.
한계: 십진수 입력은 성능을 저하시켰다. long decimal multiplication은 학습되지 않았지만, m을 128로 늘리면 다른 task들은 학습할 수 있었다.binary representation이 decimal representation보다 더 나은 성능을 보였다.
한계: 729-model grid search에서 소수의 모델만이 2000-bit numbers까지 오류 없이 일반화했으며, dropout과 gradient noise는 학습 및 일반화의 신뢰성을 높였다.많은 모델이 40 또는 200 bits까지 일반화했지만, 2000 bits에서 오류 없이 작동한 모델은 상당히 적었다.
왜 width를 사용하는가?: m = 64인 width-1 Neural GPU는 2000-bit binary multiplication까지 일반화했으며, width를 늘리면 parameter count를 늘리지 않고 hidden-state information을 증가시킬 수 있다.m이 네 배 더 큰 one-dimensional Neural GPU는 original architecture가 표현할 수 있는 모든 function을 표현할 수 있으므로, width는 factorization으로 작용할 수 있다.
속도와 데이터 효율성: n = 32, m = 64인 2-layer Neural GPU는 NVIDIA GTX 970 GPU에서 joint forward-backward step당 약 0.6s가 필요했다.unfolding 후 network는 32개의 mental image에 대해 작동하는 128개의 CGRU layer를 포함했으며, 각 mental image의 크기는 4 × 64 × 64였다.
속도와 데이터 효율성: 총 약 2000개의 training instance만 사용했는데도 일부 모델은 binary addition에서 200-bit numbers로 잘 일반화했다.표준 실험에서는 약 200k개의 example을 사용한 반면, reduced-data experiment에서는 각 training length마다 100개의 example을 사용했다.

5 결론 및 향후 연구

Neural GPU는 오류 없이 훨씬 더 긴 길이로 일반화되는 비자명한 초선형 시간 알고리즘을 학습함으로써 질적 도약을 이룬다. 저자들은 프로그램 합성과 언어 처리에의 응용을 제안하며, recurrent network 학습 전반에 유용한 parameter sharing relaxation의 가능성을 강조한다.

결론: Table 1은 Neural GPU가 비자명한 초선형 시간 알고리즘을 학습하고, 이전 architecture와 달리 오류 없이 훨씬 더 긴 길이로 일반화함을 보여준다.저자들은 이를 neural network에서 처음 얻은 이러한 결과라고 설명한다.
향후 연구: Neural GPU는 neural network를 program synthesis로 확장할 수 있으며, 이산 상태 없이 symbolic algorithm을 학습하면서 Kaiser (2012)와 같은 기존 결과를 더 높은 확장성으로 재현할 가능성이 있다.이들의 data efficiency는 놀라운 것으로 기술되며, dropout과 noise가 성능을 추가로 향상시킨다.
향후 연구: 향후 연구에는 Neural GPU를 language processing에 적용하고, parameter sharing relaxation을 사용해 deep recurrent network 전반에서 학습을 개선하는 일이 포함된다.Gating과 recursion은 overfitting 없이 더 깊은 translation model을 가능하게 할 수 있으며, convolutional word-based translation 결과를 기반으로 한다.