CIDEr-D와 METEOR

CIDEr-D와 METEOR는 모델이 수행한 캡셔닝 또는 번역의 질을 평가하는데 사용되는 메트릭이다.

CIDEr-D

CIDEr의 단점을 보완한 지표가 CIDEr-D이다. 따라서 CIDEr-D를 이해하기 위해 먼저 CIDEr을 살펴보자.

1. CIDEr : Consensus-based Image Description Evaluation for Image Caption

n-gram

우선 n-gram에 대한 개념을 확실하게 짚고 넘어갈 필요가 있다.

I love cats.

• 2-gram은 "I love" 또는 "love cats"와 같은 연속된 두 단어로 이루어진 객체를 의미한다.
• 2-grams는 {"I love", "love cats"}이라는 문장에서 가능한 모든 2-gram이 모인 집합이다.

개념

• CIDEr( Consensus-based Image Description Evaluation)은 이미지 $I_i$에 대하여 candidate sentence(생성한 문장; 이하 candis) $c_i$가 $I_i$에 대한 reference sentences(정답 문장 이하 refs)의 집합 $S_i = \{ s_{i1}, \ldots , s_{im}\}$과 얼마나 합치(consensus)하는지를 나타내는 지표이다.
• candis와 refs에 속하는 모든 단어는 우선 그것들의 stem 및 root 형태에 맵핑된다.
• $c_i$에서 n-gram으로 추출한 단어 묶음의 집합으로 $c_i$와 $s_{ij}$ 각각에 대해 TF-IDF를 계산한 뒤, 둘의 코사인 유사도를 계산한다.

구체적인 예

• 예를 들면 여러 이미지 $I_0, I_1, \ldots$를 포함하는 데이터셋이 있고, 데이터셋 안에 이미지가 $|I|$개 있다고 하자.
• 그리고, 그 중 이미지 $I_i$는 고양이가 매트 위에 앉아 있는 사진이라고 하자.
• 하이퍼파라미터 $n$은 우리가 고려하기로 마음먹은 n-gram의 최대 $n$이다.
• $\Omega$는 주어진 한 문장에서 모든 1-gram, 2-gram, …, n-gram 단어들의 집합이다.
• n-gram $\omega_k$는 $\Omega$의 $k$번째 원소이다.
• 이와 같은 상황에서, 변수를 구체적으로 다음과 같이 상정할 수 있다.

# c_i: 모델이 I_i에 대하여 생성한 문장, candidate sentence
c_i = “The cat sat on the mat.”
 
# c_i에 대하여 계산하는 경우 OMEGA와 omega_k
OMEGA = ["The", "cat", "sat", "on", "the", "mat",
"The cat", "cat sat", "sat on", "on the", "the mat"]
 
omega_0 == "The"
omega_1 == "cat"
...
omega_10 == "the mat"
 
 
# S_i: 이미지 I_i의 renfernce set
S_i = ["A cat is sitting on a mat.", "On the floor, the cat sat."]
s_i0 == "A cat is sitting on a mat."
s_i1 == "On a mat, the cat sat."
 
# s_i0에 대하여 계산하는 경우 OMEGA와 omega_k
OMEGA = ["The", "cat", "is", "sitting", "on", "a", "mat", "floor",
"A cat", "cat is", "is sitting", "sitting on", "on a", ..., "cat sat"]
...
omega_7 == "floor"
...

TF-IDF

• 여러 문서로 이루어진 문서군이 있을 때 어떤 단어가 특정 문서 내에서 얼마나 중요한(unique) 것인지를 나타내는 수치
  $$\begin{align*}\textbf{TF-IDF: } g_k\left(s_{i j}\right) &= \frac{h_k\left(s_{i j}\right)}{\sum_{\omega_l \in \Omega} h_l\left(s_{i j}\right)} \log \left(\frac{|I|}{\sum_{I_p \in I} \min \left(1, \sum_q h_k\left(s_{p q}\right)\right)}\right)\\ g_k\left(c_{i}\right) &= \frac{h_k\left(c_{i}\right)}{\sum_{\omega_l \in \Omega} h_l\left(c_{i}\right)} \log \left(\frac{|I|}{\sum_{I_p \in I} \min \left(1, h_k\left(c_p\right)\right)}\right)\end{align*}$$
