ByteNet – Neural machine translation in linear time 논문번역(updated)

ByteNet model from DeepMind’s paper Neural Machine Translation in Linear Time.

(Neural architecture for sequence processing)

 

ByteNet은 두개의 CNN을 쌓은 것이다. (인코더/디코더)

하나는 source sequence를 인코딩하고 , 하나는 디코딩하여 target sequence를 만들어낸다.

다양한 길이의 아웃풋을 생성하기 위해서 Target network는 동적으로 ‘펼쳐진다.’ (dynamically unfolded over the representation from 인코더)

ByteNet은 conv 레이어에 dilation 이라는 방법을 사용해서 receptive field의 크기를 확장한다.

ByteNet은 두가지 중요한 성질을 지닌다.

  • 수행시간이 시퀀스 길이에 대해 리니어 타임으로 증가하고, 시퀀스의 시간 해상도를 유지한다.
  • 디코더는 캐릭터 레벨의 language modelling에 있어서 state-of-the-art 성능을 낸다. (RNN으로 만든 기존 버전들보다 낫다.)
  • 영어-독일어 WMT 번역 task에 대한 character-to-character(raw 캐릭터 레벨의) machine translation에서도 state-of-the-art 성능을 낸다. (RNN w/ attentional pooling보다 낫다.) 또한 quadratic 타임에 수행한다.
  • ByteNet의 인코더가 만든 representation의 latent alignment structure가 실제 시퀀스들간의 예상되는 순서를 반영한다.

 

1  Introduction

  • neural language modeling 에서 뉴럴넷은 주어진 언어에 속한 word나 캐릭터들의 시퀀스들의 distribution을 추정한다.
  • neural machine translation에서는, 네트워크가 소스 랭귀지에서 받은 시퀀스가 주어졌을 때의 타겟 랭귀지에서의 시퀀스들의 distribution을 추정한다.

후자의 경우, 네트워크는 두개의 서브네트워크로 구성되어 있다고 볼 수 있다.

  • Source network : source sequence를 하나의 representation으로 변환하는 네트워크
  • Target network : 이 representation을 사용해서 타겟 sequence를 만들어내는 네트워크

RNN은 성능좋은 시퀀스 모델이고 언어모델링에서 많이 사용되지만 잠재적인 문제점이 있다.

RNN은 본질적으로 연속적인 구조를 가지고 있기 때문에 시퀀스를 따라 패럴럴하게 작동할 수가 없다. RNN의 포워드와 백워드 시그널들은 전체 시퀀스 길이를 다 횡단해야만 한 지점에서 다른 지점으로 갈 수 있다. 길이가 길어지면 지점들 사이의 상관관계를 학습하기 힘들다.

여러 neural architecture가 제시되었지만 이들은 소스와 타겟 시퀀스의 길이에 대해 ‘슈퍼 리니어’한 수행시간을 갖거나, 소스 시퀀스를 contant한 사이즈의 representation으로 프로세싱하기 때문에 메모리화 과정이라는 짐을 지우게 된다. 이 두가지 단점은 학습시킬 시퀀스의 길이가 길어지면 더 심해진다.

우리는 ByteNet이라는 neural translation model과 ByteNet Decoder라는 neural language model을 제시해서 이 두가지 단점을 극복하고자 한다.

 

ByteNet은 encoder-decoder 모델로서, 확장된 CNN을 사용해서 소스 네트워크와 타겟네트워크를 구성한다. 두가지 중요한 특징을 가진다.

  • Encoder로부터 나온 representation에 대해 decodering 스택해서 쌓는 구조. 이 때, 시간resolution을 유지하도록 하는 구조이다.
  • 다양한 길이의 source, target sequence를 다루기 위한 dynamic unfolding이라는 방법이다.

 

ByteNet의 encoder, decoder는 1-d convolutional neural network의 한 종류이다. (레이어 깊이는 fixed되어있음.) 이 두 CNN은 dilation을 사용해서 receptive field의 크기를 늘린다. Decoder CNN에서는 target sequence의 향후 토큰들을 보는 것을 막기 위해, convolution을 masking한다. (아래 그림에서 decoder부분의 오른쪽 반이 masking되었음을 볼 수 있음.)

ByteNet은 소스 네트워크와 타겟 네트워크를 쌓아서 연결한 후, 타겟 네트워크를 동적으로 펼쳐서 다양한 길이의 아웃풋 시퀀스를 생성한다. 우리는 ByteNet을 넓은 의미에서 시퀀스 맵핑 아키텍쳐의 하나로 볼 수 있다. (서브네트워크들을 쌓은 후 동적으로 펼치는 작업을 하는) 서브네트워크들은 convolutional이나 recurrent 둘다 될 수 있다.

