(06강) Beam Search and BLEU score

문장을 Decoding 하는데에 사용되는 대표적인 알고리즘 Beam Search에 대한 학습 번역된 문장의 평가를 위한 BLEU score에 대한 소개

1. Beam Search

1.1. Greedy Decoding

기본적인 Sequence to Sequence 모델에서의 디코딩 과정이다. Softmax를 통과하여 나온 가장 높은 확률값을 가지는 값을 예측값으로 선정하는 방법이다.

1.2. Beam Search

Greedy Decoding의 경우 [0.41, 0.39, 0.1, 0.1] 와 같이 확률 값이 나온 경우 39%의 예측값을 그냥 포기할 것이 아니라 고려해 주는 것이 좋은 디코딩 방법이 될 것이다에서 생긴 방법이다.

• 변수 K (Beam Size)를 선정한다. (후보로 선택할 갯수)

$score(y_1, ..., y_t) = log{P_{LM}(y_1, ..., y_t \mid x)} = \sum_{i=1}^{t}{logP_{LM}(y_i \mid y_i, ..., y_{i-1},x)}$

• Normalize by length

  $score(y_1, ..., y_t) =\frac{1}{t}\sum_{i=1}^{t}{logP_{LM}(y_i \mid y_i, ..., y_{i-1},x)}$

• 위와 같이 확률의 높은 순으로 K개씩 노드를 살려 다음 단어 예측을 진행한다.

• <eos>를 만난 Beam이 K개가 될 때까지 진행하고, 만들어진 K개의 후보중에 가장 높은 누적 확률을 가진 Beam을 선택하게 된다.

1.3. Length Penalty

확률의 범위는 0~1 사이의 값이다. 이는 누적하여 곱할 수록 0에 수렴하게 된다. 즉 Beam의 길이가 길수록 누적 활률의 값이 작아지게 되는데 이런점을 해소하기 위해 Length Penalty 개념이 생겼다.

$s(Y, X) = \frac{log(P(Y \mid X))}{lp(Y)} + cp(X;Y) \\ lp(Y) = \frac{(minlength+\left | Y\right |)^\alpha}{(minlength+1)^\alpha} \\ cp(X;Y) = \beta \cdot \sum_{i=1}^{\left | X \right |}{log(min(\sum_{j=1}^{\left | Y \right |}{p_{i,j}, 1.0}))}$

• 보통 $\alpha$값은 1.2 정도를 사용한다.

def _get_length_penelty(self, length, alpha=1.2, min_length=5):
    """
    Calculate length-penalty.
    because shorter sentence usually have bigger probability.
    using alpha = 1.2, min_length = 5 usually.
    """
    return ((min_length + length) / (min_length + 1)) ** alpha
    
    
new_prob = prob / _get_length_penelty(length) # new prob = prob ÷ length penalty​

2. BLEU (Bilingual Evaluation Understudy) Score

BLEU는 기계번역 결과와 사람이 직접 번역한 결과가 얼마나 유사한지 비교하여 번역에 대한 성능을 측정하는 방법이다. 측정 기준은 n-gram에 기반한다.

2.1. Precision and Recall

모델의 성능, 정확도를 판별하기 위해 분류 정확도를 계산한다. Sequence Data의 경우 단어의 일치여부와 위치까지 고려하여야 한다. 예를 들어, I love you / Oh, I love you 라는 문장이 있다면 위치가 일치하지 않아 유사도가 0이 될 것이다. 그러므로 문장의 유사도를 판별하기 위해서는 다른 측정방법이 필요할 것이다.

Reference : Half of my heart is in Havana ooh na na Predicted : Half as my heart is in Obama ooh na

$precision = \frac{numberOfCorrectWords}{lengthOfPrediction} = \frac{7}{9} = 78$

$recall = \frac{numberOfCorrectWords}{lengthOfReference} = \frac{7}{10} = 70$

$Fmeasure = \frac{precision \times recall}{\frac{1}{2}(precision + recall)} = \frac{0.78 \times 0.7}{0.5 \times (0.78 + 0.7)} = 73.78$ (조화평균)

위 계산법에 문제는 문장의 순서를 고려하지 않았다는 점이다. i go home 과 home i go 를 모두 일치한다고 보기때문이다. 이러한 이슈를 보완하기 위해 BLEU 방법이 고안되었다.

2.2. BLEU

단어의 일치정도 뿐만이 아니라 N-gram을 활용하여 단어 묶음단위를 계산하게 된다.

• N-gram overlap between machine translation output and reference sentence

• Compute precision for n-grams of size one to four

• Add brevity penalty (for too short translations)

$BLEU = min(1, \frac{lengthOfReference}{lengthOfPrediction})(\prod_{i=1}^{4}precision_i)^{\frac{1}{4}}$

• Typically computed over the entire corpus, not on single sentences

Reference

[Sooftware 머신러닝] Beam Search (빔서치)네이버 블로그 | Sooftware