• TF가 높다는 것은 그 문서(문장) 내에서 그 단어가 중요함을 뜻한다.
• IDF가 높다는 것은 전체 문서(문장)에서 그 단어가 나오는 문장이 매우 적기 때문에, 만약 그 단어를 보게 된다면 이는 매우 희귀한 것이고 따라서 높은 중요도를 줘야 함을 뜻한다.

Cosine Similarity

• $\text{CIDEr}_n$은 다음과 같이 cosine similarity의 형태로 나타내어 진다.
  $$\text{CIDEr}_n (c_i , S_i) = \frac{1}{m} \sum_j \frac{\boldsymbol{g^n}(c_i)\cdot \boldsymbol{g^n}(s_{ij})}{\left \| \boldsymbol{g^n}(c_i) \right \| \left \| \boldsymbol{g^n}(s_{ij}) \right \|}$$
  • 여기서, $\boldsymbol{g^n}(x)$는 문장 $x$에 대한 모든 $g_k(x)$ 중에서 n-grams의 각 원소에 해당하는 $g_k(x)$로 이루어진 벡터이다.
  • 예를 들면 $x=$"I love you"일 때,
    $$\boldsymbol{g^2}(x) = \left[\, g_\textrm{ I_love} (x) \quad g_\textrm{ love_you} (x) \quad g_\textrm{ you_girl} (x) \, \right ]^\top$$
• cosine similarity는 precision과 recall을 모두 고려한다는 장점이 있다.
• 최종적인 $\textrm{CIDEr}$은 다음과 같이 구한다.
  $$\textrm{CIDEr}(c_i, S_i ) = \sum_{n=1}^N w_n \textrm{CIDEr}_n (c_i , S_i)$$
• 문법적인 정합성과 더 풍부한 의미를 고려하기 위해 더 높은 n-grams를 사용한다.

2. CIDEr-D

CIDEr의 결함

• CIDEr은 stemming의 과정을 포함하는데, 이는 문장의 미묘한 의미를 훼손한다.
• candis가 바람직한 단어를 최대한 많이 포함하기 위해, 지나치게 길게 학습될 수 있다.
• candis가 바람직한 단어를 의미없이 반복하도록 학습될 수 있다.

Gameability

• CIDEr의 위와 같은 특성으로 인해, 모델에 대한 gameability(cheatability)가 존재한다.

해결책

• stemming 과정을 생략한다.
• candis의 길이와 refs의 길이 간 차이에 비례하는 Gaussian penalty를 부과한다.
• 똑같은 단어를 지나치게 반복하지 않도록 clipping을 적용한다.

수식

• 이를 모두 적용한 CIDEr-D의 수식은 다음과 같다.
  $$\begin{align*}\textrm{CIDEr-D}_n (c_i, S_{i})&= \frac{10}{m} \sum_j e^{\frac{-[l(c_i)-l(s_{ij})]^2}{2\sigma^2}} \ast \frac{\min(\boldsymbol{g^n}(c_i ),\boldsymbol{g^n}(s_{ij} )) \cdot \boldsymbol{g^n}(s_{ij} )}{\left \| \boldsymbol{g^n}(c_i ) \right \| \left \| \boldsymbol{g^n}(s_{ij} ) \right \|} \\ \textrm{CIDEr-D}(c_i , S_i ) &= \sum_{n=1}^N w_n \textrm{CIDEr-D}_n (c_i , S_i ) \end{align*}$$
• 이때 $\min$ 함수는 두 벡터 사이의 element-wise minimum을 의미한다.

---

METEOR

개요

