About

이번 블로그에서는 주로 정보를 순서를 지정하여(Ranked) 반환하는 경우에 사용하는 평가방법인 Mean Average Precision(MAP)을 소개하고자 한다. MAP은 예를들어 구글과 같은 검색엔진에서 검색결과가 검색의도와 관련도가 높은 순으로 잘 나열되어있는지를 평가하는 방법이다.

추천시스템은 수많은 아이템 중에 사용자가 관심을 보일만한 아이템들을 보여준며 가장 자신있는 것을 첫 번째로 보여준다는 점에서 검색엔진과 의미가 동일하다는 점을 생각하여 MAP은 추천시스템의 평가방법으로도 아주 유용하다. Amazon과 같은 전자상거래에서는 사용자가 상품을 장바구니에 담으면 그 다음으로 담을 것 같은 상품 리스트를 보여주는 것이 그 예다.

이제 MAP설명을 하기앞서, 먼저 선행되어야할 지식인 Precision, Recall에 대해서 간략히 설명하도록하겠다.

Precision and Recall

간단한 이해를 위해 이진 분류를 예로 사용하여 생각해보자. 만약 많은 사람들 중에서 이 사람은 범죄자다 아니다를 판단하는 문제라고 한다면,

$$ Precision = \frac{True\ Positive}{True\ Positive\ +\ False Positive} $$

Precision범죄자라고 판단한 사람들 중 진짜 범죄자인 사람이 몇명인가 비율을 의미한다.

$$ Recall = \frac{True\ Positive}{True\ Positive\ +\ False Negative} $$

Recall실제 범죄자들 중 범죄자라고 판단한 사람이 몇명인가 비율을 의미한다.

이 둘을 추천시스템에서는 아래처럼 해석할 수 있다.

종류 의미
Precision 우리가 추천한 아이템 중에 사용자가 정말 관심있어하는 아이템의 비율
Recall 실제로 사용자가 관심있어하는 아이템 중에 우리가 추천한 아이템의 비율

예를들어 추천시스템이 5개의 아이템을 추천했다고 가정해보자. 실제 전체 아이템 중에 사용자가 관심있어하는 아이템은 3개가 있고 그 중에 우리가 2개를 추천하는데 성공했다면

  • 우리가 추천한 아이템 개수: 5
  • 추천한 아이템 중 사용자가 관심있어하는 아이템 개수 : 2
  • 실제로 사용자가 관심있어하는 아이템 개수 : 3

이 되므로

  • Precision = 2/5
  • Recall = 2/3

이 된다.

여기서 사용자가 관심있어한 여부는 사용자가 실제로 Engage(Click, Added to cart.. etc)를 했는지 여부로 판단한다.

MAP@K에서 K는 뭘 의미하는가?

위에서 Precision과 Recall에 대해서 알아봤지만 이 두가지 평가방법은 순서를 신경쓰지 않는다는점을 알 수 있다. 하지만 위에서 설명했듯 추천시스템 평가에서는 무엇을 앞에 나열했는가가 매우 중요하다. 그래서 MAP에서는 K라는 값을 설정하게 된다. 여기서 K의 의미는 추천리스트의 어디까지만 평가할 것인가 결정하는 Index값이다. 아래의 예를 살펴보자.

Rank Recommendation Result
1 Forrest Gump Correct positive
2 Titanic False positive
3 Seven False positive
4 The lion king Correct positive
5 The Truman show False positive
6 Jaws Correct positive

위와같은 영화 추천리스트에서 만약 3번에 해당하는 Seven까지의 추천 결과를 평가한다면 K=3인 경우를 의미하며, 6번에 해당하는 Jaws까지 다 평가한다면 K=6인 MAP@K를 의미한다.

Average Precision

$$ AP@K = \frac{1}{m}\sum_{i=1}^K P(i)\bullet rel(i) $$

