논문링크
https://arxiv.org/pdf/1411.5726.pdf

Introduction

논문이 나온 시점에서 이미지에 설명하는 문제에 대해 이미지를 인간과 같은 방식으로 설명을 생성하는 관심이 생기고 있었다. 그 와 관련하여 Automatic evalution으로 Sentence evalution은 아직 어려운 분야였다. 

논문 이전의 Automatic evalution matric은 Precision 기반의 BLEU와 Recall 기반의 ROUGE가 있었다. 하지만 이러한 Metric은 Human evalution과 Automatic evalution의 Pearson correlation가 낮다고 표시된다. 이후 METEOR가 나오면서, 더 나은 Correlation을 보여주고 있지만 이미지 설명 평가를 할 수 없었다.

이미지 설명에 대해 평가를 할 수 있는 Automatic metric인 Consensus-based Image Desription Evaluation(CIDEr)에 대해 소개한다.

CIDEr의 방식은 다음과 같다.

Generated sentence의 각 n-gram을 Reference sentence에 대해 TF-IDF를 하고 평균을 통해 계산한다.

위와 같은 유사성 산출을 통해 다음 효과를 얻습니다.

• Grammaticality
• Correctness/truthfulness

다음 효과를 얻기 때문에 논문에서는 CIDEr을 제안한다.

The CIDEr Metric

Metric의 목표는 이미지 $I_i$에 대해 Candidate sentence, $c_i$가 이미지 설명 집합($I$) $S_i = \{s_{i1},..., s_{im}\}$ 에 대해 얼마나 유사한지를 통해 평가한다.

처음에는 Candidate sentence와 Reference sentence를 원래 형태로 매핑합니다("fishes", "fishing", "fished" - →  "fish") . 매핑한 후 1~4의 n-gram을 이용하여 계산합니다.

직관적으로 다음을 만족해야 한다.

Candidate sentence에서 많이 나타나는 n-gram은 적은 정보를 나타낼 수 있기 때문에 이에 대해 낮은 가중치를 주어야 한다. 

이를 위해 각 n-gram에 대해 TF-IDF 가중치 계산을 수행한다.

n-gram인 $\omega_k $에 대해 Candidate sentence인 $s_{ij}$에서 발생하는 횟수를 $h_k(s_{ij})$와 같이 표기하고, Candidate Sentence($c_i$)에 대해 $h_k(c_i)$로 표기한다. 각 n-gram인 $\omega_k$에 대한 TF-IDF 가중치 $g_k(s_{ij})$를 다음과 같이 계산한다.

$$ g_k(s_{ij}) = \frac{h_k(s_{ij})}{\sum_{ω_l \in Ω}h_l(s_{ij})}\text{log}(\frac{|I|}{\sum_{I_p\in I}min(1, \sum_qh_k(s_{pq}))}) $$

다음의 식에 대해 변수를 다시 한번 설명한다.

• $s_{ij}$ : $s_i$에 대해 $j$번째 Reference Sentence
• $h_k(s_{ij})$ : 참조 문장 $s_{ij}$에서 n-gram $\mathcal w_k$의 출연 횟수(빈도)
• $\sum_{ω_l \in Ω}h_l(s_{ij})$ : 모든 문장에서 $I$의 단어의 총합
• $\sum_{I_p\in I}min(1, \sum_qh_k(s_{pq}))$ : $I_p$에 대해서 해당하는 단어($h_k(s_{pq})$)가 있는지를 계산한다. 있다면 1, 없다면 0을 산출한다.
• $\Omega$ : 모든 n-gram
• $I$ : 모든 Sentence

$ g_k(s_{ij}) = \text{TF} \times \text{IDF} $ 와 같다. 첫째 항은 TF($\omega_k$의 빈도), 둘째 항은 IDF($\omega_k$ 의 희소성 )이다.

즉, 적게 나타난 단어에 가중치를 많이 주고 많이 나타난 단어에 가중치를 덜 주면서 $g_k(s_{ij})$를 계산한다.

