Off-policy Learning in Two-stage Recommender Systems

2020/04/30

https://gyazo.com/8bb2bad1072ad825f2a9fe9795cddd7b

1 INTRODUCTION

YouTube推薦論文 WSDM2019の「Top-K Off-Policy Correction for a REINFORCE Recommender System」の続編的な位置づけ

上記はYouTubeの推薦に強化学習を使用した論文

ラストオーサーが同じ

YouTubeの推薦の仕組みは

RecSys2016「Deep Neural Networks for YouTube Recommendations」

RNN使用した推薦

WSDM2018「Latent Cross: Making Use of Context in Recurrent Recommender Systems」

Attention使用した推薦

WSDM 2019「Top-K Off-Policy Correction for a REINFORCE Recommender System」

強化学習を使用した推薦

強化学習を使用する背景として無駄インプの効率的な除去が実現できそう

報酬関数（リワード）でクリックされないことを適切に学習するとそれに類似するアイテムは次回から推薦しない

このように刺激的に進化してる

「Top-K Off-Policy Correction for a REINFORCE Recommender System」の続編だと思って読んだらA/Bテストの結果はなかった（＝パブリックデータのオフライン実験のみ）だったのでちょっと残念

おそらく実験したけどうまくいかなかったと想像

MovieLensとWiki10-31Kで実験

オフラインでどのように強化学習用のシミュレータを構築したかは丁寧に書いてある

（いつもの枕言葉で）現実世界の推薦システムは多数のユーザーに多数のアイテムを低レイテンシで推薦する必要がある

そのために2段階プロセスだと効率的

候補アイテムを生成するプロセスとそれをランキングするプロセス

https://gyazo.com/51ac23d6d6aac3c8af9bb19db9f9d9f5

強化学習で2段階プロセスを統一的に考慮している仕組みはまだない

前回の論文でも候補アイテム生成時に強化学習を適用するものだった

そこで今回は独立したものではなく統一的に考えてみる

クリックログや滞在時間ログは推薦システムの改善に有効だが、既存のモデルから生成されるため、新しいモデルにそのまま学習させるにはバイアスがかかってる状態

バイアス考慮しないと 「rich gets richer」問題が発生する

そのため強化学習のOff-policyという手法で重み付けしてなんとかする

これは前回の論文の大きな主張だった

2段階のときどうなるか

具体的にはInverse Propensity Scoring (IPS) を採用

既存モデル(behavior policy)と新モデル(target policy)のimportance weightを求めることでバイアスを緩和させている

2 RELATED WORK

2.1 Two-stage Recommender Systems

YouTube, LinkedIn, Pinterest

2.2 Reinforcement Learning

大きく2つの方法

value based approaches（価値ベース, モデルフリー）

Q-learning

policy-based approaches

方策勾配計算するやつ

value basedは不安定なのでpolicy basedでやってる

2.3 Bandit Learning in Web Applications

強化学習なので探索（exploration）と活用（exploitation）を行う

ユーザーなどの特徴を考慮するContextual banditsが流行り

2.4 Off-policy Learning

https://gyazo.com/85bf80a2482793d3d5844b5b6dc77dfb

AtariやGoのようなゲームではAgentとEnvironmentが1:1で存在するからOn-policyが適用できる

一方、推薦システムでは現実世界の既存モデル（behavior policy）から発生するログを新モデル（target policy）の学習に適用しなければならない

そのための研究がOff-policy

3 RECOMMENDATION AS AREINFORCEMENT LEARNING PROBLEM

推薦システムに強化学習を応用する

ユーザーのtrajectory（動画視聴履歴）

$ \tau=\left\{\left(s_{1}, a_{1}\right),\left(s_{2}, a_{2}\right), \ldots,\left(s_{T}, a_{T}\right)\right\}

報酬関数

$ R(\tau)=\sum_{t=0}^{|\tau|} R_{t} \quad ; R_{t} \equiv r\left(s_{t}, a_{t}\right)

リワード（報酬関数）の期待値を最大化させるのが強化学習の目的

$ \max _{\theta} \mathbb{E}_{\tau \sim \pi_{\theta}}[R(\tau)]

$ \theta \leftarrow \theta+\lambda \nabla_{\theta} \mathbb{E}_{\tau \sim \pi_{\theta}}[R(\tau)]

