狠狠撸

AI
2023.11.09
Tomoki Yoshida
株式会社ディー?エヌ?エー
いろんなバンディットアル
ゴリズムを理解しよう

AI
? 経歴
? 名古屋工業大学情報工学専攻竹内烏山研究室 ※現在は別の名前
? 凸最適化理論に基づいた機械学習高速化
? 2020年 DeNA入社
? 社外のヒューリスティック最適化案件
? Pococha CS & Timeline
? 好きなこと
? 鳥、YouTube、お笑い
2
自己紹介：Tomoki Yoshida

AI 3
項目
01｜バンディットアルゴリズム
02｜Contextual Bandit
03｜Cascading Bandit
04｜Contextual Cascading Bandit

AI 4
? バンディット4種
? Bandit：最適な選択肢を見つける
? Contextual Bandit：各ユーザーごとに最適な選択肢を見つける
? Cascading Bandit：アイテム順序を最適化する
? Contextual Cascading Bandit：ベクトル表現を持つアイテム
順序を最適化する
? 最近Qiitaに公開した記事から抜粋して紹介します
? Qiita
URL：https://qiita.com/birdwatcher/items/9560afeea61d14c?317
? 実装
? GitHub URL：https://github.com/birdwatcherYT/bandit
今日の内容

AI 5
01 バンディットアルゴリズム

AI 6
? スロットマシンN台がある
? スロットマシンの腕を引くと報酬がもらえる
? 累積報酬を最大化したい
バンディットはこの戦略を示してくれる
バンディットアルゴリズム

AI 7
? ABテスト代わりに使い自動的に優秀なシステムを残す
? 例：広告配置アルゴリズムA,B,Cのどれが優れている？
? バンディットの腕：各アルゴリズム
? 報酬：クリックしたかどうか
? 企業の活用事例
? ZOZOTOWNにおけるバンディットアルゴリズムを用いた推薦
? ユーザーベクトルに応じてアイテムを推薦
? Artwork Personalization at Net?ix
? サムネをユーザーベクトルに応じて最適化
何に使われる？

AI 8
? 知識の無い状態から腕を引いていき、知見を貯めなが
ら、良さそうな腕を見極めていく
? これまでの知識を「活用」したり、
? もっと良い腕があるかもしれないと別の腕を「探索」しながら
? 累積報酬の最大化をめざす
? アルゴリズムを3つ紹介
? Epsilon Greedy
? UCB1（Upper Con?dence Bound）
? Thompson Sampling
アルゴリズム

AI 9
? (活用) 1-εの確率で今までの平均報酬が最も良い腕を選択
? (探索) εの確率でランダムな腕を選択
? 非常にシンプル
? 経験的に一番良い腕を引いていくが、小さい確率で別の
腕も選ぶ
アルゴリズム：Epsilon Greedy

AI 10
? 確率不等式を使って導出された理論に基づくアルゴリズ
ム
? 式の気持ち
? 第1項：これまでの試行から最も良さそうな腕を選びたい
? 第2項：試行回数が少なく評価が不確かな腕ほど選びたい
アルゴリズム：UCB1（Upper Con?dence Bound）

AI
? 報酬が0/1じゃないときでもこのまま使える？ → No
? UCB1の導出過程で、報酬が[0,1]の範囲であることを仮定
? 探索と活用のバランス調整のため、係数調整が必要
? UCB1の1って何？ → 名前
? 改良版のUCB2やUCB1-Tunedなどもある
? Upper Con?dence Boundって何？
? 信頼区間の上限のことで、「真の期待値を過小評価している確
率」の上限を抑えることを考えて導出されている
? キーワード：ヘフディングの不等式
11
UCB1のFAQ

AI 12
? 確率的に腕を選択する優れたアルゴリズム
? 仮定
? 報酬の分布:
? 未知パラメータの事前分布:
? 得られた知識を用いてパラメータの事後分布を計算:
?
? : パラメータの事後分布からサンプリング
アルゴリズム：Thompson Sampling（TS）