다음은 길이가 n인 n-gram 대해  $\text {CIDEr}_n$ 점수는 Candidate sentence와 Reference sentence의 평균 Cosine similarity를 사용해 계산하며 Precision과 Recall을 모두 고려한다. Precision과 Recall이 고려되는 이유는 Cosine similarity를 이용해 중요한 정보를 얼마나 잘 포착하고 있는지, 그리고 불필요하거나 잘못된 정보를 얼마나 적게 포함하고 있는지를 종합적으로 평가하기 때문이다. 

$$ \text{CIDEr}_n(c_i,S_i) = \frac{1}{m}\sum_j\frac{g^n(c_i)\cdot g^n(s_{ij})}{||g^n(c_i)||||g^n(s_{ij})||} $$

여기서 $g^n(c_i)$는 길이 n의 모든 n-gram에 해당하는 $g_k(c_i)$ 벡터에 의해 형성된 벡터이고 $||g^n(c_i)||$은 벡터 $g^n(c_i)$의 크기다. 마찬가지로 $g^n(s_{ij})$에 대해서도 같다.

마지막으로, 우리는 문법적 특성뿐만 아니라 더 풍부한 의미를 포착하기 위해 더 높은 순서(길이가 긴)의 n-gram도 사용한다. 다음과 같이 다양한 길이의 n-gram의 점수를 결합한다:

$$ \text{CIDEr}(c_i,S_i) = \sum^P_{n=1}w_n\text{CIDEr}_n(c_i,S_i) $$

논문에서 균일 가중치 $w_n = \frac{1}{N}$이 가장 잘 작동한다는 것을 발견했으며, $N = 4$ 를 사용한다.

논문링크
https://aclanthology.org/P02-1040.pdf

Introduction

Machin Translation(MT)에 대해 사람의 평가는 광범위하며 비용이 많이 발생한다. 심지어 사람이 MT의 성능을 파악하는데 몇 달이 걸릴 수 있으며 매우 큰 비용의 노동력을 필요로 한다. 

그래서 저자는 다음과 같은 특징을 가진 automatic machine translation evaluation 방법을 제안한다.

• Quick
• Inexpensive
• Language-independent that correlates highly with human evaluation
• Little marginal cost per run

다음과 같은 특징을 통해 BLEU Metric이 Human Evaluation을 대체하는 Automatic Evaluation이며 대체할 수 있다고 말한다.

BLEU의 핵심 아이디어는 다음과 같습니다.

• 다양하게 Reference Sentence를 고려
• 단어 선택과 단어 순서에 대해 "legitimate differences"를 허용

다음과 같은 방식을 통해 Reference 길이 일치에 대해 가중 평균을 사용하는 BLEU Metric을 제안한다.

The BLEU Metric

Modified n-gram Precision

Metric의 핵심은 Precision 측정이다. 단순히 Reference translation과 Candidate translation을 유니그램의 출현 횟수로 계산하게 된다면, 일치하는 단어를 중복해서 세는 경우가 발생한다. 그렇게 된다면 비현실적이지만 Example 1에서와 같이 정밀도가 높은 결과를 초래할 수 있다.

Example 1

• Candidate: the the the the the the the.
• Reference 1: The cat is on the mat.
• Reference 2: There is a cat on the mat.

다음과 같은 예시에서 Precision이 매우 높은 결과(7/7)가 나온다. 이러한 문제점으로 인해 Modified $n$-gram precision을 제시한다. Modified $n$-gram precision을 계산하는 방법은 다음과 같다.

Reference translation에서 최대 몇 번 나타나는지 계산한 뒤, 다음으로 각 Cadidate translation의 단어의 총 수를 최대 참조 수로 제한한 후, 제한된 수를 더하고 단어 Reference translation의 총 수로 나눕니다

Example 1에 대한 계산
Unigram Precision : 7/7
Modified Unigram Precision : 2/7

n-gram precision은 multi-sentence test set에 대해서도 계산을 할 수 있다. 수식은 다음과 같다.

