[2018 ACL Long] Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates

[Jasonlee1995]

BPE는 deterministic하게 sentence를 subword sequence로 segment함

해당 논문은 sentence를 multiple subword sequences로 segment하여 학습하는 subword regularization을 제안함

또한, subword regularization을 사용하기 위해 unigram tokenizer를 제안함

Subword regularization을 통해 low resource, out-of-domain scenario에서 성능을 개선할 수 있으며, dataset size가 커질수록 subword regularization로 인한 성능 향상 폭이 줄어듬

중요하다고 생각되는 부분만 간단히 요약

1. Introduction

Spurious ambiguities in subwording : 1개의 문장은 multiple subwords로 segment될 수 있음
(BPE는 deterministic하게 tokenize하지만, BPE의 token들을 통해 동일한 문장을 다양한 token의 조합으로 나타낼 수 있음)

저자는 segmentation ambiguity를 noise로 이용하여 NMT를 학습하는 방법인 subword regularization을 제안하며, 3가지 측면에서 NMT의 robustness를 증가할 수 있다고 기대함

1. model이 noise, segmentation error에 robust할 것임
   text의 경우 오타가 많은데, 이를 어느정도 보정할 것임
2. word composition에 대해 indirectly하게 학습할 것임
   똑같은 input에 대해 다양한 output이 나오도록 학습하며, 다른 input에 대해 똑같은 output이 나오도록 학습
   → word composition을 학습해야 loss가 줄 것이라는 컨셉
3. decoder가 local hypothesis를 뱉는 것을 방지
   decoder에서 1개의 token만 잘못 예측하더라도 hypothesis의 quality가 안좋아짐
   input, output에 segmentation ambiguity를 넣어서 학습하기에, 실수해도 좋은 결과를 생성할 수 있음

Subword regularization은 input, output을 다양하게 segment하여 학습하기에, 2가지를 고려해줘야함

1. multiple segmentation으로 NMT를 어떻게 학습할지?
2. 어떻게 multiple segmentation할지?

결론만 말하자면, 1번은 loss function을 손보고, 2번은 unigram tokenizer를 이용하여 해결

2. Neural Machine Translation with multiple subword segmentations

2.1. NMT training with on-the-fly subword sampling

해당 section의 흐름
기존의 NMT objective : maximize the log-likelihood
multiple subword sequences를 고려하여 NMT objective를 reformulate
reformulate objective가 현실적으로 불가능하니 k개를 sampling하여 approximate
많은 iteration으로 학습하니, k=1을 사용해도 충분히 괜찮음

기존의 NMT는 log-likelihood를 maximize하도록 학습됨

BPE와 같은 기존의 tokenizer는 sentence를 deterministic하게 segmentation하기에, P(Y|X) = P(y|x)임

저자가 제안한 subword regularization은 sentence를 multiple subword sequences로 segment하기에, segmentation probability인 P(x|X), P(y|Y)를 고려해야함

따라서, subword regularization은 marginal log-likelihood를 maximize하도록 학습하면 됨

하지만 sentence가 길어질수록 segmentation의 경우의 수가 기하급수적으로 증가하기에, marginal log-likelihood를 exact optimize하는 것은 불가능함

따라서, P(x|X), P(y|Y)로부터 sample한 k sequences의 marginal log-likelihood로 approximate해줌
(모든 segmentation 조합을 계산하는게 불가능하니, sample해서 approximate하겠다는 의미)

저자는 simplicity를 위해 k=1을 사용했으며, 충분히 많은 iteration으로 NMT를 학습하기에 괜찮다고 함
(when we have a sufficient number of iterations, subword sampling is executed via the data sampling of online training, which yields a good approximation even if k = 1)

2.2. Decoding

BPE와 같은 deterministic tokenizer와 달리, subword regularization은 multiple segmentation하기에 inference할 때 sentence X를 어떻게 segment해야할 지에 대해 신경써줘야함

저자가 제안한 2가지 decoding algorithm은 다음과 같음

1. best decoding : P(x|X)를 maximize하는 best segmentation을 사용
2. n-best decoding : P(x|X)를 maximize하는 n-best segmentations를 사용

2번 decoding algorithm의 경우, Equation (5)를 maximize하는 best translation을 선택

3. Subword segmentations with language model

3.1. Byte-Pair-Encoding (BPE)

Section 2에서는 multiple subword sequences로 NMT를 어떻게 학습할 지에 대해 다뤘음

학습을 하기 위해, sentence를 subword sequence에 대한 segmentation probability P(x|X), P(y|Y)를 알아야함

기존의 BPE와 같은 tokenizer는 deterministic하기에 multiple subword sequences를 만들 수 없으며 segmentation probability P(x|X), P(y|Y)를 계산할 수 없기에 사용할 수 없음

3.2. Unigram language model

저자는 multiple subword sequences를 만들 수 있으며, segmentation probability P(x|X), P(y|Y)를 계산할 수 있는 subword segmentation algorithm인 unigram tokenizer를 제안함

Unigram tokenizer는 unigram language model에 기반하며, 각 subword가 independent함을 assume함

만약 vocabulary set V가 존재한다면, 각 subword의 probability는 EM algorithm을 통해 구할 수 있음
(marginal log-likelihood L을 maximize하도록)