AI
報酬の分布の例
? ベルヌーイ分布（0/1報酬）
? 未知パラメータ：報酬1を返す確率
? 正規分布（連続報酬）
? 未知パラメータ：報酬の平均値（と分散）
TSではこれらの未知パラメータを推定しているわけです
13
Thompson Samplingで扱う報酬の分布

AI
? 確率で報酬1、で報酬0:
? 未知パラメータの事前分布：ベータ分布
? ベルヌーイ分布の共役事前分布
? なんの知識もなければα=1、β=1
14
TS：報酬がベルヌーイ分布の場合（0/1報酬）

AI
? 事後分布
15
TS：報酬がベルヌーイ分布の場合（0/1報酬）
この分布からサンプリングすればいい！
個数を覚えておくだけでよい

AI
? 報酬が平均μ、分散σ2
の正規分布に従う:
? 未知パラメータの事前分布：
? 正規分布（平均未知、分散既知）
? ガウスガンマ分布（平均未知、分散未知）
?
16
TS：報酬が正規分布の場合（連続報酬）
腕の添字は省略してます
分散σ2
はλ=1/σ2
として登場

AI
? 事後分布
17
TS：報酬が正規分布の場合（連続報酬）
NG分布からのサンプリ
ングは依存関係順に行う
この分布からサンプリング
すればいい！

AI
? リグレット（後悔）を比較
? リグレット：常にベストな腕を選んだ場合との差の期待値
? TSが強い！
18
実験：適当に真のパラメータを設定して学習させてみた
0/1報酬連続報酬

AI 20
? 特徴ベクトルxに応じて報酬分布が変わるバンディット
? x: ユーザーの性別、年齢、行動履歴など
? に依存した報酬が得られる → パーソナライズできる
Contextual Bandit

AI 21
線形モデルを4つ紹介
? 報酬がで表現されると仮定
? LinUCB
? LinTS
? 確率で報酬1が得られると仮定
? LogisticTS
? LogisticPGTS
θa
を学習するわけです
Contextual Banditのモデル

AI
? 報酬をで回帰し、UCBを使ったモデル
? 観測データをリッジ回帰した推定値
? 確率不等式で真の値との差が評価できる
? 1-δの確率で成り立つ不等式
22
アルゴリズム：LinUCB

AI
? UCBによる選択基準
? α>0：探索度合い（ハイパーパラメータ）
23
アルゴリズム：LinUCB
A-1
はランク1行列による修正しか行われないため、
Sherman–Morrisonの公式で逆行列の計算量を削減可能

AI
? 報酬をで回帰し、TSを使ったモデル
? 仮定
? 誤差がに従う→報酬がに従う
? パラメータの事前分布：
? 事後分布
24
アルゴリズム：LinTS
この分布からサンプ
リングすればいい！
分散既知

AI 25
アルゴリズム：LogisticTS
? 0/1報酬の線形バンディット
? 仮定
? 報酬のベルヌーイ分布：
? θa
の事前分布：
? 事後分布の負の対数を計算
? きれいな分布にならない → 最小値付近で二次近似しよう！

AI
? で最小値を取るとき、その周りで展開
? 近似した分布は
に従う
■ は勾配法（ニュートン法など）で求める
26
1回微分
2回微分

AI
? 内部の最小化問題で毎回全データを見るのは非現実的
27
→前回の結果を事前分布と
した最小化問題を解く（完
全な差分計算ではない）
最小化問題を解く際の注意事項
単純なニュートン法（係数1）だと
振動して収束しないことがあった
更新幅を調整しながら目的関数が必
ず下がるように学習する必要あり

AI
? LogisticTSの二次近似の代わりに
ギブスサンプリングを使う！
? 直接サンプリングが難しい確率分布
の代わりに、それを近似したサンプ
ル列を生成するMCMC法
? PG分布（PolyaGamma分布）を使用
※式を書いても複雑なだけなのでスルー
Pythonライブラリ：polyagamma
■ LogisticTS同様、完全な差分計算は無理
28
アルゴリズム：LogisticPGTS

