정보 처리, 랭킹 예측에서의 모델 평가를 어떻게 할까?

$\ $구글링을 떠올려보자. 우리가 검색해서 얻은 검색 결과는 분명 구글느님들의 독보적인 검색엔진 모델에 의해서 나온 결과일 것이다. 네이버나 다른 국내 포탈들에서의 검색 결과도 마찬가지이다. 우리가 검색을 하게 되면 (쿼리를 입력하면), 그와 가장 연관있는 문서들을 검색 결과로 리턴해줘야 한다. 그렇다면 이러한 검색 엔진들의 성능을 어떻게 측정할 것인가? 에 대한 물음에서 DCG와 관련된 측정법들이 개발됐다. 이러한 랭킹 데이터 퍼포먼스 측정은, 일반적인 Classification들과 차이가 있을 수 밖에 없는데, 이러한 차이점을 만들어내는 가장 큰 요인은 문서들의 정렬 순서이다. 순서의 맥락이 들어간 데이터들의 나열에서 DCG와 관련된 측정들은 유용하게 쓰일 수 있다. 이에 대한 얘기들은 아래에서 더욱 자세히 설명한다.

우리가 방금 말한 검색 엔진이나, 추천시스템에서 추천 순서 등등

$\ $DCG 및 관련 측정법들에서 큰 두가지 전제는 다음과 같다.

1. 검색어와 관련성이 더욱 높은 문서일수록, 검색 엔진에서 상단에 배치되는 것이 의미있다.
2. 전혀 관련없는 문서들보다는, 부분적으로라도 관련있는 문서들이 가치가 있다. 마찬가지로, 부분적 관련 있는 문서보다는 완벽하게 관련있는 문서가 가치가 있다.

CG (Cumulative Gain)

$\ $Cumulative Gain (CG)는 문서들의 연관성 (relevance)들의 단순 합에 불과하다. DCG는 문서 나열 순서에 의미를 부여하며 계산을 하는 반면에, DCG 보다 간단한 CG는 문서들의 relevance 합만 생각한다.

$$ CG_p = \sum_{i=1}^p rel_i $$

\(rel_i\)는 $i$번째에 있는 문서와 검색어 간의 유사성(relevance)를 의미한다.

DCG (Discounted Cumulative Gain)

$\ $DCG 측정의 전제는, 검색어와 관련성이 높은 문서가 검색 결과의 하단에 위치할 수록 페널티를 줘야한다는 것이다. 우리의 검색어와 더 관련이 있는 문서일수록 검색 결과의 상단에 노출이 돼서 많은 유저들이 이에 만족을 해야하는데, 그렇지 못하고 중요한 문서가 아래에 존재한다는 것은 검색 엔진의 퍼포먼스가 상대적으로 떨어진다는 것이다. 이 페널티는 아래에 위치하면 할수록 그에 로그 비례해서 주어진다. 아래 식 (1)을 보면 이해가 될 것이다.

$$ DCG_p = \sum_{i=1}^p \frac{rel_i}{\log_{2} (i+1)} = rel_1 + \sum_{i=2}^p \frac{rel_i}{\log_{2} (i+1)} \cdots (1)$$

로그에 비례해서 아래있는 중요한 문서가 페널티를 받는 데에 있어서, 왜 하필 로그 비례인지에 대해서는, 원래 스무스한 미분가능 반비례 함수를 그리기 위함이었지만, 이에 대한 이론적 바탕은 증명이 됐다고 한다. 위에서 확인한 (1) 식과 매우 유사하지만 조금 다른, DCG에 대한 다른 형태의 식도 존재한다.

$$ DCG_p = \sum_{i=1}^p \frac{2^{rel_i} - 1}{\log_{2} (i+1)} \cdots (2)$$

$\ $위의 (2)식은 페널티를 똑같이 주지만, 제 위치에 잘 존재하는 문서에 대해서는 그만큼 어드밴티지 또한 강하게 준다는 것을 확인할 수 있다. (2)식과 같은 방식은 메이저 웹 서치 회사들이나, Kaggle과 같은 데이터 사이언스 대회 플랫폼에서 많이 사용하는 방식이라고 한다. relevance 값에 해당하는 \(rel_i\) 값이 binary한 경우에, (1)식과 (2)식은 완전히 같다.

\((2^0 - 1) = 0, (2^1 - 1) = 1\) 이므로.

(1)식의 경우 로그의 밑을 2로 취하고 있는데, (1)식을 계산하는 방식으로 추후에 나올 nDCG까지 계산하는 경우에 로그의 밑 부분은 달라져도 크게 상관이 없다고 한다. 하지만, (2)식의 방식을 따라서 nDCG를 계산하는 경우에는 로그 밑의 값이 변하는 것에 분명히 결과도 영향을 받는다고 한다.

