Beam search and BLEU

Beam search and BLEU¶

---

✅ Beam search¶

Greedy decoding¶

• Greedy decoding은 결정을 취소 할 방법이 없다.

위 그림에서 같이 문장을 영어로 번역할 때 각 단어마다 나올 확률이 가장 높은 값으로 출력이 진행된다. 이때 "a"라는 단어가 잘못 나오게 됐다면 이 방법대로면 고칠 수 없다.

Exhaustive search¶

우리가 입력 문장을 $x$라고하고 출력 문장을 $y$라고 하면 첫번째 단어인 $y_{1}$이 나타날 확률, 두 번째 단어인 $y_{2}$가 나타날 확률 등등은 위와 같이 표현할 수 있다.

여기서 우리는 $P(y|x)$의 값이 크게 만드는 것이 목적인데 순차적으로 각각의 조건부 확률의 최적값을 찾는다고 해서 $P(y|x)$가 최대가 되지 않는다. 가령 $P(y_{1}|x)$의 최대값을 선택해서 계산할 때 보다 그것보다 더 작은 값을 선택했을때 뒤에 계산되는 값들이 더 커지게 되어서 전체적인 값이 커지는 경우가 발생할 수 있기 때문이다.

그러면 우리는 가능한 모든 sequences $y$를 계산해야한다. vocabulary size가 $V$인 경우 decoder의 각 time step(t)에서 우리는 가능한 경우의 수인 $V^{t}$을 고려해야 한다. 이렇게 계산하게 되면 너무 많은 시간이 소요되게 된다.

Beam search¶

• Greedy decoding과 Exhaustive search의 중간에 있는 방법이다.
  

💡 Core idea: decoder의 매 time step마다 우리가 설정한 $k$개의 가지수를 고려한다.

• $k$는 beam size라고 한다. (보통 5~10의 값을 가진다)

가설 $y_{1},...,y_{t}$는 로그 확률의 score가 있다. 점수는 음수이며 점수가 높을 수록 좋다. 우리는 점수가 높은 가설을 찾고 각 step에서 상위 k개를 추적한다.

📌 예시¶

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

Beam size: k=2로 예를 들어 보자

가장 먼저 처음 단어의 확률 분포를 계산한다. vocabulary상의 단어중에서 확률 분포로 output이 나타난다. 여기서 확률값이 가장 높은 2개의 후보를 뽑는다. log를 취한 확률값 이므로 값이 더 큰게 확률이 높다. "he"가 확률이 더 큰 값으로 볼 수 있다.

그 다음 단계로 각 단에서 다음 단어로 k개를 선택한다. 그러면 지금 까지 $k^{2}$의 가설이 생성된다. 다음 단계를 후보의 확률 순서로 보면 "was", "hit", "got", "struck" 순서인데 여기서 우리는 후보지 k=2개를 선택해야 하므로 "was"와 "hit"를 선택하게 된다.

위 과정을 계속 진행하다 보면 위 그림의 오른쪽 결과가 나오게 된다.

Stopping criterion¶

• greedy decoding의 경우, 우리는 decode가 토큰을 예측할 때이다.
• beam search decoding의 경우, 서로 다른 경로(다른 가설)가 존재하고 그것들은 다른 time step에서 토큰을 생성한다.
  • 어느 가설이 토큰을 생성했다면, 그 가설은 완료이다.
  • 위 결과를 임시 저장공간에 저장을 하고 남은 가설들에 대해서 토큰을 생성할 때 까지 수행한다.

우리가 beam search를 할때 우리가 설정한 timestep$T$까지 수행되었거나 아니면 가설이 완료된 갯수가 우리가 설정한 최소개수 $n$에 도달하게 되면 종료한다.

우리는 여기서 위 식대로 계산을 하게 되면 문제가 발생한다. 짧은 길이의 sequence를 가진 것이 더 score값이 높을 것이고 긴 길이를 가진 sequence는 상대적으로 더 낮을 것이다. log값은 음수이므로 계속 더해지면 더 작은 값이 된다. 따라서 우리는 길이에 따라 정규화를 시켜줘야 한다.

✅ BLEU score¶

Precision and Recall¶

여기서 NLP에서 위와 같이 score를 측정하면 큰 문제가 있다. 아래 그림을 보면 그 문제를 알 수 있다.

BiLingual Evaluation Understudy(BLEU)¶

• 예측문과 정답사이에 N-gram 중복
• 1~4크기의 N-gram에 대해서 정확도 계산
• 짥은 번역의 경우 penalty부여
• 일반적으로 한 문장에 대해서가 아니라 전체 말뭉치에 대해서 계산한다.

앞서 본 예시에 대해서 BLEU score를 확인해 보자