검색품질은 어떻게 측정할까? (2)
MRR, mAP, 그리고 nDCG
지난 번 글에서는 검색품질을 평가하기 위한 Precision과 Recall에 대해서 살펴보았다.
검색품질은 어떻게 측정할까? (1) - Precision과 Recall
이번에는 MRR, MAP, 그리고 nDCG에 대해서 내용을 확인해보도록 하자.
하나의 클릭을 평가하는
MRR (Mean Reciprocal Rank)
MRR, Mean Reciprocal Rank - 평균 상호순위 정도로 해석해볼 수 있겠다.
가장 단순하고 계산이 쉬운 지표 중에 하나라고 한다. 수식을 보면 어느정도 감이 잡힐 수 있을텐데, 각 사용자가 클릭한 상품 중 가장 상위에서 클릭된 상품 1가지를 기준으로 상호순위(Reciprocal Rank)를 적용하게 된다.
아래 표를 보면 좀 더 이해가 쉬울 수 있다.
사용자가 cat, torus, virus 와 같이 3가지 검색어를 넣었을 때, 사용자가 클릭한 키워드가 각 랭킹 순위 기준으로 몇 번째 있는가를 계산하고 이를 평균내는 방식이다.
첫 번째 cat이라는 검색어는 3번째 랭크된 값을 클릭했으니 = 1/3
두 번째 torus라는 검색어는 2번째 랭크된 값을 클릭했으니 = 1/2
세 번째 virus라는 검색어는 첫번째 랭크된 값을 클릭했으니 = 1
이 값을 평균을 내면 (1/3 + 1/2 + 1) /3 = 11/18 = 0.61정도 되는 값으로 계산될 수 있다.
비교적 간단하지만, 최상위의 클릭 상품 1가지만 고려하게 되므로 다른 지표기준들에 비해 정확도가 떨어진다고 한다.
여러 선호도를 평가하는
mAP (mean Average Precision)
평균 정밀도(?)라고 해석할 수 있는 mAP에 대해서도 알아보도록 하겠다.
이 지표는 클릭한 상품 한가지만을 고려하지 않고, 클릭한 모든 상품들에 대한 순서를 고려여 MRR에 비해서 보다 정교한 지표라고 할 수 있다. 따라서 검색결과 뿐 아니라 추천시스템을 평가할 때도 유용하게 사용되는 평가법이라고 한다.
아래 표를 보면 좀 더 이해가 쉬울 수 있는데, 세 명의 사용자가 검색결과 중 녹색으로 표기된 키워드를 선택한 경우 평균 정확률을 먼저 구할 수 있고, 이를 평균 내린 값이 mAP가 되는 것이다.
사용자가 cat이라는 검색어를 넣었을 때 Fatten, cati, cats, kitti, coat와 같은 결과값을 얻었고, 녹색으로 표기한 2개의 단어에 반응한 경우,
세 번째 cats이라는 결과를 클릭했기 때문에 (1/3)
그리고 네 번째 kitti라는 결과를 클릭했기 때문에 (2/4)
이 둘의 평균을 계산하면 (1/3+2/4)/2 = 5/12
마찬가지로 나머지 유저의 Average Precision을 계산하여 최종 값을 도출함
남은 두 사용자(User)의 값도 포함해 평균을 내본다면, {(5/12) + (11/12) + (7/10)}/3 = 0.67이라는 값을 도출해볼 수 있다.
사용자가 선택한 모든 키워드 값을 모두 계산하여 지표를 구할 수 있으므로 MRR보다는 정확도가 더 높다고 할 수 있겠다.
연관성을 기반으로 이상적인 순서와 비교하는
nDCG (normalized Discounted Comulative Gain)
nDCG를 이해하기 위해서는 CG, 그리고 DCG, IDCG 를 먼저 이해할 필요가 있다.
CG는 Cumulative Gain의 약자로 누적 증가를 계산하는 방식으로 생각할 수 있는데, 항목의 개수마다의 연관성을 계산하게 된다.
연관도(Relevance)를 계산하는 방식은 각각 정의하기 나름인데, 검색에서는 클릭수, 체류시간 등을 통해 연관도를 계산하기도 한다.
좀 더 구체적으로 설명하기 위해 아래와 같은 책 검색결과가 있다고 가정해보자.
여기서 각각의 클릭률을 통해 5점 만점 기준으로 환산하여 아래와 같이 연관도(Relevance)점수를 적용해보자. (여기서는 Relevance를 계산하는 방식은 제외)
그럼 n(검색결과 수)은 3이고, rel(연관도점수)는 4,3,5,2,4점으로 정의가 되었으니.
여기서 CG는 4+3+5+2+4 = 18점이 되는 것이라고 할 수 있다.
그리고 DCG의 경우를 살펴보자.
DCG의 수식은 아래와 같다.
로그함수의 특성 상 큰 수를 작게 만들어주고 보다 정교한 분류가 가능하고자 하는 의도도 있겠지만, DCG에서 로그를 사용하는 이유는 검색결과에서 항목의 순서를 더욱 중요하게 계산하기 위함이라고 한다. (항목의 순서의 Relevance Score가 분자에 위치하고 ^으로 계산 되기 때문)
위 책검색에 대한 CG값 계산 사례를 기준으로 다시 정리해보면,
위 서식에서 볼 수 있듯이 로그함수가 분모에 적용되어 있기 때문에 순서가 뒤에[ 위치한 검색결과인 경우일 수록 분모값이 커지고 본자, 분모를 계산한 값은 작아질 수 밖에 없게 된다.
따라서 순서를 자연스럽게 고려한 전체 계산값이 나오게 되는 산술식이라고 할 수 있겠다.
IDCG의 경우엔 이상적인 순서에 대한 값으로 계산하는 방식이다.
IDCG는 순서와 가장 이상적인 연관도(Relevance) 순서대로 계산을 하기 때문인데, 이는 순서와 상관없이 가장 이상적인 높은 Relevance를 가진 순으로 결과를 합산하게 된다.
따라서 DCG에서 4,3,5,2,4의 Relevance Score가 높은 스코어대로 5,4,4,3,2의 순서가 되고 이를 통한 계산 식을 아래와 같이 정리해볼 수 있다. 따라서 이는 완벽하게 사용자가 기대하는 순서에 대한 값으로 볼 수 있다.
여기까지 오는데, 시간이 좀 걸렸다. 헉헉..
결론적으로, nDCG는 아래와 같이 계산할 수 있다.
따라서 상대적인 품질을 나타내는 값을 계산할 수 있는데, 결국 nDCG가 높다는 것은 검색결과나 추천목록이 사용자에게 좋은 정보를 잘 제공한다고 볼 수 있겠다. (nDCG가 1에 가까울 수록 좋은 결과에 대한 품질이 좋다고 할 수 있다)
MRR은 클릭상품 1개의 기준, mAP가 클릭상품 여러개를 기준으로 검색품질을 평가했다면, nDCG는 Relevance라는 값을 우선 측정하고 이에 따라 이상적인 순서와 비교하여 검색품질을 측정하는 방법이라고 할 수 있겠다.
다시 정리하면, nDCG는 이상적인 순서를 부여받은 항목들이 앞에 배치되는 IDCG와 실제 결과의 순서를 통해 계산된 DCG값의 비교를 통해 상대적인 비율을 보는 방식이다. 이를 통해서 검색결과나 추천목록 등의 품질을 정량화하여 평가할 수 있을 것이다.
검색의 품질을 평가하고 싶다면, 혹은 노출되는 추천 큐레이션 영역을 평가하고 싶다면 이와같이 이미 잘 정리되어 있는 품질지표 공식을 먼저 활용해보도록 하자, 그리고 현재 서비스에 최적화된 품질지표를 찾기 위해 수정하고 더 나은 지표를 제안해볼 수 있어도 좋을 듯 하다. :)
검색결과 품질은 어떻게 측정해야 할까? (1) - AB테스트와 Precision, Recall
검색결과 품질은 어떻게 측정해야 할까? (2) - MRR, mAP, 그리고 nDCG
Reference
https://en.m.wikipedia.org/wiki/Mean_reciprocal_rank
https://en.wikipedia.org/wiki/Discounted_cumulative_gain
https://medium.com/musinsa-tech/map-416b5f143943
https://www.aporia.com/learn/a-practical-guide-to-normalized-discounted-cumulative-gain-ndcg/
https://www.slideshare.net/MinsubYim/evaluation-in-ir-system
https://innovation.ebayinc.com/tech/engineering/measuring-search-relevance/
