今回は、前の記事で紹介したEpsilon-GreedyまたはUCBよりも成熟したMBAアルゴリズムThompson SamplingとLinUCBについて説明します.

Thompson Sampling

Thompson Sampingは,所与のK個の動作の確率分布を解く問題であり,動作aaaに対応する報酬推定値Qt(a)Qt(a)Qt(a)Qt(a)を計算する際に確率分布に従うと仮定し,その推定値を更新し続ける方法である.特にβ分布を用いた.

β分布

Beta⁡(x∣α,β)=1B(α,β)xα−1(1−x)β−1\operatorname{Beta}(x\mid\alpha,\beta)=\frac{1}{B(\alpha,\beta)} x^{\alpha-1}(1-x)^{\beta-1}Beta(x∣α,β)=B(α,β)1​xα−1(1−x)β−1
β分布は2つの量の変数で表すことができる確率分布であり,値は0と1の間である.
このときB(α,β){B(\alpha,\beta)}B(α,β)表示α,β\alpha,\betaα,β決定されたβ関数から.

Thompsonサンプリング例

ユーザーに表示できる広告バナーがあると仮定します.
このとき,どのバッフルに露出するクリック数が最も大きいかを予測し,推奨することを目標とし,その戦略を策定することが我々の任務となる.
まずβ分布に必要な2つのデータを定義する.

α\alphaα : 横断幕を見てクリック回数

β\betaβ : 横断幕を見てクリックしなかった回数

αとβが定義されている場合、確率分布が定義されます.

Beta(α+1,β+1)Beta(\alpha + 1,\beta+1)Beta(α+1,β+1):我々が想定するβ分布

Beta(α+1,β+1)Beta(\alpha + 1,\beta+1)Beta(α+1,β+1)仮定に従うため,β分布でサンプリングした値は最終的にBennerをクリックする確率である.
Thompson Samplingでは、次の手順に従います.

データのない初期状態-最初のプリ確率分布を用いて同じ値を設定

一定期間ランダム露光−ある程度の観測値を収集してβ分布を適切なレベルに更新する

β分布からサンプリングして露光する-ある程度のデータを収集した後、Thompson Samplingの策略を使う

レッスン3では数回の露出なしに集めたご褒美の中で最高のご褒美の期待値を持つものをおすすめします

<->ThompsonサンプリングではなくGreedyアルゴリズムを使用する場合は、カリキュラム3からサンプルの平均値が最も高いものを選択して推奨することがあります.
プロセスを例図で見てみましょう.
Step1. : データなしの初期状態-初期の事前確率分布と同じ値に設定

Step2. : ある程度の観測値をランダムに収集し,β分布を適切なレベルに更新した.

Step3. : ランダムサンプリングではなくThompsonサンプリング(β分布からサンプリング)を行い,各バナーのβ分布を更新した.

Step4. 複数回の露光後にβ分布が尖ったとき(真値に収束したとき)に最大の奨励を受けるBennerを推奨する.

このような過程により,確率分布に基づいて適切な追跡を維持しながら,種々の物品を暴露し,次いで報酬が最も高い物品を暴露し,収束した結果を得ることができる.
疑似コードで見てみましょう

# Algorithm 2 Thompson sampling for the Bernoulli bandit

Require: α, β prior parameters of a Beta distribution

	Si = 0, Fi = 0, ∀i. {Success and failure counters} # α, β 를 두고 Beta 분포를 초기화
	for t = 1, . . . , T do  # 매 timestep마다 
		for i = 1, . . . , K do # K개의 액셔ㅑㄴ에 대해서 각각
			Draw θi according to Beta(Si + α, Fi + β). # 베타분포를 셈플링하고
		end for
		Draw arm ˆı = arg maxi θi and observe reward r #샘플링한 θi중 가장 큰 Sampling 값을 가진 액션을 선택
		if r = 1 then # 클릭이 일어나면
			Sˆı = Sˆı + 1 # 앞에 Beta 분포값을 업데이트
		else # 클릭을 안한다면
			Fˆı = Fˆı + 1 # 뒤에 Beta 분포값을 업데이트
      end if
	end for

Lin UCB

Contextual Bandit

まずContext Banditとは何かを見てみましょう.
前述の文書では、Contextはid以外のfeature(ユーザのプレゼンテーショングラフィック、アイテムカテゴリ、ラベル)として定義されている.
Banditには,このようにContext情報を利用する方法や利用していない方法もある.

Context-free Bandit
同じ動作に対して,ユーザのコンテキスト情報にかかわらず,常に同じ奨励があると仮定し,モデリング手法により,人間の変化はタイガーマシンの奨励確率を変えることはない.
ex ) UCB, Epsilon Greedy

