Beam Search와 NLP 모델의 성능을 평가하는 지표인 BLEU Score

 

Beam Search

 

Greedy Decoding

 

먼저 이전에 공부했던 Attention 기반의 Seq2Seq 내용의 학습 과정을 확인해볼 필요가 있다.

Seq2Seq with Attention

Attention 기법을 사용한 Seq2Seq with Attention

 

기존 Seq2Seq 모델에서는 문장 전체를 보는 것이 아니라 근시안적으로 다음에 올 확률이 가장 높은 단어를 예측한다.

이처럼 현재 time step까지의 정보를 바탕으로 다음 time step에 올 단어를 선택하는 방법을 greedy decoding이라고 한다.

 

 

그러나 앞에서 잘못된 단어를 예측했다면 뒤에서는 이 잘못된 단어 데이터를 가지고 예측을 수행하게 되는데, seq2seq 모델에서는 이처럼 잘못 예측된 결과를 되돌릴 수는 없다.

 

 

$$ P(y|x) = P(y_1 | x) P(y_2 | y_1, x) P(y_3|y_2, y_1, x) \dots P(y_t|y_1, \cdots, y_{t-1}, x) = \prod_{i=1}^{t} P(y_i| y_{i-1}, y_{i-2}, \dots, y_1, x) $$

$$ P(y_1, \dots, y_t | x) = \prod_{i = 1}^t P(y_i|y_1, \dots, y_{i-1}, x) $$

 

 

주어진 입력 문장을 $x$라고 하고, 예측 문장을 $y$, 예측 문장을 구성하는 단어를 각각 $y_t$라고 하면 다음 예측 단어는 이전까지의 예측 단어와 입력 문장을 통해 만들어지며, 이를 동시 사건으로 고려하는 결합 확률을 곱하는 수식으로 나타낼 수 있다.

 

만약 위 수식에서 $P(y_1|x)$의 값이 높은 단어 $y_1$를 예측한다고 하더라도 뒤에 곱해지는 항에서 낮은 확률이 구해진다고 하면 이는 결과적으로 목적에 맞게 예측한 결과가 아닐 수 있다.

그래서 $P(y_1|x)$에서 가장 큰 확률값을 지니는 단어는 아니더라도 뒤의 항에서 더 높은 확률을 낼 수 있는 단어를 미리 앞에서 예측한다면 $P(y|x)$를 최대화 하는 데 더 가깝게 도달할 수 있고 결과적으로 더 품질 좋은 예측 결과를 낼 수 있을 것이다.

 

그렇지만 brute force 접근법처럼 주어진 단어장 $V$에 관해 매 time step $t$에 올 수 있는 모든 예측 문장의 경우를 고려하게 되면, 단어장 $V$의 각 단어를 하나의 경우로 고려하는 데 소요되는 시간을 $O(1)$이라고 가정할 때 전체 문장의 경우의 수를 고려하는 시간복잡도는 $O(V^t)$가 된다.

하지만 현실적으로 기하급수적으로 증가하는 시간복잡도를 미루어보면 brute force 접근법은 너무 많은 시간과 비용을 들게 한다.

 

 

 

Beam Search란?

 

Beam search는 seq2seq with attention 중 자연어 생성 모델에서 테스트 시 좀 더 좋은 품질의 결과를 보인다고 알려진 방법이다.

앞서 설명한 brute force 접근법은 사용하지 않았지만, greedy decoding과 brute force를 절충한 방법을 사용하여 매 time step 마다 가장 높은 확률의 한 단어만 예측하는 기존의 greedy decoding 방법의 단점을 개선했다.

 

 

Beam search에서는 decoder의 매 time step 마다 단 하나의 예측 후보만을 고려하지 않고 이미 정해놓은 $k$개의 경우의 수를 고려하는 아이디어를 사용했다.

여기서 $k$개의 경우의 수에 해당하는 decoding output을 각각 hypothesis로 부르고, 일반적으로 5에서 10 사이의 값으로 설정되는 $k$를 beam size라고 한다.

 

$$ \text{score}(y_1, \dots, y_t) = \log P_{LM}(y_1, \dots, y_t | x) = \sum_{i=1}^t \log P_{LM} (y_i|y_1, \dots, y_{i-1}, x) $$

 

수식에서 $log$를 취하여 기존 수식에서 결합 확률을 곱하는 형태를 각 항을 더하는 식으로 만들 수 있으며, 각 time step에서의 확률에 $\log$를 취한 값을 더하는 단조증가 함수 형태의 수식을 띠게 된다.

 

