[부스트캠프][WK06 / Day29] Beam Search and BLEU score

1. 강의 내용

Beam Search and BLEU score (주재걸 교수님)

1) Beam Search

Beam Search는 자연어 생성 모델에서 Test time에서 보다 좋은 품질의 생성 결과를 얻을 수 있도록 하는 기법입니다.

Greedy decoding

Greedy decoding은 Decoding 시 해당 time step에서 가장 높은 확률을 가지는 단어 하나를 선택하는 방법으로, 만약 나중에 단어를 잘못 생성한 사실을 깨달아도 예측값을 고정해 두었기 때문에 뒤로 돌아갈 수 없어 최적의 예측값을 내어주지 못하게 됩니다.

Exhaustive search

입력문장을 x, 출력문장을 y라고 했을 때 x가 주어졌을 때 y에 대한 동시사건 확률분포로 출력된 모든 단어를 고려하는 방법입니다. 이것은 Decoder의 step t개를 모두 고려해야 하기 때문에 총 $V^t$ 개의 가능한 가지 수를 다 고려해야 합니다. 그래서 경우의 수를 현실적으로 계산하기에는 너무 많은 시간과 계산량이 필요하게 됩니다.

Beam search

Beam search는 위 두가지 방법의 중간지점으로, Decoder의 step마다 가장 확률이 높은 k개의 경우의 수(hypothesis)를 고려하게 됩니다. 여기서 k는 보통 5~10을 사용합니다.

위의 식에서 최대화 하고자 하는 값은 $P_{LM}(y_1,...,y_t|x)$ (joint probability)이며, 여기에 log를 씌워주면 log 버전의 확률값들을 더한 값으로 식이 변경됩니다. 이렇게 구한 score가 가장 높은 k개의 값을 고르게 됩니다.

위의 그림은 Beam size가 2인 경우로, 가장 확률이 높은 2개의 단어를 선택하게 됩니다. 확률값은 0~1 사이의 값이 나오므로 log를 취해주면 음수가 나오지만, 어차피 단조증가 함수이기 때문에 음수 중 가장 높은 값들을 선택해 나가면 됩니다. 해당 시점에서 선택한 k개의 단어에 대해 각각의 경우에 또 k개의 단어를 선택하게 되기 때문에 일시적으로 $k^2$개의 경우를 고려하게 됩니다. 여기서 2번째 단어를 뽑는 확률값이 가장 높은 k개의 단어를 선택하며 이런 과정을 반복하여 노란색으로 표시된 단어들을 선택하게 됩니다.

 

beam search를 적용하다보면 서로 다른 시점에서 END 토큰이 발생하게 됩니다. 그래서 END 토큰이 등장한 경우의 문장은 임시로 저장하고 남은 경우에서는 마저 END 토큰이 나올 때 까지 과정을 반복합니다. 우리가 설정한 time step T에 도달하면 종료하거나, END 토큰이 나온 경우가 n개가 되면 beam search를 중단합니다. 이렇게 모여진 hypothesis 중에서 가장 높은 하나의 score(joint probability)를 가지는 값을 선택합니다. 하지만 문장의 길이가 다를 때, 상대적으로 짧은 길이의 문장이 score가 높아지므로 이를 조정해주기 위해 길이에 따라 Normalize 해주게 됩니다.

2) BLEU

Precision and Recall

NLG를 통해 target 문장을 생성하는 경우에 모델을 test할 때, 각 time step의 단어별 softmax loss를 계산하거나 아니면 각 단어의 분류 정확도를 계산할 수 있습니다. 하지만 특정 ground truth가 나와야하는 가정에서 평가를 진행하게 되면 단어의 순서가 밀리거나 하는 문제가 발생해 위치가 안맞으면 성능이 제대로 나오지 않습니다. 이 때문에 2가지 평가 방법을 생각해 냈는데, 그것이 recall과 precision 입니다.

precision(정밀도)은 예측한 문장의 단어의 개수 중 위치에 상관없이 ground truth 문장과 겹치는 단어의 개수가 몇 개 인지를 나타내는 값으로 예측된 결과가 노출되었을 때 실질적으로 느끼는 정확도이고, recall(재현율)은 분자는 precision과 같지만 분모가 reference의 단어의 개수로 검색 시스템에서 사용자가 원하는 정보 중 얼마나 많이 사용자에게 노출시켰는가에 대한 비율입니다. 위의 그림에서 두 지표의 예시를 확인할 수 있습니다. 마지막 F-measure는 recall과 precision을 조화평균한 값으로, 산술평균보다 낮은 값에 더 가중치를 주게 됩니다. 평균들의 크기를 비교하면 산술 >= 기하 >= 조화 순서입니다. 하지만 단어의 순서가 뒤죽박죽 섞여있더라도 ground truth의 단어를 모두 포함하면 1이 되기 때문에 BLEU score를 많이 사용하게 됩니다.

BLEU score

개별 단어 수준에서 ground truth와 겹치는 수준을 고려할 뿐만 아니라 연속된 N개 단어가 얼마나 겹치는가(N-gram overlab)를 평가합니다. 이렇게 N-gram을 사용하여 평가할 때 recall 보다는 precision을 사용하는데, 모델이 얼마나 빠짐없이 번역을 했는가가 중요한 것이 아니고 예측한 문장에 얼마나 정답이 들어갔는지가 중요하기 때문입니다. 여기서 N-gram은 보통 1~4까지의 값을 사용합니다.

위의 예시를 보면 N이 1~4인 경우인데, 각 경우에서 precision을 구한 후 기하평균 해줍니다. 조화평균을 사용하지 않은 이유는 낮은 값에 가중치를 많이 주기 때문입니다. 여기에 Brevity Penalty를 주는데, reference 길이보다 짧은 문장을 생성한 경우에는 짧아진 비율만큼 precision 값을 낮춰주게 됩니다. 다른 측면에서 Brevity Penalty 값은 recall의 최대값을 의미하는데, reference와 같거나 긴 길이의 문장이 생성된 경우 100%의 recall을 기대할 수 있는 상황이가 때문에 값이 1이 됩니다. 아래는 그 예시입니다.

 

---

2. 과제 수행 과정 / 결과물 정리

필수과제 4를 마무리 하였습니다.

---

3. 피어세션 정리

https://www.notion.so/1-9fcde34f0be24d5198195a2879258475
스페셜 피어세션을 진행하며 다른 조원들과 tmi를 나누며 유익한 시간을 가졌습니다. 피어세션에서는 eda한 내용을 공유하고 궁금한 점들을 질문하며 토의하였습니다.

---

4. 학습 회고

피어세션 내 데이콘 스터디와 논문리뷰, 새로 만든 팀의 논문 읽기 등이 추가되며 바빴고 앞으로 더 시간이 부족해질 것 같습니다. 놓치는 것 없이 따라가기 위해 더 노력해야 할 것 같습니다.