Post

FAWMF

Previous Research


  • Problems with implicit feedback

    암시적 피드백 하에서는 관측된 아이템을 선호 아이템, 미관측된 아이템을 비선호 아이템으로서 추정함. 하지만 관측 행위는 선호 외에 불호와 우연성을, 미관측 행위는 비선호 외에 미노출이라는 경우의 수를 포괄하고 있음. 따라서 미관측된 아이템을 단순히 비선호 아이템으로 치부하는 것은 무리가 있음.

  • 음성 샘플링(Negative Sampling) : 사용자가 상호작용하지 아니한 아이템들 중 일부를, 해당 사용자가 상호작용한 아이템 갯수와 일정 비율로 샘플링하는 방법

    • 예시 : 쌍별 학습(Pair-wise Learning)

      \[\Omega = \Big\{(u,i,j) \mid i \in I_{u} \wedge j \in I \setminus I_{u}\Big\}\]
      • $I$ : 아이템 집합
      • $I_{u} \subset I$ : 사용자 $u$ 가 상호작용한 아이템 집합
      • $i \in I_{u}$ : 사용자 $u$ 가 상호작용한 아이템
      • $j \in I \setminus I_{u}$ : 사용자 $u$ 가 상호작용하지 아니한 아이템
  • 단순 신뢰도 할당 접근법(Simple-Confidence Approach) : 사용자가 상호작용하지 않은 아이템에 대하여, 균일한 값이나 해당 아이템의 인기도에 기반하여 가중치를 할당하는 방법

    • 예시 : WMF(Weighted Matrix Factorization)

      \[\begin{aligned} \overrightarrow{\mathbf{p}}, \overrightarrow{\mathbf{q}} &= \text{arg}\min_{\Theta}{\sum_{(u,i)}{c_{u,i} \cdot \left(r_{u,i} - \overrightarrow{\mathbf{p}}_{u} \cdot \overrightarrow{\mathbf{q}}_{i}\right)^{2} + \lambda_{\Theta}\Vert \Theta \Vert^{2}}} \end{aligned}\]
      • \(c_{u,i}:=1+\alpha \cdot r_{u,i}\) : Confience Weight
  • 노출 확률 모델링 접근법(Exposure Prob. Modeling Approach) : 노출 여부를 상호작용하지 아니한 원인으로서 규정하고, 이를 명시적으로 모델링하는 방법

    • 예시 : ExpoMF(Exposure Matrix Factorization)

      \[\begin{aligned} p\left(r_{i,j},y_{i,j} \mid \mu_{i,j}, \overrightarrow{\mathbf{u}}_{i}, \overrightarrow{\mathbf{v}}_{j} ; \lambda\right) &= \underbrace{p\left(y_{i,j} \mid \mu_{i,j}\right)}_{\text{Exposure Prob.}} \cdot \overbrace{p\left(r_{i,j} \mid \overrightarrow{\mathbf{u}}_{i}, \overrightarrow{\mathbf{v}}_{j} ; \lambda\right)^{y_{i,j}}}^{\text{Click Prob. under Exposure}} \cdot \underbrace{\mathbf{I}\left[r_{i,j}=0\right]^{1-y_{i,j}}}_{\text{non-Click Prob. under non-Exposure}} \end{aligned}\]
      • \(r_{i,j} = \big\{1,0\big\} \in \mathbf{R}_{M \times N}\) : 클릭 변수
      • \(y_{i,j} = \big\{1,0\big\} \in \mathbf{Y}_{M \times N}\) : 노출 변수

FAWMF


  • 선행 연구의 한계점
    • 음성 샘플링(Negative Sampling) : 균일 샘플링 전략을 취하는 경우 주요 정보를 포함하고 있는 음성 샘플이 선택될 가능성이 낮고, 샘플링 비율을 높일 경우 계산 비용이 증가함
    • 단순 신뢰도 할당 접근법(Simple-Confidence Approach) : 개별 음성 아이템에 맞춤화된 가중치를 할당할 수 없음
    • 노출 확률 모델링 접근법(Exposure Prob. Modeling Approach) : 모든 음성 아이템에 대하여 맞춤화된 가중치를 할당하므로 계산 비용이 높고, 사용자와 아이템 간 노출 확률이 독립적이라는 가정은 현실적이지 않음
  • FAWMF(Fast Adaptively Weighted Matrix Factorization) : 효율적 학습과 적응형 가중치 할당을 동시에 달성한 방법론
    • 사용자에 대하여 커뮤니티 구조(Community Structure)을 도입함으로써 노출 확률의 사용자 간 연관성을 반영함
    • VAE(Variational AutoEncoder) 를 활용하여 개별 노출 확률 파라미터를 커뮤니티별 노출 확률 함수로 대체함
    • fBGD(fast Batch Gradient Descent) 알고리즘을 활용하여 중복 계산 항목을 캐싱함으로써 모든 음성 아이템을 처리하면서도 효율성을 유지함

How to Modeling


01

