[NLP] 6. Beam Serach and BLEU score

Greedy Serach

seq2ses with attention과 같은 자연어 생성 모델은 바로 다음 단어만을 예측하는 task를 학습하고 inference시에는 다음 단어 생성하는 과정을 순차적으로 수행한다.

이 때 매 timestep 마다 가장 높은 확률을 가지는 단어 하나만을 택해서 Decoding 을 진행한다. → Greedy decoding

 

 

How to generate text: using different decoding methods for language generation with Transformers (huggingface.co)

전체적인 문장의 확률값을 보는게 아니라 근시안적으로 현재 timestep 에서 가장 좋아보이는 단어를 그때그때 선택하는 approach를 Greedy approach 라고한다.

이런 방식의 단점은 비로소 뒤늦게 앞에서 단어를 잘못생성했다는 것을 깨달았다고 하더라도 뒤로 돌아갈 수 없기 때문에 최적의 예측값이 아닐 경우도 있다는 점이다.

(the → nice (0.5) → woman (0.4) : 0.5*0.4 = 0.20)

(the → dog (0.4) → has (0.9) : 0.4*0.9=0.36)

 

 

 

Exhaustive Serach

이상적으로,  최적의 결과물을 찾기 위해서는 모든 경우의 수를 계산해보면 될것이다.

그렇게되면 vocabulary size가 $V$이고 timestep $t$라면 $V^{t}$ 가지의 경우의 수를 계산해야한다.

기하급수적으로 증가하는 경우의 수를 모두 계산하기에는 너무 많은 시간과 계산량이 필요하다.

 

 

 

Beam Serach

매 timestep마다 이 score가 가장 높은 k개의 candidate를 고려하는 것이 Beam Search의 핵심 아이디어이다.

이 방법은 모든 경우의 수를 고려하는 것보다 훨씬 효율적이다.

 

Beam size를 2라고 설정한다면 아래와 같은 과정이 진행된다.

<START>토큰에서 시작하고 그 다음 단어를 예측하게 될 때, Beam Size가 2이므로 he와 i가 candidate이다.

 

그 다음에는 현재 갖고 있는 hypothesis(k개)를 기준으로 각각의 경우에 대해 또 k개를 고려하고 그 중에서 가장 확률이 높은 단어 k개를 선택한다.
즉, $k^{2}$를 고려하더라도 다시 k개만의 hypothesis로 추리는 과정을 거친다.

 

 

위와 같은 과정을 반복적으로 거치다가 <END> token이 나오게 되면 search를 중단하게 된다.

 

그러나 예측 문장마다 sequence의 길이가 서로 다를 수 있다.
단어가 순차적으로 계속 생성되면서 기존에 있었던 log probability값에 항상 (-) 값을 더해주는 형태가 되기 때문에 결국은 단어가 점점 더 많이 생성 될수록 joint probability 값이 작은 값으로 나오게되는 문제가 존재한다.

 

서로 길이가 다른 여러 hypothesi 들 간에 좀 더 공평한 비교를 통해 가장 확률이 높은 최종 답을 뽑기 위해
각 hypothesis 별로 그것이 가지는 단어의 개수로 joint probability를 나누어서 word 당 평균 확률값으로서 각각의hypothesis에 대한 score를 부여한다.

 

 

---

 

 

Precision and Recall

seq2seq with attention 모델을 통한 기계번역과 같은 task에서 target 문장을 생성하는 경우에는 정답단어에 부여된 확률값이 최대한 커지도록 학습을 진행을 하게 된다.

 

학습이 완료된 후, 모델의 성능 혹은 그 정확도를 평가할 때는 test data에 대해 각 단어별 softmax loss 값을 계산하거나 각 단어의 분류 정확도를 계산할 수 있다.

그러나 특정 timestep에서 특정 ground-truth 단어가 나와야하는 그런 가정 하에 평가를 진행하게 되면 전체적인 문장으로 볼 때 단어를 중간에 하나 빼먹고 생성을 했다거나 추가적인 단어를 하나 더 많이 생성을 한 경우 정확한 평가가 이루어지기 어렵다.

