Decoding, BLEU

DONGJIN IM·2022년 3월 13일

AI 이론

AI(NLP) 이론

목록 보기

15/18

Decoding

Decoding이란?

Seq2Seq에서 Decoder를 수행할 때 어떤 단어를 출력할지 정하는 Algorithm을 말한다.
언제나 Decoder는 다음 단어를 예측할 때 다음 단어가 A일 "확률"을 반환하기 때문에, 꼭 Decoding Alogirhtm에 따라 서로 다른 결과가 반환될 수도 있다.

Greedy-Decoding

Seq2Seq에서 가장 기본적인 Decoding 방식으로, 문장 전체를 보기 보다는 현재 Time Step에서 가장 좋아 보이는 단어를 선택하는 것이다.

현재 시점에서 (다음 단어로) 예측한 확률 값을 활용하여, 가장 높은 확률을 가지는 단어를 Output으로 반환한다.

문제는 잘못 해석했을 때 뒤로 돌아가지 못한다는 점이다. 시간을 기준으로 보면, 과거로 돌아가 잘못 해석된 단어를 고칠 수 없는 문제가 발생한다.

이러한 이유로 최종 정확도 관점에서는 좋지 못한 방법인데, 한 번이라도 예측이 틀리면 그 문장은 틀린 방향으로 갈 확률이 기하 급수적으로 높아지기 때문이다.

Exhaustive Search

내가 생성할 수 있는 모든 Sequences y에 대해 확률 값을 계산하는 방법이다.

예를 들어, 3개 단어가 있을 경우, 3개 단어로 만들 수 있는 모든 문장을 만든 뒤 모든 문장에 대하여 확률을 계산하여 가장 높은 확률 값을 가진 문장을 최종적인 Output으로 반환하는 것이다.

설명을 봐도 느낌이 오겠지만, 한 개의 문장을 찾는데 너무나도 많은 계산이 필요한 Decoding 기법이다.

Beam Search

Beam Search란?

Decoder의 Time Step마다 k개의 Sequence 후보 군을 만들어 놓고, 매 Time Step마다 후보군을 Update 시키는 알고리즘이다.

k : Beam Size. 주로 5 ~ 10개로 설정함
- Beam Size를 적용하면 기계 번역에서 BLEU 성능이 2 가량 올라간다고 한다
Hypothesis(가정) : 만들어 놓은 후보군

NLP 모델 성능에 매우 크게 기여한 기법이다.
우선 Time Step마다 $K^2$ 의 가정 Sequence를 만들어 놓는다. 그리고, 이 Sequence들 중 확률이 높은 K개의 Sequence로 가정을 Update 시키는 것이다.
가장 좋은 문장이라고 보장되지는 않지만, 효율적이고 정확도도 나쁘지 않다.

곱셈이 아닌 덧셈 연산으로 Score를 계산한다는 특징을 가지고 있다.

score(y_1, ..., y_t) = logP_{LM}(y_1,...,y_t|x) = \sum_{i=1}^tlogP_{LM}(y_i|y_1,...,y_{i-1},x)

t : Sequence Length. (지금까지 예측한) 문장 길이

원래라면 $P(y_1|x)$ * $P(y_2|y_1,x)$ * $...$ * $P(y_t|y_1, y_2,...,y_{i-1},x)$ 연산이 수행되어야 했을 것이다. 하지만 Beam Search에서는 log를 씌워줌으로써 곱 연산을 덧셈 연산으로 바꿔서 계산한다.

Beam Search를 하는 도중 <END> 신호를 냈다고 예측했다면, 해당 가설은 구성이 완료된 것으로 생각하여 저장 공간에 임시로 해당 문장을 저장해 둔다. 그리고 알고리즘이 끝난 이후 최종적인 결과 문장을 예측할 때 저장 공간에 저장된 가설들을 활용한다.

Beam Search 연산 과정

Step 1 : <SOS> Token이 입력됨

문장을 시작한다는 것을 알림
Beam Size = K로 지정했다고 가정하자

Step 2 : <SOS> 입력에서 예측 확률 중 가장 높은 K개의 단어를 선택함

가장 높은 확률로 예측된 단어를 포함한 문장이 하나의 Beam으로 설정됨

Step 3 : K개의 Beam에서 각각의 Beam마다 예측 확률이 가장 높은 K개의 단어를 선택함

자식 Node는 총 $K^2$ 개가 존재하게 될 것이다.
- Beam의 개수는 K개이고, 하나의 Beam 당 K개의 단어를 선택하기 때문에, 최종적으로 모든 Beam이 가지는 단어는 총 $K^2$ 개가 될 것이다.

Step 4 : Step 3에서 뽑은 단어 중 "누적 확률" 순으로 상위 K개를 뽑음

항상 누적 확률을 기준으로 후보군을 뽑아야함을 알고 있자
어떤 Beam에서 뻗어 나왔냐에 따라 누적 확률은 달라짐
- 위에서 설명한 score 수식 확인하기