Analyses of EXMF from Bayesian Framework

  • 노출 여부의 사전 분포

    \[\begin{aligned} y_{i,j} \sim \text{Bernoulli}\left(\mu_{i,j}\right) \end{aligned}\]
    • \(y_{i,j} = \big\{1,0\big\} \in \mathbf{Y}_{M \times N}\) : Exposure Variable
    • \(\mu_{i,j}\) : Hyper-Parameter
  • 노출 여부의 우도 함수

    \[\begin{aligned} r_{i,j} \mid y_{i,j} \sim \mathcal{N}\left(\overrightarrow{\mathbf{u}}_{i} \cdot \overrightarrow{\mathbf{v}}_{j}, \lambda^{-1}\right) \end{aligned}\]
    • \(r_{i,j} = \big\{1,0\big\} \in \mathbf{R}_{M \times N}\) : Click Variable
  • 노출 여부의 사후 분포

    \[\begin{aligned} p\left(y_{i,j} \mid r_{i,j}\right) \propto \mathcal{L}\left(r_{i,j} \mid y_{i,j}\right) \cdot \pi\left(y_{i,j}\right) \end{aligned}\]

Approx. Dist.

  • 노출 여부의 사후 분포의 근사 분포

    \[\begin{aligned} y_{i,j} \mid \gamma_{i,j} \sim \text{Bernoulli}\left(\gamma_{i,j}\right) \end{aligned}\]
  • Parameter $\gamma$

    \[\begin{aligned} \gamma_{i,j} &= \mathcal{G}\left(i,j,\mathbf{R} \mid \Theta, \mathbf{w}, \mathbf{a}, \mathbf{b}\right)\\ &= \overrightarrow{\Theta}_{i} \cdot \overrightarrow{\Phi}_{j} \end{aligned}\]
    • \(\overrightarrow{\Theta}_{i} \in \Theta_{M \times D}\) : Community Membership Vector
      • Community Memebership is Probability : \(\Vert \overrightarrow{\Theta}_{i} \Vert_{L1} = 1, \theta_{i,d} \ge 0\)
    • \(\overrightarrow{\Phi}_{j} \in \Phi_{N \times D}\) : Exposure Prob. of Item $j$ for each Communities

      \[\begin{aligned} \overrightarrow{\Phi}_{j} = \sigma \left(w_{j} \sum_{l \in U}{\overrightarrow{\Theta}_{l} \cdot \alpha_{l} \cdot r_{l,j}} + b_{j}\right) \end{aligned}\]
      • \(\sum_{l \in U}{\overrightarrow{\Theta}_{l}} \cdot \alpha_{l} \cdot r_{l,j}\) : Exposure Contribution of Item $j$ for each Communities
        • \(\alpha_{i} \in \overrightarrow{\mathbf{a}}_{M}\) : User Influence
      • \(w_{j} \in \overrightarrow{\mathbf{w}}_{N}\) : Weight
      • \(b_{j} \in \overrightarrow{\mathbf{b}}_{N}\) : Bias
      • \(\sigma\) : Activation Function, Sigmoid

Optimization

  • ELBO

    \[\begin{aligned} \text{ELBO} &= \underbrace{\sum_{(i,j)}{\gamma_{i,j} \cdot \left(\overrightarrow{\mathbf{u}}_{i} \cdot \overrightarrow{\mathbf{v}}_{j} - r_{i,j}\right)^{2}}}_{\text{Clik under Exposure}} + \underbrace{\sum_{(i,j)}{\left(1-\gamma_{i,j}\right) \cdot \left(\epsilon - r_{i,j}\right)^{2}}}_{\text{non-Clik under non-Exposure}} - \sum_{(i,j)}{D_{KL}\Big[q\left(y_{i,j} \mid \gamma_{i,j}\right) \parallel \pi\left(y_{i,j}; \mu_{i,j}\right)\Big]} \end{aligned}\]
  • KL Divergence by analytical representation of Bernoulli distribution

    \[\begin{aligned} D_{KL}\Big[q\left(y_{i,j} \mid \gamma_{i,j}\right) \parallel \pi\left(y_{i,j}; \mu_{i,j}\right)\Big] &= \sum_{y_{i,j}}{q\left(y_{i,j} \mid \gamma_{i,j}\right) \cdot \log{\frac{q\left(y_{i,j} \mid \gamma_{i,j}\right)}{\pi\left(y_{i,j}; \mu_{i,j}\right)}}}\\ &= \gamma_{i,j} \cdot \log{\frac{\gamma_{i,j}}{\mu_{i,j}}} + \left(1-\gamma_{i,j}\right) \cdot \log{\frac{1-\gamma_{i,j}}{1-\mu_{i,j}}} \end{aligned}\]
  • Optimization

    \[\begin{aligned} \overrightarrow{\mathbf{u}}, \overrightarrow{\mathbf{v}}, \overrightarrow{\mathbf{\Theta}}, \alpha, w, b \mid \mu, \epsilon, D, K &= \text{arg} \min{-\text{ELBO}} \end{aligned}\]

