Temporal-Contextual Recommendation in Real-Time

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/135044/94937d6f-18fb-19a6-f73d-768e84426a31.png)

https://dl.acm.org/doi/10.1145/3394486.3403278

2020年の Knowledge Discovery and Data Mining conference (KDD) の Applied Data Science track (≠ Research track) でベストペーパー賞を取った論文。AWS AI Labsのメンバーらによる著作。Amazon Web Services (AWS) が提供しているAmazon Personalizeというサービスではコアアルゴリズムのひとつとして実装されている。

https://www.amazon.science/blog/amazon-researchers-win-best-paper-award-at-kdd

## どんな論文か

- 商品や作品などのアイテムの推薦システムとして使うモデル **Hierarchical Recurrent Network with meta data (HRNN-meta)** を提案
    - 1つのレイヤーでセッション内のdynamicsをモデルし、もう片方のレイヤーでセッション外のdynamicsを捉える
    - ユーザーやアイテムのメタデータを利用
    - エンコードしたフィードバック情報を特徴に含めることでimplicit negativeに対処
- ネガティブサンプリングを用いた効率的なトレーニング

HRNN-metaはAWSにサービスとしてデプロイされており誰でも利用可能。

## 先行研究と比べてどこがすごいのか

HRNN自体は [Personalizing Session-based Recommendations with Hierarchical Recurrent Neural Networks](https://dl.acm.org/doi/10.1145/3109859.3109896) で提案されたもの。画期的なアイデアというよりも先行研究の組み合わせにオリジナルの改善を足すことでSOTAを実現したという印象。

## 技術や手法のキモはどこか

推薦システムの目的はユーザーにとってちょうどいいタイミングでほしいアイテムを提供すること。典型的には以下の二つの情報を利用。

- user-item interaction histories (クリック・評価・視聴時間)
- user / item features (年齢・性別・ジャンル・価格)
    - メタデータという言葉が出てきたらこちらを指す

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/135044/0e39f311-a0fc-34f8-fd0f-ef94322bd724.png)
(出典: https://www.youtube.com/watch?v=M7FqgXySKYk )

### 工夫1. [Hierarchical Recurrent Neural Network (HRNN)](https://dl.acm.org/doi/10.1145/3109859.3109896)

古典的な **行列分解** の手法ではインタラクションイベントのタイミングや順序を考慮できず、ユーザーの嗜好の変化に対応できない。イベントの時間的順序や傾向をモデリングするために **Recurrent Neural Network (RNN)** を用いた。RNN にも vanilla RNN や LSTM など様々な種類があるが、ここでは特にメモリ効率の良い **Gated Recurrent Unit (GRU)** を採用している。インタラクションの履歴をもとに、あるユーザーがあるアイテムと "interact" する確率を予測する。

インタラクションの履歴は数百ステップを超えるような場合もあるため、勾配消失によって学習が効率的に進まない。そこで、単純に履歴をすべて concatenate するのではなく、ウェブページなどの閲覧セッションごとに入力データを区切る。GRU 自体も、セッション内のユーザーの行動をモデリングするための **session-level GRU** (GRU\_ses) と、セッション外でユーザーの長期的な興味の変遷をモデリングするための **user-level GRU** (GRU\_usr) の2つを組み合わせる。これを **Hierarchical GRU (HGRU)** と呼ぶ。（より一般には HRNN と呼ぶ。）

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/135044/b8b3f936-0ac8-9459-d690-602013b3f567.png)

まず、最初のセッションの履歴情報で session-level GRU を計算。