ByteNet의 구조. 파란 타겟 네트워크는 빨간 소스 네트워크 위에 쌓여진다. 타겟 네트워크는 다양한 길이의 타겟 시퀀스를 생성한다. (동적인 펼침을 통해)

RNN 서브네트워크로 구성된 ByteNet는 RNN Enc-Dec network의 일반화된 버전이라고 볼 수 있다.

하지만 RNN이나 feed-forward 네트워크에 기반한 neural language model들과는 달리, ByteNet Decoder는 긴 past input을 받아들일 수 있는 새로운 convolutional structure를 기반으로 만들어졌다.

 

ByteNet 은 computational 이득학습 특징들을 가지고 있다.

  1. Computational의 측면에서는 네트워크가 소스와 타겟 시퀀스 길이에 대해 computation양이 리니어하게 증가한다.(up to constant c ≈ log d, 여기서 d는 dependency field의 크기) 소스 네트워크에서의 트레이닝과 디코딩, 그리고 타겟 네트워크에서의 트레이닝 동안의 computation은 스트링들에서 패럴랠하게 진행될 수 있다. (타겟 네트워크의 디코딩에서는 적용되지 않는다.)
  2. 학습에 관해서는 소스 스트링의 representation은 resolution을 유지한다. Representation의 메모리화를 피함으로써 소스와 타겟 네트워크 사이의 최대 대역폭을 허용한다. 또한, 네트워크 안에서 어떤 토큰들 사이의 포워드, 백워드 신호들이 이동하는 거리는 네트워크의 fixed된 깊이(depth)에 의해서 결정되고, 각 토큰들 사이의 거리에 대해서는 거의 독립적이다. 멀리 떨어진 토큰들 사이의 dependency는 짧은 path에 의해 연결되고 쉽게 학습될 수 있다.

우리는 ByteNet을 raw 캐릭터 시퀀스에 적용했다. 우리는 ByteNet decoder를 Hutter Prize Wikipedia 문제에 적용해 보았다.

→  The model achieves 1.33 bits/character showing that the convolutional language model is able to outperform the previous best results obtained with recurrent neural networks.

Furthermore, we evaluate the ByteNet on raw character-level machine translation on the English-German WMT benchmark. The ByteNet achieves a score of 18.9 and 21.7 BLEU points on, respectively, the 2014 and the 2015 test sets; these results approach the best results obtained with other neural translation models that have quadratic running time (Chung et al., 2016b; Wu et al., 2016a). We use gradient-based visualization (Simonyan et al., 2013) to reveal the latent structure that arises between the source and target sequences in the ByteNet. We find the structure to mirror the expected word alignments between the source and target sequences.

 

2  Neural Translation Model

소스 language에서 s라는 스트링이 주어지면, neural translation model은 p(t|s)의 distribution을 예측한다. (t는 타겟 스트링) 이 distribution은 t가 s로 번역되는 확률을 나타낸다. 이 조건 확률들의 곱이 distribution 전체에 대한 식으로 정리된다.

Equation 1:

각 조건 factor는, 소스와 타겟 토큰들 사이의 복잡하고 long-range한 의존관계를 표현한다. 이 스트링들은 보통 해당하는 언어의 문장들이다. 토큰들은 단어들 혹은 캐릭터 들이다.

이 p(t|s)를 모델링하는 네트워크는 두개의 서브네트워크로 구성되어있다. 소스 스트링을 하나의 representation으로 만드는 소스 네트워크(encoder)와 소스 representation을 타겟 string으로 생성하는 타겟 네트워크(decoder)가 그것이다. 타겟 네트워크는 타겟 언어에 대한 랭귀지 모델과 같은 기능을 한다.

Neural translation 모델은 몇몇 기본적인 속성이 있다. 타겟 네트워크(decoder)는 타겟 토큰들에 대해 autoregressive하고, 소스와 타겟 스트링에서 토큰들의 순서에 대해 sensitive하다. 또한 타겟 랭귀지의 어떤 스트링에 대해서도 non-zero 확률을 부여해서 open vocabulary를 얻을 수 있다는 점도 유용한 점이다.

 

2.1  Desiderata (필요한 것)

  • Running time이 source/target string의 길이에 대해 linear해야 한다. Operation을 parallel하게 돌리는 방식으로 computation time을 줄일 수 있다.
  • Source representation의 길이가 인풋 string의 길이에 linear하게 비례해야 한다. (resolution을 유지해야 한다.) Constant한 값이어서는 안된다. 이는 모델이 translation전에 추가적인 memorization 과정을 거치는 것을 피하기 위함이다. 좀 더 일반화해서 얘기하자면, representation의 길이는 그것이 나타나고자 하는(혹은 예측하고자 하는) 정보의 양에 비례해야 한다. 
  • 네트워크 내에서 input/output token들 사이에서 forward/backward로 traverse되는 path들의 길이는 짧아야 한다. 두 token사이가 시퀀스 내에서 얼마나 멀게 위치했는지와 상관없이 path가 짧다는 특성은, 더 좋은 signal propagation을 가능하게 하고, long-range dependency들을 학습할 수 있도록 한다.

 

