Alpha-Beta-NDCG

왜 다양성이 중요한가.

Diversity에 대한 대한 요구

유저는 여러 취향을 가지고 있고 추천의 결과가 한 가지 종류의 아이템으로만 이루어져 있다면 추천이 불완전하다고 생각할 것이다.

Novelty에 대한 요구

추천은 일반적으로 list 형태로 주어지며, 유저는 list를 좌에서 우로, 혹은 위에서 아래로 탐색하는 경우가 일반적이다. $N$개의 추천 아이템이 주어진 경우, $k \leq N$인 $k$을 유저가 클릭한 경우, 유저가 $1, \dots, k-1$까지 보지 않았던 이유가 존재할 것이며, 이는 rank가 $k$ 미만인 아이템이 유저가 relevant하지 않았다고 판단했기 때문일 가능성이 높다, $i_1, i_2, \dots, i_{k-1}$는 서로 닮아 있을 가능성이 높다. 이를 대비해서, $k$번째 아이템은 이전의 아이템과 충분히 다른 아이템인 게 더 유익할 수 있다.

유저가 로맨스 영화와 호러 영화를 둘 다 좋아한다고 했을 때, 로맨스 영화만 추천하는 추천 모델은 불완전한 모델이다. 유저가 로맨스를 좋아할 것이라 판단한 후에 로맨스 영화 5개를 추천했는데 성공해도 유저는 사실 랭크 상위의 영화 1-2개 정도밖에 보지 않을 것이다. 추천에 임의로 다른 영화를 한 두개 섞는다고 하면, 이 판단이 틀렸다고 하더라도 한 번의 기회를 더 얻을 수 있다.

Diversity와 Novelty를 고려한 Metric $\alpha\beta$-nDCG

Notation

• $\alpha_\phi$: 토픽(취향이나 선호도, 이하 토픽이라 칭함)
• 유저는 topic의 집합을 선호도로 갖고 있으며 $p(\alpha_\phi \vert u)$는 유저가 그 토픽을 선호할 확률을 나타낸다.
• 아이템 또한, topic의 집합을 갖고 있으며 아이템의 토픽은 알려져 있다고 가정한다.

특정 유저 $u$가 rank $S \in \{1, 2, \dots, n\}$에 있는 item $i$를 선호할 확률은

$$p(R=1 \vert u, i) = 1 - \prod_{\phi} [1 - p(\alpha_\phi \vert u, i) p(\alpha_\phi \vert u, S)]$$

로 정의된다.

Diversity Consideration

$p(\alpha_\phi \vert u, i)$ (Diversity Term)는 Diversity를 고려한 식이다. 기존 ndcg에서 item 단위의 hit을 고려하는 것과는 별개로, topic 단위의 hit을 고려한다.

$p(\alpha_\phi \vert u, i)$는 그 유저가 유저의 선호도 $\alpha_\phi$를 만족하는 정도를 나타내는데, 이를 별도로 정의하는 이유는 같은 장르이더라도, 유저가 특정 아이템을 선호할 수 있고 선호하지 않을 수 있기 때문이다. 예를 들어서, 나는 밴드 오브 브라더스는 좋아하지만 오! 인천은 그다지 좋아하지 않는다.

$$p(\alpha_\phi \vert u, i) = \begin{cases} 0 & \text{아이템의 장르가 다름} \\ \alpha & \text{유저가 그 장르를 좋아하는데, 유저가 클릭하지 않은 경우} \\ \beta & \text{유저가 그 장르를 좋아하고, 유저가 그 아이템을 클릭한 경우} \\ \end{cases}$$

Diversity Term은 유저가 그 아이템을 좋아하거나, 그 장르를 선호하거나에 따라 score에 대해 차등을 주는 식으로 모델링된다. 간단히 요약하자면, 기존 nDCG에서는 유저가 실제로 클릭한(relevant) 대해서만 추천을 준다고 가정하는 반면, 유저가 좋아하는 장르에 대한 추천에도 약간이나마 선호도를 부여한다.

$\alpha, \beta$에 대한 정의는 논문에서 자세히 되어있지 않지만, $p(\alpha \vert u), p(\alpha \vert i)$에 따라 적절히 정의될 수 있을 것 같다.

Novelty Consideration

