Document Retrieval Evaluation Metrics - 2

2024.11.22 - [오블완 챌린지] - Document Retrieval Evaluation Metrics - 1

Document Retrieval Evaluation Metrics - 1

 

오늘은 어제 작성했던 Document Retrieval 에서의 평가 metric 2번째 포스트.
저번 포스트에서는 Confusion Matrix를 기반으로 하는 기본적인 IR evaluation metrics을 알아봤다.
오늘은 추가적으로 많이 사용하는 metrics인 Mean Average Precision (MAP), Normalized Discounted Cumulative Gain (NDCG), Mean Reciprocal Rank (MRR), Hit Rate에 대해 알아보자.

Mean Reciprocal Rank

우선 MRR.
Mean Reciprocal Rank는 검색된 문서 중 첫번째로 나타난 관련 문서의 역순위를 계산하여 평균하는 지표이다.
우선 Reciprocal Rank (RR)은 다음과 같이 계산된다.
$ \text{RR} = \frac{1}{\text{rank}}$
여기서 $\text{rank}$는 첫번째 관련 문서의 순위.
예를 들어 5개를 검색했는데 2번째에 관련 문서가 나왔다면 $\text{RR}$은 $\frac{1}{2}$가 되어 0.5가 되는 것.
MRR은 다음과 같이 계산된다.
$ \text{MRR} = \frac{1}{Q} \sum_{i=1}^{Q} \frac{1}{\text{rank}_i}$
$\text{Q}$는 전체 쿼리의 수이고, $ {\text{rank}_i}$는 $i$번째 쿼리의 가장 처음 관련 문서의 순위이다.
즉, 여러 쿼리에 대한 RR 값의 평균이라고 보면 되시겠다!
이 지표가 왜 필요하냐하면, 사용자들은 첫번째 검색 결과에 우선 순위를 두기 때문에 첫번째 결과에 얼마나 올바른 검색 결과가 잘 나오느냐를 나타내는 지표이기 때문이다.
하지만 위에서 설명한 것처럼 이 지표는 검색된 문서 중 관련 있는 첫번째 문서의 순위만 고려할 뿐, 다른 요소는 고려하지 않는다. 따라서 간략하게 계산하기는 좋지만, 여러 검색 결과의 순위와 중요성은 고려하지 못하기 때문에 엄청 좋은 지표는 아니라고 할 수 있다.

Mean Average Precision

다음은 MAP를 알아보자.
MAP는 Mean Average Precision이라는 이름부터 여러 쿼리에 대해서 Precision을 계산한 후에 평균을 구하는 방식으로 전체적인 검색 성능을 평가하는 지표이다. 이건 기존의 Precision@K의 문제점은 검색된 문서의 순서는 고려하지 않는다는 것을 보완한다.
5개를 검색했는데, 마지막 5번째에 관련된 문서가 검색되었다고 가정하면 사용자는 이 검색된 문서를 확인하지 못하게 될 가능성이 존재한다.
따라서, 이 지표에는 문서의 순위가 중요한 요소가 되는데, 관련된 문서가 상위에 존재할 수록 더 높은 점수를 받게 된다.

우선 Average Precision (AP)을 살펴보자.
$ \text{AP} = \frac{1}{\lvert \text{Relevant Documents} \rvert} \sum_{k=1}^{n} P(k) \cdot \text{rel}(k)$
$P(k)$는 상위 k개의 문서에 대한 $Precision@k$의 값이고,
$\text{rel}(k)$는 $k$번째 문서의 관련도(관련있는 문서는 1, 관련 없다면 0)으로 나타낸다.

그럼 MAP는? 
$ \text{MAP} = \frac{1}{Q} \sum_{q=1}^{Q} \text{AP}_q$
$Q$는 전체 쿼리의 수, $\text{AP}_q$는 쿼리 $q$에 대한  $\text{AP}$이다.
그렇다. 그냥 쿼리 개수로 AP를 평균 때렸다.
그럼 이게 어떻게 순서를 고려한다는건지 살펴보자면,
만약 실제 관련된 문서는 3개이고, 사용자는 5개의 문서를 검색한다고 가정하자.

• Case 1: O O X X X
• Case 2: X X X O O