먼저 Mean을 제외한 Average Precision에 대해서 살펴보자. 위의 식에서 P(i)는 해당 index까지의 Precision값을 의미하며, rel(i)는 해당 index에서 user engagement(click, added to cart … etc)가 일어났는지 여부, 즉, 잘 추천되었던 것인가 여부를 의미한다. 사용자로부터 어떠한 액션도 없었다면 그 값은 0이되므로, P(i) * rel(i)의 값도 자연스럽게 0이된다. 식에서 m이 의미하는 바는 실제로 사용자가 engage한 횟수를 의미하는데, 간단하게는 일정 기간내에 일어난 이벤트 횟수를 의미한다고 보면된다. 그 이유는 우리가 신이 아니므로 정말 이 유저가 미래에도 클릭할 것이 분명한 아이템들을 알 수 있는 것은 아니기 때문이다.

좀 더 이해를 돕기위해서 아래의 예를 보도록하자. 여기서 m, 즉, 사용자가 우리가 추천한 아이템 및 자신이 서비스를 사용하며 찾아서 클릭한 아이템의 개수가 3이라고 가정한다.

Recommendations Precision @k (k=3) AP@k (k=3)
[0, 0, 1]
(세가지 아이템을 추천하고 그 중 마지막 아이템만 사용자가 클릭한 경우를 의미한다.)
[0, 0, 1/3] (1/3)(1/3) = 0.11
[0, 1, 1]
(세가지 아이템을 추천하고 그 중 2, 3번째 아이템을 사용자가 클릭한 경우를 의미한다.)
[0, 1/2, 2/3] (1/3)[(1/2) + (2/3)] = 0.38
[1, 1, 1]
(세가지 아이템을 추천하고 사용자가 추천된 모든 아이템을 클릭한 경우를 의미한다.)
[1/1, 2/2, 3/3] (1/3)[(1) + (2/2) + (3/3)] = 1

여기서 쉽게 발견할 수 있는 사실은 추천한 아이템을 사용자가 더 많이 액션을 취했을수록 AP가 높아진다는 점이다. 만약 1개의 아이템만 잘 추천되었지만 그 순서를 달리하면 결과가 어떻게 될까?

Recommendations Precision @k (k=3) AP@k (k=3)
[1, 0, 0] [1/1, 1/2, 1/3] (1/3)(1) = 0.33
[0, 1, 0] [0, 1/2, 1/3] (1/3)[(1/2) + (1/3)]= 0.28
[0, 0, 1] [0, 0, 1/3] (1/3)(1/3) = 0.11

위의 표를 보게되면 동일한 양의 아이템을 추천 성공한 경우에는 그 아이템이 좀 더 앞쪽에 배치될수록 높은 점수가 나오는 것을 확인할 수 있다.

“Mean” Average Precision

자, 이제 MEAN이 왜 붙게되는지 살펴보도록 하자. 그 경우는 간단하다. 한명의 사용자에게 추천한 결과를 평가한 것이 Average Precision이고, 전체 사용자 U에 대해서 평가를하는 것이 Mean Average Precision(MAP)이다.

$$ MAP@K = \frac{1}{\lvert U\rvert} \sum_{u=1}^{\lvert U\rvert} (AP@K)_{u} $$

Conculusion

MAP은 검색 결과나 추천시스템을 평가할 때 아주 유용하고 널리 사용되는 평가법이다. 이뿐만 아니라, MAR(Mean Average Recall)역시도 사용할 수 있는데 그건 위에서 살펴본 Recall을 Precision대신해서 넣으면 된다. 재밌는 점은 Precision은 우리가 틀린 예측을하게되면 그 값이 떨어지지만, Recall에는 변화가 없다는 점이다.(분모는 실제로 positive인 개수이므로 변화가 없다)

구현 코드가 필요하신분은 링크에서 확인하도록 하자.

이 글이 도움되었다면, 댓글이나 공유를 해주세요. 큰 힘이 됩니다. :)

Reference

Mean Average Precision (MAP) For Recommender Systems