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?

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/343913/06337776-7a72-a4dd-0abf-757945ea09e4.png)

- $\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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/343913/4a4dddaf-8602-3979-86c8-dc49d82becb0.png)

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

**def.1(relevant entity)**

```math
\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
```

```math
\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).**

```math
\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**

```math
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 のベクトルを得る

```math
\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 分のベクトルを得る

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

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

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

**Learning Algorithm**

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

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

```math
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})
```

- ベイズの定理で分解

```math
\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 つのデータセットで実験

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/343913/6c26fce3-c507-fdd2-eb81-e0ff28c4c89b.png)

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/343913/5c7b217f-071d-29ed-ddba-a5b92b5e3b22.png)

- Top-k レコメンド

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/343913/af65c172-84e3-c6d3-9c3a-c8db893f3b6b.png)

- CTR 予測

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/343913/6f37b4f3-22cb-462d-9278-97f2758a3b9a.png)

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/343913/5570304f-72b0-3b85-cec8-625feb36bd71.png)

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

**case study**

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/343913/a343677d-bb33-8d99-b856-3936646e5dd1.png)

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

## 所感

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