추천 모델의 평가 지표에 대해서 정리하고 있다. 1편으로 NDCG에 대해서 알아보았다.
https://steady-programming.tistory.com/96
[Recommender System] 추천 모델 평가 지표 (1) NDCG
논문 링크 (5776회 인용)추천 시스템에서 모델의 성능을 비교하기 위한 평가 지표에 대해 살펴보고자 한다. 첫번째로, 많이 쓰이는 지표 중 하나인 Normalized Discounted Cumulative Gain (NDCG)에 대해 알아
steady-programming.tistory.com
본 포스팅에서는 많이 사용하는 또 다른 지표인 mAP에 대해 알아보고자 한다.
Preliminary
mAP에 대해 알아보기 이전에 precision과 recall에 대해 알아보자. precision과 recall에 대해 얘기할 때, confusion matrix가 빠지면 섭섭하다.
precision은 pos로 예측한 것 중에 실제로 pos인 것의 비율을, recall은 실제로 pos인 것 중에 pos로 예측한 것의 비율을 뜻한다. precision을 해석하면 정확도라는 뜻인데, '모델의 정확도'로, recall은 '재현'이라는 뜻인데 실제 pos인 것을 '재현'한 것이라고 생각하면 이해하기가 쉽다.
\[ Precision = \dfrac{\text{True positive}}{\text{True positive + False positive}} \]
\[ Recall = \dfrac{\text{True positive}}{\text{True positive + False negative}} \]
추천 시스템으로 이 개념을 가져오면 어떻게 해석할 수 있을까?
- Precision: 추천한 아이템 중에 유저가 관심을 보인 아이템의 비율
- Recall: 유저가 관심을 보인 아이템 중에 추천한 아이템의 비율
positive을 유저가 관심을 보인 것으로 해석하면 된다. 여기서 관심을 보였다는 것은 보통 implicit feedback으로 구매, 클릭 등으로 판단한다.
예를 들어, 유저에게 10개의 아이템을 추천했는데 그 중에 3개의 아이템에 유저가 관심을 보였고, 실제로는 유저가 3개의 아이템 뿐만 아니라 추가로 4개의 아이템에 관심을 보였다고 하자. 그러면, 이 유저의 Precision은 3/10이고 Recall은 3/7이다.
@K
논문을 보면 @K라는 단어가 많이 등장한다. @K는 무엇을 의미할까? 기존의 precision과 recall은 positive로 분류한 샘플의 '순서'를 고려하지 않는다. 직관적으로 생각해볼 때, 분류 문제에서 precision과 recall을 사용하는데 여기서 '순서'가 중요하지 않기 때문이다. 그런데 추천 시스템에서는 어떤 아이템을 어느 순서로 추천했는지가 중요하다. 이 '순서'의 개념을 적용하기 위해서 상위 K개까지의 precision을 구하는 것이다. 예시로 살펴보자. (예시 1로 명한다.)
| Rank | Recommendation | Result | Precision @K |
| 1 | Forrest Gump | True Positive | 1/1 |
| 2 | Titanic | False Positive | 1/2 |
| 3 | Seven | False Positive | 1/3 |
| 4 | The lion king | True Positive | 2/4 |
| 5 | The Truman show | False Positive | 2/5 |
| 6 | Jaws | True Positive | 3/6 |
유저에게 6개의 아이템을 추천한 상황으로, 유저가 실제로 반응했는지는 Result 칼럼에 나와있다. 여기서 순서를 고려하지 않은 Precision은 3/6이다. 추천한 6개의 아이템 중에 3개의 아이템만 유저가 반응했기 때문이다.
이제 Precision @K을 살펴보자. K개까지의 아이템만 봤을 때의 Precision 값을 의미한다. 각 순위에 위치한 아이템마다 유저의 반응 여부가 달라지므로 @K 별로 precision 값이 다르다. 만약에 유저가 반응한 아이템이 모두 상위에 위치한다면 precision이 어떻게 변화할까? (예시 2로 명한다.)
| Rank | Recommendation | Result | Precision @K |
| 1 | Forrest Gump | True Positive | 1/1 |
| 2 | The lion king | True Positive | 2/2 |
| 3 | Jaws | True Positive | 3/3 |
| 4 | Titanic | False Positive | 3/4 |
| 5 | Seven | False Positive | 3/5 |
| 6 | The Truman show | False Positive | 3/6 |
precision이 상당히 올라가는 것을 알 수 있다. 즉, Precision @K는 어떤 아이템을 '어느 순서'로 유저에게 추천했는지를 반영하는 것이다.
AP@K
K개의 아이템을 추천하면 각 아이템별로 precision이 계산되므로 총 K개의 precision을 얻는다. 한 유저에 대한 '하나의 Precision@K'가 곧 Average Precision @K 이다. AP@K의 정의를 살펴보자.
\[ AP@K = \dfrac{1}{m} \sum^K_{i=1} \text{Precision @i} \times rel(i) \]
여기서 $rel(i)$는 해당 유저가 i번째 아이템에 반응했는지 여부를, $m$은 모든 아이템 공간에서 유저가 반응을한 아이템의 개수이다. 즉, 위의 예시에서 총 100개의 영화가 있었는데 그 중에 유저가 5개의 영화에 반응을 했다면 $m=5$인 것이다.
$m=5$로 가정하고 예시 1의 AP@K을 계산해보자.
\[ AP@K = \dfrac{1}{5} ( 1 + \dfrac{2}{4} + \dfrac{3}{6} ) = 0.4 \]
예시 2의 AP@K을 계산해보자.
\[ AP@K = \dfrac{1}{5} ( 1 + 1 + 1 ) = 0.6 \]
예시 2가 유저가 반응한 아이템을 더 상위에 추천했고 그 결과가 더 높은 AP@K로 이어진다. 즉, 다시 말해서 동일하게 유저가 반응하는 아이템을 추천하는 경우는, 해당 아이템을 더 상위에 추천할수록 AP@K는 높아지는 것이다.
그렇다면 유저가 반응하는 아이템을 더 적게 추천하는 경우는 어떨까? 아래 예시를 보자. (예시 3으로 명한다.)
| Rank | Recommendation | Result | Precision @K |
| 1 | Forrest Gump | False Positive | 0 |
| 2 | Titanic | False Positive | 0 |
| 3 | Seven | False Positive | 0 |
| 4 | The lion king | True Positive | 1/4 |
| 5 | The Truman show | False Positive | 1/5 |
| 6 | Jaws | True Positive | 2/6 |
예시 1에 비해서 예시 3은 첫번째 아이템을 맞추지 못했다고 가정해보았다. 예시 3의 AP@K는 아래와 같다.
\[ AP@K = \dfrac{1}{5} (1/4 + 2/6) = 0.11 \]
예시 1의 AP@K는 0.4이었는데, 확실히 낮아진 것을 확인할 수 있다. 즉, AP@K는 유저가 반응하는 아이템의 수가 추천하는 K개의 아이템에 많이 포함될수록 그 값이 높아지는 것이다.
정리하면 AP@K는 아래의 경우에 reward을 준다.
- 유저가 반응하는 아이템의 수가 추천하는 K개의 아이템에 더 많이 포함될수록 그 값이 높다.
- 유저가 반응하는 아이템의 수가 동일하다면 더 상위로 추천할수록 그 값이 높다.
Mean Average Precision @K
각 유저별로 K개의 아이템을 추천하면 각 유저별로 AP@K가 계산될 것이다. 이 유저들의 AP@K 평균이 mAP@K이다.
\[ mAP@K = \dfrac{1}{U} \sum^U_{i=1} \text{AP@K}_i \]
Recall @K ?
여태까지 precision 관점에서 mAP@K에 대해 상세하게 알아보았다. 이쯤에서 드는 생각이, precision과 recall은 쌍으로 같이 다니는데, recall @K도 자주 사용하는지 여부가 궁금해졌다. Mean Average Recall @K (mAR@K)는 mAP@K 공식에서 precision 대신 recall을 넣어주면 된다. 논문을 보면.. mAR@K보다는 mAP@K로 결과를 보고하는 경우가 더 많이 보이긴 하다. 아마도 precision은 틀린 예측을 하면 그 값이 작아지지만 (FP가 커지므로) recall은 영향을 받지 않기 때문에 (분모가 TP+FN) 그런거 아닐까? 라는 생각이 든다... (정확하지는 않아서 댓글로 의견을 주시면 좋을 것 같다.)
Code
이제 코드를 살펴보자. 기본적인 구조는 implicit library을 참고하였다. 코드는 아래 링크에 올려두었다.
https://github.com/bohyunshin/recommender/blob/master/recommender/tools/evaluation.py
recommender/recommender/tools/evaluation.py at master · bohyunshin/recommender
Implementation of various recommender algorithm. Contribute to bohyunshin/recommender development by creating an account on GitHub.
github.com
import numpy as np
from scipy.sparse import coo_matrix, csr_matrix
from tqdm.auto import tqdm
from collections import defaultdict
from .utils import check_random_state
def ranking_metrics_at_k(model, test_user_items, K=10,
show_progress=True, num_threads=1):
""" Calculates ranking metrics for a given trained model
Parameters
----------
model : RecommenderBase
The fitted recommendation model to test
test_user_items : csr_matrix
Sparse matrix of user by item that contains withheld elements to
test on
K : int
Number of items to test on
show_progress : bool, optional
Whether to show a progress bar
num_threads : int, optional
The number of threads to use for testing. Specifying 0 means to default
to the number of cores on the machine. Note: aside from the ALS and BPR
models, setting this to more than 1 will likely hurt performance rather than
help.
Returns
-------
float
the calculated p@k
"""
if not isinstance(test_user_items, csr_matrix):
test_user_items = test_user_items.tocsr()
users, items = test_user_items.shape
if items < K:
raise ValueError(f"K cannot be larger than number of items, got K as {K} but number of items is {items}")
# precision
relevant = 0
pr_div = 0
total = 0
# map
mean_ap = 0
ap = 0
# ndcg
cg = (1.0 / np.log2(np.arange(2, K + 2)))
cg_sum = np.cumsum(cg)
ndcg = 0
# auc
mean_auc = 0
test_indptr = test_user_items.indptr
test_indices = test_user_items.indices
batch_size = 1000
start_idx = 0
# get an array of userids that have at least one item in the test set
to_generate = np.arange(users, dtype="int32")
to_generate = to_generate[np.ediff1d(test_user_items.indptr) > 0]
progress = tqdm(total=len(to_generate), disable=not show_progress)
while start_idx < len(to_generate):
batch = to_generate[start_idx: start_idx + batch_size]
ids, _ = model.recommend(batch, N=K)
start_idx += batch_size
for batch_idx in range(len(batch)):
u = batch[batch_idx]
likes = defaultdict(int)
m = 0
for i in range(test_indptr[u], test_indptr[u+1]):
likes[test_indices[i]] = 1
m += 1
pr_div += min(K, m)
ap = 0
hit = 0
miss = 0
auc = 0
idcg = cg_sum[-1]
num_pos_items = m
num_neg_items = items - num_pos_items
for i in range(K):
if likes[ids[batch_idx, i]] == 1:
relevant += 1
hit += 1
ap += hit / (i + 1)
ndcg += cg[i] / idcg
else:
miss += 1
auc += hit
auc += ((hit + num_pos_items) / 2.0) * (num_neg_items - miss)
mean_ap += ap / min(K, m)
mean_auc += auc / (num_pos_items * num_neg_items)
total += 1
progress.update(len(batch))
progress.close()
return {
"precision": relevant / pr_div,
"map": mean_ap / total,
"ndcg": ndcg / total,
"auc": mean_auc / total
}
우선은 `defaultdict`로 `likes` 변수를 정의한다. 일반 리스트가 아닌, `defaultdict`로 변수를 지정한 이유는 이후에 연산을 빠르게 하기 위함이다. metric을 계산할 때 유저가 반응을 했는지 그 여부를 확인해야하는데 파이썬 리스트의 `find` 메써드를 이용하면 시간 복잡도가 최악의 경우 `log(n)`이기 때문에 빠르게 탐색할 수 있는 변수 타입을 선택했다. 이후에 유저가 추천한 아이템을 실제로 반응했는지 `test_user_items`에서 확인하고, mAP, ndcg의 정의에 따라서 metric을 계산한다.
Conclusion
저번 포스팅에 이어서 추천 시스템에서 많이 사용하는 metric에 대해 상세하게 알아보고 직접 코드도 구현해보았다. 확실히 개념을 짚고 코드를 보니까 이해가 훨씬 빨랐다. 필자는 개념을 단순히 휙 넘어가는 타입은 아닌 것 같다... 그래서 시간이 오래걸리긴하는데 그래도 한번 정리하고 나면 머리속에 훨씬 잘 남는 것 같은 느낌이다. ndcg, mAP가 가장 많이 사용하는 지표인 것 같고, 논문을 읽으면서 새로운 지표가 눈에 띄면 그때마다 정리할 계획이다.
댓글