$ \nabla_{\theta} V\left(\pi_{\theta}\right)=\mathbb{E}_{\pi_{\theta}}\left[r(s, a) \nabla_{\theta} \log \pi_{\theta}(a | s)\right]

というのが強化学習の基本的な流れ

https://gyazo.com/d5045b61f1d4eb0b188b8762499b6387

3.1 Off-policy Learning with Inverse Propensity Scoring

Off-policyどうするか

既存のモデルの雰囲気を汲み取るやりかた

これがInverse Propensity Scoring (IPS) と呼ばれる方法

$ V\left(\pi_{\theta}\right)=\mathbb{E}_{\pi_{\theta}}[r(s, a)]=\mathbb{E}_{\beta}\left[\frac{\pi_{\theta}(a | s)}{\beta(a | s)} r(s, a)\right]

4 OFF-POLICY LEARNING IN TWO-STAGE RECOMMENDER SYSTEMS

4.1 Two-stage Recommender Systems

（単純に）2つに分解しよう

$ \pi(a | s)=\sum_{A^{k}} p\left(A^{k} | s\right) q\left(a | s, A^{k}\right)

4.2 Two-stage Off-policy Policy Gradient for the Candidate Generation Model

どのように方策勾配を計算するか

とりあえず式展開

$ \pi_{\theta}(a | s)=\sum_{A^{k}} p_{\theta}\left(A^{k} | s\right) q\left(a | s, A^{k}\right)

$ \begin{aligned} \nabla_{\theta} \hat{V}\left(\pi_{\theta}\right) &=\frac{1}{n} \sum_{i=1}^{n} \frac{\pi_{\theta}\left(a_{i} | s_{i}\right)}{\beta\left(a_{i} | s_{i}\right)} r_{i} \nabla_{\theta} \log \pi_{\theta}\left(a_{i} | s_{i}\right) \\ &=\frac{1}{n} \sum_{i=1}^{n} \frac{\nabla_{\theta} \pi_{\theta}\left(a_{i} | s_{i}\right)}{\beta\left(a_{i} | s_{i}\right)} r_{i} \\ &=\frac{1}{n} \sum_{i=1}^{n} \frac{\sum_{A^{k}} q\left(a_{i} | s_{i}, A^{k}\right) \nabla_{\theta} p_{\theta}\left(A^{k} | s_{i}\right)}{\beta\left(a_{i} | s_{i}\right)} r_{i} \end{aligned}

$ \begin{aligned} \nabla_{\theta} \pi_{\theta}\left(a_{i} | s_{i}\right) &=\sum_{A^{k}} q\left(a_{i} | s_{i}, A^{k}\right) \nabla_{\theta} p_{\theta}\left(A^{k} | s_{i}\right) \\ &=\sum_{A^{k}} p_{\theta}\left(A^{k} | s_{i}\right) q\left(a_{i} | s_{i}, A^{k}\right) \nabla_{\theta} \log p_{\theta}\left(A^{k} | s_{i}\right) \\ &=\mathbb{E}_{A^{k} \sim p_{\theta}\left(A^{k} | s_{i}\right)}\left[q\left(a_{i} | s_{i}, A^{k}\right) \nabla_{\theta} \log p_{\theta}\left(A^{k} | s_{i}\right)\right] \end{aligned}

実際に計算するための工夫

4.2.1 Unbiased Approximation by Candidate Set Sampling

4.2.2 Sampling with Replacement on Candidate Set Generation

4.3 Variance Reduction Tricks

5 EXAMPLE: APPLICATION ON A SOFTMAX RECOMMENDER

実験で用いる損失関数を3つ定義する

まずはリワードの定義

https://gyazo.com/5cd646f3a290a4974caec716ed973c7a

Cross-entropy Loss

一般的なもの

$ J_{\mathrm{CE}}(\theta)=-\frac{1}{n} \sum_{i=1}^{n} r\left(s_{i}, a_{i}\right) \log p_{\theta}\left(a_{i} | s_{i}\right)

One-stage IPS Loss

1stage

IPS: 比率使用するOff-plicyの方法

$ J_{1-\mathrm{IPS}}(\theta)=-\frac{1}{n} \sum_{i=1}^{n} \frac{\operatorname{sg}\left(p_{\theta}\left(a_{i} | s_{i}\right)\right)}{\beta\left(a_{i} | s_{i}\right)} r\left(s_{i}, a_{i}\right) \log p_{\theta}\left(a_{i} | s_{i}\right)

