バンディットによるカルーセル順序のパーソナライズ

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

https://qiita.com/birdwatcher/items/9560afeea61d14cff317

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

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

- [arxiv論文](https://arxiv.org/abs/2009.06546)
- [論文著者のgithub](https://github.com/deezer/carousel_bandits)

## 概要
- 音楽配信アプリにおけるプレイリスト順序最適化をバンディットで行う
    - プレイリストがアイテムです
- $K$個から$L$個を取ってきて並べてユーザーに提示する
    - 著者のgithubの例
        - アイテム全体の数: $K = 862$
        - 提示するアイテムの数: $L = 12$
        - UIで最初に見えるアイテムの数: $L_{\rm init} = 3$
        
        ![](https://github.com/deezer/carousel_bandits/raw/master/images/carousel.png)
（論文著者の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）
        - ログデータからロジスティック回帰で作成したらしい
        - **本来未知の値**

### 結果

![](https://github.com/deezer/carousel_bandits/raw/master/images/general_exp.png)
（論文著者のgithubの図より引用）

- トンプソンサンプリング系は全体的に強い傾向
    - `ts-lin-*`: [LogisticTS](https://qiita.com/birdwatcher/items/9560afeea61d14cff317#logisticts)を全体に適用
    - `ts-seg-*`: [シンプルなTS](https://qiita.com/birdwatcher/items/9560afeea61d14cff317#%E3%83%99%E3%83%AB%E3%83%8C%E3%83%BC%E3%82%A4%E5%88%86%E5%B8%8301%E5%A0%B1%E9%85%AC)をユーザーセグメントごとに配置したもの
- **真面目に学習するよりもセグメント切ったほうが強い傾向**
    - ユーザーのパーソナライズはセグメントに分けるだけで良いということに...（後述の実験で自分でも実験してみます）

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

### 著者の実装を紐解く
- 学習ロジック: [LogisticTS](https://qiita.com/birdwatcher/items/9560afeea61d14cff317#logisticts)（前回Qiitaで解説した）
    - [著者の実装コード](https://github.com/deezer/carousel_bandits/blob/d98ff3b7dd1e19e102f52de147e53ae6339b9f5a/online_logistic_regression.py#L40)
        - （[原著論文](https://proceedings.neurips.cc/paper_files/paper/2011/file/e53a0a2978c28872a4505bdb51db06dc-Paper.pdf)どおり対角成分のみの場合の）LogisticTSの更新式
- 報酬の計算の仕方 
    - [著者の実装コード](https://github.com/deezer/carousel_bandits/blob/d98ff3b7dd1e19e102f52de147e53ae6339b9f5a/environment.py#L77): 報酬はユーザーが最も最初にクリックした位置までしか与えていないように見える（？）
        - 論文内の説明と実装が一致していない（？）
    - [引用されていた別論文](https://arxiv.org/pdf/1602.03146): この論文では具体的なアルゴリズムが示されており、**最後にクリックした位置までを更新**していた
        - 本Qiitaの「仮定」で説明したのはこれと一致する
- 学習データ作成
    - [著者の実装コード](https://github.com/deezer/carousel_bandits/blob/d98ff3b7dd1e19e102f52de147e53ae6339b9f5a/policies.py#L273)
        - 提示したアイテム順に見ていき学習データを作れば、LogisticTSに与えるだけで良い
        - Cascadeのために新たなモデル実装が不要（**データセットの前処理だけで対応可能**）
            - Contextual Banditを既に実装している人 歓喜！
    - [この箇所](https://github.com/deezer/carousel_bandits/blob/d98ff3b7dd1e19e102f52de147e53ae6339b9f5a/policies.py#L286)でも初クリックまでだけを見ていそう

### アルゴリズム
ここまでの理解を通して、擬似コードで記述してみました。

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

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

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

https://github.com/birdwatcherYT/bandit
- [personalized_cascading.py](https://github.com/birdwatcherYT/bandit/blob/main/personalized_cascading.py)に実装

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

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

**最後のクリックまでを見る場合**
![last_wide.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/294661/8939f5bd-4f5e-e97d-1602-a8c3f4024ef3.png)
**最初のクリックまでを見る場合**
![first_wide.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/294661/1c436de5-6587-bd0e-643d-b76774e39e1b.png)

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

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


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

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