Bleu
February 2022
개요
BLEU(Bilingual Evaluation Understudy)
BLEU는 PPL과는 달리 높을 수록 성능이 더 좋음을 의미합니다.
3가지 요소가 있습니다.
- n-gram을 통한 순서쌍들이 얼마나 겹치는지 측정(precision)
- 문장길이에 대한 과적합 보정(Brevity Penalty)
- 같은 단어가 연속적으로 나올때 과적합 되는 것을 보정(Clipping)
BLEU 계산 과정
번역 문제를 생각해봅시다.
영어 sentence를 모델에 넣으면 모델은 한글 sentence를 출력합니다.
그럼 그 한글 sentence가 얼마나 잘 예측된 것인지 알려면 사람이 정확히 번역한 문(true sentence)와 비교해 보면 됩니다.
1. n-gram(1~4)를 통한 순서쌍들이 얼마나 겹치는 측정(precision)
띄어쓰기 단위로 토큰화를 했을 경우
true sentence와 일치하는 토큰이 많을수록 높은 점수를 주도록 합니다.
-
예측된 sentence:
빛이 쐬는노인은완벽한어두운곳에서잠든 사람과 비교할 때강박증이심해질기회가훨씬 높았다 -
true sentence: 빛이 쐬는 사람은
완벽한어둠에서잠든 사람과 비교할 때우울증이심해질가능성이훨씬 높았다
\(1-gram\ precision: \frac{일치하는 1-gram의 \ 수 (예측된 \ sentence 중에서) }{모든 1-gram 쌍 \ (예측된 \ sentence 중에서)} = \frac{10}{14}\) \(2-gram\ precision: \frac{일치하는 2-gram의 \ 수 (예측된 \ sentence 중에서) }{모든 2-gram 쌍 \ (예측된 \ sentence 중에서)} = \frac{10}{14}\) \(3-gram\ precision: \frac{일치하는 3-gram의 \ 수 (예측된 \ sentence 중에서) }{모든 3-gram 쌍 \ (예측된 \ sentence 중에서)} = \frac{10}{14}\) \(4-gram\ precision: \frac{일치하는 4-gram의 \ 수 (예측된 \ sentence 중에서) }{모든 4-gram 쌍 \ (예측된 \ sentence 중에서)} = \frac{10}{14}\)
\[(\prod^{4}_{i=1} precision_i)^{\frac{1}{4}} = (\frac{10}{14} \times \frac{5}{13} \times \frac{2}{12} \times \frac{1}{11})^{\frac{1}{4}} = 0.254\]2. 같은 단어가 연속적으로 나올 때 과적합 되는 것을 보정(Clipping)
위 예제에서 단어 단위로 n-gram을 할 경우 보정할 것이 없지만
다음 영어의 예제에서 1-gram precision을 구하면, 예측된 문장에 중복된 단어들(the:3, more:2)이 있습니다.
많은 중복된 단어를 사용하여 높은 점수를 취하면서도 질이 낮은 문장이 되는 것을 막기 위해
중복 단어 갯수를 보정합니다.
이를 보정하기 위해 true sentence에 있는 중복되는 단어의 max count(the:2, more:1)를 고려하게 됩니다.
보정 방법은 Clipping으로 max count를 넘지 못하도록 계산합니다.
- 예측된 sentence:
The moredecompositionthe moreflavorthefood has - true sentence:
The morethemerrier I always say
3. 문장길이에 대한 과적합 보정(Brevity Penalty)
예를 들면 문장 길이가 정답보다 훨씬 짧으면서 true sentence에 포함되는 토큰으로 대부분 이루어져 있을 경우
정답과 길이 차이가 크게 나는 문장이라도 높은 점수를 얻기 때문에 이를 보정하는 것이 필요합니다.
따라서 보정 계수를 구하여 예측 sentence와 true sentence 사이의 문장 길이로 인한 점수 왜곡을 보정합니다.
-
예측된 sentence: 빛이 쐬는 노인은 완벽한 어두운곳에서 잠듬
-
true sentence: 빛이 쐬는 사람은 완벽한 어둠에서 잠든 사람과 비교할 때 우울증이 심해질 가능성이 훨씬 높았다
BLEU score
최종적으로 다음의 식으로 계산되어집니다.
-
예측된 sentence: 빛이 쐬는 노인은 완벽한 어두운곳에서 잠든 사람과 비교할 때 강박증이 심해질 기회가 훨씬 높았다
-
true sentence: 빛이 쐬는 사람은 완벽한 어둠에서 잠든 사람과 비교할 때 우울증이 심해질 가능성이 훨씬 높았다
미분가능한 BLEU의 미분
- $A$를 ref, $B$를 hyp 행렬이라고 하였을 때
- $n$: n-gram
- $s$: (문장의 길이 - $n$)
- $v$: vocab 크기
- $e$: eos 인덱스
행렬 $A,B$의 크기는 $n \times v$
상수
\[\begin{matrix} \mathbf{o}_{1 \times s} &=& \begin{bmatrix} 1 & \cdots & 1 \end{bmatrix} \\ \mathbf{e}_{1 \times s} &=& \begin{bmatrix} 1 & \cdots & 1 & 0 \cdots & 0 \end{bmatrix} \end{matrix}\]n-gram matching 계산
\[\begin{matrix} prod(A) &=& \prod_{i=1}^s A_i = A_1 A_2 \cdots A_s \\ prod(B) &=& \prod_{i=1}^s B_i = B_1 B_2 \cdots B_s \end{matrix}\] \[\begin{matrix} sum(A) &=& \mathbf{o} A \\ sum(B) &=& \mathbf{o} B \end{matrix}\] \[\begin{matrix} len_A &=& (1 - A^T_{e}) \otimes E \\ len_B &=& (1 - B^T_{e}) \otimes E \end{matrix}\] \[\begin{matrix} mask_A &=& prod(1 - (AA^T \times D)) \otimes len_A \\ mask_B &=& prod(1 - (BB^T \times D)) \otimes len_B \end{matrix}\] \[\begin{matrix} count_A &=& mask_A \otimes sum(A) \\ count_B &=& mask_B \otimes sum(B) \end{matrix}\] \[\begin{matrix} clipped &=& h.mult(v.mult(AB, count_A), \ mask_B) \\ unclipped &=& h.mult(v.mult(AB, count_B), \ mask_A) \end{matrix}\]BP를 포함한 BLEU 계산
\[\begin{matrix} hyp\_length &=& sum(mask_B) \\ ref\_length &=& sum(mask_A) \end{matrix}\] \[\begin{matrix} tp &=& sum(min(clipped, \ unclipped)) \\ tpfp &=& hyp\_length = sum(mask_B) \end{matrix}\]\(\begin{matrix} BP &=& \begin{cases} 0 & hyp\_length = 0 \\ 1 & hyp\_length > ref\_length \\ e^{1-ref\_length / hyp\_length} & hyp\_length \le ref\_length \end{cases} \\ BLEU &=& BP \cdot e^{\sum_n w_n \log{tp_n \over hyp\_length }} \\ loss_{BLEU} &=& -log(BLEU) \end{matrix}\) —
Gradient 계산
