[5.3.] Various Sequence To Sequence Architectures(1)

1. Basic Models

[Sequence to sequence model]

sequence $x$를 입력하면 sequence $y$를 출력하는 신경망을 어떻게 구성하면 될까?

 

RNN(혹은 GRU, LSTM)으로 이루어진 encoder 파트

 - input sentence를 represent 하는 벡터를 출력함

 

(파란색 펜) 입력된 벡터로 sequcen $y$를 출력하는 decoder 파트

 

이러한 아키텍처는 "image captioning"에서도 효과적

 

AlexNet

사전학습된 AlexNet 사용 - 마지막 softmax 레이어를 제외하면 input image 를 4096차원의 feature vector로 encoding한 셈이 됨

이 feautre vector를 RNN에 입력하여 한번에 한 단어씩 캡션을 생성하게 함

 

2. Picking the Most Likely Sentence

sequence to sequence 모델과 language model 의 차이점

 

[Machine translation as building a conditional lanuage model]

- $P(y^{<1>}, y^{<2>}, \cdots, y^{<T_{y}>})$ : probability of sentence 를 계산함

- 입력되는 $x^{<t>}$들은 결국 이전 출력값 $y^{<t>}$ 이므로 지우고 무시해도 됨! ($x^{<0>}$는 영벡터)

 

- 초록색 encoder, 보라색 decoder

- 이때 decoder 부분이 language model 과 동일함

- 즉 language model과 machine translation model은 매우 비슷한데, 차이라면 language model은 representation of all zeros으로 시작하지만 machine translation model은 encoded network가 앞에 붙어있다는 점 (representation of input sentence 로 시작함) 

- 따라서 후자를 'conditional language model' 이라고 부르며, 문장의 확률(probability of any sentence)을 구하기보다는, 입력 문장이 주어졌을 때의 문장의 확률을 구하는 것 ($P(y^{<1>}, y^{<2>}, \cdots,y^{<t_{y}>} | x_{<1>}, \cdots)$)

 

 

[Finding the most likely translation]

"Jane visite l'Afrique en septembre"

 

Given this input French sentence, the model might tell you what is the probability of difference in corresponding English translations

 

$$P(y^{<1>}, \cdots, y^{<T_{y}>}|x)$$

 

- $x$ : french sentence

- $y^{<1>}, \cdots, y^{<t_{y}>}</t_{y}>$ : probability of different English translations of the input

- output을 random하게 샘플링하지 않는다

 

그냥 임의로 샘플링하다보면 이상한 번역문장도 나올 것임

-> 따라서 conditional probability를 최대화하는 영어문장을 샘플링해야 함!

$$\mathop{arg\ max}_{y^{<1>}, \cdots, y^{<T_{y}>}} P(y^{<1>}, \cdots, y^{<T_{y}>}|x)$$

-> machine translation 을 개발할 때 $P(y^{<1>}, \cdots, y^{<t_{y}>}|x)$를 최대화하는 $y$값을 찾는 알고리즘을 찾아야 함

 

[Why not a greedy search?]

greedy search 란? 제일 그럴 듯한 $\hat{y}^{<1>}$를 출력했으면 그 다음 best $\hat{y}^{<2>}$를 출력하고 그 다음 best $\hat{y}^{<3>}$를 출력하고 ... 

 

그러나 우리가 필요한 것은 best $P(y^{<1>}, \cdots, y^{<t_{y}>}|x)$ - 즉 최고의 joint probability

- greedy approach 는 각 단어를 best로 뽑는 것이니 다름

 

"Jane is visiting Africa in September"

"Jane is going to be visiting Africa in September"

 

두 출력문장이 있을 때 더 좋은 것은 전자. 후자는 나쁘지 않은데, 그래도 probability가 전자가 더 높게 나와야 함

 

만약 알고리즘이 첫 두개 단어로 "Jane is"로 골랐다고 치자

"going"이 더 자주 쓰는 표현이므로  $P("Jane\ is\ going"|x) > P("Jane\ is\ visiting"|x)$ - 즉 "Jane is going" 의 확률이 더 높게 나올 것이다