3 ByteNet

위에서 살펴본 요구 조건들을 충족시키는 neural language/translation 모델을 만들고자 한다.

ByteNet 구조는

  • Target network staked on a source network : generates variable-length output via dynamic unfolding
  • Target network(ByteNet Decoder) : a language model that is formed of one-dimensional convolutional layers that use dilation and are masked
  • Source network : use dilation / but not masked

 

3.1  Encoder-Decoder stacking

Encoder와 decoder가 연결된 아키텍쳐로 구현되었다. 둘 사이의 representation의 bandwidth를 최대화하기 위해서 encoder가 계산한 representation위에 encoder를 붙였다. 이것은 fixed size vector representation이나 attentional pooling을 사용하는 방식들과 다른 점이다.

 

3.2  Dynamic unfolding

길이가 다른 시퀀스를 다루는 encoder/decoder를 직접 연결할 수 없기 때문에 dynamic unfolding을 사용해야 한다.

Source sequence의 길이 : |s|

Target sequence의 길이 : |t|

먼저 |t|에 대한 tight upper bound |\hat{t}| 를 source length |s|에 대한 linear function으로 정의한다.

Screen Shot 2017-07-11 at 2.51.58 PM.png

tight upper bound |\hat{t}|는,

  • 거의 모든 경우에 actual |t|의 크기보다 크면서, 동시에
  • 필요한 computation양을 너무 크게 증가시키지 않아야 한다.

이 함수가 정의되고 나면, source encoder에서 source 시퀀스의 길이 |s|가 주어졌을 때 |\hat{t}| 길이의 representation을 출력하도록 한다.

예를 들어 우리의 경우, 영어에서 독일어로 번역하는 모델에서 a=1.20, b=0을 사용했다. (독일어 문장들이 영어문장보다 대부분 길기 때문이다.)

이러한 방식으로 computation과 high bandwidth (resolution preserving)의 두마리 토끼를 잡을 수 있었다.

Encoder에서의 계산이 끝나면, 이 representation에 대해서 decoder가 step-by-step으로 unfolding을 하도록 한다. (End-of-sequence가 출력되기 전까지)

이 unfolding은 |\hat{t}|의 길이 이후에도 더 수행될 수 있다. Unfolding이 encoder representation 의 길이 |\hat{t}|를 넘어가면,  zero-padded on the fly 된다. (즉, if target network’s output is beyond the length of the source sequence, the corresponding conditioning column is set to zero)

이 경우, predictions of the target network는 이전 스텝에서의 source and target representations에게만 conditioned된다.

그림 2에서 이 과정을 살펴볼 수 있다.

Screen Shot 2017-07-11 at 3.02.40 PM.png

그림 2: ByteNet 구조에서의 동적인 펼침(dynamic unfolding). 각 스텝에서 타겟 네트워크는 그 스텝에서의 소스 representation에 대해 conditioned 된다. 혹은 representation 길이 이상의 스텝에서는 아무런 condition이 설정되지 않는다. Decoding은 타겟 네트워크가 EOS 심볼을 생성하면 종료된다.

 

3.3  Input Embedding Tensor

Target sequence t = t0, …, tn이 주어졌을 때, ByteNet decoder는 첫 n개의 token들(t0 ~ tn-1까지)을 특정 look-up table에 embedding한다. (t1부터 tn까지는 prediction의 target이 된다.)

이 embedding를 n x 2d 사이즈의 텐서에 concatenated시킨다. (d는 네트워크 내의 inner channel의 갯수)

 

3.4  Masked one-dimensional convolutions

  •  Target network applies masked one-dimensional convolutions to the embedding tensor that have a masked kernel of size k.(The masking ensures that information from future tokens does not affect the prediction of the current token.)
  • The operation can be implemented either by zeroing out some of the weights on a wider kernel of size 2k – 1 or by padding the output map.

 

3.5 Dilation

  • The masked convolutions use dilation to increase the receptive field of the target network.
Dilation makes the receptive field grow exponentially in terms of the depth of the networks , as opposed to linearly.
  • We use a dilation scheme whereby the dilation rates are doubled every layer up to a maximum rate r (우리 실험에서는 r=16)

  • the scheme is repeated multiple times in the network always starting from a dilation rate of 1.

 

