はじめに

以前、以下の記事でバンディットアルゴリズムについて紹介しました。

その中のContextual Cascading Banditでは、アイテムの順序を最適化する手法でしたが、ここでいうContextはアイテムのベクトルのことで、ユーザーのベクトルではありませんでした。
そのため、ユーザーごとに異なる順序を提示したいケース（パーソナライズ）には対応していません。
今回はユーザーベクトルを考慮したアイテムの順序最適化について学んでいきます。

論文紹介

カルーセル順序のパーソナライズをContextual Banditで学習している論文
Carousel Personalization in Music Streaming Apps with Contextual Bandits
を紹介します。

概要

音楽配信アプリにおけるプレイリスト順序最適化をバンディットで行う
- プレイリストがアイテムです
$K$個から$L$個を取ってきて並べてユーザーに提示する
- 著者のgithubの例
  - アイテム全体の数: $K = 862$
  - 提示するアイテムの数: $L = 12$
  - UIで最初に見えるアイテムの数: $L_{\rm init} = 3$
  （論文著者のgithubの図より引用）
ユーザーごとに異なるアイテム順序を見せる

仮定

モデル

ユーザー$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 がつく）
playlist_features.csv: 862個のアイテム
- 97次元重みベクトル $\theta_i$ （ground-truth）
  - ログデータからロジスティック回帰で作成したらしい
  - 本来未知の値

結果

（論文著者のgithubの図より引用）

トンプソンサンプリング系は全体的に強い傾向
- ts-lin-*: LogisticTSを全体に適用
- ts-seg-*: シンプルなTSをユーザーセグメントごとに配置したもの
真面目に学習するよりもセグメント切ったほうが強い傾向
- ユーザーのパーソナライズはセグメントに分けるだけで良いということに...（後述の実験で自分でも実験してみます）

アルゴリズム

論文内では、別の論文を引用しているものの、具体的なアルゴリズムが示されておらず具体的な手順が明確にはわからないため、引用論文とgithubの実装を紐解いて解釈をこちらにまとめます。

著者の実装を紐解く

アルゴリズム

ここまでの理解を通して、擬似コードで記述してみました。

アルゴリズム

$\mu_a\leftarrow 0, \Sigma_a\leftarrow \lambda I, \forall a$
学習ループ
1. $D_a\leftarrow\emptyset, \forall a$
2. ミニバッチ蓄積ループ
  1. 特徴ベクトル$x$を受け取る
  2. $\tilde \theta _a\sim\mathrm{MultiNorm}(\theta_a|\mu_a,\Sigma_a),\forall a$
  3. $x^\top\tilde{\theta}_a$の上位$L$個を大きい順に提示
  4. ユーザーがクリックした結果を受け取る（複数アイテムのクリック許容）
  5. 提示したアイテム順に、最後のクリック位置までをデータセットに追加する（クリックされていなければ$L_{\rm init}$個だけ追加）
    1. クリックしてたら$r=1$、そうでなければ$r=0$
    2. $D_a\leftarrow D_a \cup \{(x,r)\}$
3. $\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$
4. $\mu_a\leftarrow\hat\theta_a, \Sigma_a\leftarrow H(\hat\theta_a)^{-1}, \forall a$

前回Qiitaで書いたLogisticTSとの差分を太字で示してます。
腕を提示する部分とデータ作成部分で吸収できていることがわかります。
2.2.5.のデータセット追加部分は、前述のように実装と論文の記述が異なるように思えましたが、論文通り最後のクリックまでとして書いてみました。

自分で実装して実験してみる

前述のとおり、データセットの変換を噛ませば新たなモデルの実装は不要だったので、前回のQiita実装から少しの変更で試すことができました。

personalized_cascading.pyに実装

比較のために、LogisticTS以外に対しても適用してみました。
小規模に $K = 20, L = 10, L_{\rm init} = 5$ で実験。

リグレットは、論文内の記述を参考に
$$
\mathrm{regret}=真のパラメータで計算した上位L個の確率の和-推定パラメータで計算した上位L個の確率の和
$$として計算して、その和を累積リグレットとしてプロットしてます。

最後のクリックまでを見る場合

最初のクリックまでを見る場合

Logistic*: シグモイド関数を通した線形モデル
Lin*: シグモイド関数を通さない線形モデル
BernoulliTS: パーソナライズしないベースラインモデル
ClusterBandit*: クラスタリングを使ってユーザーセグメントごとに独立なBernoulliTSを持つモデル

仮定に合ったLogistic系が強いという結果になりました。
クラスタリングよりも線形モデルのほうが強いという結果になりました。

余談

Cascade系の実装がデータセットの前処理だけで済む事がわかったので、実装の一般化をして前回実装したCascadeUCBやCascadeKLUCBのコードを削除しようと思ったのですが、全体の試行回数を保持するタイプのアルゴリズムだと挙動が変わるため統一化できませんでした。
全体の試行回数とは、アイテムリストを提示した回数のことですが、前処理でデータセットを展開してレコード数を増やしてしまうと、正確な全体の試行回数を保持できず、差が生じます。

まとめ

LogisticTSを使ってアイテム順序のパーソナライズを実現できる
Cascadeに関する処理はデータセット作成部分で吸収できる