AI 29
実験：適当に真のパラメータを設定して学習させてみた
? 0/1報酬で実験
モデルの仮定に合ったLogistic系が強い（当然）
文脈考慮しないTS（ベースライン）
連続報酬を仮定したモデルもまあまあ機能する

AI 30
実験：モデルの表現力を見る
? 特徴空間を分割して、各空間ごとに好む腕を設定
なぜかLinUCBが強くなった
学習後にランダムな
ベクトルを1000件与
えると、グループご
とに好む腕を多く提
示できている→
線形モデルだけど、
意外と表現力ある！
切片項（バイアス
項）を入れないとう
まくいかないことが
あった

AI 32
? 順序を最適化する
バンディット
? 仮定
? ユーザーは並んだアイテムを上から順に見る
? ユーザーがアイテムを好んでいた場合は必ずクリックを行う
? クリックされたアイテム以降はユーザーに見られていない
? 全L個のアイテム中、K個のアイテムを順序付きで提示
Cascading Bandit

AI 33
? 各アイテムeの好み確率P(e)は、
それぞれ独立なベルヌーイ分布に従う
? 提示したK個のアイテムが少なくとも1つクリックされる
確率
を最大化する
Cascading Bandit：補足

AI 34
? アイテムeについて、次のUCBが大きい順にK個並べる
? クリックされたアイテム以上のアイテムを観測
? クリックされない場合、提示していたK個のアイテム全て観測
したとみなす
アルゴリズム：CascadeUCB

AI 35
04 Contextual Cascading Bandit

AI 36
? ベクトルを持ったアイテム順序を最適化するバンディッ
ト
? アイテム数が多くても学習が進みやすい！
? 各アイテムeの好み確率をで回帰（線形モデル）
? θはアイテム間で共通
Contextual Cascading Bandit

AI 37
? LinTSをCascadeに適用したモデル
アルゴリズム：CascadeLinTS

AI 38
? LinUCBをCascadeに適用したモデル
アルゴリズム：CascadeLinUCB

AI 39
実験：真の確率をに設定して実験
確率の積になるとリグレットが分かりづらいため、logをとって計算
Context系強い（当然）
TSが弱いのはモデルの仮定にあっていないからと
思われる

AI 41
? 4タイプのバンディットを紹介
? Bandit: 最適な選択肢を見つける
? Contextual Bandit: 各ユーザーごとに最適な選択肢を見つける
? Cascading Bandit: アイテム順序を最適化する
? Contextual Cascading Bandit: ベクトルを持つアイテム順序を
最適化する
? 実装自体は重くない
? 実務で使う際は、過去のログデータから集計した値を腕
の好み具合としてシミュレーションしてみることが重要
そう
おわりに

AI 42
? Finite-time Analysis of the Multiarmed Bandit Problem
? 多腕バンディット問題におけるUCB方策を理解する
? Bandit Algorithms in Information Retrieval
? A Contextual-Bandit Approach to Personalized News Article Recommendation
? Thompson Sampling for Contextual Bandits with Linear Payo?s
An Empirical Evaluation of Thompson Sampling
? Net?ixも使っている！Contextual Banditアルゴリズムを徹底解説！（Part 1）
? PG-TS: Improved Thompson Sampling for Logistic Contextual Bandits
? [論文紹介] PG-TS: Improved Thompson Sampling for Logistic Contextual Bandits
Cascading Bandits: Learning to Rank in the Cascade Model
? The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond
? Cascade Model に適用する Bandit Algorithms の理論と実装
? Cascading Bandits for Large-Scale Recommendation Problems
参考文献

狠狠撸

いろんなハ?ンテ?ィットアルコ?リス?ムを理解しよう

Recommended

More Related Content

What's hot (20)

いろんなハ?ンテ?ィットアルコ?リス?ムを理解しよう