Step 5 : Stopping Criterion의 기준을 맞출 때 까지 Step 3 ~4의 과정을 반복

Beam Sarch의 Stopping Criterion
- T라는 time step의 최댓값이 설정되었을 때, 그 시간까지 Beam Search를 수행하고 종료
- 임시 저장 공간을 N개로 설정하고, N개의 공간에 모두 (<END>로 끝난) 가설이 저장되었으면 Beam Search를 종료

Step 5 : Stopping Criterion을 맞춰 종료되었을 경우, 임시 저장 공간에 저장된 가설들 중 확률이 가장 높은 문장을 최종 Output으로 선택함

Length Penalty

위 알고리즘 문제점은 긴 가정(Hypothesis)는 Score가 작을 수 밖에 없다는 것이다.
확률은 항상 0 ~ 1 값을 가지고, log를 씌웠기 때문에 매번 Time Step에 더해지는 값은 음수이기 때문이다.
즉, 덧셈 연산을 통해 Score를 계속해서 더하고, Score는 항상 음수의 값을 가지므로 길이가 길수록 Score가 작아진다.

Length Penalty는 Socre의 합을 Normalize시켜 Score가 Time Step에 영향을 받지 않도록 하는 기법이다.
덧셈 연산을 통해 구한 확률에 Length Penalty를 나눈 값을 최종적인 확률로 생각하는 것이다.

Length Penalty 구하는 방법

lp(Y) = (\frac{min\_length + |Y|}{(min\_length + 1)})^a

lp(Y) : Beam Y에 대한 Length Penalty
|Y| : Beam Y의 길이
min_length : 보통 5로 설정함
a : alpha. 보통 1.2 정도로 값을 사용함

BLEU score

BLUE Score란?

Bilingual Evaluation Understudy의 야갖로, input과 output이 모두 Sequence로 이루어져 있는 경우 사용하는 지표(Metric)이다.

자연어 생성 모델의 정확도를 평가하는 지표로써, 0이 가장 작고 1이 가장 큰 값을 가진다.

Machine translation과 같은 Generation task에 주로 사용된다.
(ROUGE score : Text Summarization에서 자주 활용되는 Metric)

BLUE score의 도입 배경

Precision : 정밀도
- $precision = \frac{\#(correct\;\; words)}{length\_of\_prediction}$
- 예측한 문장 중 정답인 단어 개수 비율
Recall : 재현율
- $recall = \frac{\#(correct\;\; words)}{length\_of\_reference}$
- 실제 Data 문장에 포함된 단어 중 예측한 문장에서 올바르게 예측한 단어 개수 비율
F1 score(F-measure)
- $recall = \frac{\#(correct\;\; words)}{length\_of\_reference}$
- 조화 평균
위 3개 Metric을 NLP에 적용할 떄 발생하는 문제점
- Reordering에 대한 Penalty가 없음
- NLP의 Data는 시간적 순서가 중요함과 동시에 꼭 정확한 자리에 완벽히 같은 Data가 존재할 필요도 없음
- (ex) I love you가 원래 단어였는데, 예측을 Oh, I love you로 했다면 비슷한 의미이지만 Recall이나 Precision을 생각해보면 단어 위치가 모두 다르므로 0의 정확도나 재현율을 가진다고 생각할 것이다.

BLEU score

N-gram 활용
- N-gram : 특정 단어를 고려할 때, 이전 (N-1)개 단어까지 같이 포함시켜 해당 영역에 정답 word가 존재한다면 올바르게 예측했다고 생각함

Precision을 계산
- 예측한 문장(Prediction) 길이를 기준으로 Score를 매김
- (ex) I love you와 Oh, I love you를 생각해보자. 예측한 문장 길이를 기준으로 해야 하므로 Oh, I love you를 기준으로 생각해야 한다. 2-gram을 생각해보자. 먼저, Oh는 0 ~ 1번째 Reference Sentence 단어에는 존재하지 않으므로 correct word가 아니다. 하지만, I는 1 ~ 2번째 Refernece Sentence에 존재한다(첫 번째 단어). love와 you도 동일하다. 따라서, 2-gram일 때의 Precision은 0.75가 될 것이다.
BLEU score에서는 n-grams of size를 1 ~ 4로 설정한 이후 Precision 연산을 각각의 size에 대해 모두 수행하고, 총 4개의 Precision을 모두 활용하여 계산함
BLEU score 구하는 공식

$BLEU = min(1, \frac{length\_of\_prediction}{length\_of\_reference})(\prod_{i=1}^4 precision)^{\frac{1}{4}}$
- $min(1, \frac{length\_of\_prediction}{length\_of\_reference})$ : Brevity Penalty
  - 예측 문장이 짧아진 비율만큼 점수를 깎는 목적으로 곱해짐
  - 문장이 길어질 경우에는 점수를 깎지 않음(1 적용)