계산 방식은 다음과 같다.

1. 문장별로 n-gram count를 계산한다.
2. 문장별로 Clipped n-gram count를 계산한다.
3. 마지막 1번의 값을 2번의 값으로 나눈다.

Example 2

• Candidate : "the cat sat on the mat. the quick brown fox jumps over the lazy dog. the the the the the the"
• Reference : "a cat is sitting on the mat. a fast brown fox leaps over a lazy dog. on the mat is a cat" ​

Example 2에 대한 계산

Clipped counts:
"the cat sat on the mat" => 5
"the quick brown fox jumps over the lazy dog" => 7
"the the the the the the" => 2

Unclipped counts:
"the cat sat on the mat" => 6
"the quick brown fox jumps over the lazy dog" => 9
"the the the the the the" => 6


Modified n-gram precision: $ \frac{5+7+2}{6+9+6} ≈ 0.667$

 Modified n-gram precision은 66.7%로 계산되었으며, 이는 후보 문장들이 참조 문장들의 단어 사용 패턴을 66.7%만큼 반영하고 있다는 것을 의미한다.

Combining the modified n-gram precisions

다양한 n-gram 크기에 대한 Modified n-gram precision에 대해 각각 1 ~4 - gram에 대해 기하평균을 적용하여 계산을 한다. 그 이유는 n-gram Precision에 대하여 n에 대해 대략 지수적으로 감소하기에 각각에 대해 로그의 가중 평균을 사용한다(로그의 가중 평균은 기하평균을 사용하는 것과 동일).

산술평균과 조화평균을 사용하지 않는 이유는 각각이 일반적인 값이 아니며(산술평균을 사용하지 않는 이유) 각각이 비율이나 속도에 대한 값이 아니기 때문이다.

Sentence length

Candidate Sentence의 길이가 너무 길거나 짧아서는 안되기에 Evaluation Metric이 이를 강제해야 하며 n-gram Precision이 어느 정도 이에 대해 어느 정도 강제하고 있다.  Modified n-gram precision이 어느 정도 Penalty를 주고 있지만, 번역 길이를 강제하는 것에 대해서는 실패한다.  그에 대해서는 다음의 예시를 통해 확인할 수 있다.

Example 3

• Candidate: of the
• Reference 1: It is a guide to action that ensures that the military will forever heed Party commands.
• Reference 2: It is the guiding principle which guarantees the military forces always being under the command of the Party.
• Reference 3: It is the practical guide for the army always to heed the directions of the party.

수정된 유니그램 정밀도는 2/2이며, 수정된 바이그램 정밀도는 1/1이다.

The trouble with recall

Example 3와 같은 길이 문제를 해결하기 위해 Recall을 함께 사용했다. 하지만 BLEU는 Candidate translation에 대해 여러 Reference translation를 고려한다. Candidate translation이 Reference translation 모두 Recall 하는 것은 좋은 번역이 아니다. 다음 예시를 살펴보자

Example 4

• Candidate 1: I always invariably perpetually do.
• Candidate 2: I always do.
• Reference 1: I always do.
• Reference 2: I invariably do.
• Reference 3: I perpetually do.

첫 번째 후보는 Reference에서 더 많은 단어를 기억하지만, 두 번째 후보보다 확실히 더 나쁜 번역이다. 따라서, 모든 Reference 에 대해 단순한 Recall은 좋은 측정이 아니다. 참조 번역에 대해 동의어를 발견하고 Recall을 계산하지만 매우 복잡하다.

Sentence brevity penalty(BP)

다음과 같이 Recall에 대해 복잡하므로 논문에서는 Sentence brevity penalty를 도입한다. 간단히 말하면, Candidate($c$)의 길이가 Reference($r$)의 길이보다 적다면 Penalty를 준다. 그에 대한 식은 다음과 같다.

식을 정리하면 다음과 같다.  Candidate의 길이가 Reference의 길이보다 적다면 지수적으로 감소를 시킬 것이며, 그렇지 않다면 Penalty를 1로 고정한다.

