[DL輪読会]Off-policy Learning in Two-stage Recommender Systems (WWW2020)

DEEP LEARNING JP [DL Papers] Off-policy Learning in Two-stage Recommender Systems (WWW2020) Jun Hozumi, Matsuo Lab http://deeplearning.jp/ 1

• http://deeplearning.jp/

書誌情報 • Title: Off-policy Learning in Two-stage Recommender Systems • Author: Jiaqi Ma, Zhe Zhao, Xinyang Yi, Ji Yang, Minmin Chen, Jiaxi Tang, Lichan Hong and Ed H. Chi • • Conf.: WWW(WebConf) 2020 • • University of Michigan, Simon Fraser University and Google USA 先月末に発表されたばかり 概要: 二段階推薦システムのための、二段階オフポリシー方策勾配法の提案 2

はじめに • 現在実用化されている推薦システムでは「候補生成」と「ランキング」の二段階に分け たアプローチが用いられる • それぞれのモデルは過去のフィードバックデータをもとに旧来の推薦手法を用いて別々 に学習されるが、推薦された商品に対するフィードバックしか観測できないことから、 必然的にバイアスがかかったものになる • 本研究では、方策オフ学習を用いてこのバイアスを修正することを試みる 3

方策オフ補正の採用 • 方策オフ学習は、インタラクティブなシステムにおいて、部分的なフィードバックのみ を観測することによって生じるバイアスを緩和する • これを用いて、ターゲット方策と呼ばれる訓練されているシステムと、ログに記録され た暗黙のフィードバック・データを生成したシステムとの間の不一致によって引き起こ されるバイアスを修正する（方策オフ補正） • 最も一般的な方策オフ補正の1つは、Inverse Propensity Scoring(IPS)である • IPSでは、ログデータ上の経験的な訓練対象に、目標ポリシーと行動ポリシーの間の確率比である サンプルごとの重要度の重みを割り当てることで、修正された目的のバイアスがないものとなる ようにする 4

本研究の目的 • 方策オフ補正は近年の推薦システム研究において関心が高まっているが、推薦システム が単段であると仮定するか、またはランキングモデルを明示的に考慮せずに（二段階シ ステムの）候補生成モデルに方策オフ補正を適用するかのいずれかになっている • しかし、段階間の相互作用を無視すると、候補生成方策を学習する際にサンプルの非効 率性が生じ、さらにはバイアスを導入してしまい全体最適でない方策を学習してしまう 可能性もある • このギャップを埋めるために、候補生成モデルの学習中にランキングモデルを明示的に 考慮する効率的な二段階方策オフ勾配法を提案する • 二段式推薦システムのターゲット政策を、候補生成政策とランキング政策の構成として 定式化し、候補生成モデルに対するIPSベースの方策オフ補正の重要度を導出する • また、候補生成モデルに弱い仮定を置き、より効率的なモンテカルロ近似アルゴリズムも用いる 5

前提: 凡例 • （用語の使い方は標準的な強化学習と概ね同じ） 6

前提: 問題の定式化 • 価値関数V(π)を最大化する方策π(a|s)を求める • 本研究では推薦システム上でユーザの状態分布は時間によって変化しないことを仮定 • T=1の1ステップ強化学習（contextual bandit） • 本研究では方策勾配法のアプローチを用いる • REINFORCEよりπをθでパラメータ化することで勾配を以下の式で書ける 7

前提: IPSを用いた方策オフ学習 • 実務で用いられる推薦システムはログデータを用いたオフライン学習が用いられる • 学習対象とする方策πとは異なる行動履歴方策βによってログデータが生成されること によるバイアスをInverse Propensity Scoring (IPS) によって補正する • • 「π/β」をimportance weightと呼ぶ 勾配を以下の式で推定する 8

提案手法: 二段階推薦モデル • 本研究で取り扱う推薦システムは、最終的に1商品のみを推薦するものとする • 候補生成モデルpで選ばれなかった商品は、ランキングモデルqで推薦されない • 二段階推薦モデルでは、πを以下のように分解できる • 一般にpとqは別々に学習され、本研究ではpの方策オフ修正に焦点を当てる • 上記の式よりπとpの差異はq次第であるが、商品に対するpとqの挙動が異なる場合、 p/βによる方策オフ修正では最適解を得ることができない 9

提案手法: 候補生成モデルにおける二段階方策オフ学習 • pをθでパラメータ化する • これを方策勾配の式に代入する 10

提案手法: 候補集合からのサンプリングによる不偏推定 • 先程の式の計算は計算量的に無理 • そこで、Ak〜pθ(Ak|si)をサンプリングすることで∇θ πθの不偏推定量を得る • AkにAiが含まれない場合、勾配が0になることにも注目 11

提案手法: 候補集合生成での置換によるサンプリング • 候補集合が置換を伴うサンプリングによって生成されると仮定すると、以下の式を得る • この仮定により、さらに式を変形する 12

提案手法: 分散削減トリック • importance weight • これを防ぐために複数の分散削減トリックを採用する • • weight capping • self-normalized importance sampling により分散が大きくなる サンプリングによる分散を減らすために、前式の∇θlogpθ (Ak-1|Si)にα(<1)をかける 13

実例: ソフトマックス推薦システム • 報酬を定義する • （単純な）クロスエントロピー誤差を用意 • • 二段階方策オフ学習の目的関数はクロスエントロピー誤差の重み変更で表されるため それにIPSを採用する（One-Stage IPS Loss） • sgはstop gradient operation 14

実例: 提案手法をソフトマックス推薦システムで用いる場合 • そしてそれを二段階にする(Two-Stage IPS Loss) • τはサンプリングサイズ 15

提案手法: アルゴリズムの全体像 • Two-Stage IPS Lossをアルゴリズムとして記述すると以下のようになる 16

実験: 基本的な設定 • 先ほどのクロスエントロピー、One-stage IPS, Two-stage IPSで比較実験を行う • データセットに「MovieLens-1M」と「Wiki10-31K」を採用 • 候補生成モデル、ランキングモデルは以下のアーキテクチャを採用 17

結果: MovieLens-1M • 全体的に2-IPSが指標面で上回る • • システムの改善には部分ではなく全体を見た改善をすべきということを示唆する結果 候補生成モデルのみの推薦精度(one-stage evaluation)でも2-IPSが良い 18

結果: Wiki10-31K • （MovieLens-1Mの対象は3,900作品だが、 Wiki10-31Kは31,000もある） • Wiki10-31Kでも提案手法がベースラインを上回った 19

まとめ • 本研究では二段階推薦システムの学習におけるバイアスの補正に取り組んだ • 二段階推薦システムの方策を候補生成方策とランキング方策に定式化することで 、候補 生成モデルに対して二段階の方策オフ勾配法を導出した • 効率的なモンテカルロ近似アルゴリズムで計算量の問題も克服した • 実世界のデータセットを用いた実験を通じて、提案手法が一般に用いられる他の手法に 比べて、二段階推薦システムの性能を向上させることができることを実証した • 今後の研究では、多段レコメンダーシステムへの移行をどのように行うかや、システム 全体のEnd-to-Endを学習させられるかについて考えたい 20