sg: stop-gradient operation

Two-stage IPS Loss

$ J_{2-\mathrm{TPS}}(\theta)=-\frac{1}{n} \sum_{i=1}^{n} \frac{\operatorname{sg}\left(p_{\theta}\left(a_{i} | s_{i}\right)\right)}{\beta\left(a_{i} | s_{i}\right)} r\left(s_{i}, a_{i}\right) h(\theta)

$ \begin{aligned} h(\theta)= \sum_{A^{k-1}}\left[\operatorname{sg}\left(p_{\theta}\left(A^{k-1} | s_{i}\right)\right) q\left(a_{i} | s_{i},\left\{a_{i}\right\} \cup A^{k-1}\right)\right. \simeq \frac{1}{\tau} \sum_{A^{k-1} \sim p_{\theta}}\left[q\left(a_{i} | s_{i},\left\{a_{i}\right\} \cup A^{k-1}\right)\right.& \\\left.\left(\log p_{\theta}\left(a_{i} | s_{i}\right)+\log p_{\theta}\left(A^{k-1} | s_{i}\right)\right)\right] \end{aligned}

6 EXPERIMENT

3つの損失関数を使用して実験を比較

6.1 Experiment Methodology

A/Bテストを行うのが理想

利用できる環境は稀 => （YouTubeでテストしろや）

オンラインテストを模倣する2つの方法を使用した

6.1.1 Supervised-to-Bandit Conversion

データセットにfull-label informationが必要

推薦システムの論文でよく使用されるデータセットには適用できない

全データセットって理論的にありえるのかな

x: data iの特徴ベクトルs, y: binary vector

$ \mathcal{D}_{\text {full }}=\left\{\left(\mathbf{x}^{i}, \mathbf{y}^{i}\right)\right\}_{i=1}^{n}

バンディットのデータセット作る

$ \mathcal{D}_{\text {bandit }}=\left\{\left(\mathbf{x}^{j}, a^{j}, p^{j}, r^{j}\right)\right\}_{j=1}^{l}

p: behavior policyによる あるuser-item pairの発生確率

rはyを元に算出したリワード

a: クラス, a ∈ {1, 2, · · · ,m}, 他クラス想定

バンディットデータセットを元に学習

6.1.2 Online Simulation

シミューレータの実装

部分的なデータセット

$ \mathcal{D}=\left\{\left(u^{i}, a^{i}, r^{i}\right)\right\}_{i=1}^{m}

u: ユーザー, a: アイテム

6.1.1のように完全なデータセットがない場合はDのrを推定するシミュレータを実装する

6.2 Detailed Setup

6.2.1 Datasets

MovieLens-1M

3,900 movies made by 6,040 users

ユーザーのデモグラ情報あり

スコア4以上がpositive feedback, 4未満をnegative feedback

MovieLens-20Mはユーザー情報なかったり、ratingがスパースだったりするので1Mにした

Wiki10-31K

約20K samples

ラベル数は31K classes

サンプル:ラベル=1:N

6.2.2 Model Architectures

https://gyazo.com/e7965e2f6b2cb7e9f37ff4307a1b7d2d

(a): two towerモデル

候補生成とbehavior policyモデルで使用

それぞれでネットワークがあるため計算が効率的

(b):

ランキングモデルとシミュレータモデルで使用

ユーザーとアイテムをさらにニューラルネットで計算するためより強い

実験設定＆方法が丁寧に記載されている

Movie Lens-1Mの場合

データのvalidationはちゃんとやってる

シミュレータの実装

ユーザーとアイテムのペアを入力したらレイティングを推定するシミュレータ

Wiki10-31Kは完全なデータセットという体だからシミュレータなし

シミュレータを元にBehavior Policy, Ranking Modelsを学習

候補生成モデルの学習

パラメータまわりは詳細に記載されていた、これが再現性か

6.3 Off-policy Learning Results

https://gyazo.com/5aa0b83cbd278b731da3a6d9b3b93667

https://gyazo.com/2fd5b7d237b5dd3a6b270912c370432c

7 CONCLUSION AND FUTURE WORK

Offline-policyによる2段階推薦システムを定式化した

候補生成とランキングのpolicy

方策勾配の導出

参考文献

やはりオンラインの結果みたい

強化学習効果ありそう

学習安定させるための工夫がつらそう

われわれも候補記事生成の1段階目もっと工夫できそう