후자는 앞에 나온 단어들 기반으로 best 를 뽑는 방식밖에 안 되니까. 하지만 결과적으로는 전체 문장은 best가 아니게 됨.

 

그런데 전체 단어의 조합 개수는 굉장히 많음 - vocab 사이즈가 10000이고 10개단어로 이루어진 문장이라고 하면 $10000^{10}$개의 조합이 나올 수 있음

모든 조합에 대해서 점수를 매길 수 없음 --> approximate search algorithm 을 사용하게 됨

 

approximate search algorithm  : conditional probability를 최대화하는 $y$를 뽑는다 (항상 되는 건 아님)

 

"search algorithm to find the most likely English sentence"

 

 

3. Beam Search

Step1. 네트워크의 일부분을 활용하여, input sentence $x$가 주어졌을 때 첫번째 output $\hat{y}^{<1>}$에 대한 probability를 계산

- 한번에 한 단어를 예측하는 대신에, Beam search 는 여러 단어를 고려한다 

- Beam search의 파라미터 $B$(beam width) 를 3라고 해보자 => 한번에 세 단어를 고려한다는 의미

 

첫번째 단어로 올 the most likely three possibilities : in, Jane, september

 

정리: Beam Search 하고자 하면 먼저 input sentence를 encode 하고, decoder의 첫번째 softmax output를 (10000개 가능성 중에서) 저장해두고 top3를 킵해둔다

 

step2. step1에서 선정한 세 단어 각각에 대해 두번째 단어가 무엇일지 고려한다

에를 들어 세 단어 중 하나가 "in" 이 었다. decoder의 두번째 스텝에 "in"을 입력하여 $P(y^{<2>}|x, "in")$을 계산한다

궁극적으로 여기서 알고자 하는 건 $P(y^{<1>}, y^{<2>} | x)$, 즉 가장 그럴 듯한(the most likely) $y^{<1>},y^{<2>}$ 쌍에 대한 확률을 구하는 것

조건부확률 규칙에 따라, 

$$P(y^{<1>}, y^{<2>} | x) = P(y^{<1>}|x)P(y^{<2>}|x, y^{<1>})$$

세 단어에 대해 각각 계산을 수행함

이 단계에서는 $10000*3$ 만큼 계산하게 됨; beam width x vocab

--> 30000개 $P(y^{<1>}, y^{<2>} | x)$ 중에서 top3 를 고름

예를 들어, in september, jane visits, jane is 이 세 개가 뽑혔다고 해보자

--> september는 첫번째 단어 후보에서 탈락된 것임

 

Beam Search 는 매 단계마다 네트워크의 복사본 세 개(beam width)를 가져다가 sentence의 일부분을 evaluate 한다

- 네트워크를 30000개를 복사할 필요가 없음

 

step3. 두번째 단어까지 세 개의 후보가 나온 상황, $P(y^{<1>}, y^{<2>}|x)$를 메모리에 저장해둠

동일한 방식으로 계산 ($P(y^{<3>}|x, "in september")$) - top3 뽑음

 

한 번에 beam width 만큼 possibilties 를 고려함

- 만약에 $B=1$이면 greedy search 와 동일해짐

 

 

4. Refinements to Beam Search

[Length normalization]

$$arg\mathop{max}_{y} \prod_{t=1}^{T_{y}} P(y^{<t>}|x, y^{<1>}, \cdots, y^{<t-1>})$$

 

즉 

 

$$P(y^{<1>}, \cdots, y^{<T_{y}>}|x) = P(y^{<1>}|x) P(y^{<2>}|x, y^{<1>})\cdots P(y^{<T_y>}|x, y^{<1>},\cdots, y^{<T_{y}-1>})$$

 

- 곱하게 되는 확률값들은 전부 1 이하의 값 => 계속 곱하면 numerical underflow 발생할 수 있음(too small for the floating point of representation in your computer to store accurately)

 

따라서 log를 취한다

