[Recommender System] 추천 모델 평가 지표 (3) mAP, NDCG에 대한 note

추천 시스템을 평가하는데 많이 사용되는 mean average precision과 normalized discounted cumulative gain에 대해 아래 게시글에서 자세하게 살펴봤다.

https://steady-programming.tistory.com/96

[Recommender System] 추천 모델 평가 지표 (1) NDCG

https://steady-programming.tistory.com/97

[Recommender System] 추천 모델 평가 지표 (2) Mean Average Precision (mAP)

 

최근에 실험 결과를 도출하면서 @K의 값을 1, 3, 7, 10으로 늘려가며 metric 값을 비교해봤는데 그 과정에서 알게된 점 몇가지를 정리하고자 한다.

K의 값이 커질수록 mAP도 커진다.

mAP는 결국 모든 유저의 AP의 평균이므로 AP (average precision)으로 개념을 좁혀서 살펴보자. 우선 AP@K의 정의를 다시 한번 상기해보자.

 

\[ AP@K = \dfrac{1}{m}\sum_{i=1}^{K} precision@i \]

 

여기서 m은 유저가 상호작용을 한 아이템의 개수를, precision@i은 i번째에서의 precision 값을 의미한다. 이 정의를 잘 살펴보면 한 유저에 대해 AP을 계산할 때, m은 고정이라는 것이다. 그렇다면 K을 늘리는 상황에서 AP는 어떻게 변화할까? AP@K-1와 AP@K을 생각해보자. AP@K가 AP@K-1보다 precision@K 값을 더 가진다. 그런데 precision@K을 잘 생각해보자. 이 값은 0 이상, 1 이하의 범위를 가진다. 만약에 K-1번째까지, 추천한 아이템 중에 유저가 상호작용을 한 아이템이 있었다면 precision@K 값은 무조건 0보다 초과한 양의 실수 값을 가진다. 따라서 아래의 관계가 성립함을 알 수 있다.

 

\[ precision@k-1 \leq precision@k \]

 

자연스럽게 아래도 성립한다.

 

\[ AP@k-1 \leq AP@k \]

 

이 간단한 derivation을 사용해서, 학습한 모델이 잘 working 하는지, 또는 정의한 map에 실수는 없는지 확인할 수 있다. 즉, @1, 3, 7, 10과 같이 K을 늘림에 따라서 map가 어떻게 변화하는지 살펴보고, 혹시라도 그 값이 줄어든다면 뭔가 잘못됐다는 신호로 받아들이고 코드를 다시 살펴봐야 한다. 필자도 @1, 3, 7, 10의 결과를 살펴보다가 그 값이 줄어드는 것이 이상해서 map을 파이썬 코드로 작성한 부분을 다시 살펴봤는데, m이 아니라 K로 나눈 실수가 있었다는 것을 발견했다. 이 글을 읽는 독자는 이런 실수를 하지 말자.

AP을 다르게 정의하는 경우도 있다.

위에서, AP을 아래와 같이 정의한다고 언급했다.

 

\[ AP@K = \dfrac{1}{m}\sum_{i=1}^{K} precision@i \]

 

mAP을 정리한 글 중에서 유명한 글에서는 때에 따라서 이를 아래와 같이 정의할 수도 있다고 한다.

 

\[ AP@K = \dfrac{1}{min(m, K)}\sum_{i=1}^{K} precision@i \]

 

$m >> K$인 상황을 생각해보자. 너무나 active한 유저라서 이 유저가 상호작용한 아이템의 개수가 K보다 월등히 많은 상황이다. 이런 상황에서는 기존의 m으로 나누는 AP 정의를 사용한다면, AP가 심하게 작아질 수 있다. 이를 보정하기 위해 min(m, K)로 나누는 것이다.

 

이 정의를 보며 그럴 수도 있겠구나, 라는 생각을 했는데 만약 이 정의를 사용한다면 첫번째 섹션에서 언급한 mAP의 특징이 보존되지 않을 수 있겠다 라는 생각이 들었다. 그 이유는, min(m, K)로 나누는 상황에서는 K의 영향을 받는다. 따라서 K가 증가함에 따라서 나누는 수가 커질 수도 있다. 즉, K가 커질수록 AP값을 도출하는데 분모로 들어가는 값이 커지므로 AP값이 작아질 수 있다는 것이다. 일반적인 정의는 m으로 나누는 것으로 보이는데, 상황에 따라서 min(m, K)로 나누는 상황이 존재할 수 있으므로 유의해야 겠다.

K의 값이 커질수록 반드시 NDCG가 증가하는 것은 아니다.

