[Model/Metric] 모델 정량 평가를 위한 metric

[bohyunshin]

metric without considering near candidate filtering

mean Average Precision (mAP)

mAP는 모든 유저의 AP에 대한 평균입니다.

$mAP = \dfrac{1}{U} \sum_{u=1}^U AP_u$

AP는 각 유저별로 계산되며 아래와 같이 정의됩니다.

$AP = \dfrac{1}{m} \sum_{i=1}^{K} P(i) r(i)$

각 notation의 정의는 아래와 같습니다.

• $P(i) = precision@i$
• $r(i) = I(\text{ith item is hitted})$, 즉 binary variable
• m = 유저가 상호작용을 한 아이템의 수 (저희 데이터에서는 평점을 남긴 식당의 수)

문헌에 따라서, AP을 아래와 같이 정의하기도 합니다.

$AP = \dfrac{1}{min(m, K)} \sum_{i=1}^{K} P(i) r(i)$

$m >> K$ 인 경우(active user는 상호작용한 아이템의 수가 많음)에 $\dfrac{1}{m}$을 곱하는 AP 정의에서는 AP가 심하게 작아질 수 있기 때문에 이런 정의를 사용하기도 합니다. 본 프로젝트에서는 $\dfrac{1}{m}$의 정의를 따릅니다.

Normalized Discounted Cumulative Gain

NDCG는 모든 유저의 NDCG에 대한 평균입니다.

$NDCG = \dfrac{1}{U} \sum_{u=1}^U NDCG_u$

각 유저별로 계산되는 NDCG는 아래와 같습니다.

$NDCG_u = \dfrac{DCG_u}{IDCG_u}$

첨자를 빼고 정의하겠습니다. DCG, IDCG는 아래와 같이 정의됩니다.

$DCG = \sum_{i=1}^K \dfrac{rel(i)}{\log_2 (i+1)}$
$IDCG = \sum_{i=1}^m \dfrac{1}{\log_2 (i+1)}$

여기서 m은 유저가 상호작용한 아이템의 수 입니다. IDCG는 DCG의 최대값입니다. 즉, 추천을 가장 잘 했을 때의 DCG 값입니다.

아래의 예시를 생각해보겠습니다.

• 유저가 좋아한 아이템: [2,6,10]
• 유저에게 5개의 아이템을 추천하는 상황
• 유저에게 추천한 아이템: [2,5,6,3,1]

가장 best 추천은 유저가 좋아한 아이템 [2,6,10]을 상위 3개 아이템에 배치하는 것입니다 -> [2,6,10,*,*]
아이템에 대한 유저의 선호도가 표현되어 있지 않다면, [2,6,10,*,*] 이든, [6,10,2,*,*] 이든 동일하게 best 추천입니다.
이때의 DCG, 즉 IDCG는 아래와 같습니다.

$IDCG = \dfrac{1}{\log_2 2} + \dfrac{1}{\log_2 3} + \dfrac{1}{\log_2 4}$

유저에게 [2,5,6,3,1]의 순서로 아이템을 추천했다면, item 2,6은 잘 추천한 것이고 5,3,1은 틀리게 추천한 것입니다. 이때의 DCG는 아래와 같습니다.
5,3,1은 유저가 좋아한 아이템이 아니므로, DCG 계산에서 제외됩니다.

$DCG = \dfrac{1}{\log_2 2} + \dfrac{1}{\log_2 4}$

$DCG / IDCG$을 한 값이 이 유저에 대한 $NDCG$가 됩니다.

[bohyunshin]

metric with near candidate filtering

TBD

[bohyunshin]

metric 정의하면서 했던 생각을 여기에 함께 정리할게요.

notation

• $m$: 유저가 좋아한 아이템의 수
• $K$: 유저에게 추천할 아이템의 수

$m < K$ 인 경우

유저가 좋아한 아이템의 수보다 더 많은 아이템을 추천하는 경우입니다. 예를 들어서, $m=3, K=10$이라고 해볼게요.
위 논의에 의하면, 이 유저의 average precision은 아래와 같이 정의됩니다.

$AP = \dfrac{1}{3} \sum_i^{K} P(i) r(i)$

가장 좋은 추천은 유저가 좋아한 3개의 아이템을 추천한 10개의 아이템의 최상단, 1등, 2등, 3등에 배치하는 것입니다.
이때의 average precision을 구해보면,

$AP = \dfrac{1}{3} ( \dfrac{1}{1} + \dfrac{2}{2} + \dfrac{3}{3} ) = 1$

즉, 가장 best case에 대해서 이 유저의 AP는 1로 정의됩니다.
기존 코드에서는 $m < K$인 경우, map 또는 ndcg 계산에서 아예 제외했었습니다. 적어도 유저가 추천한 아이템의 개수만큼 선호도를 표현한 상황을 가정한 것이죠. 근데 가만히 생각해보니 굳이 이럴 필요는 없을 것 같았습니다. 위의 예시에서도 볼 수 있듯이 $m < K$인 경우도 map가 잘 정의되니까요.

$m > K$인 경우

heavy user의 경우입니다. 추천한 아이템의 개수보다 유저가 좋아한 아이템의 수가 더 많은 상황입니다.