Case 1은 관련된 문서가 1,2번째에서 검색되었고, case 2는 4,5번째에서 검색되었다.
이 때 Precision@5를 구하면 같은 값이 나오게된다. 하지만 MAP에서는?
AP를 계산할 때 $P(k)$는 $Precision@k$라고 적어놨다.
1번째 문서에 대해서는 $P(\text{First Retrieved Document})$는 $Precision@1$을 적용한다.
그럼 2번째 문서에 대해서는 $Precision@2$를 적용하게 되는 것이다.
Relevant Documents가 3이라고 가정하면,
Case 1은 5개를 검색했으니 $\text{AP@5}=\frac{1}{3}(1 + 1 + 0 + 0 + 0)=0.66$이다.
괄호 안에 3개의 뒤의 항이 0이 되는 이유는 $\text{rel}(3, 4, 5)$는 0이기 때문에 0을 곱해주었기 때문.
그럼 case 2를 보자. $\text{AP@5} = \frac{1}{3}(0 + 0 + 0 + 0.25 + 0.4) = 0.21$ 4개 중에 1개를 맞추는 4번째 문서의 $\text{Precision@4}$는 0.25, 5개 중에 2개를 맞추는 5번째 문서의 $\text{Precision@5}$는 0.4. 그리고 괄호 안 앞의 3개의 항은 $\text{rel}(1,2,3)$이 0이므로 0.
이런식으로 검색 순서마다 AP@5의 값이 차이가 나는 것이다!
그럼 MAP는? 그냥 평균이다. case 1,2의 AP@5를 쿼리 2개(case 1,2)로 평균.
즉, $\text{MAP@5}=\frac{0.66+0.21}{2}=0.435$

 

Normalized Discounted Cumulative Gain

다음은 NDCG. NDCG는 약어를 NDCG라고도 쓰고, nDCG라고도 쓰는 것 같다.
개인적으로 약어는 대문자로 쓰는 것을 선호해서 여기서는 NDCG라고 표기한다.
NDCG는 검색 결과의 순위에 따라서 가중치를 부여하면서 관련 문서의 순위 품질을 평가한다.
NDCG를 이해하기 위해서는 CG, DCG, IDCG를 천천히 알아가야한다. 휴.. 길고 긴 여정..

CG. Cumulative Gain이다. 검색 결과에서 관련성 점수의 단순한 합으로, 문서의 순위와는 관계없다.
그냥 관련 문서가 많이 검색될 수록 높은 점수를 받는 셈.

$ \text{CG} = \sum_{i=1}^{k} \text{rel}_i$
여기서 $\text{rel}_i$는 $i$번째 문서의 관련성 점수(0,1로 하거나 아니면 실제로 관련성에 따라 매겨진 값)이고,
$k$는 다들 아시다시피 평가할 검색 결과의 상위 $k$개 문서.
CG만 사용하게 되면 $precision$의 경우와 마찬가지로 문서의 순위를 고려하지 않기 때문에 이를 해결하기 위해 DCG로 넘어간다.

DCG. Discounted Cumulative Gain이다. 여기서는 검색된 문서의 순위에 따라서 가중치를 부여해서 관련성 점수를 계산하게 된다. 순위가 낮아질 수록 (아래 수식에서는 $i$가 커질수록) 해당 문서의 기여도가 낮아진다.

$ \text{DCG} = \sum_{i=1}^{k} \frac{\text{rel}_i}{\log_2(i+1)}$
여기서 $\text{log}_2(i+1)$은 순위 $i$가 클수록 분모가 커지기 때문에 해당 문서의 기여도를 감소시킨다.
따라서! 첫번째 문서가 관련된 문서일 경우에 DCG의 계산에 큰 영향을 주지만, 마지막 문서라면, 영향이 미미해진다.

IDCG. Ideal Discounted Cumulative Gain.
얘는 검색 결과가 가장 이상적으로 정렬되었다고 가정했을 때의 DCG이다.
그러니깐, 관련성이 높은 문서가 상위 순서에 모두 위치한 경우의 DCG를 의미한다고 보시면 되시겠다!
$ \text{IDCG} = \sum_{i=1}^{\lvert \text{Relevant Documents} \rvert} \frac{\text{rel}_i}{\log_2(i+1)}$
IDCG는 DCG를 정규화하는 기준점으로 작용한다. 그래서 Normalized DCG인 것!

마지막 NDCG. Normalized Discounted Cumulative Gain.
NDCG는 DCG를 IDCG로 정규화해서 검색 결과의 품질을 0~1 사이의 값으로 나타낸다.
수식은 위에서 한참 썼으니, NDCG는 간단하다.

