목차
배경 (이라 쓰고 푸념이라 읽는다)
올해들어 딥러닝 기반 추천 시스템을 공부하고 있다. 추천 시스템에 도입되는 딥러닝은 graph-based, latent model 등이나, 문제 자체는 분류 또는 회귀와 거의 대응된다. 근데 매트릭이 좀 특이하다. 주로 검색 분야에서 사용되던 지표를 사용하거나, 일반적으로 사용하는 분류 지표에 Top N 같은 개념을 적용해서 계산하고 성능을 평가한다. 일단, 나는 검색 시스템을 잘 모르다보니, 이 지표를 이해하는 게 좀 어려웠다. 특히 여기서 설명하려는 이 nDCG를 이해하는 데에 매우 오랜 시간이 걸렸다.
우선 nDCG는 위키나 여러 블로그에서 정리해둬서 수식 자체가 어렵지는 않다. 그런데 우선 랭킹 문제와 분류/회귀 문제가 다른데 이에 대한 개념 없이 다짜고자 관련성(relevance), ideal이라는 개념을 접하니, 그래서 모델 결과를 어떻게 해석하라는 건지 매우 막막했다. 하여간 이번 기회에 nDCG가 뭔지 제대로 한 번 이해하고 계산해보고 그 결론을 정리해보았다.
이 글에서 알 수 있는 정보
- nDCG가 측정하는 것이 무엇인지
- nDCG의 수식과 그 수식에 따라 값을 구하는 방법
글의 대상
- 나
- nDCG 수식을 봐도 개념이 두루뭉술하고 이해가 잘 안되는 사람
- 과연 얘가 잘 이해한건지 궁금한 사람
nDCG란?
- nDCG는 검색 결과나 추천에서 랭킹 성능을 측정하기 위한 지표
- 검색이나 추천 알고리즘의 성능이 좋은, 그러니까 효과적인 경우, 쿼리나 특정 유저와 아이템의 관련성이 높을수록 높은 순위에, 낮을수록 낮은 순위에 배치될 것. 이 때, nDCG는 관련성이 높은 문서가 상위에 추천되는지를 측정한다.
- nDCG는 랭킹 성능을 측정하는 지표이므로, 쿼리-아이템 또는 유저-아이템과의 관련성(relevance)은 절대적인 값이며, 모델이나 알고리즘이 결정하는 것은 랭킹, 즉 아이템의 순서이다.
수식과 예제를 통한 성능 계산
CG → DCG → (IDCG) → nDCG 순서대로 정의와 그 계산법을 알아보자.
수식 설명을 위한 약간의 가정
- 유저와 아이템이 있는 추천 문제
- 유저는 한 명으로 고정, 아이템 [a,b,c,d,e]에 대해서 유저와의 관련성은 [1,2,3,4,5]이다.
- 모델 또는 알고리즘은 특정 유저에 대한 아이템 추천 순서를 결정한다
- 결정한 순서가 [a,c,d,e,b]라고 할 때, 이 순서를 관련성에 따라 [1,3,4,5,2]라고 기재할 수 있다
- TopN의 N = p는 5로 한다
Cumulated Gain (CG)
Cumulated Gain (CG)는 말 그대로 관련성의 누적 합을 의미한다. 아래에서 p는 Top N의 N을 의미하는 수로, 상위 p 개까지의 관련성을 더할 것인지를 결정한다. CG는 p를 정하지 않으면, 어떤 알고리즘의 결과이던 똑같은 값이 나오게 된다. 따라서, p를 통해 몇 개까지의 관련성을 유효하다고 볼 것인지 결정해야 한다.
다만 CG의 경우, 5개까지의 관련성을 본다고 할 때, [1,2,3,4,5]의 값과 [5,4,3,2,1]의 값이 같다. 즉, TopN에 포함된 아이템의 종류가 같으면, 더 관련성 있는 아이템이 높은 순위에 있는 모델과 그렇지 않은 모델의 성능이 같게 측정될 수 있다. 따라서 이 값을 직접 사용하지 않고, discount 를 적용한 DCG를 사용한다.
$$ CG_p = \sum_{i=1}^p rel_i $$
Discounted Cumulated Gain (DCG)
Discounted Cumulated Gain (DCG)는 관련성을 로그를 씌운 순위로 나누어 합한 값이다. 순위에 로그를 씌우면 값이 완만하게 증가하는데, 관련성을 이 값으로 나누게 되면 관련성의 영향력이 후순위일수록 작아지게 된다. DCG에서 discounted는 이렇게 후순위의 영향력을 줄이는 것을 의미한다. 즉 DCG의 값은 상위 순위의 관련성의 영향을 많이 받고, 하위 순위 아이템의 관련성의 영향은 적게 받게 된다.
위 예시로 비교해보면, [1,2,3,4,5]에 대한 DCG는 7.42가 되지만, [5,4,3,2,1]에 대한 10.27이 된다. 그러니까, Top N의 아이템이 같더라도, 랭킹에 따라서 값이 달라지게 된다.
$$ DCG_p = \sum_{i=1}^p \frac {rel_i}{log_2{(i+1)}} $$
(IDCG)
Ideal Discounted Cumulated Gain (IDCG)는 DCG 결과의 가장 이상적인 값을 말한다. 아래 nDCG 공식에서 이 값을 사용하게 되는데, 모델과 직접 관련없이 관련성에 대해서 절대적이다.
위 예시의 상황에서, 가장 이상적인 추천 순위는 [5,4,3,2,1]이 될 것이다. 따라서, 이러한 예제 상황에서 IDCG는 10.27이 된다.
normalized Discounted Cumulated Gain (nDCG)
normalized Discounted Cumulated Gain (nDCG)은 정규화된 DCG를 말하는데, 이 정규화는 모델의 랭킹에 대한 DCG를 이상적인 DCG, 즉 IDCG로 나누어 0~1 사이의 값으로 나타낸다는 것을 의미한다. nDCG의 수식은 아래와 같다.
$$ nDCG_p = \frac{DCG_p}{IDCG_p} $$
만약 어떤 모델의 랭킹 결과가 [1,2,3,4,5]라고 하면, nDCG는 다음과 같이 구할 수 있다.
$$ DCG_p = \frac{1}{\log_2{2}} + \frac{2}{\log_2{3}} + \frac{3}{\log_2{4}} + \frac{4}{\log_2{5}} + \frac{5}{\log_2{6}} = 7.42 $$
$$ IDCG_p = \frac{5}{\log_2{2}} + \frac{4}{\log_2{3}} + \frac{3}{\log_2{4}} + \frac{2}{\log_2{5}} + \frac{1}{\log_2{6}} = 10.27 $$
$$ nDCG_p = \frac{DCG_p}{IDCG_p} = 0.72 $$
이 모델의 nDCG는 0.72가 된다.
마무리
수식을 통해 nDCG를 구하는 방법에 대해서 알아보았다. 가능하면 다음 글에서는 코드 수준에서 어떻게 계산하는지, binary 문제에서는 어떻게 계산하는지를 작성해보고자 한다.
