7만⁺ 개발자 양성한 ‘제주코딩베이스캠프’가 만든 부트캠프
#인공지능 

정보 검색(Information Retrieval) 평가 방법: MAP, MRR, DCG, NDCG

정보 검색 모델을 평가하는 MAP, MRR, DCG, NDCG 방법에 대해 알아보자.

2024-05-10 | 이태환

음악 스트리밍 서비스에서 사용자가 무슨 노래를 들어야 할지 모를 때, 많은 사용자들이 재생한 TOP 100 플레이리스트를 제공합니다. 이렇게 사용자의 플레이 수를 통계 내어 순위를 계산하면, 사용자의 만족도를 높일 수 있습니다.

개인화된 추천 시스템 및 정보 검색에서도 순위(랭킹) 정보를 함께 제공하여 사용자의 만족도를 평가합니다. 따라서 정보 검색 모델 및 시스템을 평가할 때, 검색 결과의 랭킹을 고려한 평가 방법들이 많이 사용됩니다. 여기서는 MRR, MAP, DCG, NDCG라는 네 가지 평가 방법에 대해 알아보겠습니다.

 

1. MAP (Mean Average Precision)

  • 개념: MAP은 여러 개의 검색 쿼리에 대한 평균 정밀도(Average Precision)의 평균값으로, 검색 시스템의 전반적인 성능을 평가하는 지표입니다.
  • 계산 방법:


1-1. 각 쿼리에 대해, 관련 음악이 나타날 때마다 해당 순위까지의정밀도를 계산합니다.

1-2. 이를 모두 더한 후, 사용자가 선호하는 음악의 총 개수(4개)로 나눠 해당 쿼리의 AP를 구합니다.

    $$ AP@5 = {1\over 4} \sum_{k=1}^{5} P(k) = {1\over 4} (1/1 + 2/3+3/4) = 0.604 $$

1-3. 모든 쿼리의 AP를 평균 내어 MAP를 계산합니다.

    $$AP@5 = {1\over 4} \sum_{k=1}^{5} P(k) = {1\over 4} (1/2+2/3+3/4) = 0.479$$

    $$MAP@5 = {1\over 2} (0.604 + 0.479) = 0.546 $$

 

  • 장점: 전체 검색 결과의 품질을 종합적으로 평가할 수 있으며, 상위 랭킹의 음악 추천에 더 큰 가중치를 줍니다.

 

  • 단점: 계산 과정이 다소 복잡하고, 관련 문서가 검색 결과에 없는 경우 해당 쿼리의 AP가 0이 됩니다.

 

💡 MAP@K에서 K는 컷오프 파라미터이다. MAP 계산에서 사용자가 선호하는 아이템의 개수인 m이 K보다 클 수 있는가?

네, MAP@K에서 K는 사용자가 지정한 컷오프 파라미터로, 상위 K개의 검색 결과만 고려하여 MAP을 계산합니다. 사용자가 선호하는 아이템의 개수인 m이 K보다 클 수 있습니다.

예를 들어, 사용자가 선호하는 아이템이 10개(m=10)이고, MAP@5를 계산한다고 가정해 보겠습니다. 이 경우, 상위 5개의 검색 결과만 고려하여 MAP을 계산하게 됩니다. 만약 사용자가 선호하는 아이템 중 일부가 상위 5개 검색 결과에 포함되지 않는다면, 이들은 MAP@5 계산에 영향을 미치지 않게 됩니다.

따라서 m이 K보다 크다고 해서 문제가 되는 것은 아닙니다. 다만, K를 너무 작게 설정하면 사용자가 선호하는 아이템 중 상당 부분이 MAP 계산에 반영되지 않을 수 있으므로, 적절한 K 값을 선택하는 것이 중요합니다.

일반적으로 K 값은 사용자의 관심사와 검색 시스템의 특성을 고려하여 결정합니다. 예를 들어, 사용자가 상위 10개 정도의 검색 결과에 주로 관심을 가진다면 MAP@10을 사용할 수 있고, 상위 100개 검색 결과까지 고려해야 한다면 MAP@100을 사용할 수 있습니다.

 

2. MRR (Mean Reciprocal Rank)

  • 개념: MRR은 검색 결과 중 첫 번째로 나타난 관련 문서의 순위에 기반하여, 검색 시스템이 관련 문서를 얼마나 빨리 찾아내는지를 평가하는 지표입니다.
  • 계산 방법:


 

2-1. 쿼리에 대해, 첫 번째 정답 추천결과의 역순위, RR을 구한다.

    $$ RR = {1 \over rank} $$