( "I love you" 라는 문장을 생성을 해야하는데 첫 단어로서 "Oh I love you" 라는 단어를 생성을 하게되면 첫번째 timestep 에서 나와야 하는 단어는 "I" 였는데 우리는 "Oh" 라는 단어를 생성하면서 단어가 하나씩 다 밀리게 되어 어느 timestep 에서도 정답을 맞추지 못하여 정확도가 0%로 계산된다.)

→ 이는 생성된 문장 전체를 가지고 문장들을 비교하고 유사도를 평가하는 것이 아니라 고정된 위치에서 정해진 단어 하나 그 단어가 나와야 된다는 단순화된 평가방식 때문에 발생하는 문제점이다.

→ 그래서 생성하는 sequence 문장과 ground-truth 문장 전체적인 차원에서 평가를 진행을 해야할 필요가 있다.

 

 

 

• precision(정밀도)
  9개의 단어를 생성했고 그리고 이중에 word 별로 위치에 상관없이 ground-truth 문장과 실제로 겹치는 단어(초록색으로 색칠한 단어)가 몇 개 있는가를 세면 7개로 정밀도는 78%이다.
• recall(재현율)
  precision과 똑같이 겹치는 단어를 분자에 두지만 분모는 precision과 달리 reference에 존재하는 단어의 개수를 기준으로 재현율 값을 계산한다.
  reference에는 10개의 단어가 등장했기 때문에 70%의 값이 계산된다.
• F-measure
  precision 과 recall을 조화평균하여 precision과 recall 의 값 중 더 작은 값에 치중을 하는 평가지표이다.

 

 

 

BLEU Score

 

BLEU score는 개별 단어 레벨에서 봤을 때 얼마나 공통적으로 ground-truth 문장과 겹치는 단어가 나왔느냐에 대한 그 계산뿐만 아니라 연속된 두개의 단어 혹은 3개 혹은 N개의 연속된 단어(N-gram)로 봤을때에 문구 혹은 phrase가 정확하게 ground-truth와 얼마나 겹치는가를 계산해서 최종 평가에 반영한다.

 

기계번역 task에서 BLEU score는 precision를 고려한다. 

"I love this move very much"라는 ground-truth 문장이 있다고 생각해보자.

이를 한국어로 번역하는 경우에 "나는 이 영화를 많이 사랑한다" 는 ground-truth 측면에서는 very 에 해당하는 "정말" 이라는 단어 하나가 생략된 것을 알 수 있다.

그렇지만 이 단어가 생략됐다고 하더라도 이 문장이 어느 정도 충분히 좋은 정확도를 가지는 번역결과라고 볼 수 있다. 

즉, 재현율에 해당하는 ground-truth에서 하나하나 다 빠짐없이 번역을 했는가에 요소보다는 번역결과만을 보고 우리가 몸소 느낄수 있는 정확도에 해당하는 precision만을 고려하게 된다.

 

BLEU는 1-gram부터 4-gram까지 각 경우에 대해서 precision을 계산한 후 precision 을 모두 곱한 후 1/4 승을 취해준다.

즉, uni-gram, bi-gram, tri-gram, four-gram에 대해서 기하평균을 내준다.

기하평균의 의미는 4개의 서로다른 precision값을 단순히 산술평균 내는 것이 아니라 조금은 더 낮은 값에 혹은 값이 작은쪽에 더 많은 가중치를 부여하는 그런 형태로 평균값을 계산하는 방법이다.

조화평균을 쓰지 않은 것은 조화평균의 경우 크기가 작은 값에 지나치게 큰 가중치를 주는 특성 때문이다.

 

brevity penalty 항은 ground-truth 문장 길이보다 짧았을 때 짧아진 비율만큼 계산된 precision 값을 낮춰주고자 하는 역할이다.

 

brevity penalty 값은 recall의 최대값을 의미한다고 볼 수 도 있다.

reference 문장에 10개의 단어가 있고 생성한 문장의 단어가 10개라고 하면

만약 10개 단어가 모두 다 매칭이 된 이상적인 상황일 때는 100% 의 recall이 나올 것이다.

만약 예측된 문장의 단어수가 ground-truth 보다 많지만 ground-truth에 있는 단어들을 모두 다 빠짐없이 소환했다는 이상적인 경우에는 recall의 최댓값으로서 1이 나온다.

즉 , BLEU Score은 brevity penalty로 recall을 어느정도 고려한다고 볼 수 있다.