Conclusion

여러 방법을 적용하여 다음과 같은 사항을 고려한다.

• Sentence brevity penalty(BP) :Candidate translation과 Reference translation의 길이, 단어 선택과 단어 순서에 대해 고려한다.
• Modified n-gram Precision : 원본 길이를 직접 고려하지 않고, 대신 목표 언어의 참조 번역 길이 범위를 고려한다.

정리한 식은 다음과 같다.

로그로 바꾸면 더욱 식이 간결하게 다음과 같이 바뀐다.

논문에서의 Baseline은 $N = 4$와 균일 가중치 $w_n = 1/N$을 사용한다.

오류사항이 있으면 지적부탁드립니다 :)

논문 링크
https://aclanthology.org/W05-0909.pdf

Introduction

논문이 써질 시점을 기준으로 Machin Translation(MT) 평가에 대해 Automatic Metric이  상당한 주목을 받게 되었다. 그 이유는 MT System에 대해 Metric을 사용하여 Evalution 하는 것이 두 개 국어를 할 줄 아는 사람이 Evaluation을 하는 것보다  훨씬 바르고 쉽고 저렴하기에 MT Metric에 대해 관심이 높아졌다. 하지만 여러 수식이 MT Evalution Metric이 되는 것은 아니다.  다음은 Metric에 대한 조건이다.

Metric의 조건

• 인간의 평가와 매우 높은 상관관계를 가져야 함
• MT 품질에 대해 민감해야 함
• Consistent (비슷한 Text에 대해 비슷한 Score)
• Reliable (비슷한 점수에 대해 비슷한 성능)
• General (다양한 도메인과 시나리오에서 적용 가능 해야 함)

IBM의 BLEU가 다음의 조건을 만족하는  MT Evaluation Metric의 대표적인 예이다. 하지만 BLEU는 여러 가지 단점을 가지고 있다.

Weakness in BLEU

• The Lack of Recall : BLEU는  정밀도(precision)에 기반을 둔 평가 지표라는 점을 강조하는 것으로, Recall을 직접적으로 다루지 않는다.
• Use of Higher Order N-gram : BLEU는 문법의 적절성 수준을 간접적으로 측정하기 위해 Higher Order N-gram을 사용
• Lack of Explicit Word-matching Between Translation and Reference : N-gram 은 명시적인 단어(의미 있는 단어)에 대해 matching을 요구하지 않지만 공통 기능 단어에 대해 잘못된 매칭을 계산하게 됩니다.
• Use of Geometric Averaging of N-gram : BLEU는 N-gram에 대해 기하평균(1, 2, 3, 4-gram)을 사용하게 된다. 하나가 0이 된다면 BLEU는 전체가 0이 되어서 측정이 될 수 없다. 그래서 n-gram에 대해 동등한 가중치 산술 평균을 사용한 BLEU가 더 나은 상관관계가 있다.

3번째에 대해 간단한 예시이다.

• 참조 문장: "The cat sat on the mat."
• 번역된 문장: "A cat was sitting on a mat."

이러한 매칭 방식은 특히 기능 단어들이 포함된 경우, 실제 의미 전달과 문장 구조의 정확성을 완벽하게 반영하지 못할 수 있다. 예를 들어, "on the"와 같은 기능 단어 시퀀스는 많은 문장에서 반복적으로 나타날 수 있으며, 이러한 반복이 의미 전달이나 문법적 정확성과 직접적으로 관련되지 않음에도 불구하고, BLEU 점수에서는 이를 긍정적인 매칭으로 간주할 수 있다.

The METEOR Metric

Metric for Evaluation of Translation with Explicit ORdering(METEOR)은 위에서 지적한 BLEU의 약점을 명시적으로 해결하기 위해 설계되었다. Machine Translation과 Reference Translation 사이의 명시적인 단어와 단어의 일치에 기반한 점수를 계산하여 번역을 평가한다. 만약 여러 개의 Reference Translation 주어진 경우는 각 점수를 매기고 최고 점수를 사용한다.

