http://sdsawtelle.github.io/blog/output/mean-average-precision-MAP-for-recommender-systems.html?source=post_page-----df56c6611093----------------------#Precision-and-Recall-of-Recommender-Systems

MAP(Mean Average Precision)

• 정보 검색 수행 알고리즘에서 가장 많이 사용하는 평가 지표
• 알고리즘이 item의 순위 순서를 반환할 경우, 순위 또한 맞춰야 한다.
  (추천을 순위 지정 작업처럼 취급 - 순위까지 예측)
• 사용자 추천 시스템에도 사용이 가능
  (ex. 아마존 - 어떤 아이템을 장바구니 추가 후 추가로 구매하고 싶을 품목을 보여주는 기능)

Precision and Recall

• $Precision = \frac {\text{\# of correct positve}} {\text{\# of predicted positive}}$

  • 맞춘 실제 정답 수 / 정답이라고 예측한 수
  • 1 - false positive rate

• $Recall = \frac{\text{\# of correct positve}} {\text{\# of with condition}}$

  • 맞춘 실제 정답 수 / 실제 정답 수
  • 1 - false negative rate

Precision and Recall of Recommender Systems

• 용어 정리

• recommender system precision:

  • $P = \frac{\text{\# of our recommendations that are relevant}}{\text{\# of items we recommended}}$
  • 실제로 relevant하게 추천된 아이템 수 / 추천한 아이템 수

• recommender system recall:

  • $r = \frac{\text{\# of our recommendations that are relevant}} {\text{\# of all the possible relevant items}}$
  • 실제로 relevant하게 추천된 아이템 수 / 사용자가 원하는 아이템 수(wishList? / 모든 추천 조합 수?)

Precision and Recall at Cutoff k

• $P(k), r(k)$ 계산시에 N개의 추천 중 $k$까지 잘라서 계산한다.

Average Precision

• N: 추천 시스템이 추천하는 아이템 수

• m: 사용자가 원하는 아이템 수

• $AP@N$
  $= \frac{1}{m} \sum_{k=1}^N (P(k) \text{ if } k^{th} \text{ item was relevant })$
  $= \frac{1}{m} \sum_{k=1}^N P(k) \cdot rel(k)$,
  $rel(k) = 1 \text{ (or not) } rel(k) = 0$
  (relevant. 옳은 항목에 대해서만 계산)

• $k$까지의 $P(k)$를 구함 (순위가 높을수록(먼저 나올수록) 값이 높게 측정)

• 정답이 아닌 추천을 하더라도 AP 스코어 자체가 감소하지는 않는다. (하위에 둘 경우, k까지만 자르면 됨)

The "Mean" in MAP

• 남은 모든 item($|U|$)에 대한 평균 계산
• $MAP@N = \frac{1}{|U|} \sum_{u=1}^| U|(AP@N)_u = \frac{1}{|U|} \sum_{u=1}^| U|\frac{1}{m} \sum_{k=1}^N P_u(k) \cdot rel_u(k)$

Common Variations on AP Formula

• N=5이지만, 사용자가 m=10을 원할 경우, 일반적으로 $min(m, N)$ 으로 정규화

• $AP@N = \frac{1}{min(m, N)} \sum_{k=1}^N P(k) \cdot rel(k)$

• 최종 스코어 ( $rel(k) = 0$ 인 경우 계산을 생략한다. )

  • $AP@N = \frac{1}{min(m, N)} \sum_{k=1}^N P(k) \cdot rel(k)$ $\qquad \text{ if } m \ne 0$
    $AP = 0$ $\qquad \text{ if } m = 0$

Recall 추가

$AP@N = \sum_{k=1}^N(\text{precision at } k) \cdot (\text{change in recall at } k) = \sum_{k=1}^N P(k) \Delta r(k)$

$\Delta r(k) = (k-1^{th}) \text{ to } k^{th}$

References

• http://sdsawtelle.github.io/blog/output/mean-average-precision-MAP-for-recommender-systems.html?source=post_page-----df56c6611093----------------------#Precision-and-Recall-of-Recommender-Systems