[18-1] Beam Search와 BLEU score

Beam Search는 자연어 생성 decoding 중 하나입니다.

Beam Search를 사용하면 sequence to sequence with attention의 자연어 생성 모델에서 좋은 품질(텍스트)을 얻을 수 있습니다.

 

1️⃣ 자연어 생성 decoding

 

1) Greedy decoding

 

탐욕적 decoding입니다. 현재 스텝에서 가장 확률이 높은 단어를 선택합니다. 

하지만 이 방법은 최적의 예측값을 내어주지 못합니다.

 

 

2) Exhaustive search

 

전체 길이 $T$에서 가장 높은 확률값을 선택합니다.

 

 

현재 스텝에서는 최적의 예측값이라고 하더라도, 뒷부분에서 나오는 확률 값이 낮을 수 있기 때문에 최적의 예측값이 아닐 수도 있지만 차선의 예측값을 구할 수 있습니다.

 

문제는 timestep $t$까지의 모든 vocabulary 수 $V^{t}$를 모두 계산해야 하기 때문에 많은 cost가 소요됩니다.

 

 

2️⃣ Beam Search

 

매 timestep마다 하나의 가능성을 찾는 greedy decoding과 모든 timestep의 가능성을 찾는 exhaustive search를 적절히 섞은 방법이 Beam Search입니다.

 

사용자가 정의해놓은 k개의 가능한 가지수를 고려해서 택하는 방법입니다. (k는 beam size)

k개의 경우의 수에 해당하는 decoding의 output 각각을 hypothesis라고 부르게됩니다.

 

 

score를 구할 때 log를 붙이는 이유는 곱셈을 덧셈으로 변경해줘서 기하급수적으로 커지는 값을 방지하는 것입니다.

 

 

예를 들어, Beam size : $k=2$인 경우 Beam Search를 수행해봅시다.

문자가 생성될 때는 <START> token이 가장 먼저 나오게 됩니다.

 

https://web.stanford.edu/class/cs224n/slides/cs224n-2019-lecture08-nmt.pdf

 

<START> token에서 $log P_{LM}$을 구했을 때, 가장 확률이 큰 2개(=beam size;k)를 선택합니다.

(여기서 마이너스 값이 나오는 이유는 $log$를 씌어주었기 때문에 1을 기준으로 작으면 마이너스 값이 나옴)

 

https://web.stanford.edu/class/cs224n/slides/cs224n-2019-lecture08-nmt.pdf

 

그리고 "he"와 "I"에 대한 다음 단어를 예측하게 됩니다. 다음 단어도 각 단어에 대해 확률이 가장 높은 k(=2) 개를 선택합니다. 이후, 계산된 k(=2)개를 뽑은 후, 다시 각각의 k(=2)개를 다시 계산합니다.

("he"에서 -0.7이 나오고 "hit" 단어에서 -1이 계산되었다면 "he" -> "hit"으로 가는 확률은 -1.7 임)

 

https://web.stanford.edu/class/cs224n/slides/cs224n-2019-lecture08-nmt.pdf

 

 

Greedy decoding은 항상 <END> token이 나오는 시점이 끝이지만,

Beam search decoding은 여러 가지 hypotheses가 존재하고, 이에 따라 다양한 <END> token이 나오게 됩니다.

 

따라서 Beam search는 사용자가 completed hypotheses 개수를 설정해주어야 됩니다.

미리 정해둔 n개의 completed hypotheses가 나오게 되면 beam search는 종료하게 됩니다.

 

이후, beam search가 끝나면 n개의 completed hypotheses 중 확률이 가장 큰 값 1개를 골라야 합니다.

하지만 beam search는 hypotheses의 길이가 자유롭게 나올 수 있기 때문에 상대적으로 긴 길이 sequence는 낮은 scores가 나오게 됩니다.(계속해서 마이너스 값을 더해주기 때문에)

따라서 단어의 개수로 나눠 평균을 구해줍니다.

 

 

3️⃣ BLEU score

 

BLEU score는 자연어 생성 모델에서 생성 모델의 정확도를 평가하는 척도입니다.

 