예를 들어서, 15개의 아이템을 좋아하는 유저에게 10개의 아이템을 추천하는 상황을 생각해봅시다.
이 유저에게 할 수 있는 가장 좋은 추천은, 추천한 10개의 아이템이 모두 유저가 좋아하는 상황입니다.
이때의 AP를 계산해보면,

$AP = \dfrac{1}{15} ( \dfrac{1}{1} + \dfrac{2}{2} + \cdots + \dfrac{10}{10} ) = \dfrac{10}{15}$

$m < K$인 경우와는 다르게, AP의 값이 1이 안 됨을 확인할 수 있습니다. 정의 때문에 그런 것인데, 만약에 $\dfrac{1}{m}$이 아니라 $\dfrac{1}{min(m,K)}$을 곱해주는 상황이라면 1이 됩니다.

AP의 최대값이 1이 되는 것이 make sense하긴 한데, 어찌됐든 가장 좋은 추천일 때, AP가 최대값을 가지므로 $\dfrac{1}{m}$을 곱하는 것으로 정의하는 것도 크게 이상해보이지는 않습니다. 또한, $\dfrac{1}{min(m,K)}$을 곱하는 것으로 정의한다면 $K$가 커짐에 따라서 map가 선형적으로 증가하지 않기 때문에, 이런 특징을 보존하려면 $\dfrac{1}{m}$으로 곱해야합니다.

결론

AP을 $\dfrac{1}{m}$을 곱하는 것으로 정의하겠습니다. 또한, $m < K$인 경우도 map, ndcg 계산에 포함하도록 하겠습니다.

[ds-wook]

@bohyunshin 님

LightGBM 실험 결과 공유드립니다.
기존 코드에서는 m < K 인 경우, map 또는 ndcg 계산에서 아예 제외했었습니다. 적어도 유저가 추천한 아이템의 개수만큼 선호도를 표현한 상황을 가정한 것이죠. 근데 가만히 생각해보니 굳이 이럴 필요는 없을 것 같았습니다. 위의 예시에서도 볼 수 있듯이 m < K 인 경우도 map가 잘 정의되니까요.
라는 말을 듣고 m < K인 경우를 포함하여 계산을 했는데
Evaluation Results

K	MAP	NDCG
3	0.00083778	0.00333636
7	0.00118509	0.00674820
10	0.00116059	0.00859931
20	0.00153389	0.01459180

Evaluation Results

K	MAP	NDCG
3	0.00089996	0.00176018
7	0.00119419	0.00231575
10	0.00131165	0.00266296
20	0.00155701	0.00373966

MAP에서는 큰 차이가 없으나 NDCG에서는 차이가 매우 큽니다. 이는 먼가 m < K인 경우에 따라 영향이 있는것으로 보여집니다.
Ranker모델의 경우 MAP보단 NDCG가 중요하다고 들었는데 그럼 포함을 해야하는것이 맞지 않나라는 생각이 들었습니다.
이 부분에 대해서 생각 있으시면 저한테 말씀 부탁드립니다 :)

[bohyunshin]

@ds-wook 님, 오프라인으로 논의한 내용 여기다가 정리할게요.

저의 경우, m < K 인 유저를 포함할 때

욱님 경우와 마찬가지로 map, ndcg가 모두 감소했습니다. 다만, ndcg가 더 감소했다기보다 그냥 둘다 감소한 정도로 기억하고 있습니다.

m < K 인 유저를 포함할 때, 왜 metric이 감소할까?

• overall map, ndcg는 각 유저의 map, ndcg을 평균한 것이기 때문에 m < K 인 유저를 포함해서 overall map, ndcg가 감소했다는 것은 추가한 유저 (m < K)의 map, ndcg가 낮아서 전체적인 평균을 감소시킨 것으로 해석할 수 있습니다.
• 그러면 m < K 인 유저의 map, ndcg가 왜 낮을까 생각해보면..
  • 유저가 평점을 남긴 식당의 수 (m)가 추천 식당의 수 (K)보다 낮은 경우입니다.
  • 직관적으로 생각해보면, 유저가 평점을 남긴 식당의 수가 적기 때문에 이 식당이 K개의 추천 식당 중에서 상위에 있기가 어려울 수 있습니다.
  • 10개의 평점을 남긴 유저에게 10개의 식당을 추천해주는 상황과, 3개의 평점을 남긴 유저에게 10개의 식당을 추천해주는 상황을 생각해보면 후자의 경우가 더 어려운 경우라고 생각합니다.
  • 따라서 m < K 인 유저의 map, ndcg가 낮게 나올 수 있다고 생각합니다.
• 또한, 저희 데이터 분포 특성상 m < K 인 유저가 많을 수 있습니다.
  • 유저별로 평점을 남긴 식당의 수 분포를 생각해보면, 거의 5개 이하로 skewed 되어 있고 train / validation을 나누면 이는 더 줄어듭니다.
• 결론적으로 m < K 인 유저의 metric 값이 적고, 그 수가 많다면 overall map, ndcg가 감소하는 방향으로 영향을 줄 수 있다고 생각합니다.