fBGD

  • fBGD(fast-Batch Gradient Descent) : 역전파 시 반복해서 계산해야 하는 일부 항목을 캐싱함으로써 학습 속도를 향상시키는 배치 경사하강법

  • 반복 계산이 발생하는 요소:

    \[\begin{aligned} \frac{\partial \mathcal{J}}{\partial \alpha_{l}} &= \sum_{j \in I}{\frac{\partial \mathcal{J}}{\partial \overrightarrow{\Phi}_{j}} \cdot \frac{\partial \overrightarrow{\Phi}_{j}}{\partial \alpha_{l}}} \end{aligned}\]
  • 목적 함수 $\mathcal{J}=-\text{ELBO}$ 를 아이템 $j$ 에 대한 커뮤니티 노출 확률 $\overrightarrow{\Phi}_{j}$ 에 대하여 미분한 결과:

    \[\begin{aligned} \frac{\partial \mathcal{J}}{\partial \overrightarrow{\Phi}_{j}} &= \sum_{i \in U}{\Big[\left(\overrightarrow{\mathcal{u}}_{i}^{T}\overrightarrow{\mathcal{v}}_{j}\right)^{2} - 2r_{i,j}\left(\overrightarrow{\mathcal{u}}_{i}^{T}\overrightarrow{\mathcal{v}}_{j}- \epsilon\right) - \epsilon^{2}\Big] \cdot \overrightarrow{\Theta}_{i}}\\ &= \sum_{i \in U}{\left(\overrightarrow{\mathcal{u}}_{i}^{T}\overrightarrow{\mathcal{v}}_{j}\right)^{2} \cdot \overrightarrow{\Theta}_{i}} - 2\sum_{i \in U}{r_{i,j} \cdot \overrightarrow{\mathcal{u}}_{i}^{T}\overrightarrow{\mathcal{v}}_{j} \cdot \overrightarrow{\Theta}_{i}} + 2\sum_{i \in U}{r_{i,j} \cdot \epsilon \cdot \overrightarrow{\Theta}_{i}} - \epsilon^{2} \sum_{i \in U}{\overrightarrow{\Theta}_{i}}\\ &= \sum_{i \in U}{\left(\overrightarrow{\mathcal{u}}_{i}^{T}\overrightarrow{\mathcal{v}}_{j}\right)^{2} \cdot \overrightarrow{\Theta}_{i}} - \epsilon^{2} \sum_{i \in U}{\overrightarrow{\Theta}_{i}} - 2\sum_{i \in U}{r_{i,j} \cdot \left(\overrightarrow{\mathcal{u}}_{i}^{T}\overrightarrow{\mathcal{v}}_{j} - \epsilon\right)\cdot \overrightarrow{\Theta}_{i}} \end{aligned}\]
  • 사용자-잠재요인 벡터와 아이템-잠재요인 벡터의 내적값 풀이:

    \[\begin{aligned} \overrightarrow{\mathcal{u}}_{i}^{T}\overrightarrow{\mathcal{v}}_{j} &= \sum_{g=1}^{K}{u_{i,g} \cdot v_{j,g}}\\ \left(\overrightarrow{\mathcal{u}}_{i}^{T}\overrightarrow{\mathcal{v}}_{j}\right)^{2} &= \left(\sum_{g=1}^{K}{u_{i,g}v_{j,g}}\right) \cdot \left(\sum_{h=1}^{K}{u_{i,h}v_{j,h}}\right)\\ &=\sum_{g=1}^{K}{\sum_{h=1}^{K}{u_{i,g}u_{i,h} \cdot v_{j,g}v_{j,h}}}\\ \end{aligned}\]
  • 캐싱:

    \[\begin{aligned} M_{g,h} &= \sum_{i \in U}{u_{i,g}u_{i,h} \cdot \overrightarrow{\Theta}_{i}}\\ S &= \sum_{i \in U}{\overrightarrow{\Theta}_{i}} \end{aligned}\]
  • 캐싱을 적용한 $\overrightarrow{\Phi}_{j}$ 에 대한 $\mathcal{J}$ 미분값:

    \[\begin{aligned} \frac{\partial \mathcal{J}}{\partial \overrightarrow{\Phi}_{j}} &= \sum_{g=1}^{K}{\sum_{h=1}^{K}{M_{g,h} \cdot v_{j,g}v_{j,h}}} - \epsilon^{2} \cdot S - 2\sum_{i \in U}{r_{i,j} \cdot \left(\overrightarrow{\mathcal{u}}_{i}^{T}\overrightarrow{\mathcal{v}}_{j} - \epsilon\right)\cdot \overrightarrow{\Theta}_{i}} \end{aligned}\]
  • $\alpha_{l}$ 에 대한 $\overrightarrow{\Phi}_{j}$ 미분값:

    \[\begin{aligned} \frac{\partial \overrightarrow{\Phi}_{j}}{\partial \alpha_{l}} &= \overrightarrow{\Phi}_{j} \cdot \left(1-\overrightarrow{\Phi}_{j}\right) \cdot \overrightarrow{\Theta}_{i} \cdot w_{j} \cdot r_{l,j} \end{aligned}\]
This post is licensed under CC BY 4.0 by the author.