하지만 real word setting에서는 vocabulary set V가 없기에, 다음과 같은 과정을 통해 vocabulary set V를 구함

1. training corpus로부터 big seed vocabulary set을 만듬
2. vocabulary size가 원하는 size가 될 때까지, 다음 과정을 반복
   (a) vocabulary set에 대해 EM algorithm을 통해 $p(x)$를 optimize
   (b) 특정 subword $x_i$가 vocabulary set에서 제거되었을 때, log-likelihood의 변화량인 loss를 측정
   (c) loss를 기준으로 top $\eta$%에 해당하는 subword만 살리고, 나머지 subword는 vocabulary set에서 제거 (e.g. $\eta = 80$)

해당 방법을 통해 vocabulary set V를 구한 뒤, EM algorithm을 통해 각 subword의 probability를 계산할 수 있음

각 subword의 probability를 알기에, segmentation probability P(x|X), P(y|Y)를 계산할 수 있음

3.3. Subword sampling

NMT를 학습하기 위해, multiple subword sequences 중 1개의 subword sequence sample해야함

즉, P(x|X) distribution에서 1개의 x를 sample해야하는데, sample하는 방법이 2가지가 있음

1. l-best sampling : l-best segmentations에서 1개의 segmentation을 sample
2. complete sampling : 모든 segmentations에서 1개의 segmentation을 sample

참고로 sampling할 때, hyperparameter $\alpha$를 이용하여 distribution의 smoothness를 control

3.4. BPE vs. Unigram language model

BPE는 text를 encode하는데 사용되는 total symbols의 수를 minimize하는 dictionary (substitution) encoder의 일종임

Unigram tokenizer는 text의 total code length를 minimize하는 entropy encoder로 볼 수 있음
(Shannon's coding theorem에서의 symbol s에 대한 optimal code length는 -log p(s)임)

BPE와 unigram tokenizer는 모두 fewer bits를 이용하여 text를 encode하는 data compression principle에 기반함

다만, unigram tokenizer는 multiple segmentations에 대한 probability를 측정할 수 있으며, subword regularization에 사용할 수 있다는 점에서 더 flexible함

4. Related Work

저자의 intuition으로 돌아가보면, segmentation ambiguity를 noise로 이용하여 NMT를 학습하여 robustness를 improve하는 것임

이는 DNN의 overfitting을 방지하기 위해 noise injection을 하는 다양한 기존 연구와 맞닿아있음

특히, 저자는 subword regularization이 input sentence를 multiple invariant sequences로 convert한다는 점에서 data augmentation으로 볼 수 있다고 표현함

다만 subword regularization은 underlying language model에 기반하여 segmentation noise와 error를 emulate한다는 점에서, synthetic noise를 heuristic하게 inject하는 기존의 방법과 다소 다르다고 볼 수 있음

5. Experiments

5.1. Setting

5.2. Main Results

BPE, unigram tokenizer without subword regularization (l=1) 모두 비슷한 성능을 보이는데, data compression algorithm에 기반하였기에 당연한 결과라고 볼 수 있음

Subword regularization을 통해 성능을 높일 수 있으며, low resource scenario에서 성능 gain이 더 큼

n-best decoding을 통해 성능을 높일 수 있으며, subword regularization을 사용하지 않고 n-best decoding을 하면 성능이 악화됨

저자는 이에 대해 decoder가 학습할 때 보지 못한 multiple segmentation으로 인한 confusion 때문이라고 추측

즉, n-best decoding을 하기 위해선 subword regularization이 필수적임

5.3. Results with out-of-domain corpus

기존 scenario와 비교했을 때, out-of-domain scenario에서 subword regularization을 사용하면 성능 gain이 더 큼

즉, subword regularization은 open-domain에 더 적합하다고 볼 수 있음

5.4. Comparison with other segmentation algorithms

Unigram tokenizer + subword regularization의 성능이 제일 좋음

5.5. Impact of sampling hyperparameters

Sampling size $l$에 따라 최적의 smoothing parameter $\alpha$의 값이 달라짐

$l$이 클수록 more aggressive regularization이기에 low resource scenario에 더 적합할 수 있으나, performance가 $\alpha$에 더 sensitive해짐

따라서, high resource scenario에서는 적당한 $l$을 사용하여 smoothing hyperparameter를 좀 덜 신경쓰라는게 저자의 조언

$l = \infty, \alpha = 0.0$인 경우, 성능이 안좋음

즉, segmentation probability P(x|X)를 무시하고 segmentation을 uniform sample하게되면 성능이 안좋다는 것

이를 통해 actual translation에 존재하는 real noise를 emulate하는게 성능에 도움이 된다는 것을 알 수 있음

5.6. Results with single side regularization

이전의 모든 실험들은 source sentence와 target sentence에 모두 subword regularization을 적용한 것임

Source 혹은 target 중 1개만 subword regularization을 적용하는 single side regularization에 대해 실험

Single side regularization은 full subword regularization보다 성능이 안좋지만, baseline보다는 성능이 좋음

즉, subword regularization은 encoder-decoder architecture뿐만 아니라 encoder만 사용하거나 decoder만 사용하는 다양한 NLP tasks에서도 충분히 applicable함
(e.g. text classification, image caption generation)