METEOR Metric의 Uni-gram 매핑 과정은 두 가지로 나뉘며, 이 것은 참조 문장과 생성 문장에 대해 최적 정렬을 찾아내는 과정이다.

유니그램 매핑과정

첫 번째 단계는 세 가지 모듈을 사용하여 모든 유니그램이 매핑될 수 있도록 한다.

• 정확한 모듈: 두 유니그램이 정확하게 일치할 때 이들을 매핑한다. 예를 들어, "computers"는 "computers"에 매핑되지만, "computer"에는 매핑되지 않는다.
• 포터 어간 모듈: 포터 어간제거기(Porter Stemmer)를 사용해 유니그램을 어간으로 변환한 뒤 같은 어간을 가지는 유니그램끼리 매핑합니다. 예를 들어, "computers"는 어간이 "comput"인 "computers"와 "computer" 모두에 매핑된다.
• WN 동의어 모듈: 두 유니그램이 서로 동의어일 경우 매핑한다. 이는 단어넷 같은 외부 자원을 활용하여 의미적 유사성을 기반으로 한 매핑이 가능하다.

두 번째 단계는 최적의 유니그램 매핑 부분 집합 선택한다.

$$ (pos(t_i)-pos(t_k))* (pos(r_j)-pos(r_l)) $$

pos($t_x$)는 시스템 번역 문자열에서 유니그램 $t_x$의 숫자 위치를 의미하며, pos($r_y$)는 참조 문자열에서 유니그램 $r_y$의 숫자 위치를 의미한다. 주어진 정렬에 대해, 모든 유니그램 매핑 쌍이 교차하는지 여부를 평가하고, 이 두 번째 단계에서 교차가 가장 적은 정렬이 선택한다.

결론적으로 다시 정리하자면, 매핑쌍이 가장 많은지를 선택한 후 교차가 작은 정렬을 선택하면 그에 대해서 Precision과 Recall을 계산한다.

수식 계산 과정

$$ Fmean = \frac{10PR}{R+9P} $$

다음 수식에 대해 몇 가지를 설명한다.

1. Recall에 높은 가중치를 준 이유 : BLEU의 Recall에 대해 부족한 Reward를 보완하기 위해 비율을 높게 주었다.
2. 조화평균을 사용한 이유 : 데이터셋에서 비율의 평균을 다룰 때 조화평균을 사용하기 때문이다.

$$ Penalty=0.5*(\frac{\#chunk}{\#unigrams\_matched})^3 $$

이전 Precision, Recall 그리고 Fmean은 Unigram의 일치에 대해서 계산하며, 더 긴 일치를 고려하기 위해 Penalty를 계산하기 위해서 $chunk$를 사용한다.(여기서 순서에 대해 고려함)

n-gram이 길수록 청크의 수는 줄어들며, 극단적인 경우에서 전체 시스템 번역 문자열이 참조 번역과 일치할 때는 청크가 하나만 있다. 다른 극단적인 경우, 일치가 없다면 유니그램 일치의 수만큼 많은 청크가 있습니다.

예시

• 시스템 번역 : " the president spoke to the audience"
• 참조 번역 : " the president then spoke to the audience"

두 개의 번역에 대해 두 개의 청크가 있다. “the president”와 “spoke to the audience”. 

청크의 수가 증가하면 페널티가 증가하여 최대 0.5가 되며, 청크의 수가 1로 감소함에 따라 페널티는 감소한다. 하한은 유니그램의 수에 따라 결정된다. 

산출 과정

단일 시스템 번역에 대해 METEOR는 각 참조 번역에 대해 위의 점수를 계산한 다음, 번역에 대한 점수로 가장 좋은 점수를 계산한다. 시스템에 대한 전체 METEOR 점수는 BLEU에서 수행되는 방식과 유사하게, 전체 테스트 세트에 걸쳐 누적된 집계 통계에 기반하여 계산된다.