$$arg\mathop{max}_{y} \sum_{t=1}^{T_{y}} log P(y^{<t>}|x, y^{<1>}, \cdots, y^{<t-1>})$$

 

문장이 길수록 값이 작아지므로, 모델이 짧은 output을 선호하는 경향이 생길 수 있다

(1보다 작은 값은 로그 취했을 때 음수가 되므로 더할수록 값이 작아짐)

 

따라서 translation 문장에 있는 개수만큼 normalize 해준다 (평균을 구하게 됨)

 

$$\frac{1}{T_{y}}\sum_{t=1}^{T_{y}} log P(y^{<t>}|x, y^{<1>}, \cdots, y^{<t-1>})$$

 

$\frac{1}{T_{y}^{\alpha}}$로 나누기도 함

- 하이퍼파라미터 $\alpha$는 일반적으로 0.7

- $\alpha$가 1이면 normalize를 안 하는 효과 (no normalization)

- $\alpha$가 0이면 단어 개수로 그대로 나누는 효과 (full normalization)

 

wrap-up:

beam search 하면서 다양한 길이의 문장을 본다 $T_{y}=1, 2, \cdots ,$ 그리고 여기 예시에서 output sentence length가 최대 30까지 간다고 해보자

각 길이의 문장들에 대해서 possibility가 높은 top $B$개를 선정하게 됨

그 다음, 이 output 문장들을 전부 보고 $\frac{1}{T_{y}}\sum_{t=1}^{T_{y}} log P(y^{<t>}|x, y^{<1>}, \cdots, y^{<t-1>})$으로 점수를 매긴다 (일명 normalized log likelihood objective) - 가장 높은 점수인 것이 최종 문장

 

[Beam search discussion]

 

- Beam width $B$

     - 값이 매우 크면: 많은 가능성을 고려하므로 더 좋은 결과물이 나올 수 있음, 대신에 느리다

     - 값이 매우 작으면 : 결과물은 별로 안 좋음, 대신에 빠르고 필요한 메모리도 적다

 

실제로는 $B=100$ 정도로 크게 진행하기도

 

이 부분 이해 못해도 괜찮음

 

 

5. Error Analysis in Beam Search

beam search 는 heuristic search algorithm 이기 때문에 항상 가장 그럴 듯한 문장을 출력하는 것은 아니다

- 결과가 그다지 좋지 않을 때, beam search가 문제일까 나의 RNN 모델이 문제일까? 분석해보자

 

인간이 쓴 best translation $y^{\ast}$

"Jane visits Africa in september"

 

알고리즘이 예측한 (별로 좋지 않은) $\hat{y}$는

"Jane visited Africa last September"

 

나에게는 encoder/decoder로 이루어진 RNN 모델이 있고, Beam search 를 사용하고 있다.

 

데이터를 더 모으는 게 도움이 될 수 있듯 beam search의 beam width 를 늘리는 것도 방법

- 그러나 데이터를 모으는 게 전부가 아니듯 beam search 도 width 늘린다고 되는 건 아님

 

RNN computes $P(y|x)$

--> 모델로 하여금 $P(y^{\ast}|x)$와 $P(\hat{y}|x)$를 계산하게 하고 무엇이 더 큰지 비교해봄

- 모델 문제인지 서치 알고리즘 문제인지 대충 파악할 수 있음

 

[Beam analysis on beam search]

case1. $P(y^{\ast}|x) > P(\hat{y}|x)$

- beam search chose $\hat{y}$, but $y^{\ast}$ attains higher probability

--> beam search 가 문제다 (P값을 최대화하는 문장을 찾지 못하고 있음)

 

case2. $P(y^{\ast}|x) \leq P(\hat{y}|x)$

- $y^{\ast}$ is a better translation than $\hat{y}$, but RNN predicted $P(y^{\ast}|x) \leq P(\hat{y}|x)$

--> RNN 모델이 문제다

*만약 length normalization 을 이용하고 있다면 위 확률값들을 evaluate할 게 아니라 length normalization 과 관련되는 optimization objective 를 evaluate 해야 한다

 

development set에서 알고리즘의 출력이 잘못된 것을 확인함