[NLP] Beam search decoding , BLEU score

이번 포스팅에서는 크게 두 가지 개념을 다룰 것이다.

먼저 Seq2seq with Attention 등의 자연어 생성 모델에서 test time에서 더 좋은 품질의 결과를 얻을 수 있도록 하는 기법인 Beam search decoding에 대해 알아볼 것이며, 그 과정에서 Greedy decoding과 Exhaustive decoding도 함께 볼 것이다.

그 후, 자연어 생성 모델의 정확도 지표인 BLEU score에 대해 살펴볼 것이며, 그 과정에서 Precision, Recall, F-measure도 함께 볼 것이다.

Greedy decoding

test time에서는 다음 단어를 생성하는 과정을 반복하여 순차적으로 문장을 생성한다. 매 time step마다 가장 높은 확률을 가지는 단어 하나를 택하여 decoding을 진행하며 이러한 것을 Greedy decoding이라 한다. 즉, 문장 전체를 보고 판단하는 것이 아닌, 매 time step마다 가장 좋아보이는 단어를 선택하는 것이다. Greedy decoding의 경우 아래 그림과 같은 문제가 발생할 수 있다.

현 시점에서 가장 확률이 높은 단어를 선택해나갈 때, 한 번 잘못 예측하면 잘 못 예측한 대로 다음 단어를 예측하게 된다. 점점 잘못됨을 깨닫더라도 돌아갈 수 없다. 이러한 문제를 보완하기 위한 방법이 Exhaustive search이다.

---

Exhaustive search decoding

Exhaustive search는 현 시점에서 단어를 예측할 때 다음에 순차적으로 올 단어들의 joint probability가 가장 크게되도록 하는 단어를 찾는다.

예를 들어, p(y1|x)를 예측할 때 그 때는 가장 큰 확률값을 갖지 않는 단어이더라도 p(y2|x)부터 p(yt|y1, ···, yt-1,x)의 확률이 가장 클 수 있는 단어를 예측하는 것이다.

그러나 이러한 방법을 위해서는 vabcabulary size가 V이고, time step이 t일 때, V**t만큼의 계산을 수행해야 한다.

복잡도가 너무 커지는 이 문제를 보완하기 위한 방법이 바로 Beam search이다.

---

Beam search decoding

Beam search는 위의 Greedy decoding과 Exhausitive search 두 방법을 적절하게 타협한 방식이다.
decoder의 매 time step에서 k개의 경우의 수만 고려하여 현 시점의 단어를 선택하는 기법이다. 이때 k를 beam size라고 하며 hypotheses y1, y2, ···, yt는 log 확률로 계산한다. 단조증가함수이므로 최대 확률을 갖는 값이 똑같지만 product계산이 아닌 sum계산을 하므로 연산이 수월하다.

Exhaustive search처럼 모든 경우를 다 고려하는 것이 아니기 때문에 global optimal solution을 보장하진 않지만 훨씬 더 효율적이다.


Beam search decoding이 동작하는 방식을 구체적인 예시로 살펴보자.


■ Beam size: k=2

<sos>토큰을 시작으로 단어 생성을 시작한다. k=2이므로 각 time step에서 두 가지 경우의 수를 고려한다. 0≤P≤1값을 가지는 Probability에 log를 씌우면 음수를 가진다.

두 가지 경우의 수 각각에 대하여 그 다음에 올 두 가지 단어를 고려한다. log로 인해 덧셈으로 연결되는 joint probability를 계산하여 전체 네 가지 경우로 부터 확률이 가장 큰 두 가지 경우를 선택한다.

선택된 두 가지 경우의 수 각각에 대하여 다시 그 다음에 올 두 가지 단어를 고려하고, 마찬가지로 상위 2개의 경우를 선택한다.

선택된 두 가지 경우 각각에 대해 또 다시 두 가지 경우를 고려하고, 그 결과로 부터 상위 2개의 경우를 선택하는 이 과정을 계속 반복한다.

이 예시에서는 최종적으로 <start> he hit me with a pie가 가장 큰 확률을 갖는 hypotheses로 선택된다.

위의 과정을 언제까지 반복해서 결과를 얻게 되었는 지를 살펴보자.

단순하게 매 time step에서 가장 확률이 높은 단어를 선택하는 Greedy decoding의 경우, <eos>토큰이 나오면 끝이 난다.

매 time step에서 k개의 단어를 고려하는 Beam search decoding의 경우, k개의 서로 다른 hypotheses는 서로 다른 시점에 <eos>토큰을 얻게될 것이며 먼저 <eos>토큰을 만난 hypotheses는 따로 저장해두고 남은 hypotheses들도 <eos>를 만날 때까지 beam search를 진행한다.

