Identifying New Podcasts with High General Appeal Using a Pure Exploration Infinitely-Armed Bandit Strategy
https://gyazo.com/2939746fb4b1ee22ab51a8b353639661
選んだ理由
バンディットアルゴリズムに興味があるため
気になるタイトルだったため
Infinitely-Armed Bandit とは...となり目を引いた
著者情報
Spotify
何をした論文か
Spotify の Podcast の推薦で fixed-budget Infinitely-Armed Bandit として定式化、ISHA(UISHA) というアルゴリズムを提案
一般的な人気が高い Podcast を見つけるために Bandit を使っている
ISHA は他のバンディットアルゴリズムと比較して、最も性能が高いというわけでないが、並列化が可能で高速に動作し、実装も容易
実プロダクトに自然に導入可能な形になっている
導入
Podcast などでは常に新しいコンテンツがアップロードされている
できるだけ早くどの新しいコンテンツ(Podcast)が多くの視聴者にとって(一般的に)人気である確率が高いか特定し、パーソナライズレコメンドシステムがより注目できるようにすることは重要
あまり研究が進んでいないらしい(本当?)
(心の声)コールドスタート問題とくればバンディットの出番だな
以下の点で上記の取り組みは重要
アップロードされる頻度がかなり高いため、ほとんどのコンテンツは消費されない
多くのユーザにとって魅力的でないコンテンツがたくさんある
https://gyazo.com/3ef992ed4006f26899b7c6d360abc912/thumb/400#.jpg
モチベーション
一般的な人気度合い(General Appeal)が高くなる Podcast を早期に発見し、Podcast キャリアの早い段階でクリエイターを伸ばしたい
良い Podcast を発見するために、一般的な人気度合いの推定値を偏りなく得たい
無作為にユーザを選択して各アイテムをある程度出して視聴率の期待値出すのは Podcast の数が多く現実的でない
Podcast の数 * N (N は期待値を得るために十分な値)
多腕バンディットアルゴリズムを使うことで、上記の問題を回避
ISHA という Infinitely-armed bandit algorithm を提案
スケールする(大規模対応)
腕選択の並列化によって遅延報酬を自然に処理できる
fixed-budget infinitely-armed Bandit in the pure exploration という問題設定(固定予算、無限腕)
予算(探索回数): ユーザ
腕(アーム): Podcasts
目的: 最良の腕(Podcast)を特定すること
教師あり学習で、ユーザが何を聴くか予測するのを学習することに対する問題点
ユーザが何を聴いているかについてのデータを使うと、 popularity bias が生じてしまう。
長期的には良くない並びに drift する危険性がある
有名人による Podcast などを多く推薦することは良い推薦になりうるが、既存のフォロワーを持たないクリエイターが作った良い Podcast を見落とす可能性がある
(Section 4 で紹介されているが)全体で集計した人気順(つまり、レコメンドシステムなどが動いた結果などを含む)と(ランダムに表示して得られた時の)一般的な人気順の順位相関係数は $ 0.3 程度となり低い相関を示している
一般的な人気が高い Podcast が Popularity Bias がある手法だと見落としているということになる
提案手法
ISHA
(何の略かわかりませんでした...(hogehoge Successive halving Algorithm?)
Successive Halving アルゴリズムのひとつ
元の Successive Halving と違う点として、$ nを $ T = \lceil n\log_2(n)\rceil となるように取る
anytime algorithm バージョンでは $ n=2^1, 2^2, 2^3, 2^4, 2^5,... と増やしていく
Successive Halving はループごとに悪い腕の候補数を半分にしていくアルゴリズム
これによって、各ループで $ n回の計算が行われ、 $ \log_2(n) 回ループするので、予算 $ T を使い切ることになる
腕の pull 数が $ 1 \rightarrow 2 \rightarrow 4 \rightarrow ... \rightarrow n となり、腕の数が $ n \rightarrow \frac{n}{2} \rightarrow \frac{n}{4} \rightarrow ... \rightarrow 1となるため
ループを抜けると腕の候補数が $ 1 つになる
お気持ちとしては、ひとつひとつの腕でなく、腕の集合に注目して各ラウンド(ループ)でより良い腕が生き残る確率が高く、ひとつひとつの腕単位で見ると、腕候補の更新で良い腕が(悪い腕だとみなされ)捨てられるかもしれないが、腕の集合の期待値では良くなるという感じ
https://gyazo.com/d718616d98ec55d4683638b2d2591176
lil'UCB-X との比較
データセット: New Yoker caption contest dataset
腕の数: 3,795
simple regret は最良の腕との差分であり、小さいほど良い
lil'UCB-X の X の部分は X 個の腕をランダムにとってくるということ
ISHA では、それぞれの予算において適切な腕の数を探索することができている(腕の数を考える必要がない)
lil'UCB-10 では少ない予算では、Simple Regret は良い(早い段階でそこそこ良い腕を識別することができている)が、予算が大きくなっても Simple Regret の値は良くならず、最良の腕を見つけることができていない(候補が少ない)
lil'UCB-10000 などでは、大きな予算での Simple Regret は良く、最良の腕に近いものを見つけることができているが、少ない予算ではかなり悪くなっている(探索いい感じになる前に予算がなくなる)
https://gyazo.com/924f75d91cd86326611be4b8aac13fed
実験
人工データでの実験
Beta(1,1), Beta(1,3) で作成されたデータ
Spikes は以下の式で上のベータ分布2つを合成した分布
https://gyazo.com/05c351828c6e283be3b986dfb2e768d3/thumb/500#.png
(a): 腕の数と予算のトレードオフ
(b), (c): Infinitely-armed algorithm 同士の比較
ベースラインの紹介
SIRI: UCBアルゴリズムの派生
Successive Rejects と ISHA が一貫して良い結果となっている
(d): lil'UCB との比較
腕の数を決定することは難しいことがわかる
(e): Explore-vs-exploit algorithm との比較
ベースラインの紹介
f-failure: f回失敗するまで同じ腕をつかう
m-learning: 最初の m 回は 1-failure を用いて、その後は最も期待値の高い腕を選び続ける
s-run: s 回連続成功する腕を見つけるまで 1-failure を適用し、見つけたらその腕を選び続ける
これらのアルゴリズムをそのまま実プロダクトに組み込むことはできない
他のアルゴリズムでは分布を仮定しているものがある
概ね同程度の Regret という結果
(f): Anytime Bandit 同士の比較
任意のタイミングで打ち切られるアルゴリズム
他の Anytime Bandit Algorithm と比較して良い結果となり、非 Anytime Bandit と比べても同程度であることがわかる
https://gyazo.com/49675ee07f36226314708e1fa5ab1ec0
https://gyazo.com/dc304fbd7715a5f0c8202415cb5831ea
実データに対する実験
データ(分布)
700個の Podcast をランダムに選ばれたユーザに提示したデータセットから分布を作成したもの
一般的な人気(General Appeal)が反映されている
ISHA を用いて一般的に人気である Podcast を見つけることができるかどうか
予算と腕の数と Regret の関係
予算が多いと腕が多くなるにつれて Regret が小さくなる
逆に予算が少ないと腕の数によらず Regret が大きい
https://gyazo.com/35f4a87850d7336d38b5d734b0e3d7f5
ISHA のラウンド(ループ回数)が大きくなるにつれ、一般的な人気(General Appeal)が大きな腕が生き残るようになることがわかる
https://gyazo.com/81f7b5c3a2d29641022b9bfe6bb0c07b
上記の Podcast のデータ(分布)と Movielens-1M におけるバンディットアルゴリズムの比較
ここで ISHA は各ラウンドで、腕選択の結果を捨てて(忘れて)いたが、 UISHA(Unforgetful ISHA)では過去すべての腕選択の結果を用いるようにした
その結果 Successive Rejects と Empirical CBT は小さな予算では UISHA より良い Regret となっているが、予算が十分大きくなると、UISHA の Regret は同程度となっている
この研究における実験では、Podcast 数: $ 32k、 予算:$ 2^{19} だから同等と書かれていた
https://gyazo.com/e740bf1422f7760257e823b70ff3a9cf
https://gyazo.com/9fa76f079f2b876a92fdcef611d5575a
UISHA の他の優位性
UISHA は並列に腕を選択することができる
予算(ユーザ数): 480k, 腕(Podcast): 32k の場合
15ラウンド(ループ)で最適な腕を選択する($ 2^{15} \log_22^{15}\approx 480k)
一方 Successive Rejects では 411 ラウンド、Empirical CBT では 480k ラウンド必要
ユーザの反応が5秒で返ってくるとするとすべてのラウンドが終わるには以下のようになり、UISHA が実用上優秀であることがわかる
UISHA: 75秒
Successive Rejects: 34分
Empirical CBT: 28日
また、視聴完了など時間がかかる場合はこれ以上かかる(判定に1日分待つ場合だと...)
更に、Successive Rejects は複雑度が高く並列化周りの実装が難しい(らしい)
the engineering complexity of SR can be much higher than for UISHA
感想
Hyperband と似たようなアルゴリズムだと思うが、どのあたりが強くなる要因だったのか気になる
最初の腕の数が ISHA のほうが小さくて序盤の絞りが強いから?(Hyperband をあまり読めていない)
シンプルなアルゴリズムかつ性能と速度のバランスが取れていて良いアルゴリズムだと思った
UISHA を人工データで使用しなかったのはなぜだろう
色んな所に使えそうで良かった