RippleNet

RippleNet: Propagating User Preferences on the Knowledge Graph for Recommender Systems

• 2018/08 に投稿された NLP の論文
• https://arxiv.org/pdf/1803.03467.pdf

TL;DR

• 観測データが少ない(コールドスタートな)場合に、推薦精度を向上させるためにユーザの補助情報(年齢など)を利用することがある。
• 補助情報としてナレッジグラフを利用した推薦フレームワーク(RippleNet)を提案。
• 映画、本、ニュースなどの推薦評価で SOTA

導入

グラフ G の構成要素

• (h, r, t) -> (head, relation, tail)の関係
  • e.g. (Jurassic Park, film.film.director, Steven Spielberg)

やりたいこと

• user u が item v をクリックする確率を予測
  • $\hat{y}_{u v}=\mathcal{F}(u, v ; \Theta)$
    • Θ はモデルのパラメータ

What is RippleNet?

• $\mathcal{V}_{u}$:ユーザのクリック履歴(seeds)
• A ripple set $\mathcal{S}_{u}^{k}$ : seed から k 離れた triples
  • 例えば、Hop1 は seed から 1 離れた triples
• embedding
  • 黄色のブロック
    • item v の embedding
      • 何らかの特徴量でベクトル化
  • 緑色のブロック
    • ユーザの item v に対するレスポンスを含んだ embedding
  • グレーのブロック
    • 最終的なユーザの embedding

グラフ知識を用いる利点は、より深いユーザの embedding を得られる可能性があること。
例えば、"Forrest Gump"を視聴したユーザは、Tom Hanks のファンかもしれない。なので、"The Terminal" や"Cast Away"といった彼の別の作品を好むかもしれない。

def.1(relevant entity)

\mathcal{E}_{u}^{k}=\left\{t \mid(h, r, t) \in \mathcal{G} \text { and } h \in \mathcal{E}_{u}^{k-1}\right\}, \quad k=1,2, \ldots, H

\mathcal{E}_{u}^{0}=\mathcal{V}_{u}=\left\{v \mid y_{u v}=1\right\}

• k = 0: ユーザのクリック履歴から生成
• k = 1: ユーザがクリックしたアイテム情報から relation を辿って到達できる距離 1 のアイテム集合

def.2(ripple set).

\mathcal{S}_{u}^{k}=\left\{(h, r, t) \mid(h, r, t) \in \mathcal{G} \text { and } h \in \mathcal{E}_{u}^{k-1}\right\}, \quad k=1,2, \ldots, H

ripple set におけるユーザーの潜在的な好みの強さは、ホップ数 k の増加とともに弱まると考えられる。(図の青色が薄まっていく部分）
ユーザの seed から離れすぎているエンティティに関しては、むしろノイズになる可能性が高い。よって、シナリオに関係のあるカテゴリに限定して利用した方が、効果的に関係性を表すことができる。

Propagation

p_{i}=\operatorname{softmax}\left(\mathbf{v}^{\mathrm{T}} \mathbf{R}_{i} \mathbf{h}_{i}\right)=\frac{\exp \left(\mathbf{v}^{\mathrm{T}} \mathbf{R}_{i} \mathbf{h}_{i}\right)}{\sum_{(h, r, t) \in \mathcal{S}_{u}^{1}} \exp \left(\mathbf{v}^{\mathrm{T}} \mathbf{R h}\right)}

• item v は d 次元のベクトルで表現できる
  • ベクトル化の方法は何でも可
• $\mathbf{R}_{i} \in \mathbb{R}^{d \times d}$
  • relation
• $\mathbf{h}_{i} \in \mathbb{R}^{d}$
  • head の item
• $p_{i}$ : item v と head item との類似性
  • 例えば、"Forrest Gump"と"Cast Away"は directors で強く結びついている
• Hop 1 なアイテムは 4 つあるので、Rh のブロックも 4 つ

relevance probabilities 取得後、Hop 1 のベクトルを得る

\mathbf{o}_{u}^{1}=\sum\left(h_{i}, r_{i}, t_{i}\right) \in \mathcal{S}_{u}^{1} (p_{i} \mathbf{t}_{i})

• $\mathbf{t}_{i} \in \mathbb{R}^{d}$
  • tail

この操作を繰り返すことで、Hop H 分のベクトルを得る

\mathbf{u}=\mathbf{o}_{u}^{1}+\mathbf{o}_{u}^{2}+\ldots+\mathbf{o}_{u}^{H}

• $\mathbf{o}_{u}^{H}$ はそれまでの情報も含有している。必要なことらしい

\hat{y}_{u v}=\sigma\left(\mathbf{u}^{\mathrm{T}} \mathbf{v}\right)

Learning Algorithm

\max p(\Theta \mid G, Y)

• モデルパラメータ Θ の最大化を目指す

p(\Theta \mid \mathcal{G}, \mathrm{Y})=\frac{p(\Theta, \mathcal{G}, \mathrm{Y})}{p(\mathcal{G}, \mathrm{Y})} \propto p(\Theta) \cdot p(\mathcal{G} \mid \Theta) \cdot p(\mathrm{Y} \mid \Theta, \mathcal{G})

• ベイズの定理で分解

\begin{aligned}
\min \mathcal{L}=&-\log (p(\mathrm{Y} \mid \Theta, \mathcal{G}) \cdot p(\mathcal{G} \mid \Theta) \cdot p(\Theta)) \\
=& \sum_{(u, v) \in \mathrm{Y}}-\left(y_{u v} \log \sigma\left(\mathbf{u}^{\mathrm{T}} \mathbf{v}\right)+\left(1-y_{u v}\right) \log \left(1-\sigma\left(\mathbf{u}^{\mathrm{T}} \mathbf{v}\right)\right)\right) \\
&+\frac{\lambda_{2}}{2} \sum_{r \in \mathcal{R}}\left\|\mathbf{I}_{r}-\mathbf{E}^{\mathrm{T}} \mathbf{R E}\right\|_{2}^{2}+\frac{\lambda_{1}}{2}\left(\|\mathbf{V}\|_{2}^{2}+\|\mathbf{E}\|_{2}^{2}+\sum_{r \in \mathcal{R}}\|\mathbf{R}\|_{2}^{2}\right)
\end{aligned}

• 最終的なロス関数

実験

3 つのデータセットで実験

• IMO. d,H ともに小さめ
• KG は Microsoft Satori で作成

• Top-k レコメンド

• CTR 予測

• ripple set のサイズは大きすぎるとよろしくない

• Hop 数も大きすぎるとノイズになってよろしくない

case study

• 推薦記事が選ばれたパスがなんとなくわかる
  • "Navy SEAL"–"Special Forces"–"Gun"–"Police"
• IMO. すべての道は"Donald Trump"に通じる、感ある

所感

• オンラインでの使い方が謎い
  • user embedding の生成に item v の入力が必要。
    • 予測のたびに、ユーザのクリックログが必要となりそう。
    • 処理時間厳しい気がする
  • あらかじめ、user embedding を生成して保存しておけるなら、最終的な内積演算のみで済む。
    • 過去のクリック履歴を item v に用いて、user embedding 生成するかぁ