nDCG (normalized DCG)

$\ $DCG는 CG와는 다르게 문서들의 순서에 따라 결과 값이 달라지긴 하지만, 우리가 다른 쿼리를 입력해서 다른 결과물들을 얻거나, 또한 얻어낸 결과물들의 갯수가 쿼리마다 다를 때에는 DCG 방식도 사용이 힘들어진다. 따라서, 이러한 한계점을 보정하기 위해 가장 이상적인 DCG 값으로 해당 DCG 값을 나눠준 값을 사용하는데 이를 nDCG라고 하며 식은 다음과 같다.

$$ nDCG_p = \frac{DCG_p}{IDCG_p} $$

여기에서, \(IDCG_p\) 는 가장 이상적인 문서 배열을 가질 때에 \(DCG_p\) 값을 의미한다.

$$IDCG_p = \sum_{i=1}^{|REL_p|} \frac{2^{rel_i} - 1}{\log_{2} (i+1)}$$

nDCG의 개념 또한 매우 간단하며, 아래에서 직접 계산해보면 쉽게 이해할 수 있다. \(nDCG\)의 경우, 다른 측정법들과 마찬가지로 \(partial\ relevance\ feedback\ is\ available\) 한 경우에는 \(IDCG\) 계산이 힘들어지므로, \(nDCG\) 계산도 힘들어지게 된다.

\(partial\ relevance\ feedback\ is\ available\) 한 경우라는 것은, 우리가 유저에게서 얻는 implicit feedback 이나 explicit feedback과 같은 feedback 데이터들을 모두 모을 수 없고 말그대로 부분적으로 (온전하지 못하게) 데이터를 얻어낸 경우를 의미한다.

계산 Example

$\ $검색 엔진에 쿼리를 입력해서 총 6개의 Document들을 얻었다고 가정해보자. 실험에 참가한 참가자들이 각 문서들이 쿼리와 얼마나 관련성이 있는 0에서 3까지 점수를 줬다. 아래와 같이 문서 6개를 \(D_k\)로 표현한다.

$$D_1, D_2, D_3, D_4, D_5, D_6$$

각 문서에 매겨진 관련성 점수는 각각 \(3, 2, 3, 0, 1, 2\) 이다. 이 경우 \(CG_6\)은 \(CG_6 = \sum_{i=1}^{6} rel_i = 3 + 2 + 3 + 0 + 1 + 2 = 11\)이며, 단순 합에 불과하고, 그러므로 문서의 정렬 순서에 영향을 받지 않는다. 다음으로는 차근차근 \(DCG_6\)을 계산해보자.

위와 같이 각 $i$에서 \(rel_i\), \(log_{2} (i+1)\), \(\frac{rel_i}{\log_{2} (i+1)}\)을 계산하고, 최종적으로 아래와 같은 결과 값을 얻는다.

$$DCG_6 = \sum_{i=6}^{6} \frac{rel_i}{\log_{2} (i+1)} = 3 + 1.262 + 1.5 + 0 + 0.387 + 0.712 = 6.861$$

이렇게 \(DCG\) 값을 계산할 때에, \(D_3\)와 \(D_4\)의 위치를 바꾸는 것은 분명히 결과 값에도 영향을 준다. 3번 문서가 4번 문서에 비해 연관성에 높은데, 이 문서를 아래로 내릴 경우, 연관성이 더 높은 문서가 아래 위치함에 따라 페널티를 받게 된다. nDGC는 이상적으로 연관성이 높은 문서들이 다 위에 존재하는 경우에 \(DCG\) 즉, \(IDCG\)를 계산해야 하는데, 이상적으로 연관성이 높은 문서들일수록 위에 존재한다는 것은, 연관성 점수가 단조 감소하도록 문서들이 나열돼야 한다는 것이다. 즉, \(3,\ 2,\ 3,\ 0,\ 1,\ 2\) 는 연관성 점수가 증가 감소를 반복하는 fluctuation을 보여주는데 이러한 것이 아니라, \(3,\ 3,\ 2,\ 2,\ 1,\ 0\) 과 같이 단조 감소하는 방향으로 문서들이 나열돼 있을 때를 가리킨다. 이 경우에 \(IDCG_6\)은 7.141에 해당하며, 따라서 \(nDCG_6 = \frac{DCG_6}{IDCG_6} = \frac{6.861}{7.141} = 0.961\) 이라는 결과를 얻는다.