$p(\alpha_\phi \vert u, S)$ (Novelty Term)는 유저가 특정 위치 $S\in \{1, 2, \dots, n\}$에 존재하는 추천에 대해 얼마나 만족하는지를 나타내는 지표이다. 이를 별도로 모델링하는 이유는, 유저가 상위 랭크 $1, 2, \dots, S-1$에서 특정 토픽 $\alpha_\phi$를 봤다면, rank $S$에서 같은 토픽 $\alpha_\phi$인 아이템을 보더라도 만족도가 그리 높지 않을 것이라는 가정을 포함하고 있다.

$$p(\alpha_\phi \vert u, S) = p(\alpha_\phi \vert u) \prod_{j = 1}^S [1-p(\alpha_\phi \vert u, i_j)]$$

유저가 이전에 본 항목에 같은 토픽의 아이템이 많이 들어있을 경우, Novelty Term은 감소한다. 새로운 토픽의 아이템이 추천될 경우, 이 값은 증가한다. 증가폭은 유저가 그 토픽을 선호할 확률 $p(\alpha_\phi \vert u)$에 비례한다.

구현

약간 다르게 구현한 점

1. user-item rating이 binary이다.

한계

논문을 읽을 때까지만 하더라도 "오오...오오...아주 좋은 work이군..." 생각하고 있었다. 하지만 실제로 이 논문을 구현해보고 테스트해보니, 실제 이 metric을 활용하기 힘든 요소가 존재한다.

첫번째로는, ab-ndcg 계산 자체가 상당히 느리다는 점이다. k개의 아이템 리스트에 대한 평가를 하자면, k번 루프를 돌아야 한다. k개의 아이템에 대해, topic마다 또 루프를 돌아야 한다. 이건 구현을 빠르게 하면 어떻게 해결할 수 있을 것 같긴 한데, 아무리 빠르게 하더라도 기존 ndcg에 비해 수배-수십배 정도 속도가 느려지는 건 어쩔 수 없다. 근데 ndcg 자체도 계산하는 데 시간이 꽤 드는 비싼 metric이다.

Test data에 user가 실제로 interact한 아이템이 없는 경우, 여러 추천 모델의 ab-ndcg 값이 비슷해진다. 즉, 설명력이 상당히 떨어진다. 실제 추천 시스템의 평가에서는 (여러 현실적인 이유로 인해) Truncated NDCG같은 top-K 개에 대해서만 평가를 하는 경우가 일반적인데, 이러면 추천 시스템이 만든 top-k 추천에 실제 유저가 interact한 값이 없는 경우가 많다. 이 경우 추천에 대한 평가가 부정확하다.

느낀 점

팔랑귀라 그런지, nDCG가 내가 믿고 있던 것보다 훨씬 불완전한 메트릭이라는 말에 설득이 된 것 같다. 다만 이런 메트릭을 혼자 쓰면 다른 것들과 비교를 할 수가 없지 않나? 싶은 생각도 들었다. Novelty가 중요하다는 얘기만 들었었는데, 그럴 듯 한 설명을 들은 것은 처음이라 신기했다. Diversity를 고려한 Offline Metric에 대해 조금 더 공부를 해 보려고 생각하고 있었는데, 지금 이 방법을 구현해봤을 때 결과가 그렇게 만족스럽지는 않아서, 약간 난감해졌다.

Axioms for Diverse Ranking Evaluation

추천 리스트와, 그 추천 리스트에 대한 평가 메트릭에 관한 공리를 논문에 같이 정의해놨다. 실제로 논문에서 8가지 공리가 정의되어 있지만, 대략적으로 요약하자면 다음과 같다. (논문 내에서 대충 적어도 큰 틀에서는 맞는데, 상충되는 부분에 대해 좀 더 자세히 정의되어 있다.)

1. 두 아이템의 토픽이 완전히 같다고 가정하면, 유저는 relevancy가 더 높은 아이템이 추천되는 추천 리스트를 선호한다.

2. 유저가 좋아하는 아이템이 추천 리스트에 포함될 경우, 이 아이템이 더 상위 랭크에 있는 추천 리스트가 더 하위 랭크에 있는 추천 리스트보다 선호된다.

3 한 추천 리스트에서 같은 토픽이 너무 자주 추천되는 경우, 이 토픽이 유저가 선호하는 토픽이라 할 지라도 유저가 좋아하지 않는 토픽의 아이템을 더 선호할 수 있다.

4. 유저는 본 적 없는 아이템을, 이미 싫어하는 아이템보다 더 선호한다.

---