2-2. 이를 모든 쿼리에 대해 평균을 냅니다.

    $$ MRR = {1 \over U} \sum_{u=1}^{U} {1 \over rank_{i}} = {1 \over 2} (1+0.5) = 0.75 $$

 

  • 장점: 간단하고 직관적인 평가 방법으로, 검색 결과의 최상위 문서에 중점을 둡니다.

 

  • 단점: 첫 번째 관련 문서 이후의 랭킹은 고려하지 않으므로, 전체 검색 결과의 품질 평가에는 제한적일 수 있습니다.

 

3. DCG와 NDCG (Discounted Cumulative Gain & Normalized DCG)

  • 개념:
    • DCG는 검색 결과의 관련성과 순위를 모두 고려하여 검색 품질을 평가하는 방법입니다.
    • NDCG는 DCG를 정규화한 값으로, 쿼리 간 비교를 가능하게 합니다.

 

💡 DCG는 추천 결과가 정답에 점수(Gain)을 매기고 합산한 CG에서 하위에 추천된 정답 결과에 더 적은 Gain 값을 주어, 상단에 정확한 추천이 되도록 평가하는 방식

    $$ CG@K = \sum_{k=1}^{K} G_i $$

 

3-1. 각 추천 결과에 대해 관련성 점수를 부여합니다. (0-4점 등)

3-2. 각 추천 결과의 관련성 점수에 $log_2 i$를 나누어 후순위로 추천된 음악의 관련성 점수를 깎아서 합산한 DCG를 계산합니다.

    $$ DCG@5 = rel_{1} + \sum_{i=2}^{5} {rel_i \over log_{2}(i+1)} $$

    $$ = 4 + {2 \over log_2 4} + {3 \over log_2 5}+ {1 \over log_2 6}= 4+1 +1.29 + 0.39= 6.68 $$

💡 $rel_i$: $i$ 번째 문서의 관련성 점수

3-3. 이상적인 DCG(IDCG)를 계산합니다. (관련성 점수가 높은 순으로 추천됐을 때의 DCG)계산 방법:

    $$ IDGC@5= 4 +{4 \over log_2 3}+ {3 \over log_2 4} + {2 \over log_2 5} +{1 \over log_2 6} \\ = 4+2.52 +1.5 +0.86 + 0.39= 9.27 $$

3-4. NDCG = DCG / IDCG로 정규화합니다.

    $$ NDCG@5 = {DCG@5 \over IDCG@5} = {6.29 \over 8.88} = 0.721 $$

 

💡 NDCG에서 rel은 어떻게 구할까요?

NDCG에서 rel(relevance)은 각 문서의 관련성 점수를 나타내며, 일반적으로 0부터 4까지의 정수로 표현됩니다. rel 값을 결정하는 방법은 다음과 같이 다양합니다:

  1. 사용자 설문조사
  2. 전문가 평가
  3. 클릭 데이터 분석
  4. 기계학습 모델

rel 값을 적절하게 부여하는 것이 NDCG 평가의 핵심이며, 이를 기반으로 DCG와 NDCG를 계산하여 검색 시스템의 성능을 평가합니다.

 

  • 장점:
    • DCG는 관련성과 순위를 모두 고려하여 검색 품질을 평가할 수 있으며, 상위 랭킹의 문서에 더 큰 가중치를 부여합니다.
    • NDCG는 DCG의 장점을 그대로 가지면서, 쿼리 간 비교가 가능해집니다.

 

  • 단점:
    • DCG는 서로 다른 쿼리 간 비교가 어려울 수 있으며, 절대적인 평가 지표로 사용하기에는 제한이 있습니다.
    • NDCG는 관련성 점수 부여 과정에서 주관성이 개입될 수 있으며, 계산 과정이 상대적으로 복잡합니다.

 

 💡 NDCG는 MRR과 MAP에 비해 다음과 같은 점에서 개선되었습니다.

  1. 관련성 점수를 고려하여 관련 정도의 차이를 반영합니다.
  2. DCG를 통해 상위 랭킹 문서에 더 큰 가중치를 부여하여 사용자 중심적인 평가가 가능합니다.
  3. 정규화를 통해 서로 다른 쿼리 간의 비교가 가능해집니다.
  4. 관련성의 다양한 레벨을 지원하여 보다 세밀한 평가가 가능합니다.

이러한 장점들로 인해 NDCG는 MRR이나 MAP에 비해 정교하고 사용자 중심적인 평가 척도라고 할 수 있습니다.

 

이상으로 MRR, MAP, DCG, NDCG에 대해 알아보았습니다. 각 평가 방법은 저마다의 장단점을 가지고 있으므로, 정보 검색 시스템의 특성과 평가 목적에 따라 적절한 방법을 선택하는 것이 중요합니다. 또한 객관적인 기준을 마련하고 여러 평가 방법을 함께 사용하여 검색 시스템의 성능을 다각도로 분석하는 것이 도움될 수 있습니다.

추천 블로그 : 클릭률 그리고 추천 시스템, 기술과 가치의 조화 – 모두의연구소 (modulabs.co.kr)