はじめに
以前、以下の記事でバンディットアルゴリズムについて紹介しました。
その中のContextual Cascading Banditでは、アイテムの順序を最適化する手法でしたが、ここでいうContextはアイテムのベクトルのことで、ユーザーのベクトルではありませんでした。
そのため、ユーザーごとに異なる順序を提示したいケース(パーソナライズ)には対応していません。
今回はユーザーベクトルを考慮したアイテムの順序最適化について学んでいきます。
論文紹介
カルーセル順序のパーソナライズをContextual Banditで学習している論文
Carousel Personalization in Music Streaming Apps with Contextual Bandits
を紹介します。
概要
- 音楽配信アプリにおけるプレイリスト順序最適化をバンディットで行う
- プレイリストがアイテムです
- $K$個から$L$個を取ってきて並べてユーザーに提示する
- ユーザーごとに異なるアイテム順序を見せる
仮定
モデル
ユーザー$u$ と アイテム$i$ のペアに対して、クリックする確率を
$$
p_{u,i}=\sigma (x_u^\top \theta_i)
$$
- $\sigma$: シグモイド関数
- $\theta_i$: アイテムが持つパラメーター(これを学習する)
で表現する。
報酬
-
複数アイテムをクリックできる(multiple plays)
- 1つだけでなくてよい
- 報酬の設定方法
- 最後にクリックされた位置まで0/1報酬を設定する
- 何もクリックなかった場合は$L_{\rm init}$個だけ観測したことにする
- 論文の例($L=12, L_{\rm init} = 3$)
- クリックしなかった場合:
[0, 0, 0, X, X, X, X, X, X, X, X, X]
- 2番目をクリックした場合:
[0, 1, 0, X, X, X, X, X, X, X, X, X]
- 2番目と6番目をクリックした場合:
[0, 1, 0, 0, 0, 1, X, X, X, X, X, X]
(Xは報酬なしを表している)
- クリックしなかった場合:
実験
データセット
-
user_features.csv
: 974,960ユーザー- 96次元Embeddingベクトル
- バイアス項はコード内にあり、それを含めてユーザーベクトル $x_u$
- segment: kmeansで100個のクラスタに分けた結果のラベル
- ユーザーのまとまりを作って、それぞれのセグメントでcontextを考慮しないバンディットを走らせる場合に使う
- バンディットがパーソナライズをサポートしてなくても、クラスタごとに別のバンディットモデルを用いれば雑にパーソナライズできるという思想(semi-personalization)
- (実験名に
-seg
がつく)
- ユーザーのまとまりを作って、それぞれのセグメントでcontextを考慮しないバンディットを走らせる場合に使う
- 96次元Embeddingベクトル
-
playlist_features.csv
: 862個のアイテム- 97次元重みベクトル $\theta_i$ (ground-truth)
- ログデータからロジスティック回帰で作成したらしい
- 本来未知の値
- 97次元重みベクトル $\theta_i$ (ground-truth)
結果
- トンプソンサンプリング系は全体的に強い傾向
-
ts-lin-*
: LogisticTSを全体に適用 -
ts-seg-*
: シンプルなTSをユーザーセグメントごとに配置したもの
-
-
真面目に学習するよりもセグメント切ったほうが強い傾向
- ユーザーのパーソナライズはセグメントに分けるだけで良いということに...(後述の実験で自分でも実験してみます)
アルゴリズム
論文内では、別の論文を引用しているものの、具体的なアルゴリズムが示されておらず具体的な手順が明確にはわからないため、引用論文とgithubの実装を紐解いて解釈をこちらにまとめます。
著者の実装を紐解く
- 学習ロジック: LogisticTS(前回Qiitaで解説した)
- 報酬の計算の仕方
-
著者の実装コード: 報酬はユーザーが最も最初にクリックした位置までしか与えていないように見える(?)
- 論文内の説明と実装が一致していない(?)
-
引用されていた別論文: この論文では具体的なアルゴリズムが示されており、最後にクリックした位置までを更新していた
- 本Qiitaの「仮定」で説明したのはこれと一致する
-
著者の実装コード: 報酬はユーザーが最も最初にクリックした位置までしか与えていないように見える(?)
- 学習データ作成
アルゴリズム
ここまでの理解を通して、擬似コードで記述してみました。
アルゴリズム
- $\mu_a\leftarrow 0, \Sigma_a\leftarrow \lambda I, \forall a$
- 学習ループ
- $D_a\leftarrow\emptyset, \forall a$
- ミニバッチ蓄積ループ
- 特徴ベクトル$x$を受け取る
- $\tilde \theta _a\sim\mathrm{MultiNorm}(\theta_a|\mu_a,\Sigma_a),\forall a$
- $x^\top\tilde{\theta}_a$の上位$L$個を大きい順に提示
- ユーザーがクリックした結果を受け取る(複数アイテムのクリック許容)
-
提示したアイテム順に、最後のクリック位置までをデータセットに追加する(クリックされていなければ$L_{\rm init}$個だけ追加)
- クリックしてたら$r=1$、そうでなければ$r=0$
- $D_a\leftarrow D_a \cup \{(x,r)\}$
- $\hat \theta_a\leftarrow \arg\min_{\theta_a} \frac{(\theta_a-\mu_a)^{\top} \Sigma_a^{-1}(\theta_a-\mu_a)}{2} - \sum_{(x,r)\in D_a} \log\mathrm{sigmoid}(y\theta_a^{\top} x), \forall a$
- $\mu_a\leftarrow\hat\theta_a, \Sigma_a\leftarrow H(\hat\theta_a)^{-1}, \forall a$
前回Qiitaで書いたLogisticTSとの差分を太字で示してます。
腕を提示する部分とデータ作成部分で吸収できていることがわかります。
2.2.5.のデータセット追加部分は、前述のように実装と論文の記述が異なるように思えましたが、論文通り最後のクリックまでとして書いてみました。
自分で実装して実験してみる
前述のとおり、データセットの変換を噛ませば新たなモデルの実装は不要だったので、前回のQiita実装から少しの変更で試すことができました。
比較のために、LogisticTS以外に対しても適用してみました。
小規模に $K = 20, L = 10, L_{\rm init} = 5$ で実験。
リグレットは、論文内の記述を参考に
$$
\mathrm{regret}=真のパラメータで計算した上位L個の確率の和-推定パラメータで計算した上位L個の確率の和
$$として計算して、その和を累積リグレットとしてプロットしてます。
-
Logistic*
: シグモイド関数を通した線形モデル -
Lin*
: シグモイド関数を通さない線形モデル -
BernoulliTS
: パーソナライズしないベースラインモデル -
ClusterBandit*
: クラスタリングを使ってユーザーセグメントごとに独立なBernoulliTSを持つモデル
仮定に合ったLogistic系が強いという結果になりました。
クラスタリングよりも線形モデルのほうが強いという結果になりました。
余談
Cascade系の実装がデータセットの前処理だけで済む事がわかったので、実装の一般化をして前回実装したCascadeUCBやCascadeKLUCBのコードを削除しようと思ったのですが、全体の試行回数を保持するタイプのアルゴリズムだと挙動が変わるため統一化できませんでした。
全体の試行回数とは、アイテムリストを提示した回数のことですが、前処理でデータセットを展開してレコード数を増やしてしまうと、正確な全体の試行回数を保持できず、差が生じます。
まとめ
- LogisticTSを使ってアイテム順序のパーソナライズを実現できる
- Cascadeに関する処理はデータセット作成部分で吸収できる