- 논문 링크 (5776회 인용)
추천 시스템에서 모델의 성능을 비교하기 위한 평가 지표에 대해 살펴보고자 한다. 첫번째로, 많이 쓰이는 지표 중 하나인 Normalized Discounted Cumulative Gain (NDCG)에 대해 알아보자. Cumulative Gain, Discounted CG, Normalized DCG의 순서로 살펴볼 예정이다.
Preliminary
추천 알고리즘의 성능은 어떤 기준으로 평가할 수 있을까? 유저에게 K개의 아이템을 추천하는 상황을 생각해보자. 유저가 좋아하는 아이템이 상위에 있을 수록 '좋은 추천'이라고 말할 수 있다. 그렇다면 '유저가 좋아하는' 아이템은 어떻게 정의할까? 추천 시스템에서는 유저와 아이템간의 'relevance'을 정의하고 이 relevance가 클 수록 유저와 아이템이 깊은 관계를 가지고 있다고 생각한다. 바로 여기에 유저와 아이템간의 '관련성'과 관련 있는 아이템이 어느 순위에 있는지, '랭킹'의 개념이 들어간다. 이 두 개념을 담고 있는 추천 시스템 평가 지표가 NDCG이다. 이하에서 논의할 때, '관련성'이라는 단어를 많이 쓸텐데, 이 '관련성'은 데이터 도메인에 따라 다르게 정의될 수도 있고, 때로는 생략하고 NDCG를 계산하기도 하는 것 같다. 우선 이렇게 생각하고 개념을 살펴보자.
Cumulative Gain
K개의 아이템을 추천할 때, 아이템들이 가지고 있는 relevance의 단순 총 합이다.
\[ CG = \sum^K_{i=1}relevance_i \]
만약에 어떤 유저에게 5개의 아이템을 추천했는데 각각의 relevance 점수가 $[2, 3, 3, 1, 2]$ 라고 해보자. 그렇다면 이에 대한 CG는 $CG = 2 + 33 + 3 + 1 + 2 = 11$이다.
Discounted Cumulative Gain (DCG)
CG는 단점이 있다. 예를 들어서, 유저에게 추천한 5개의 아이템 relevance 점수가 어떤 경우는 $[2, 3, 3, 1, 2]$이고 다른 경우는 $[3, 3, 2, 2, 1]$ 이라고 하자. 이 두 경우에 대해서, CG는 11로 동일하지만 두번째 경우가 relevance가 높은 아이템을 유저에게 상위로 추천했기 때문에 (높은 순위, 1등, 2등..) 첫번째 경우에 비해서 더 좋은 추천을 했다고 말할 수 있다. 즉, CG에는 랭킹에 대한 개념이 들어있지 않기 때문에 한계를 가진다. 이를 개선한 지표가 DCG로, 각 아이템의 랭킹을 함께 고려한다.
\[ DCG = \sum^K_{i=1} \dfrac{relevance_i}{\log_2 (i+1)} \]
Discounted는 각 아이템의 순위로 discount 되었다는 뜻이다. 수식을 살펴보면 순위가 높을수록, i가 작아지므로 나눠주는 값이 작아진다. 따라서 DCG 값은 커진다. 순위가 낮을수록, i는 커지므로 나눠주는 값이 커진다. 따라서 DCG 값은 작아진다. 다시 말해, relevance가 큰 아이템이 높은 순위로 추천되었다면, $\log_2 (i+1)$ 값이 작아지므로 DCG는 커지도록 보정이 되는 것이다. 즉, $A=[2,3,3,1,2]$는 $B=[3,3,2,2,1]$보다 낮은 DCG 값을 가지게 된다. 도메인에 따라서 relevance의 penalty을 아래와 같이 다르게 주는 경우도 있다.
\[ DCG = \sum^K_{i=1} \dfrac{2^{relevance_i}}{\log_2 (i+1)} \]
추천 아이템 세트 A,B의 DCG을 계산해보자.
\[ DCG_A = \dfrac{2}{\log_2(1+1)} + \dfrac{3}{\log_2 (2+1)} + \dfrac{3}{\log_2 (3+1)} + \dfrac{1}{\log_2 (4+1)} + \dfrac{2}{\log_2 (5+1)} \approx 6.64 \]
\[ DCG_B = \dfrac{3}{\log_2 (1+1)} + \dfrac{3}{ \log_2(2+1) } + \dfrac{2}{\log_2(3+1)} + \dfrac{2}{\log_2 (4+1)} + \dfrac{1}{\log_2 (5+1)} \approx 7.14 \]
B 추천 아이템 세트의 DCG가 더 큼을 확인할 수 있다.
Normalized Discounted Cumulative Gain
DCG도 단점이 있다. 만약에 10개의 아이템을 추천하는 상황과 100개의 아이템을 추천하는 상황을 생각해보자. DCG의 수식을 생각해보면, 100개의 아이템을 추천하는 상황의 DCG 값이 더 클 가능성이 높음을 유추해볼 수 있다. 즉, 실제로는 relevance 값이 낮은 아이템이 상위 순위로 추천되었는데, 단순히 아이템의 개수가 많아서 DCG가 높게 나오고, 더 좋은 추천을 하는 것처럼 보이는 문제가 발생할 수 있다. 따라서, DCG을 정규화 (normalize)해야하는데, 이를 NDCG라고 한다. NDCG는 DCG 값을 IDCG로 정규화한 것을 의미한다.
\[ NDCG = \ \dfrac{DCG}{IDCG} \]
IDCG는 가장 이상적인 상황에서의 DCG로, 쉽게 생각해서 DCG가 가질 수 있는 최대값이라고 보면 된다. 그러면 NDCG는 0에서 1사이의 값을 가지는, 일종의 비율이 된다. 위에서 살펴본, 5개의 아이템을 추천하는 상황을 생각해보자. $[2,3,3,1,2]$의 순서로 추천해줄 수도 있고, $[1,2,2,3,3]$ 또는 $[3,3,2,2,1]$의 순서로 추천해줄 수도 있다. relevance가 높은 순서대로 추천해주는 상황이 가장 좋지 않을까? 따라서 그 값이 IDCG가 된다.
\[ DCG_A = \dfrac{2}{\log_2(1+1)} + \dfrac{3}{\log_2 (2+1)} + \dfrac{3}{\log_2 (3+1)} + \dfrac{1}{\log_2 (4+1)} + \dfrac{2}{\log_2 (5+1)} \approx 6.64 \]
\[ DCG_B = \dfrac{3}{\log_2 (1+1)} + \dfrac{3}{ \log_2(2+1) } + \dfrac{2}{\log_2(3+1)} + \dfrac{2}{\log_2 (4+1)} + \dfrac{1}{\log_2 (5+1)} \approx 7.14 \]
B 아이템 세트를 추천하는 상황이 이상적이므로, A 아이템 세트의 NDCG는 6.64/7.14 = 0.93 이다.
DCG을 IDCG로 나누기 때문에 일종의 정규화 효과가 있고, K가 작든, 크든 그 값은 0과 1사이의 값을 가지기 때문에 NDCG을 서로 비교할 수 있다.
NDCG을 리포트할 때, 보통은 NDCG@K라는 표현을 많이 쓴다. NDCG는 상위 K개의 아이템을 추천할 때 그 성능에 대한 정의이기 때문이다.
의문점
여기까지 공부했을 때, 필자를 괴롭혔던 부분은 1) relevance는 무엇이고 2) 애초에 추천을 할 때 relevance가 높은 순서대로 추천을 하면 NDCG는 무조건 1이 되는 것 아닌가 하는 점이었다.
우선 relevance는 논문을 살펴보면 각자의 상황에 따라서 다르게 정의하는 것으로 보였다. 보통 유저에게 K개의 아이템을 추천해줄 때, 학습된 유저 벡터와 아이템 벡터의 유사도 점수를 계산하고, 그 점수가 가장 높은 상위 K개의 아이템을 선택하므로 이 점수가 relevance로 정의되는게 아닌가라는 생각이 들었다. (일반적인 추천 시스템 문제에서 이거는 틀린 생각인 것 같다. 아래에서 논의)
다음으로 애초에 relevance의 내림차순으로 추천을 할 것 같은데, 그러면 NDCG의 DCG와 IDCG가 동일한 값이 되고 그러면 항상 NDCG는 1이 되는 것 아닌가 하는 의문이 들었다. 그런데 추천 알고리즘 논문에서 NDCG는 리포트할 때 모두 0과 1사이의 값이 나오는 것 아닌가. 이에 대한 답은, relevance 점수가 일반적인 추천 시스템 문제에서 주어지지 않고 클릭을 했는지 등 true / false 여부로만 주어지므로 NDCG가 약간 다르게 정의된다는 것이다. 즉, 유저의 구매 여부, 클릭 여부 등 유저의 선호의 정도가 표현되어 있지 않은 implicit dataset에 대해서는 relevance는 유저가 아이템에 대해서 행동 (구매, 클릭 등)을 했다면 relevance을 1로, 그렇지 않다면 0으로 정의하는 것이 관례인 것 같았고 이것이 개인적으로는 합리적으로 느껴졌다.
한가지 의아한 점은 implicit github 코드에는 유저가 아이템과 상호작용 했든, 하지 않았든, 모두 relevance을 1로 정의하는 것 같았다. 이렇게 정의하면 몇가지 문제점이 있는데, 다음 포스팅에서 살펴보기로 하고 우선 아래 예시를 살펴보자.
| Rank | Correct | relevance score | contribute to DCG |
| 1 | T | 1 | O |
| 2 | T | 1 | O |
| 3 | F | 0 | X |
| 4 | F | 0 | X |
| 5 | F | 0 | X |
| 6 | T | 1 | O |
| 7 | T | 1 | O |
| 8 | F | 0 | X |
| 9 | T | 1 | O |
| 10 | F | 0 | X |
필자는 애초에 relevance 점수가 유저 벡터와 아이템 벡터간의 유사도 점수라고 생각했는데, relevance 개념은 그런 것이 아니라, 데이터에서 찾아야한다. 예를 들어서, 유저가 아이템에 대해서 남긴 평점이 있다면 그것이 relevance score가 될 수 있다. 그런데 생각해보면 이 relevance score가 존재하는 상황이 그렇게 많을 것 같지는 않았다. NDCG가 검색 랭킹의 품질을 평가할 때도 쓰이는데, 검색 상황에서도 유저가 검색 결과 중 어떤 것을 더 좋아하는지 알 길이 없기 때문이다.
위 예시에서 DCG는 아래와 같이 계산한다. 유저가 반응한 아이템에 대해서만 DCG를 구하고 이를 더한다.
\[ DCG = \dfrac{1}{\log_2 (1+1)} + \dfrac{1}{\log_2 (2+1)} + \dfrac{1}{\log_2 (6+1)} + \dfrac{1}{\log_2 (7+1)} + \dfrac{1}{\log_2 (9+1)} = 2.62 \]
중요한 것은 IDCG이다. IDCG는 그 정의상, DCG의 max 값이다. 즉, 추천을 최고로 잘 했을 때의 DCG 값이다. 위의 상황에서 추천을 가장 잘한 경우는 언제일까? 유저가 아이템 1, 2, 6, 7, 9와 상호작용했다. 이게 truth이므로 이 아이템을 가장 상단 5위까지 추천해준다면, 그것이 이 유저에 대한 가장 좋은 추천이고 이때 DCG의 max 값을 가진다. 이를 아래와 같이 계산한다.
\[ IDCG = \sum^{5}_{i=1} \dfrac{1}{ \log_2 (i+1) } = 2.94 \]
\[ NDCG = 2.62 / 2.94 = 0.89 \]
근데 사실 이렇게 하면.. 테스트 데이터에서 유저가 C, D 아이템에 반응한 상황일 때, [C,A,B,E,D]로 추천한 경우와 [D,A,B,E,C]로 추천한 경우의 NDCG는 동일하게 된다. 이는 binary 데이터에 대해서 NDCG 값을 계산하는 것에 대한, 어쩔 수 없는 단점이는 생각이 들었다. 애초에 유저가 C, D 아이템과 반응을 했지, 어느 것을 더 좋아하는지는 알려주지 않았기 때문에, 랭킹을 하는 상황에서도 C, D가 추천 결과에 모두 있다면, 그 랭킹 순서를 달리해도 metric에 차이가 없는 것이 자연스러운 것으로 이해했다.
댓글