LoginSignup
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@morinota(morinota)

カルーセルUIの特性を考慮して推薦モデルを学習させるために、banditパラメータ更新にカスケードモデルを適用する論文を読んだ!

Posted at

これは何?

ざっくりどんな内容の論文。

  • 音楽ストリーミングアプリ（Deezer）における カルーセル（スワイプ可能な推薦リスト）のコンテンツパーソナライズ機能を、文脈付きマルチアームバンディット（Contextual Multi-Armed Bandit: CMAB）問題とみなして改善アプローチを提案・実験してる論文。
    • より詳細には、Multi-plays CMAB (1ラウンドで複数のアームが選ばれる) のバンディット問題として定式化してる。
  • 提案アプローチについては以下の２通りのbandit手法を提案・検証してる。
    • セミパーソナライズ戦略（クラスタリングを活用した、context-free bandit）
    • フルパーソナライズ戦略（ユーザ特徴量 & アイテム特徴量を使ったcontextual bandit）
  • また、カルーセルUIの特性「ユーザはすべてのスロットを見ない可能性がある」ことを考慮して、オンライン学習時の工夫としてカスケードアーム更新モデルを導入してる (個人的にこの話が本論文を読む1番のモチベーションでした...!:thinking:)
    • ざっくりカスケードアーム更新モデルとは、カルーセルの後ろの方に表示されたアイテムは、タップされなかったとしても「見られてない」可能性があるのでnegative sampleとして扱わない、みたいなやり方。オンライン学習サンプルの作り方の工夫でした!
    • ちなみに、「ユーザ行動のカスケード性」「カスケードモデル」とは??
      • ざっくり理解では「ユーザは手前側に表示されたアイテムから吟味していくはず...!」みたいなユーザ行動の仮定を使うよ、ってこと:thinking:
    • このカスケードは、モデルアーキテクチャによらないので使い勝手良さそう...!:thinking:
  • また、提案手法の実装コードと、半合成データを使ったオフライン評価用の環境を公開してるみたい(https://github.com/deezer/carousel_bandits)。

背景 & 研究のモチベーション

  • レコメンドの実応用の動きについて
    • ユーザにパーソナライズされたコンテンツを推薦することは、ニュース、動画、音楽配信などのメディア系サービスにおいて重要。
      • 良いレコメンダーがあると、ユーザはコンテンツ迷子にならずに済み、お気に入りのコンテンツを楽しめるし、新しい作品との出会いもある。結果として、UX & エンゲージメントが向上する!
    • そのため、研究成果を実サービスに活かそうとする動きが活発に。
  • 実サービスでの採用例: カルーセル(Carousel)
    • 特に音楽ストリーミングサービスでは、カルーセルUI（スワイプで切り替えられる推薦リスト）が主流!
    • カルーセルUIで何を表示するかが重要! なぜなら...
      • カルーセルには表示枠(=スロット数)に制約。　表示スロット数 << コンテンツ数。
      • ユーザごとに好みも異なる。
  • カルーセルUIの技術的な課題:
    • 見られないスロットもある(スワイプしないと見えない)。
  • この論文の貢献:
    • カルーセルUIの推薦を、文脈付きマルチアームバンディット (Contextual Multi-Armed Bandit: CMAB) 問題として定式化。
      • 1ラウンド内で複数のアームが選択される Multiple Plays MAB に対応。
      • ユーザ行動のカスケード性を考慮したオンライン学習方法を提案。
    • 実サービスにてオンライン評価して実験。
    • 実験用データ & シミュレーション環境をオープンソースで公開。

提案手法: Multi-plays CMAB(Contextual Multi-Armed Bandit) * カスケードモデル

まずMultiple Playsのバンディットって??

  • カルーセルUIにおける推薦は、**Multiple Plays (複数プレイ)**のMAB(多腕バンディット)問題と言える。
  • Multiple Plays MABとは??
    • 1ラウンド内で $L$ 個のアームを選んで、報酬を受け取るという問題設定。
      • (i.e. ランキングタスクがMultiple Plays MABってこと...??:thinking:)
    • その一方で、通常のSingle Play MABは1ラウンドで1つのアームのみを選択して報酬を受け取る問題設定。
  • Multiple Plays MABをざっくり定式化すると...(contextは一旦無視ver.)
    • 表記
      • アーム(アイテム): $K$ 個のアーム。
      • ラウンド: $t = 1, 2, \ldots, T$。
      • 選択可能なアームの集合: $S_t \subseteq {1, 2, \ldots, K}$。
      • 報酬: 各選択したアーム $i \in S_t$ に対して、報酬 $r_{i}$ はベルヌーイ分布に従うと仮定 (論文内ではbinaryの報酬を想定してるみたい:thinking:)
      • 報酬のベルヌーイ分布のパラメータを $p_{i}$ とする (=これはつまり、アーム $i$ が選ばれたときの報酬期待値 $E_{p_{i}(r)[r]}$ と同じ意味...!:thinking:)
    • 目標:
      • トップ $L$ 個のアームを選択することで、報酬を最大化する。
      • つまり、最も報酬期待値の高い $L$ 個のアーム集合 $\delta^*(L)$ を特定したい。
    • 方策の性能指標: 累積後悔(Cumulative Regret)
      • $Reg(T) = \sum_{t=1}^{T} (\sum_{i \in \delta^*(L)} p_{i} - \sum_{i \in S_t} p_{i})$
      • もし常に最適なアームを選べていたら、後悔はゼロ。
      • でも探索をしないと良いアームを見つけられないので、最初のうちはある程度のregretが発生する。
      • 良いアルゴリズムは、このregretをできるだけ小さくすることが目標。

Multiple Plays MABをカルーセル推薦に適用する

  • カルーセルUIにおける推薦の定式化:

    • 表記
      • K個のアイテム(アーム) (ex. プレイリスト、アルバム)
      • N人のユーザ。
      • L個のスロット(カルーセルの表示枠)にアイテムを配置する (L << K)
      • 報酬関数 $r_{ui}$ について。ストリームすれば1、しなければ0。
    • 目標:
      • 各ユーザ $u$ に対して、ストリーム確率が最も高い $L$ 個のアイテムを選びたい。つまり以下。
        • $S_t = argmax_{S \subseteq {1, 2, \ldots, K}, |S| = L} \sum_{i \in S} p_{ui}$
        • (要するに $p_{ui}$ は、ユーザ $u$ にアイテム $i$ を見せた時にストリームされるかの期待値 $E_{p(r|u,i)}[r]$ ってこと...!:thinking:)

  • 好みが違うからユーザごとに異なる推薦をする必要がある。じゃあどうする??

    • **最も単純な戦略は、「ユーザ数(N個分)のMABを独立に動かす」**こと!。だがこれは厳しい!
      • 学習コストが膨大になる。非現実的。
      • 推定すべきパラメータの数が K * N個になる。多すぎる。ログデータを十分に貯めるのに何年かかるのか...!:thinking:
    • 本論文では2つの戦略を提案してる。
      • クラスタリングを活用したセミパーソナライズ戦略。
      • 文脈つきバンディットを活用したフルパーソナライズ戦略。

  • ちなみに...個人的に実運用で気になったポイント!

    • プラットフォームの技術的制約により、カルーセルUI内のアイテムは定期的に更新される(i.e. リアルタイム推論ではなくバッチ推論で運用する想定...!!:thinking:)

提案1: クラスタリングを活用したセミパーソナライズ戦略

  • 全てのユーザを個別に扱うと計算コストが大きすぎるので、ユーザを $Q$ 個のクラスタに分け、クラスタごとにMABを動かす。
  • これにより、推定すべきパラメータ数が $K \times Q$ 個に削減できる。 (Q << N)
  • 似たユーザをクラスタ化して、一緒に扱う。
    • ex.「ロック好き」「ポップ好き」などのクラスタを作れる。
  • 良いクラスタ設計が性能の鍵。

提案2: 文脈つきバンディットを活用したフルパーソナライズ戦略

  • 各ユーザに $D$ 次元の特徴量ベクトル $x_{u}$ をcontextとして、回帰モデルを用いる。
    • つまり...$p_{ui} = E_{p(r|u,i)}[r] = \sigma(x_u^T \theta_{i})$ と仮定し、観測されたバンディットフィードバックを活用して、より良いモデルパラメータ推定値 $\hat{\theta}_{i}$ を更新していく...! :thinking:
  • これにより、推定すべきパラメータ数は $K \times D$ 個に削減できる。(D << N)
    • 個人的に思ったことメモ:raised_hand:
      • 推定するパラメータ数が $K \times D$ 個ってことはつまり、どうやらこの論文では、contextual banditとして線形回帰モデルをアイテムごとに用意する想定っぽい。
        • i.e. ユーザ間ではモデルパラメータをshareするが、アイテム間ではモデルパラメータを共有しない戦略。
      • なのでニュース推薦など、推薦候補アイテムがダイナミックに入れ替わるユースケースに適用する場合には、ユーザ間だけでなくアイテム間でもモデルパラメータを共有する戦略を取るべきのはず...!:thinking:

カルーセルUIの特性を考慮するためにカスケードモデルを適用

現実のカルーセルUIの特性による問題:

  • 通常のMABの設定では、「選択したすべてのアイテム（L個）について報酬（0 or 1）が得られる」という前提。
  • 一方でカルーセルUIでは、すべてのスロットがユーザに見られるとは限らない。
  • ファーストビューの表示スロット $L_{init}$ 個 (ex. 最初の3枚) のみ確実に見られる。
  • ユーザはスワイプしないと追加のアイテムを見れない。でも実際にどこまでスワイプしたかを正確に計測するのは難しい...! よって、バンディットフィードバックが不完全になる。

もしこの問題を無視してしまうと...

  • 「クリックされなかったアイテムは全部 0 の報酬」とする。
  • でもユーザが「見てすらいない」可能性。
  • 結果として、クリック率（display-to-stream確率）が過小評価される

対応策: banditのパラメータ更新にカスケードモデルを導入! (i.e. ユーザ行動にカスケード性を仮定する!)

  • ざっくり、本論文におけるカスケードモデルの考え方!
    • 「ストリームされたアイテムの位置までのスロットは、ユーザが見たとみなす」
    • ちなみに...
      • 書籍「反実仮想機械学習」におけるカスケードモデルは、「あるランキングのk番目のポジションで発生する期待報酬は、そのポジションよりも上位に提示されたアイテムのみに依存して決まる」みたいな考え方として説明されてた! より定義が一般化されてる感...!:thinking:
  • 具体的には、カスケードアーム更新モデル (cascade-based arm update model) を提案。
    • ユーザの行動に応じてどこまでのアイテムが「ユーザに見られたか」を判定し、「ユーザに見られた」アイテムのみを学習に使用する。
    • 判定方法の具体例:
      • 例1: 何もストリームされなかった場合。
        • ファーストビューに含まれる $L_{init}$ 個のアイテムは「見た」と判断する。
        • それ以降のアイテムは「見られてない」と判断する。
      • 例2: 4番目のアイテムがストリームされた場合。
        • 1~4番目のアイテムは「見られた」と判断する。
        • 5番目以降のアイテムは「見られてない」と判断する。
      • 例3: 2番目と6番目のアイテムがストリームされた場合。
        • 1~6番目のアイテムは「見られた」と判断する。
        • 7番目以降のアイテムは「見られてない」と判断する。
  • この工夫がより何が解決できるのか??
    • 見られてないアイテムを学習の対象から外せる。
    • 見られたけどストリームされてないアイテムは、報酬0としてカウントできる。
    • 結果として、学習がより現実のユーザ行動に即したものになる。

遅延フィードバック (Delayed Feedback)　について

これはbanditモデルのパラメータ更新の話...!:thinking:

  • 観測された報酬(bandit feedback)を、リアルタイムでモデルに反映するのは難しい。
  • 代わりに、1日の終わりなど「バッチ処理」でフィードバックを受け取る。これが遅延フィードバック (Delayed Feedback)。
  • なぜ遅延FBになるの??
      1. 技術的制約:
      • 大規模プラットフォームでは、モデルパラメータを毎回リアルタイム更新するのは非効率。
      1. 現実のシステムと一致させるため:
      • 多くのアプリでは「その場でFBを取る」よりも「後でまとめてログを処理」する。
  • 悪影響は??
    • データが即時に反映されないので、学習が遅れる可能性。
    • でも実際のシステムの制約を考慮すると、現実的。(まあそうだよなぁ...:thinking:)

実験方法

音楽ストリームアプリ Deezer における問題設定

  • $K = 862$ 個のプレイリスト。
    • 自社の専門キュレーターによって作成。(=あ、めちゃめちゃドメイン知識要求されるクリエイティブな作業だ...!!:thinking:)
  • カルーセルUIの仕様:
    • 総スロット数: $L = 12$
    • 最初に表示されるスロット数: $L_{init} = 3$
  • 評価方法:
    • オフライン評価: 半合成データを用いて、各バンディットアルゴリズムの性能を比較。
    • オンライン評価: Deezerの本番環境でA/Bテストを実施。

オフライン評価のシミュレーション環境について

  • ユーザ数: $N = 974,960$ (匿名)
  • 特徴量: $D = 97$ 次元のユーザ特徴量ベクトル $x_u$ を用意。
    • 具体的には...
      • 行列分解により、ユーザ特徴量ベクトルを生成。
      • その後、バイアス項を追加。(=たぶん正規分布とかに従う乱数を追加してそう!)
  • クラスタリング: $Q = 100$ 個のクラスタに分ける。
    • ユーザ特徴量ベクトルに対して k-means を適用し、類似したユーザをクラスタリング。
  • 真のストリーム期待値 $p_{ui}$ を生成しておく:
    • (観測される報酬をシミュレートするために、擬似的に真の値を用意してる)
    • $p_{ui} = \sigma(x_u^T \theta_{i})$ として、各(ユーザ, プレイリスト)ペアのストリーム期待値を生成。
      • 各アイテム $i$ の真のモデルパラメータ $\theta_{i}$ は、2020年1月の観測データを元に推定させた値を使ってるっぽい。
  • シミュレーションの流れ:
    • 毎ラウンド、ランダムな20,000人のユーザに対して推薦。
    • 各方策は、$L = 12$ 個のプレイリストを推薦。
    • 観測される報酬は、カスケードアーム更新モデルに基づいてシミュレーションされる。
      • 具体的には、手前のアイテムから $p_{ui}$ に基づいてコイントスしていく感じ...?? それで1つでもクリックされたらそれ以降のアイテムは見ない??
        • (まあより具体的にはコードが公開されてるのでそれを見たらわかりそう)
    • 毎ラウンド終了時に、観測された報酬に基づいて方策のモデルパラメータを更新。
    • 累積後悔 (Cumulative Regret) で各方策の性能を評価する。

評価したい方策一覧 (セミ/フルパーソナライズ)

デフォルトでは、すべてのアルゴリズムのパラメータ更新にカスケードモデルを採用する。
ちなみに追加実験として、モデルパラメータの更新にカスケードアーム更新モデルを仮定するかnaiveな方法をとるかの比較も行ったみたい。カスケードモデルを採用しなかった場合の結果は *-no-cascade というsuffixがついてる。

  • ランダム方策(ベースライン):
    • random: 一様ランダムにプレイリストを推薦
  • epsilon-greedy方策 (セミパーソナライズ):
    • epsilon-greedy-seg-explore : epsilon=0.1で探索多め。
    • epsilon-greedy-seg-exploit : epsilon=0.01で探索少なめ。
  • ETC方策 (セミパーソナライズ):
    • etc-seg-explore: n=100。最初の100ラウンドは一様ランダムに探索し、その後は常に推定されたトップL個のアームを選択。
    • etc-seg-exploit: n=20。最初の20ラウンドは一様ランダムに探索し、その後は常に推定されたトップL個のアームを選択。
  • KL-UCB方策 (セミパーソナライズ):
    • kl-ucb-seg: UCBアルゴリズムを用いたセミパーソナライズ戦略。
  • Thompson Sampling方策 (セミパーソナライズ):
    • ts-seg-naive: Beta(1,1)分布を用いたThompson Samplingアルゴリズム。
    • ts-seg-pessimistic: Beta(1,99)分布を用いたThompson Samplingアルゴリズム。悲観的ポリシー。
  • contexualなThompson sampling方策 (フルパーソナライズ):
    • ts-lin-naive: ロジスティック回帰モデルを用いたThompson Samplingアルゴリズム。モデルパラメータ推定値の初期値が全てゼロ
    • ts-lin-pessimistic: ロジスティック回帰モデルを用いたThompson Samplingアルゴリズム。バイアス項の推定値の初期値が-5?

実験結果

オフライン実験(シミュレーション)の結果

セミパーソナライズ戦略 vs フルパーソナライズ戦略

  • etc-seg-* は初期はランダム同様の挙動 → 探索終了後に急激に改善
  • ts-lin 系は数ラウンドで線形に安定
  • ts-seg-pessimistic が最も早く安定し、最終的に全ポリシーを上回る
  • セミパーソナライズ戦略でも十分に高精度
    • 計算コスト的にも、推定するモデルパラメータ数は $K \times Q$ 個 vs. $K \times D$ 個でほぼ同等。
  • 良い感じにクラスタリングできるなら、セミパーソナライズ戦略は大規模アプリに適した選択肢と言える。

カスケードアーム更新モデルの効果

  • *-no-cascade 系: 見られてないスロットにも報酬0を与えて学習する。
  • cascade 系: カスケードアーム更新モデルを用いて、見られた可能性があるスロットのみを学習に使用。
  • 全体的に、カスケードアーム更新モデルを用いた方策の方が高い性能を示した。

オンライン実験(A/Bテスト)の結果

  • 2020年2月に Deezer の本番環境で A/B テストを実施。
  • 推薦プレイリストを毎日更新 (日時のバッチ推論...!:thinking:)
  • ts-seg-naiveなどの一部の方策のみをオンライン実験で使用。
  • 結果:
    • random-top-100 (クラスタごとに事前に選定された100個のプレイリストをランダムに推薦) と比較して、
    • バンディット戦略(特にセミパーソナライズ)が大幅に勝利。
    • カスケードアーム更新モデルを用いた方策がさらに効果的だった。
2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?