$ \text{NDCG} = \frac{\text{DCG}}{\text{IDCG}}$
NDCG가 1이면, 검색 결과가 아주 이상적으로 정렬되었음을 의미하고, NDCG 값이 작을수록 검색 결과의 품질이 낮다고 볼 수 있다.

이것도 예시를 봐야겠지..
7개의 문서가 있다. 상위 5개의 검색 결과에 대해 $\text{rel} = [1, 0, 3, 3, 0]$라고 가정하자.
그리고, 검색되지 않은 문서들까지 합쳐서 보면 [1, 0, 3, 3, 0, 3, 0]이라고 하자.
여기서는 관련도 점수를 0,1 binary가 아니라 실제로 관련도 마다 점수가 있다고 가정한다.
지금 상황에서는 맨 뒤의 [3, 0]은 검색이 안된 상황.
NDCG@5를 구해보자!

우선 CG는 단순합이니 쉽다.
$ \text{CG@5} = 1 + 0 + 3 + 3 + 0 = 7$

DCG는 아래와 같이 계산되겠지..

$\text{DCG@5} = \frac{1}{\log_2(1+1)} + \frac{0}{\log_2(2+1)} + \frac{3}{\log_2(3+1)} + \frac{3}{\log_2(4+1)} + \frac{0}{\log_2(5+1)} $
$ = 1 + 0 + 1.5 + 1.292 + 0 = 3.792 $

그럼 IDCG를 구하려면 관련 문서가 이상적으로 정렬되었을 때니깐, 검색된 5개의 문서의 관련도가 [3, 3, 3, 1, 0] 으로 정렬된 경우를 구하면 된ㄴ다.
$ \text{IDCG@5} = \frac{3}{\log_2(1+1)} + \frac{3}{\log_2(2+1)} + \frac{3}{\log_2(3+1)} + \frac{1}{\log_2(4+1)} + \frac{0}{\log_2(5+1)} $
$= 3 + 1.892 + 1.5 + 0.431 + 0 = 6.823 $

마지막으로 NDCG! DCG를 IDCG로 나눠주면 된다.
$ \text{NDCG@5} = \frac{\text{DCG@5}}{\text{IDCG@5}} = \frac{3.792}{6.823} \approx 0.556 $

NDCG는 순위의 품질을 평가하기 때문에 검색결과에서 순위가 중요한 상황에 적합하기도 하고, 0,1 바이너리에 관한 점수말고도 실제 디테일한 관련도 점수가 있다면 평가하기에 장점이 있다. 물론 관련성 점수가 정확해야 NDCG도 정확하게 되시겠다!

 

Hit Rate

드디어 이번 포스팅의 마지막 지표 Hit Rate이다. 사실 얘는 간단하다.
HitRate@k는 상위 k개의 검색결과에 관련 문서가 하나라도 포함되는지를 확인하는 간단한 지표.
아주 단순하고 유용한 지표이다. Retrieval System의 기본적인 성능을 평가할 때 참 좋다.

 

$ \text{Hit Rate@k} = \begin{cases} 1 & \text{if } \lvert \text{Relevant Documents} \cap \text{Retrieved Documents}@k \rvert > 0 \\ 0 & \text{otherwise} \end{cases}$

 

간단한 예제로 살펴보면 5개의 문서를  검색했을 때,
검색 결과는 [A, B, C, D, E], 실제 관련 문서는 [C, F, G]라고 하자.
그럼 C가 검색결과인 [A, B, C, D, E]에 포함되었으므로, HitRate@5 = 1.
정말 간단하다.
이건 기본적인 성능평가이기 때문에 포괄적으로 여러 평가를 하기에도 부족하고,
문서 순서나 중요도를 고려하는 부분도 부족하면서도 평가할 때 빠지면 또 아쉬운 그런 친구.

이번 포스팅에서는 저번보다 복잡한 지표들을 여럿 알아보았는데,
역시 평가지표는 여러개 쓰는게 다양한 방면에서 평가하기에 좋다.
언제나 뭐가 절대적으로 좋다기보단 필요한 평가에 따라 잘 골라서 쓰는게 중요하다!!

 

후.. 수식 쓰는 건 역시 힘들었다ㅎ...
그럼 오늘도. 오블완!