• Metric for Evaluation of Translation with Explicit ORdering
• BLEU의 단점을 보완한 번역 문장 평가 지표

논문에서 꼽은 BLEU의 단점

• Lack of Recall: BLEU focuses on precision but doesn't account for recall, which is crucial for assessing translation quality.
• Use of Higher-Order N-grams: BLEU uses these as an indirect measure of grammaticality, but METEOR believes an explicit measure is better.
• Lack of Explicit Word-Matching: BLEU uses N-gram counts without explicit word-to-word matching, leading to incorrect "matches."
• Use of Geometric Averaging: This can result in a score of "zero" if one component N-gram score is zero, making sentence-level scores meaningless.

용어

• alignment
  • 컴퓨터 번역 문장(candis)과 인간 번역 문장(refs) 한 쌍이 주어졌을 때, METEOR은 두 문장 사이에서 alignment를 만든다.
  • alignment는 각 문장의 모든 unigram이 다른 문장의 0 또는 1개의 unigram의로 맵핑이다. 단, 두 문장이 동일할 경우 맵핑은 이루어지지 않는다.
• stage
  • alignment를 생성하는 과정을 stage라고 한다. 예를 들어, 문장 한 쌍에 대하여 한 번의 stage를 거치면 한 개의 alignment가 도출되고, 세 번의 alignment를 만들기 위해서는 세 번의 stage를 거쳐야 한다.
  • 각 stage는 여태까지 만들어낸 alignment와 중복되지 않는 새로운 alignment를 생성한다.
  • 각 stage는 두 phase로 이루어져 있다.
• phases of a stage
  • 첫 번째 phase에서 세 개의 외부 모듈로 두 번역 문장 쌍 사이에서 가능한 모든 unigram 맵핑을 탐색한다.
    • “Exact” module: 두 unigram이 정확하게 일치하는 경우에만 두 unigram을 연결한다.
    • 예) computer는 computers와 맵핑되지 못하고, 오직 computer와만 맵핑될 수 있다.
    • “porter stem” module: 두 개의 unigram이 Poter stemmer를 사용하여 형태소 분석(stemmed)된 후 동일한 경우에 매핑한다.
    • 예) computer는 computers와 computer 모두에 매핑된다.
    • “WN synonymy” module: 두 단어가 서로 유의어 관계인 경우에 맵핑된다.
  • 두 번째 phase에서는 가장 적합한 alignment를 선택한다. 이때, 위의 모든 제약을 만족하면서 mapping간 교차점(*unigram mapping cross*)이 가장 적은 alignment가 선택된다. 예컨데, 아래 두 alignment 중에서 a가 아래 b보다 더 우월하다.

Example alignment (a).

 

Example alignment (b).

METEOR score의 계산

• Final alignment가 선정되면, METEOR score를 계산한다.

Fmean의 계산

$$\begin{align*} \textrm{unigram precision: } P&=\frac{\textit{# mapping}}{\textit{# unigrams of candis}} \\ \textrm{unigram recall: } R&=\frac{\textit{# mapping}}{\textit{# unigrams of refs}} \end{align*}$$

• 같은 #mapping에 대한 비율의 평균적인 score가 필요하므로, 조화평균을 사용한다.
• 이때, $R$에 더 큰 가중치를 주어, $P$와 $9R$의 조화평균으로 Fmean을 다음과 같이 계산한다.

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

Penealty의 계산

• Fmean은 unigram의 경우만 고려하므로 unigram이 연속적으로 맵핑되는 경우에 대해 가중치를 부여할 필요가 있다.
• 이는 문장의 쌍에서 mapping의 개수 대비 chunks의 수가 많을수록 penalty를 가하는 방식으로 구현한다.

$$\textit{Penalty}=0.5 \times \left( \frac{\#\textit{ chunks}}{\#\textit{ mapping}} \right)^3$$

METEOR score의 계산

$$\textit{Score}= \textit{Fmean}\times(1- \textit{Penalty})$$