다양한 형태로 원하는 내용과 관련있는 결과를 얻어내는 것을 정보 검색(Information Retrieval, 이하 IR)이라고 한다.
IR의 정확도 및 효율을 분석하기 위한 평가기준을 알아본다.
- True Positives(tp) = 선택된 결과(positives)가 관련이 있어서 선택과 정답이 일치하는(true) 경우
- True Negetives(tn) = 선택되지 않은 결과(negatives)가 관련이 없어서 선택과 정답이 일치하는(true) 경우
- False Positives(fp) = 선택된 결과(positives)가 관련이 없어서 선택과 정답이 일치하지 않는(false) 경우
- False Negatives(fn) = 선택되지 않은 결과(negatives)가 관련이 있어서 선택과 정답이 일치하지 않는(false) 경우
tp + tn + fp + fn = 전체 문서
#정확도(accuracy) #정밀도(precision) #재현율(recall) #MRR(Mean Reciprocal Rank) #MAP(Mean Average Precision) #NDCG(Normalized Discounted Cumulative Gain)
정확도
정확도는 모든 컨텐츠 중 IR의 결과가 정답과 일치하는 비율을 구한다. 이는 정밀도나 재현율과 다르게 전체 컨텐츠에 대한 IR의 신뢰도를 판단할 수 있는 근거가 된다.
정확도(accuracy) = (tp + tn) / (tp + tn + fp + fn)정밀도
정밀도는 IR이 선택한 결과 중 관련이 있는 비율을 구한다. 이는 가장 간단하고 직접적인 평가 기준으로, IR이 선택한 컨텐츠가 얼마나 정확한가를 판단하는 기준이 된다.
정밀도(precision) = tp / (tp + fp)재현율
재현율은 관련있는 컨텐츠 중 IR이 선택한 비율을 구한다. 정밀도가 선택한 컨텐츠의 정확성을 보는 기준이라면 재현율은 IR이 관련있는 컨텐츠들을 얼마나 놓치지 않고 가져올 수 있는지를 가늠할 수 있는 기준이 된다.
재현율(recall) = tp / (tp + fn)MRR
MMR은 우선순위를 고려한 평가기준 중 가장 간단한 모델. 사용자가 몇 개의 컨텐츠에 관심이 있었는지, 각 관련 컨텐츠는 어느 위치에 있었는지를 고려하지 않는다. 오직, 가장 상위의 관련 컨텐츠의 위치만을 고려하여 점수를 계산함으로써 가장 관련있는 컨텐츠가 얼마나 상위에 올라가 있는지를 평가한다.
알고리즘
- 각 사용자마다 제공한 추천 컨텐츠 중 관련있는 컨텐츠 중 가장 높은 위치를 역수로 계산(1/k)한다.
- 사용자마다 계산된 점수를 모아 평균을 계산한다.
| A User | B User | C User | |
|---|---|---|---|
| Doc 1 | Non relevant | Non relevant | Relevant |
| Doc 2 | Non relevant | Relevant | Relevant |
| Doc 3 | Relevant | Relevant | Non relevant |
| Result | 1 / 3 | 2 / 1 | 1 / 1 |
- A User는 Doc 1 -> Doc 2 -> Doc 3 에서 매칭이 되었으므로 1 / 3
- B User는 Doc 1 -> Doc 2 에서 매칭이 되었으므로 1 / 2
- C User는 Doc 1 에서 매칭이 되었으므로 1 / 1
이렇게 구해진 모든 사용자 reciprocal rank의 평균값을 계산하면
MMR = (A User + B User + C User) / User length
0.61 = ( 1/3 + 1/2 + 1/1 ) / 3MRR의 장점
- 간단하고 쉽다.
- 제공된 목록 중 가장 상위의 관련된 컨텐츠에만 집중하기 때문에, 사용자에 가장 관련있는 컨텐츠가 최상위에 있는가를 평가할 때 용이하다.
- 새로운 컨텐츠가 아니라 이미 사용자가 알고 있는 컨텐츠 중 가장 선호할만한 컨텐츠를 보여주고자 할 때 좋은 평가 기준이 된다.
MRR의 단점
- 제공된 목록 중 하나의 컨텐츠에만 집중하기 때문에 나머지 부분에 대해서는 평가하지 않는다.(2, 3번째 관련 컨텐츠에 대해서는 평가를 하지 않는다.)
- 관련 컨텐츠의 개수가 달라도 첫 번째 관련 컨텐츠의 위치가 같은 경우 같은 점수를 가지므로 변별력을 가지기 어렵다.
- 사용자가 컨텐츠에 대해 잘 알지 못해 여러 번 탐색을 해야 하는 경우 살펴봐야 하는(관련있는) 컨텐츠의 개수가 1개 이상일 가능성이 높으므로 좋은 평가 기준이 되기 어렵다.
MRR은 장단점이 뚜렷한 평가 모델로써, 사용자가 원하는 목적이 비교적 뚜렷하고 잘 알고 있는 알려진 컨텐츠를 추천하는 IR(배달 어플리케이션의 배달 음식점 검색)을 평가할 때 좋은 모델이 될 수 있다.
MAP
MMR의 단점을 해결하기 위해 가장 쉽게 생각할 수 있는 방법은 상위 N개까지의 정밀도를 구하는 것(Precision@N)이다.
알고리즘
- 각 사용자마다 관련된 컨텐츠를 구하여 해당 관련 컨텐츠 위치까지의 목록(sublist)에 대하여 정밀도를 계산한다.
- 계산된 정밀도 값들에 대하여 사용자별로 평균을 내고, 그 결과를 모두 모아 평균을 계산한다.
| Doc 1 | Doc 2 | Doc 3 | Doc 4 | Doc 5 | Result | |
|---|---|---|---|---|---|---|
| A User | Relevant | Non relevant | Relevant | Relevant | Non relevant | 1 , 3 , 4 |
| B User | Non relevant | Non relevant | Non relevant | Relevant | Relevant | 4, 5 |
- A User는 첫 번째 관련 컨텐츠까지 정밀도가 1/1 = 1이고, 다음 관련 컨텐츠인 세 번째 관련 컨텐츠까지 정밀도는 2/3(총 3개 중 2개가 관련된 컨텐츠)이다. 동일한 방법으로 네 번째 컨텐츠까지의 정밀도는 3/4이다.
- 3개의 정밀도 값 평균을 내면 평균 정밀도인 (1/1 + 2/3 + 3/4) / 3 = 0.8
- B User는 네 번째 관련 컨텐츠까지 정밀도가 1/4이고, 다음 컨텐츠인 다섯 번째 컨텐츠까지 정밀도가 2/5이다.
- 2개의 정밀도 값 평균을 내면 평균 정밀도인 (1/4 + 2/5) / 2 = 0.325
MAP = (A User + B User) / User length
0.56 = ( 0.8 + 0.325 ) / 2MAP 장점
- 추천 컨텐츠의 단순한 성능을 평가하는 것이 아니라 우선순위를 고려한 성능을 평가할 수 있다.
- 상위에 있는 오류(관련없는 컨텐츠)에 대해서는 가중치를 더 주고, 하위에 있는 오류에 대해서는 가중치를 적게 주어 관련 컨텐츠가 상위에 오를 수 있도록 도움을 준다.
MAP 단점
- MAP는 관련 여부가 명확하지 않은 경우에는 계산하기 어렵다.
- 1~5점으로 평가하는 평점같이 관련 여부를 판단하기 어려운 경우는 MAP를 사용하기 어렵다.(4~5점은 관련있다고 판단하더라도 3점은 관련 여부를 판단하기 어려울 것이다.)
이와 같이 MAP는 MRR과는 다르게 상위 N개의 추천 컨텐츠에 대하여 평가를 할 수 있고, precision@N과는 다르게 추천 컨텐츠의 우선순위를 고려하여 점수를 계산할 수 있다.
MAP은 전반적으로 훌륭한 평가 모델이 될 수 있다. 만약 컨텐츠의 관련 여부를 이분법으로 나눌 수 있다면 MAP은 좋은 평가 모델이 될 것이다. 하지만, 사용자에게 더 관련이 있는 컨텐츠를 상위에 노출시키고 있는지에 대해 평가하고 싶다면 다음에 설명하는 NDCG라는 평가 모델을 활용해야 한다.
NDCG
NDCG는 관련 여부에 대해 이분법적으로 구분하는 것이 아니라 더 관련있는 컨텐츠는 무엇인가?에 대해 집중하여 더 관련있는 컨텐츠를 덜 관련있는 컨텐츠보다 더 상위에 노출시키는지에 대해 평가한다.
알고리즘
- 모든 추천 컨텐츠들의 관련도를 합하여 CG(cumulative gain)을 구한다.
- CG에서 추천 컨텐츠들의 관련도를 합하였다면, DCG는 각 추천 컨텐츠의 관련도를 log함수로 나누어 값을 구한다. log함수 특성상 위치 값이 클수록(하위에 있을 수록) DCG의 값을 더 작아지게 함으로써 상위 컨텐츠의 값을 점수에 더 반영할 수 있게 한다.
- DCG 값에 관련도를 더 강조하고 싶다면, 2^관련도 - 1과 같이 관련도의 영향을 증가시킬 수 있다.
- 사용자마다 제공되는 추천 컨텐츠의 DCG와는 별개로 IDCG(이상적인 DCG)를 미리 계산해놓는다.
- 각 사용자의 DCG를 IDCG로 나누어서 사용자별 NDCG를 구한다.
- 사용자별 NDCG의 평균을 구하여 해당 IR의 NDCG를 구한다.
이해가 명확하게 되질 않으므로 예시를 들 수 없었다. 해서 일단 원문의 내용을 넣었고, 원문에는 상세히 작성되었으니 확인해보자
NDCG 장점
- 기존 방법과는 다르게 다양한 관련도에 대한 평가가 가능하다.
- 이분법적인 관련도에도 뛰어난 성능을 보인다.
- log 함수를 이용하여 하위 컨텐츠에 대한 영향을 줄임으로써 좋은 성능을 보인다.
NDCG 단점
- 사용자와의 관련성을 파악하기 어려운 상황에는 문제의 소지가 있다. 사용자가 컨텐츠에 대한 평가를 하지 않는다면(평점을 입력하지 않는 경우) 해당 관련도를 어떻게 처리해야 할지에 대해 정의해야 한다. 0점 처리해도 문제가 될 것이고, 평균 값을 이용해도 문제가 될 수 있다.
- 사용자의 관련 컨텐츠가 없다고 판단될 경우, 임의로 NDCG를 0으로 설정해주어야 한다.
- 보통 K개의 NDCG를 가지고 IR을 평가하는데 IR에서 제공한 컨텐츠가 K보다 부족한 경우, 부족한 관련도를 최소 점수로 채워서 계산해야 한다.
보다시피 NDCG는 특별한 경우가 아니고서는 훌륭한 평가 기준이 될 수 있다. 다만, 특별한 경우에 대해서 예외처리를 해주어야 하고 관련도에 대한 기준을 상황마다 명확하게 세워야 한다. 이런 부분을 감안하더라도 평점 기반의 추천 서비스에서 NDCG를 활용하면 좋은 평가를 할 수 있는 것이라 생각된다.