보통 사전에 설정한 최대 time step의 개수인 T시점에 도달하거나 k개의 hypotheses가 토큰을 가졌을 때 멈춘다.

Beam search decoding을 마치면, joint probability가 가장 높은 hypothesis로 output을 결정해야 한다. 그러나 이 때 한 가지 문제점이 발생한다.

hypotheses마다 setence를 구성하는 word의 개수가 다를 수 있으며, 그러한 경우 word의 개수가 많은 hypotheses가 더 작은 score를 가지게 된다. 각 단어마다 log를 취한 확률값은 음수로 나오기 때문에 그 값을 더한 joint probability값이 줄어들기 때문이다.

이러한 문제를 극복하기 위해 다음과 같이 joint probability에 단어의 개수를 나누어 normalize한 후 score를 비교한다. 아래 수식에서 t는 time step, 즉 단어의 길이를 뜻한다.

---

BLEU score는 자연어 생성 모델의 품질 및 결과의 정확도를 평가하는 지표이다. BLEU score를 보기 전에 precision과 recall에 대해 짚어보자.

Precision & Recall

Precision과 Recall도 결과의 정확도를 평가하는 지표이다. 아래의 예시에 대한 precision과 recall을 살펴보자.

precision의 경우, 예측 결과인 prediction에서 reference와 같은 word의 개수를 predicton의 전체 word 개수로 나눈다.

recall의 경우, 예측 결과인 predicion에서 reference와 같은 word의 개수를 reference의 전체 word 개수로 나눈다. precision과 달리 reference에 포함된 단어를 모두 잘 예측했는지에 대한 정보까지 체크한 것이다.

위의 두 가지 지표는 차이가 꽤 있으므로 이를 혼합하여 사용하는 지표가 F-measure이다. 혼합하기 위해 두 지표의 평균값을 취하는데, 이때 평균은 산술평균, 기하평균, 조화평균 중 조화평균에 해당한다.

산술평균, 기하평균, 조화평균을 구하는 식은 아래와 같으며, 조화평균을 내분하면 작은 값에 더 큰 가중치를 부여하는 방식임을 알 수 있다.

위의 세 가지 지표인 Precision, Recall, F-measure은 자연어 생성 모델의 결과를 평가하는 데 있어 큰 결점이 있는데 바로다음과 같다.

model2의 prediction을 보면, reference에 있는 모든 단어를 포함하고 있으며, 그 길이도 일치하기 때문에 세 가지 지표 모두에서 정확도 100%가 나온다. 그러나 문법적으로 정확하지 않은 잘못 예측한 문장이며, 평가 지표들이 순서를 고려하지 못하고 있음을 알 수 있다.

이러한 문제점을 보완하기 위해 나온 지표가 BLEU score이다.

---

BLEU (Bilingual Language Evaluation Understudy)

기계 번역에서 자주 사요되는 BLEU score는 위에서 다룬 세 가지 지표와 달리 예측 문장과 정답 문장을 한 단어씩 1:1비교만 하지 않고 n개의 연속된 단어를 비교하여 순서를 고려한다.

계산할 때는 recall이 아닌 precision방식을 사용한다. word의 개수가 일치하지 않더라고 전체적인 의미를 얼마나 적절하게 번역했는 지를 평가하는 것에 초점을 두기 때문이다.

BLEU의 수식을 보면 다음과 같다. 1-gram, 2-gram, 3-gram, 4-gram의 precision에 대해 기하평균을 구한 후, reference길이보다 짧은 길이를 예측하면 그 비율만큼을 곱해주어 Brevity-panalty를 부여한다. 즉, recall의 요소도 어느정도 반영하고 있음을 알 수 있다.

BLEU score를 통해 예측 결과를 평가해보자.

---

[reference]
• deeplearning.ai-Beam Search: https://youtu.be/RLWuzLLSIgw
• deeplearning.ai-Refining Beam Search: https://youtu.be/gb__z7LlN_4
• OpenNMT-beam search: https://opennmt.net/OpenNMT/translation/beam_search/
• CS224n-NMT: https://web.stanford.edu/class/cs224n/slides/cs224n-2019-lecture08-nmt.pdf
• Sequence to sequence learning with neural networks, ICML’14: https://arxiv.org/abs/1409.3215
• Effective Approaches to Attention-based Neural Machine Translation, EMNLP 2015: https://arxiv.org/abs/1508.04025