![image (4).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/135044/a8802c21-6b28-31ec-139f-65b7c6f57c6b.png)
(出典: https://www.youtube.com/watch?v=M7FqgXySKYk )

セッションの終わりの session-level GRU の隠れ状態 $s_m$ を入力して user-level GRU を更新。

![image (5).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/135044/38ffbd95-d30c-ef67-f9e9-4691e800bafb.png)
(出典: https://www.youtube.com/watch?v=M7FqgXySKYk )

user-level GRU の隠れ状態を入力して session-level GRU を初期化。次のセッションのデータで計算。

![image (6).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/135044/6c9818d3-5d63-dfc3-2e03-8c073356d98c.png)
(出典: https://www.youtube.com/watch?v=M7FqgXySKYk )

### 工夫2. Feedback Encoding

上記スライド (先行研究の解説動画より引用) ではアイテムIDを入力としていた。本論文ではユーザーのメタデータおよびフィードバック情報も concatenate している。

- ユーザーのメタデータ
    - user features (年齢など)
    - user dynamic features (デバイス、言語など)
- フィードバック情報
    - ひとつ前のアイテムに対するインタラクション (評価、購入数、価格、閲覧時間など)

特にフィードバック情報により暗黙的なネガティブ (クリックせずにスルー、クリックしたけど短時間だけ見てやめる、など) への反応がよくなった。

### 工夫3. アイテム情報も利用

HRNN のデコーダーでは j 番目のアイテムのスコアを $$\phi_j(\mathbf{h_k})=(\mathbf{w}^\top_j\mathbf{h}_k+b_j)$$ のように計算する。これに加えて、アイテムの特徴ベクトル $\mathbf{f}_j$ の埋め込み表現を重みとみなした場合の計算 $$\phi^\prime_j(\mathbf{h_k},\,\mathbf{f}_j)=(\mathbf{w}(\mathbf{f}_j)^\top\mathbf{h}_k+b(\mathbf{f}_j))$$ も並行して行う。これの重み付き和 $$\tilde{\phi_j}(\mathbf{h_k})=(1-\lambda)\phi_j(\mathbf{h_k})+\lambda\phi^\prime_j(\mathbf{h_k,\,\mathbf{f}_j})$$ をアイテム j のスコアとする。ただし、$0\le\lambda\le 1$はミキシングパラメーターで、訓練時にはランダムの値とする。推論時に $\lambda=1$ とすればメタデータに基づいたコールドスタートの推論を行うことができる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/135044/17dd32da-6fa0-b09f-9049-cf345fdf9a70.png)

### 工夫4. Negative Sampling

アイテム数が10万を超えるような状況下ですべてのユーザーとアイテムのペアでスコアを計算してソフトマックスを取るのは非効率。Negative Samplingを利用して計算量を減らした。

## どうやって有効だと検証したか

実験に利用したデータセットは以下のもの。

- MovieLens (映画の評価)
- Youchoose (ECサイト)
- Reddit (掲示板)
- Outbrain (広告)
- Taobao (ECサイト)

### Meta-Data Models

MovieLens (ml-20m) を用いてメタデータありなしの perplexity (PPL) の違いをチェック。ml-20m は 20 million interactions, 131 263 items, 138 493 unique users を含む。ここでのアイテムメタデータは映画のジャンル情報、フィードバックは映画の評価 (星の数) に対応。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/135044/9a864492-b44c-5df4-5354-7f0389193518.png)


### Hierarchies, Sessions and Time

モデルを hierarchical にしたのは、ユーザーはセッション内では似たような興味をもち、次のセッションでは別の興味を持っているかもしれないという仮定のもと。

以下の映画を見たユーザーに対して、最後のインタラクションから $\Delta t$ 経過したときに推薦される映画とジャンルの違いを確認

- Secret of Roan Inish (Children|Drama|Fantasy|Mystery)
- Postman (Comedy|Drama|Romance)
- Thin Blue Line (Documentary)
- Say Anything... (Comedy|Drama|Romance)
- Babe: Pig in the City (Children|Comedy)



![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/135044/16665381-47ef-b1bd-ce52-fd0fbb07d39f.png)


### RNNs vs. HRNNs

他のアルゴリズムとの比較。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/135044/486a8c71-e049-3a00-c5a3-c7e0a3b7d39a.png)

Feedback encoding の有無の比較。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/135044/31e4460a-eb07-6d2a-98b4-7ade8bd4200d.png)

Full Netflix dataset でもテスト。テストデータは2005年12月のデータ。訓練データはそれ以前の98.1M interactions。全部で17.7k unique items。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/135044/a2e89413-d674-c28b-e89e-2f529bc6c2ce.png)

Yoochooseデータセットでの比較。

Mean Reciprocal Rank (MRR), normalized Discounted Cumulative Gain (nDCG) といった評価指標は BrainPad さんのブログによくまとまっている。

https://blog.brainpad.co.jp/entry/2017/08/25/140000

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/135044/a175d087-53d8-f237-0458-118325845c54.png)


### Cold Start with Item Metadata and IPS

ジャンル情報を使ってMovieLensデータセットでコールドスタートアイテムの推薦のテスト。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/135044/80d82b7c-12f6-66e1-a91b-6a78b234492a.png)

## 議論はあるか

HRNN-meta は AWS の Amazon Personalize サービスの中で利用できる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/135044/58ba50ab-fee6-0ef6-3dab-f1797a45754a.png)

今回の手法はブラックボックス的だが、うまく学習できなかったときに根本原因は何か特定/サジェストするような機能を持たせるのが重要だと言及されている。

## 次に読むべき論文は

論文ではないがAWSのブログ [What’s new in recommender systems](https://aws.amazon.com/jp/blogs/media/whats-new-in-recommender-systems/) (2020年11月投稿) にバンディッドとHRNN-metaの組み合わせに関して解説がなされているので読んでおきたい。