Contextual Bandit
プレイヤーのContext情報によって、同じ動作でもボーナスが異なります.例えば、同じスポーツ記事を見ても、年齢や性別によってクリック傾向が異なります.これは個人化推薦と関係がある.

LinUCB

今からLinUCBについて知りましょう
Arm-selection Strategy:アクションを選択するためのポリシー式
At≐argmax⁡a[xt,aTθa∗+αxt,aTAa−1xt,a], where Aa=DaTDa+IdA_{t}\doteq\underset{a}{\operatorname{argmax}}\left[{\mathrm{x}_{t, a}^{\mathrm{T}}\theta_{a}^{*}}+\alpha\sqrt{\left. x_{t, a}^T\mathbf{A}_{a}^{-1}\mathrm{x}_{t, a}\right.}\right],\quad\text { where }\mathbf{A}_{a}=\mathbf{D}_{a}^{\mathrm{T}}\mathbf{D}_{a}+\mathbf{I}_{d}At​≐aargmax​[xt,aT​θa∗​+αxt,aT​Aa−1​xt,a​​], where Aa​=DaT​Da​+Id​

xt,a:dmathm{x}{t,a}:dxt,a:d-ユーザとコンテキストの特徴をコンテキストベクトルとして使用する
(暴露物のプレイヤーの性別、年齢、暴露された時間空間情報、物の付加情報等)

θa∗\theta_{a}^{*}θa∮:動作aaaのddd階層学習パラメータ、各動作に1つのパラメータがあり、各動作がデータを収集するにつれて更新される

Da:tmathbf{D}a}:tDa:t点のmmm個のコンテキストベクトル(学習データ)からなるm×dm\times dm×チームです.
(現在のtimestepに基づいて合計m個の動作データが収集された場合、m×dm\times dm×d行列)

最初のterm xt,aTθa∗\mathrm{x}_{t, a}^{\mathrm{T}}\theta_{a}^{*}xt,aT​θa∮は、所与のコンテキストにおいてアクションaが選択されたときに得られる奨励金の期待値である.(Expected reward term)
第2学期αxt,aTAa−1xt,a\alpha\sqrt{\left. x_{t, a}^T\mathbf{A}_{a}^{-1}\mathrm{x}_{t, a}\right.}αxt,ata∮1 xt,aはそのaction aaaの探索であり,時間が経つにつれて収集された学習データが多ければ多いほど少ない.(Exploration Term)
このような式は学習データが増えるにつれてExploration Termが小さくなり,最終的にはExpected奨励に収束し,最も奨励の高いActionを選択する方向にExplorationを行う.
絵で調べてみよう

図には、3つの異なるContextを持つユーザーが表示されます.
ここで、xtmathm{x}txtは各ユーザのContext Vectorであり、各次元に以下の4つの次元の特性があると仮定する.

1階層:男性

2階層:女性

3次元:young

第四次元:old

代入図中のプレイヤーは,最初のプレイヤーのContextVectorxt=[1,0,0,1]TMathrm{x}t=[1,0,0,1]T=[1,0,0,0,1]Tがmalとoldの特性を持つと考えられる.
今、これらのプレイヤーがどんなものを選ぶかがMAB問題でお勧めの方法です.各項目(アクション)θa∗\theta_{a}^{*}θ勉強しなければなりません.
最初のプレイヤーはパンが好きです
2位のプレイヤーはパスタとビール
3番目のプレイヤーはパスタとパンが好きです.
もしそうなら、θ1∗\theta_{1}^{*}θ1∗は2人で集められたためD 1 D 1 Dに更新された.
2番目の3番目の動作も同様にDDDを更新する.

これらを学習した後、図のようにContext Vectorなどの次元のベクトルθa∗\theta_{a}^{*}θa∮たちは救われるだろう.
1つ目の動作(パスタ)のパラメータは、2つ目の次元が最も高い重みを持つことであり、女性の特性を持つプレイヤーに与えることができることを学ぶ最大の奨励である.
2番目(パン)、3番目(ビール)も同様に、学習はそれぞれ古い、若い特性を持つプレイヤーに高い奨励金を与える.
これにより、LinUCBは各プレイヤーのcontext vectorに基づいて、どのアイテムがより高い奨励を受けるか(クリック率がより高い)を学び、推奨します.

Context Bandit例：Naver Airs推奨システム

Banditの各動作はitemとなり,itemが多すぎると,人気度に基づくフィルタリングにより探索対象を数千個に縮小し,Context Banditアルゴリズムによりユーザの好みを探索・利用する.