이전까지 살펴본 seq2seq 모델은 매 time step 마다 output 중에서 가장 확률이 큰 값만을 골라서 번역 문장을 완성해나갔다. (greedy decoding) t시점에서 뒤늦게 잘 못 예측했다는 사실을 이후에 알아차리더라도 돌아갈 수 없다
seq2seq 모델이 입력문장 x 일 때, 출력문장 y를 만들어낼 확률은 P(y|x)이다. y가 정답일때 P(y|x)를 최대로 만들도록 학습시킨다.
P(y|x)를 만드는 식을 살펴보면 (입력문장 x일때 y의 첫번째 단어 y1일 확률)*(입력문장 x 이고 첫번째 y1 일때 y2일 확률) .....이다.
그럼 전체 타임스텝 t에 대하여 P(y|x)를 만드는 모든 경우의 수를 고려하면 vocab size V의 t승 가지를 조합해봐야 한다. O(V^t) 이건 말도 안되는 complexity이므로 차선책으로 Beam search가 등장했다.
1. Beam Search
원래같으면 매 timestep마다 V개의 경우의 수를 살펴봐야 하지만 beam search에서는 미리 정해 둔 beam size k개만 고려한다.
현재 순간에서 가장 유망한 t개의 hypothesis(y1, y2,...,yt) 를 선택한다. log를 씌워서 곱셈을 전부 덧셈으로 만든다.
(t=1)첫번째 time step에서 가장 유망한 두개를 뽑는다.
(t=2)앞서 나온 두 경우의 수에 이어서 각각 또 유망한 2개를 뽑는다. 지금까지는 k^2개의 경우의 수를 살펴보고 있다.
(t=3) 이전 스텝에서 가장 유망한 hit, was를 선택해서 k=2 개씩 선택한다.
(t=4) 이전 time step에서 가장 유망한 a, me를 선택해서 k=2개씩 선택한다.
이렇게 계속 진행하다보면 어떤 branch는 <eos>를 내보낼 수 있다. 그럼 해당 branch는 더 뻗지 않고 완료됐다고 생각하고 어딘가에 따로 저장한다. 다른 branch는 계속해서 search를 진행한다.
끝까지 <eos>가 안 나온다면 두 가지 상황에서 종료를 한다.
1) 미리 정해둔 n개 만큼 complete sentence를 저장한 경우 혹은
2)미리 정해둔 timestep T까지만 search를 수행 한다.
탐색이 끝나고나면 complete sentence를 저장해둔 공간으로 가서 complete sentence의 log(joint probability)가 높은 문장을 최종 선택한다.
하지만 문장이 짧을 수록 확률이 크다는 문제가 있다. 단어가 길게 계속 생성되면 계속 -log(확률)을 더하기 때문에 길수록 불리하다. 따라서 공평한 확률을 계산하기 위해 각 complete sentence 의 길이로 나눈다.
'boostcamp AI tech > boostcamp AI' 카테고리의 다른 글
| Transformer - self attention (1) | 2023.12.06 |
|---|---|
| BLEU, Precision-Recall (0) | 2023.11.30 |
| Seq2Seq with attention (1) | 2023.11.30 |
| Long-Short Term Memory, GRU (0) | 2023.11.29 |
| Word Embedding - Word2Vec, GloVe (1) | 2023.11.27 |