Beam search 모델에서는 매 time step 마다 score가 가장 높은 $k$개의 후보를 고려하므로 항상 globally optimal solution을 보장할 수는 없지만 brute force 접근법보다는 상대적으로 효율적인 모습을 보여준다.

 

 

 

 

 

기존 seq2seq 모델처럼 greedy decoding 방법을 사용하면 모델은 $\text{}$ token이 예측 단어로 나올 때까지 예측 문장을 생성하지만, beam search decoding에서는 각기 다른 가설마다 다른 time step에서 $\text{}$ token을 만들게 된다.

만일 어떤 가설에서 특정 time step에서 $\text{}$ token을 예측 단어로 생성하면, 그 가설에 관한 예측 생성은 그만두고 예측 문장 결과를 임시로 저장한 후 남아 있는 다른 가설에 관한 후보를 가지고 $\text{}$ token을 생성할 때까지 decoding을 진행해 간다.

 

모델의 decoding 과정은 사전에 정의한 특정 time step에 도달할 때까지 수행할 수도 있고, 아니면 최소 몇 개 이상의 가설에 관해 $\text{}$ token을 만들 때까지 수행하는 방법이 있다.

이처럼 정해진 조건을 만족할 때까지 decoding 과정을 완료하면 예측 문장을 완성한 가설에 관하여 가장 높은 확률을 지닌 가설을 최종 예측 문장으로 택한다.

 

 

 

 

$$ \text{score}(y_1, \dots, y_t) = \sum_{i=1}^t \log P_{LM} (y_i|y_1, \dots, y_{i-1}, x) $$

 

그러나 위의 수식에서 한 가지 문제가 있는데, 바로 예측 문장의 길이 $t$가 길어질수록 일반적으로 낮은 score를 갖게 된다는 것이다.

각 가설이 예측한 문장의 길이는 다를 수 있는데, 어떤 한 가설의 예측 문장 결과가 좋음에도 불구하고 문장의 길이가 긴 이유로 인해 확률이 낮게 나와 이를 택하지 않는다면 문제가 발생할 수 있다.

실제로 확률 값은 0에서 1 사이의 값을 지니고, 여기에 $\log$를 취할 경우 0 이하의 값을 갖게 되므로 time step이 길어질수록 score의 음의 절댓값이 커진다는 것을 알 수 있다.

이를 위해 위의 수식을 가설의 예측 문장 길이인 $t$로 나누어서 정규화해주는 작업을 거치는 것이 필요하다.

 

$$ \text{score}_{\text{Norm}}(y_1, \dots, y_t) = \frac{1}{t}\sum_{i=1}^t \log P_{LM} (y_i|y_1, \dots, y_{i-1}, x) $$

 

 

그래서 decoder에서 완성된 가설 예측 문장 후보에 관해 $\text{score}_{\text{Norm}}$ 값이 가장 큰 모델을 최종적인 예측 문장으로 고르며, 실제 예측해야 할 GT와의 오차가 줄어드는 방향으로 학습을 계속 진행해 가는 방법이 바로 beam search이다.

 

 

 

 

BLEU Score

 

 

생성 문장 평가 지표

 

Seq2seq 등 자연어 처리를 통해 어떠한 target 문장을 생성하는 모델을 학습할 때는 특정 time step에서 예측한 단어가 target 단어가 되도록 softmax loss에서 최대 확률을 갖는 단어가 target 단어가 되도록 학습을 반복한다.

 

그러나 특정 time step에서 GT에 해당되는 단어가 나오도록 모델을 학습하는 태스크를 수행한다면 어떤 다른 한 예측 단어가 끼어 들어가서 전반적으로 예측을 잘 했음에도 불구하고 문장 생성을 잘 하지 못했다고 평가될 수 있다.

이는 생성된 문장 전체를 가지고 유사도를 비교하는 것이 아니라 고정된 위치에 특정 단어가 등장해야 함을 전제로 하고 있기 때문이다.

그러므로 전체 생성된 문장을 통해 실제 생성해야 하는 문장과 얼마나 유사하게 예측했는지를 평가하는 지표가 필요하다.

 

 