m으로 나누는 정의에서는 K의 값이 커질수록 AP의 값이 커짐을 정의를 통해 살펴보았다. 그렇다면 NDCG의 경우는 어떨까? NDCG의 정의를 살펴보자.

 

\[ NDCG = \dfrac{DCG}{IDCG} \]

 

여기서,

 

\[ DCG = \sum_{i=1}^{K} \dfrac{rel(i)}{\log_2 (i+1)}, IDCG = \sum_{i=1}^{M} \dfrac{rel(i)}{\log_2 (i+1)} \]

 

binary relevance, 즉 rel(i)가 1 또는 0의 값을 가지는 상황을 생각했다. M은 K번째까지의 추천 아이템 중에서 유저가 상호작용한 아이템의 수이다. 여기서 K의 값이 커짐에 따라서 DCG는 증가한다. 양의 실수 값이 더해지기 때문이다. 그런데, K의 값이 커짐에 따라서 M의 값도 증가한다. 추천 아이템에서 더 낮은 순위의 아이템까지 추천할 수록 유저가 상호작용한 아이템의 수가 늘어나기 때문이다. M의 값이 증가함에 따라서, IDCG도 증가한다. 즉, NDCG에서 K의 값이 증가할 수록 DCG, IDCG의 값이 모두 증가한다. 어떤 값이 더 빨리 증가하는지에 따라서 NDCG가 커질수도, 작아질 수도 있다.

 

scikit-learn에서 구현된  ndcg를 살펴봄으로써 이 가정이 맞는지 확인해보자.

 

import numpy as np
from sklearn.metrics import ndcg_score

true_relevance = np.array([[1, 0, 0, 1, 1]])
scores = np.array([[10, 4, 8, 1, 3]])

for k in range(1, 5+1):
    ndcg_sklearn = ndcg_score(true_relevance, scores, ignore_ties=True, k=k)
    print(ndcg_sklearn)

"""
1.0
0.6131471927654585
0.46927872602275655
0.6713860725233042
0.8529278650606569
"""

 

NDCG가 감소하다가, 다시 증가함을 확인할 수 있다.

Binary relevance인 상황에서, 여전히 DCG의 최대값은 IDCG이다.

DCG, IDCG가 아래와 같이 정의되는 상황에서,

 

\[ DCG = \sum_{i=1}^{K} \dfrac{rel(i)}{\log_2 (i+1)}, IDCG = \sum_{i=1}^{M} \dfrac{rel(i)}{\log_2 (i+1)} \]

 

여전히 DCG의 최대값은 IDCG이며, 따라서 $0 \leq NDCG \leq 1$이 유지되는 것이 맞나? 라는 의문이 들었다. 유저가 상호작용을 한 아이템은 5개, K=10 개의 아이템을 추천하는 상황을 생각해보자. 가장 best 추천은 유저가 상호작용을 한 아이템 5개를 1등~5등에 추천하는 상황이다. 이때, 어느 아이템이 몇등에 있는지는 구분할 수 없다. 그냥, 5개의 아이템이 5등 안에만 있으면 된다. 이게 10 combination 5 중에서 가장 best 상황이며, 이때의 DCG 값이 즉, IDCG 이다.

 

\[ IDCG = \dfrac{1}{\log_2 2} + \dfrac{1}{\log_2 3} + \dfrac{1}{\log_2 4} + \dfrac{1}{\log_2 5} + \dfrac{1}{\log_2 6} \]

 

10 combination 5 중에서 이 값이 가장 큰 DCG일 수밖에 없다. $\dfrac{1}{\log_2 2}, \cdots, \dfrac{1}{\log_2 11}$ 중에 가장 큰 5개의 합이기 때문이다. 따라서 binary relevance인 상황에서도 여전히 $DCG \leq IDCG$ 이다.

Conclusion

mAP와 NDCG는 정말로 다시 살펴볼 때마다 그 개념이 헷갈리는 metric이다. 그만큼, 100% 이해하기가 쉽지 않고 다양한 상황에 맞춰서 커스텀하게 정의해야하는 부분도 있는 것 같다. 이 포스팅이 필자와 같이 두 metric의 개념을 헷갈리는 독자들에게 도움이 되었길 바라는 바이다.

 

참고로, mAP와 NDCG는 아래 코드에 구현했다.

https://github.com/bohyunshin/recommender/blob/master/recommender/libs/utils/evaluation.py

recommender/recommender/libs/utils/evaluation.py at master · bohyunshin/recommender

 

헷갈리는 부분은 pytest을 통해 확인했다.

https://github.com/bohyunshin/recommender/blob/master/tests/module/test_evaluation_metric.py

recommender/tests/module/test_evaluation_metric.py at master · bohyunshin/recommender