먼저, Score를 측정은 정답 격인 Reference 문장과 예측을 하는 Predicted 문장을 비교하는 것입니다.

 

 

Score를 측정에 있어 precision과 recall 개념을 사용합니다.

 

precision(정밀도)는 ground truth 단어와 겹치는 단어가 몇 개 있는가를 세줍니다.

(예측된 결과가 노출이 되었을 때 사용자가 실질적으로 느끼는 정확도)

 

recall (재현율)는 correct word에서 reference의 길이로 나눠줍니다.

(실제 문서(reference)의 word 총 개수 중에서 사용자에게 얼마나 잘 보여주었는가)

 

F-measure는 조화 평균을 말합니다.

(산술/기하/조화 평균 중 작은 값에 치중되는 평균)

 

 

여기서 recall를 사용한 이유는 Reference 단어를 고정해놓고 평가를 하게 되면 predicted가 단어를 하나 더 만들거나 적게 만들 경우, 아래와 같이 단어가 밀리게 되면서 정확도가 0%로 계산될 수 있기 때문입니다.

 

 

이번에는 다른 Predicted (model 2)를 주목해봅니다.

model2는 정확히 모든 단어가 recall 되었고, precision도 정확하기 때문에 100%가 나왔습니다.

하지만 문법적인 구조(ordering)가 맞지 않습니다.

 

 

https://www.edwith.org/bcaitech1

 

이러한 issue를 해결하기 위해서 BLEU Score를 사용합니다.

BLEU Score는 개별 word level에서 봤을 때 얼마나 공통적으로 ground truth와 겹치는 단어가 나왔느냐에 대한 계산뿐 아니라 N-gram이라는 N개의 연속된 단어가 얼마나 ground truth와 겹치느냐를 최종 score에 반영합니다.

 

 

따라서 BLEU Score에서는 recall은 무시하고, precision만 사용하게 됩니다.

왜냐하면 아래 예시처럼 reference 문장 전체를 구현하지 않아도 사용자가 느낄 때 의미가 전달되는 문장이 있기 때문입니다. 아래는 Reference(en)을 Predicted(ko)한 예시입니다.

 

Reference : I love this movie very much.

Predicted : 나는 이 영화를 정말 많이 사랑한다.

여기서 "very much"는 "정말 많이"라는 뜻으로 번역해야 하지만 "정말"을 빼도 의미가 전달됩니다. 위 예시와 같이  "reference 문장의 단어가 얼마나 들어가 있는지 확률을 계산해주는 recall"은 자연스러운 의미 전달을 해칠 우려가 있어 BLEU에서 사용하지 않습니다.

 

 

BLEU는 기하 평균을 사용합니다.

 

$$(\Pi^{4}_{i=1}precision_{i})^{\frac {1} {4}}$$

 

 

BLEU는 brevity penalty를 사용합니다.

 

$$min(1,\frac {length\_of\_prediction} {length\_of\_reference})$$

 

Brevity penalty는 

 

• reference 길이보다 짧은 문장을 생성하는 경우 (reference =10 문장 > prediction = 7문장 ) => 0.7
• reference 길이보다 긴 문장을 생성하는 경우 (reference =10문장 < prediction =13 문장 ) => 1 (항상 1)

을 나타냅니다. brevity penalty는 "recall의 최대값"과 같은 의미라고 생각하면 됩니다.

 

 

BLEU는 N-gram을 사용해 N개의 단어를 묶어서 비교하는 방법을 사용합니다.

 

가령, 2-gram의 경우 아래와 같이 단어를 2개씩 묶어서 Reference와 비교하는 것을 뜻합니다.

3-gram은 단어를 3개씩, 4-gram은 단어를 4개씩 묶어서 비교합니다.

 

N-gram을 사용하면 문법적 구조(ordering)이 붕괴되는 것을 막을 수 있습니다.

N-gram을 통해 위에서 model2가 100% 나오는 것을 방지할 수 있습니다.

 

https://www.edwith.org/bcaitech1