$$ \text{precision} = \frac{\text{#(correct words)}}{\text{length of prediction}} $$

 

 

Precision은 위치에 상관없이 맞힌 단어의 수를 예측한 문장의 길이로 나눈 지표이다.

이는 예측된 결과가 노출되었을 때 우리가 이를 보고 실질적으로 느끼는 정확도로 해석할 수 있다.

 

 

$$ recall = \frac{\text{#(correct words)}}{\text{length of reference}} $$

 

 

Recall은 위치에 상관없이 맞힌 단어의 수를 실제 문장의 길이로 나눈 지표이다.

실제로 맞혔어야 할 결과에서 예측한 문장이 얼마나 잘 맞혔는지를 평가하는 정확도로 해석할 수 있다.

그러나 예측 문장으로 쓸모없는 많은 단어를 예측해서 운이 좋게 실제 문장에서 등장하는 단어를 맞히면 생성 문장의 품질이 좋지 않아도 recall 값이 올라가게 되는 단점이 있다.

 

 

$$ \text{F1 score} = \frac{1}{\frac{\frac{1}{\text{precision}} + \frac{1}{\text{recall}}}{2}} =\frac{\text{precision} \times\text{recall}}{\frac{1}{2}\left(\text{precision} + \text{recall}\right)} $$

 

 

이 두 가지의 지표를 모두 고려하는 방법으로써 precision과 recall의 조화 평균을 구한 F1 score를 사용할 수 있다.

조화 평균은 precision과 recall 각각의 역수를 더한 것의 평균을 구하고 이를 역수로 취한 것을 의미한다.

산술 평균 또는 기하 평균을 사용하지 않는 이유는 산술 평균, 기하 평균, 조화 평균 간의 관계를 이해해 볼 필요가 있다.

 

 

 

$$ \frac{a + b}{2} \ge \sqrt{ab} \ge \frac{2ab}{a + b} $$

 

 

 

임의의 수 $a$, $b$에 관해 조화 평균은 산술 평균과 기하 평균보다 작거나 같음을 알 수 있다.

이는 좀 더 작은 값에 많은 가중치를 주어서 가중 평균을 하는 것으로 해석할 수도 있는데, 이는 어떤 한 지표가 현격하게 좋게 나온다고 하더라도 다른 한 지표가 낮게 나오면 전반적으로 좋지 않게 예측했다고 평가하는 관점을 적용하는 것이다.

 

 

 

 

BLEU Score

 

앞서 precision과 recall은 실제 target 문장에 등장하는 단어를 잘 예측했는지를 평가하지만 그 단어의 등장 위치는 고려하지 않는다.

이러한 문제를 해결하기 위해 제안된 BLEU Score는 자연어 처리 생성 모델에서 생성된 결과의 품질 또는 정확도를 평가하는 척도이다.

 

개별 단어 관점에서 봤을 때 얼마나 공통적으로 GT와 겹치는 단어가 나왔는지를 계산하는 것뿐만이 아니라 연속된 N개의 단어 phrase가 GT와 얼마나 겹치는지인 N-gram overlap을 고려하여 평가에 반영하는 아이디어를 사용한다.

 

 

$$ \text{BLEU} = \min(1, \frac{\text{length of prediction}}{\text{length of reference}})(\prod_{i=1}^{N} \text{precision}_i)^{\frac{1}{N}} $$

 

 

위의 수식은 한 개의 단어뿐만이 아니라 두 개, 세 개 등 복수 개의 연속된 단어 phrase가 GT에서 얼마나 나왔는지를 평가하는 BLEU score이다.

여기서 BLEU score로는 recall이 아닌 precision을 사용하는데, 이는 예측으로 생성된 문장이 GT와 얼마나 유사한지를 중점적으로 평가한다고 해석할 수 있다.

Recall을 사용하면 위에서 언급한 바처럼 쓸모 없는 단어를 많이 만든 예측 문장은 품질이 좋지 않아도 recall 값이 올라가게 되어 BLEU score가 올라가게 되는데, 이를 예방하고자 BLEU score에서는 precision을 사용한다.

 

 

 

 

또한 N개의 연속된 단어의 precision의 평균을 구할 때 기하 평균을 사용했는데, 이는 잘못 예측된 경우에 좀 더 많은 가중치를 두어서 가중평균을 내리겠다는 의도가 담겨 있다.

그러나 조화 평균을 사용하지 않은 건 아마도 잘못 예측한 경우에 지나친 가중치를 부여하는 것을 막고자 하는 의도로 이해할 수 있을 것이다.

 

수식에서 $\min(1, \frac{\text{length of prediction}}{\text{length of reference}})$ 항은 GT 문장보다 짧은 문장을 예측했을 때는 그만큼 score 값을 낮추고, 더 긴 문장를 예측했을 때는 1을 곱하는 역할을 한다.

 

출처
1. 네이버 커넥트재단 부스트캠프 AI Tech NLP Track 주재걸 교수님 기초 강의