3.6 Residual blocks

  • 각 레이어는 wrapped with residual block that contains additional convolutional layers with filters of size 1.

  • 우리는 두가지 variants of residual blocks를 적용했다.

  • one with ReLUs : machine translation experiments 에 적용.
  • one with Multiplicative Unit : language modeling 에 적용.

Screen Shot 2017-07-11 at 2.51.47 PM.png

(왼쪽 : Residual block with ReLU for decoders / 오른쪽 : Residual multiplicative block for decoders & corresponding expandsion of the MU)

두 경우 모두 activation function 이전에 layer normalization을 사용했다. (sequence processing에서 앞으로 올 token들에 대한 activation statistic을 계산하는 것을 피해야 하는 경우에 알맞는 방법이다. Batch normalization을 사용하면 이를 피할 수 없게 된다.)

Dilation을 따라 몇개의 residual block을 거친 후에는, convolution 레이어를 하나 더 적용하고 ReLU activation을 적용했고, 마지막으로 softmax 레이어를 더했다.

<참고 : 오리지널 논문에서 이 normalization 부분을 설명한 내용(결국 같은 얘기>

Sub-Batch Normalization

– 기존 BN에 수정을 더해서 target network와 디코더에 적용가능하도록 했다.

– Standard BN은 batch, height, width dimension을 따라서 convolutional layer의 activation들의 mean과 variance를 계산한다.

– 디코더에서는, standard BN operation at training time would average activations along all the tokens in the input target sequence, and the BN output for each target token would incorporate the information about the tokens that follow it. This breaks the conditioning structure of Eq.1, since the succeeding tokens are yet to be predicted.

이를 해결하기 위해, we present Sub-Batch Normaization (SubBN). BN의 변형으로, the batch of training samples is split into two parts : the main batch and the auxiliary batch.

1) For each layer, the mean and variance of its activations are computed over the auxiliary batch.

2) At the same time, the loss is computed only on the predictions of the main batch, ignoring the predictions from the auxiliary batch.

Bag of Character N-gram

The tokens that we adopt correspond to characters in the input sequences. An efficient way to increase the capacity of the model is to use input embeddings not just for single tokens, but also for n-grams of adjacent tokens.

At each position we sum the embeddings of the respective n-grams (1에서 5까지의 n) component-wise into a single vector.

Although the portion of seen n-grams decreases as the value of n increases – a cutoff threshold is chosen for each n – all characters (n=1) are seen during training.

This fallback structure provided by the bag of character n-grams guarantees that at any position the input given to the network is always well defined. The length of the sequences corresponds to the number of characters and does not change when using bags of n-grams.

 

4.  Model Comparison

4.1  Recurrent ByteNets

ByteNet 구조는 decoder에서 동적인 길이의 encoder output를 받아들일 수 있기 때문에, 반드시 CNN으로 구현할 필요는 없다.

따라서 우리는

  • Convolutional encoder / recurrent decoder의 구조도 시도할 수 있고,
  • Recurrent encoder (bidirectional RNN) / recurrent decoder의 구조도 시도할 수 있다. (Target RNN은 source RNN 위에 쌓여진다.)

이전에 연구된 RNN Enc-Dec network 모델이 우리의 Recurrent ByteNet과 비슷하지만, 그 모델은 s0과 t0 사이를 제외하고는 encoder와 decoder사이의 모든 연결이 제거된 형태이다.

(즉 Recurrent ByteNet은 weight sharing scheme으로 볼 때 RNN Enc-Dec network의 일반화된 모델이라고 볼 수 있다. Convolutional ByteNet도 마찬가지이다.)

Screen Shot 2017-07-11 at 2.53.29 PM.png

: Recurrent ByteNet variants of the ByteNet architecture.

  • Left: Recurrent ByteNet with convolutional source network and recurrent target network.
  • Right: Recurrent ByteNet with bidirectional recurrent source network and recurrent target network. (a strict generalization of the RNN Enc-Dec network.)

 

4.2  Comparison of properties

  • RCTM (Recurrent continuous translation model)
  • RNN Enc-Dec
  • RNN Enc-Dec Att with the attentional pooling mechanism
  • Grid LSTM translation model
  • Extended Neural GPU model

이런 기존 연구들과 네트워크의 특성을 비교하는 부분. (일단 자세한 내용은 생략)

Screen Shot 2017-07-11 at 3.43.28 PM.png

그리고 ByteNet의 성능은 매우 우수했다. (..)

실험 결과부분은 논문 참조.

Byte-net model from DeepMind’s paper Neural Machine Translation in Linear Time.

Advertisements

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