[NLP] Beam Search, BLEU Score

🧚🏻‍♀️참고
이 포스트는 Boostcourse의 ‘자연어처리의 모든 것’을 듣고 정리한 포스트입니다.

| 출력 생성 알고리즘

Greedy decoding

문장을 생성할 때 현재 시점에서 가장 좋아 보이는 것을 그리디하게 선택하는 방법으로, 모델이 END 토큰을 생성할 때까지 decoding을 진행한다. 예측값이 틀리더라도 되돌릴 수 없으며, 현재 시점에서 가장 좋은 것을 선택하더라도 나중에는 오히려 확률이 낮을 수 있다는 한계가 존재한다.

Exhaustive Search

Exhaustive Search는 가능한 모든 시퀀스를 확인한다. 하지만 매번 vocabulary의 크기만큼 확인을 해야하다보니 수행 시간이 오래 걸린다.

Beam Search

\[score (y_1, \cdots, y_t) = logP_{LM}(y_1, \cdots, y_t | x) = \sum_{i=1}^t {logP_{LM}(y_i|y_1, \cdots, y_{i-1}, x)}\]

Greedy decoding과 Exhaustive search의 중간 정도에 해당하는 방법이다. Beam search는 가장 가능성이 높은 k개의 시퀀스만을 확인한다. 이때 확인하는 시퀀스는 가설, k는 Beam size라고 부른다. Beam size의 경우 보통 5-10 사이의 값으로 설정한다. 아무래도 K개만 확인하다보니 최적의 결과를 보장할 수는 없지만 Exhaustive search에 비해 효율적이라고 할 수 있다.

Beam search은 시점 T에 달성하거나 최소 n개의 가설이 완성될 때까지 진행한다.

최종 가설은 score들을 각자의 시점 T로 나눈 뒤 비교하여 선정한다. 계산된 score를 그대로 비교하지 않고 시점으로 나누는 이유는, Beam search의 score를 계산할 때 0-1 사이의 확률값에 log를 씌워 음수 형태로 계산하기 때문이다. 가설이 길어질수록 음수가 더 많이 더해지게 되므로 시점으로 나누어 주어 이를 보완한다.

\[score (y_1, \cdots, y_t) = \frac{1}{t} \sum_{i=1}^t {logP_{LM}(y_i|y_1, \cdots, y_{i-1}, x)}\]

| 평가 지표

Precision and Recall

\[\begin{align} precision &= \frac{correct\ words}{len\ of\ prediction} \\ recall &= \frac{correct\ words}{len\ of\ GT, reference} \\ F-measure &= \frac{precision x recall}{\frac{1}{2} (precision + recall)} \end{align}\]

Precision과 Recall은 단어의 수만으로 평가하기 때문에 순서가 다르더라도 모든 단어가 포함되어 있다면 좋은 성능을 가진다고 판단할 수 있다.

BLEU Score

BiLingual Evaluation Understudy(BLEU)는 N-gram을 이용하여 예측값과 GT의 precision을 비교하는 방법이다. 1-gram부터 4-gram까지의 Precision을 계산하고, GT에 비해 길이가 짧은 예측에 대해선 brevity penalty를 적용한다.

\[BLEU = min(1, \frac{len\ of\ prediction}{len\ of\ GT, reference})(\Pi_{i=1}^4{precision_i})^{\frac{1}{4}}\]