Learning to Rank와 nDCG

최근 검색 모델에도 관심을 가지게 되면서, 랭킹모델과 IR에 대해 다시 공부중이다. 기존에 관심있었던 커머스 분야의 추천 랭킹 시스템에서는, ‘유저가 실제로 살 것 같은 하나의 아이템’을 잘 추천해주는 것이 중요했기 때문에, MRR이나 nDCG 같은 순위 기준의 랭킹 평가 방법을 굳이 사용하지는 않았었다. cost function도 단순히 binary classification 문제를 해결하는 형태로 구성된다. 상품단위의 구매 AUC를 줄세우기만 해도 구매에 대한 측정은 충분히 가능했기 때문. 어떤 순위로 등장했는지를 평가하는 것은 중요하지 않았다.

하지만 일반적인 서비스에서의 검색, 추천 시스템은 노출되는 아이템의 Ranking을 얼마나 리스트 단위로 잘 정리하는지가 중요하다. 물론 “도메인에 따라”, “문서 혹은 아이템을 몇 개씩 노출하느냐에 따라” 등, 각각 전략이 달라질 수는 있다. 그래도 랭킹 모델을 정리하는 basis는 동일하다. 이는 크게 세 가지 부류로 나눌 수 있으며 각 방법은 모델을 학습하거나 평가할 때, 얼마나 많은 아이템을 비교 대상으로 고려하는 지를 기준으로 나뉜다.

본 포스팅은 이러한 방법들을 intuitive하게 소개하고, 가장 널리 알려진 랭킹 평가 방법인 nDCG에 대해 소개한다.

 

 

---

1. Pointwise approaches

Pointwise는 단어 그대로, 하나의 아이템 단위의 접근이다. 하나의 point를 classifier나 regressor의 학습 데이터로 사용하는 것. 서론에 언급했던 방법이 여기에 해당된다. 이는 현재의 질의(이하 Q)에 가장 연관성이 높은, 혹은 가장 확률이 높은 아이템을 예측하는 것이라고 할 수 있다. 예측 결과를 sorting하여 보여주는 것이 최종 결과의 형태. 예를 들면 하나의 predictor가 logistic regressor를 아이템 단위로 적용하고, 각 score를 정렬하여 순위를 매긴다. 

하지만 실제 유저가 ranking을 접할때는 (0,1) 여부를 결정하는 label로 평가되는 것이 아니라, 전체적인 순위를 훑어본 뒤 결정을 하는 것이기 때문에 ranking을 prediction 한다는 관점과는 맞지 않을 수 있다.



2. Pairwise approaches

Pairwise는 문서 혹은 아이템을 하나의 ‘쌍’으로 활용한다. 만약 Q에 반환된 아이템(I1, I33, I12, I21, I4, …)이 있을 때, 이를 2개 단위로 쪼개 pair를 생성한다. 이를테면 (I1, I33), (I33, I12)… 이다. 이 때 랭킹의 ground truth와 가장 많은 pair가 일치하는 optimal한 순서를 찾아내는 것이다. 이런 접근 방법의 핵심은 순서가 뒤바뀌는 것을 cost function에 활용하여, 잘못된 순서를 바로잡자는 것이다.

한 point의 label 혹은 score에 의존하는 Pointwise에 비교하여, Pairwise 방법은 ground truth에 가까운 order를 찾는 과정이기 때문에 더 잘 동작할 것이라고 기대할 수 있다. 그렇다면 문제는 pair의 조합을 최적화하는 것인데, 이 때 RankNet과 같은 뉴럴넷 기반의 알고리즘을 사용한다.



3. Listwise approaches

Listwise는 Q에 반환된 문서 리스트 전체를 ground truth와 한방에 비교하는 방법이다. 일부 영역에서는 Querywise approaches로 응용하여 활용되기도 한다. Querywise는 질의(Query)를 타입별로 나누어 별도의 Learning을 하는 것으로, 타입별 모델의 Ranker가 생성된다.

Listwise는 결과의 ‘랭킹’ 즉 순위를 가장 적절하게 나열하는 것 자체를 목적으로 하기 때문에 모든 방법중에 가장 복잡도가 높고 결과가 좋은 편이다. 가장 널리 알려진 랭킹 평가 방법인 nDCG를 통해 listwise를 자세히 알아보자.



4. nDCG(normalizing Discounted Cumulative Gain)

MRR(Mean ), MAP(Mean Average Precision), Top K Recall 등의 방법은 한 명의 사용자가 가진 relevant 아이템이 많을 수록 평가하기 수월하다. 하지만 impression에 대한 데이터가 없거나, 한 명의 사용자가 반응한 랭킹이 상위에만 지나치게 집중되어 있다면 이러한 방법들은 한계를 드러낸다. 그리고 실제로 대부분의 검색, 추천 랭킹 시스템은 극단적으로 skewed한 인기도를 가지고 있다. 그래서 nDCG는 순위에 가중치를 주기 위한 방법을 적용한다. 또한 하나의 랭킹으로 여러 명을 평가하기 위해 밀도(혹은 점수)를 추가하여, 2차원 점수를 평가한다는 의미를 가지기도 한다.

nDCG는 현재 점수(밀도)의 랭킹에서 가장 이상적인 랭킹과 현재 랭킹을 cummulative한 점수로 비교한다. 그리고 랭킹이 낮아짐에 따라 중요도가 감소하는 것은 log normalization으로 완화한다. nDCG를 계산하기 위한 수식들은 다음과 같다.

만약 4,3,4,2,1의 score를 가지고 있는 5개 Q의 반환 결과가 있다면, 이에 대한 ideal vector를 4,4,3,2,1 이라고 한다. 그리고 이 두개의 relevant score list로 nDCG 스코어를 생성하는 것. 당연하게도 1에 가까울수록 좋은 랭킹이다. 더 직관적인 이해를 돕기 위해 파이썬 코드로 이를 표현하였다.

def cumulative_gain_score(rel_list, p):
    return sum(rel_list[:p])
    
def discounted_cumulative_gain_score(rel_list, p):
    dcg = rel_list[0]
    for idx in range(1, p):
        dcg += (rel_list[idx] / np.log2(idx+1))
    return dcg

rank_relevant_score = [4,3,4,2,1]
ideal_vector = [4,4,3,2,1]
print("CG :", cumulative_gain_score(rank_relevant_score, p=len(rank_relevant_score)))
print("ICG :", cumulative_gain_score(ideal_vector, p=len(ideal_vector)))
print("DCG :", discounted_cumulative_gain_score(rank_relevant_score, p=len(rank_relevant_score)))
print("IDCG :", discounted_cumulative_gain_score(ideal_vector, p=len(ideal_vector)))

dcg = discounted_cumulative_gain_score(rank_relevant_score, p=len(rank_relevant_score))
idcg = discounted_cumulative_gain_score(ideal_vector, p=len(ideal_vector))
ndcg = dcg / idcg
print("NDCG :", ndcg)

전체 코드 링크 :
https://github.com/yoonkt200/ml-theory-python/tree/master/05-ranking-metric


참고하면 좋을 자료

https://en.wikipedia.org/wiki/Learning_to_rank
https://medium.com/@nikhilbd/pointwise-vs-pairwise-vs-listwise-learning-to-rank-80a8fe8fadfd
https://iamksu.tistory.com/72
https://separk1031.tistory.com/entry/RRMRRReciprocal-Rank
https://en.wikipedia.org/wiki/Discounted_cumulative_gain
http://freesearch.pe.kr/archives/1574