You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, Ed H. Chi. 2019. Top-K Off-Policy Correction for a REINFORCE Recommender System. In The Twelfth ACM International Conference on Web Search and Data Mining (WSDM’ 19), February 11-15, 2019, Melbourne, VIC, Australia.
Tobias Schnabel, Adith Swaminathan, Ashudeep Singh, Navin Chandak, and
Thorsten Joachims. 2016. Recommendations As Treatments: Debiasing Learning and Evaluation. In Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48 (ICML’16). 1670–1679.
The text was updated successfully, but these errors were encountered:
usaito
changed the title
op-K Off-Policy Correction for a REINFORCE Recommender System.
Top-K Off-Policy Correction for a REINFORCE Recommender System.
Jan 23, 2019
0. 論文概要
Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, Ed H. Chi. 2019. Top-K Off-Policy Correction for a REINFORCE Recommender System. In The Twelfth ACM International Conference on Web Search and Data Mining (WSDM’ 19), February 11-15, 2019, Melbourne, VIC, Australia.
** 図表は全て本論文からの引用です.
1. 要約
2. 背景
3. 手法
bias除去
今回用いるnotationは以下の通り. ユーザーの状態遷移を考慮に入れたMDP.
ここで, 方策πのパラメータθは, 勾配方策定理により, 以下をサンプルから推定したもので更新する.
しかし, 背景でも述べたように今回は推薦システムに方策を適用することを考えるので, 勾配を計算するのに用いるtrajectoryは, 自身ではなくて, 過去の方策(behavior policy) βによるものである. これにより, 勾配方策定理が成り立たないため, パラメータ更新に工夫が必要である.
本論文では, Importance Samplingを用いることで, このlogged bandit feedbackを用いることに起因するbiasを取り除く. de-biasされた勾配は以下の通り. これは真の報酬の勾配に対してunbiasedである.
Propensity Scoreのように, behavior policyで逆重み付けしていると解釈できる.
勾配の更新式がわかったので, ここからユーザーの状態s のモデル化に入る. 本論文では, RNNの一種であるCFNを用いて状態をモデル化する. (deep learning詳しくないので, そろそろ勉強しなければ)
また, 上述したbias除去のためには, behavior policy βを推定することが必要である. (もちろんlogとして残っていればそれを用いれば良いのだが, 複数のpolicyが混ざっていたりする状況の方が一般的). これは, RNNで得られたユーザーの状態表現を用いて別のNetworkで推定する. behavior policyの推定ように状態表現を別に得るやり方も試したそうだが, 精度は変わらなかったそう.
behavior policyの推定部分も含めたarchitectureは以下の通り.
Top-Kへの拡張
さて, 大きな問題である勾配推定のbiasを除去する方法を提案した後は, この勾配推定をTop-Kの状況に拡張することを考える. 累積報酬を書き換えると以下のようになる. Aがk個のitemで構成されるactionになる.
ここで, 推薦されるアイテム集合Aは, stochastic policyから独立に復元サンプリングすることによって得ることとする.
このような状況のもとで, bias補正前の勾配は, アイテムaがアイテム集合Aに現れる確率を用いて以下のように書き換えられる.
このTop-K versionの勾配に対して, bias補正をかけると,
よって, Kの値が変わると, softmax値が小さいアイテムから報酬が得られた場合について, パラメータの更新度合いを変化させるような役割を持つ. この効果については, 実験で検証する.
4. 実験
4.1. 報酬が状態に依存しない場合(人工データ)
報酬が状態に依存せず, アイテムごとに報酬が決定している状況において, behavior policyによって得られたbandit feedbackから, 最適な方策を求める. bias除去を入れた場合と入れなかった場合を比較.
アイテムのindexが大きくなるにつれて, 報酬が大きくなるように報酬構造は設計されている. よって, bias除去を入れることによって, 最大の報酬を与えるアイテムに大きな確率が割り当てられていて, うまく方策を学習できていることがわかる.
4.2. 報酬が状態に依存しない場合のTop-K推薦(人工データ)
次に, 先ほどの実験をK個のアイテムを推薦可能とする状況に拡張する. 今回は, K=2として, 10個のアイテムはまたも状態非依存で以下のように決まっているとする.
a_1 = 10, a_2 = 9, a_i = 1, (i = 3, 4, ..., 10.)
つまり, 一つ目と二つ目のアイテムを推薦するような方策を学習したい. 単純なbias除去とTop-Kの状況に拡張したbias除去(λが入っているやつ)の2つの方策を比較.
Top-Kを考慮に入れた勾配で更新することで, 2つ目のアイテムとそれ以外の差が明確になっているため, パッケージとしてより良い推薦ができるとの結果.
4.3. 実データを用いた実験
Youtubeの視聴時間を報酬と見て, A/Bテストで異なる方策で動画を推薦した. Top K個の動画を推薦する場合を考えて, K=1, 2, 16, 32で5日間実験した時の結果がFigure 5. K=16をbaselineとしている.
ある程度の大きさのKを設定して推薦することで, 視聴時間を改善できることが示された.
5. コメント
推薦によって, 報酬だけではなくてユーザーの状態が変化するというのはとても現実的な設定で, 広告配信など他にも適用が考えられるため非常に参考になった.
スペースの関係からか, 実験について図を掲載せずに結果だけ述べている部分があったので少し残念
そろそろでぃーぷらーにんぐ勉強しないと
6. 関連論文ピックアップ
Thorsten Joachims. 2016. Recommendations As Treatments: Debiasing Learning and Evaluation. In Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48 (ICML’16). 1670–1679.
The text was updated successfully, but these errors were encountered: