CLiMF

prior research

• BPR Rendle, S., Freudenthaler, C., Gantner, Z., & Schmidt-Thieme, L. (2012). BPR: Bayesian personalized ranking from implicit feedback. arXiv preprint arXiv:1205.2618.

• BPR(Bayesian Personalized Ranking)은 OCCF(One-Class Collaborative Filtering)의 AMAU(All Missing As Unknown) 문제를 AMAN(All Missing As Negative), 즉 관측과 미관측의 이진 범주를 구분하는 판별 문제로 처리하지 않고 관측과 미관측의 선호 강도에 차등을 두는 순위 문제로 전환하였음

• 하지만 AUROC(Area Under the ROC Curve)를 최적화 목표로서 설정함. 이는 모든 관측이 모든 미관측보다 높은 점수를 취하도록 할 뿐, 낮은 순위에서의 우열과 높은 순위에서의 우열에 차등을 두지 않음. Top-k 추천 품질을 개선하기 위해서는 상위 편향 지표(top-biased measure)를 최적화 목표로서 설정하여야 함.

idea

• CLiMF(Collaborative Less-is-More Filtering) : 상위 편향 지표인 MRR(Mean Reciprocal Rank) 최적화를 수행하는 학습 전략

• RR(Reciprocal Rank): 사용자 $u$ 에 대하여 정답 아이템이 처음 등장하는 순번의 역수

  \[\begin{aligned} \mathrm{rr} &= \frac{1}{\text{Rank of 1st Relevent Item}} \end{aligned}\]

• MRR(Mean Reciprocal Rank): 모든 사용자에 대하여 정답 아이템이 처음 등장하는 평균적인 순번

  \[\begin{aligned} \mathrm{mrr} &= \frac{1}{\vert U \vert}\sum_{u \in U}{\mathrm{RR}_{u}} \end{aligned}\]

mrr optimization

• smoothing trick:

  \[\begin{aligned} \sigma(x) &= \frac{1}{1 + \exp{-x}} \end{aligned}\]

• 사용자 벡터와 아이템 벡터의 내적값이 클수록 해당 아이템이 상위에 랭크될 가능성이 높다는 뜻으로 이해할 수 있음:

  \[\begin{aligned} \frac{1}{\mathrm{Rank}(u,i)} &\approx \sigma\left(\langle\mathbf{p},\mathbf{q}\rangle\right) \end{aligned}\]

  Dot Product	Sigmoid Function
  \(\langle\mathbf{p},\mathbf{q}\rangle \to +\infty\)	\(\sigma \to 1\)
  \(\langle\mathbf{p},\mathbf{q}\rangle \to 0\)	\(\sigma \to 0.5\)
  \(\langle\mathbf{p},\mathbf{q}\rangle \to -\infty\)	\(\sigma \to 0\)

• 순위는 다른 아이템과의 상대적 위치이므로, 아이템 간 선호의 우열을 다루는 항목이 필요하며, 이때 사용자 $u$ 와 아이템 $i$ 의 내적값이 $j$ 보다 더 클 가능성이 높을수록 순위가 더 높다는 뜻으로 이해할 수 있음:

  \[\begin{aligned} \mathbb{I}\left[\mathrm{Rank}(u,i) < \mathrm{Rank}(u,j)\right] = \begin{cases} 1, \quad &\text{If $i$ is Higher than $j$}\\ 0, \quad &\text{Otherwise} \end{cases} \end{aligned}\]

• dot product comparison:

  \[\begin{aligned} \sigma\left(\langle\mathbf{p},\mathbf{q}_{i}\rangle-\langle\mathbf{p},\mathbf{q}_{j}\rangle\right) \end{aligned}\]

  Dot Product	Sigmoid Function
  \(\langle\mathbf{p},\mathbf{q}_{i}\rangle >\langle\mathbf{p},\mathbf{q}_{j}\rangle\)	\(\sigma \to 1\)
  \(\langle\mathbf{p},\mathbf{q}_{i}\rangle=\langle\mathbf{p},\mathbf{q}_{j}\rangle\)	\(\sigma \to 0.5\)
  \(\langle\mathbf{p},\mathbf{q}_{i}\rangle <\langle\mathbf{p},\mathbf{q}_{j}\rangle\)	\(\sigma \to 0\)

• objective function:

  \[\begin{aligned} \mathcal{J} &= \sum_{u \in U} \sum_{i \in I_{u}^{+}}{\left(\ln{\sigma\left(\langle\mathbf{p},\mathbf{q}_{i}\rangle\right)} + \sum_{j \in I \setminus I_{u}^{+}}{\ln{\sigma\left(\langle\mathbf{p},\mathbf{q}_{i}\rangle-\langle\mathbf{p},\mathbf{q}_{j}\rangle\right)}}\right)} - \lambda_{\Theta}\Vert \Theta \Vert^{2} \end{aligned}\]