ホーム » 「ベイズ推定」タグがついた投稿

タグアーカイブ: ベイズ推定

バンディットアルゴリズムの続き

2020年2月7日 / コメントする

こんにちは。kzです。

今回は前回のバンディットアルゴリズムの続きです。UCBと簡単なトンプソンサンプリングの実装を行います。前回実装した $\epsilon$ -GreedyとBoltzmann Softmaxとの最終的な比較も行います。

Keywords

この記事のキーワードを先にリストアップします。

$\epsilon$ -Greedy
Boltzmann Softmax
Hoeffding’s inequality
UCB
Bayesian UCB
Thompson Sampling
scaled inverse chi-squared Distribution

先頭２つは前回やったので３つ目から話します。

強化学習　Bandit Algorithm で入門する

Hoeffding’s inequality

Hoeffdingの不等式です。これはUCBの導出に使います。証明にはマルコフの不等式とチェビシェフの不等式を使います。まあそれは置いておいて、この不等式の意味を考えます。

確率変数 $Z$ の平均とその期待値の誤差 $t\in\mathbb{R}_+$ の確率を $t$ で測っています。これがまさに後述するUCBの核の考え方です。こちら側で $t$ そ操作することで、期待値のブレの許容範囲をある確率の範囲で操作することができます。

UCB

UCBはアームの期待値に加えてその上限（Upper Confidence Bound）、いわばアームの可能性（分散）、を考慮したアルゴリズムです。どうやって上限を加味するかといいますと、対象のアームを選択した回数の逆数で重み付けします。こうすることで多数引いたアームにはより小さい上限を、少数引いたアームにはより大きい上限を付与することができます。

これは直感的にもいいですよね。何度も引いたことのあるガチャガチャよりも数回しか引いたことのないガチャガチャの方が可能性を感じますよね。そういうことです。

ただし、

見ての通り、分母 $N_t(a)$ が小さいほど大きい値が加算されます。イメージは次の感じです。

お気づきかもしれませんが逆数と言いつつ、ルートを付けてます。気になりますよね。ということで証明します。先程のHoeffdingの不等式を用います。

Hoeffdingの不等式において $X_i \in [a,b]$ を $[0,1]$ として次が得られます。（ $u\geq 0$ ）。報酬はベルヌーイを仮定しました。

$a \in \mathcal{A}$ を一つとり固定します。私たちの問題に書き換えるためNotationを定義します。

$r_t(a)$ 報酬（確率変数）
$\mathcal{Q}(a)$ を真の行動価値
$\mathcal{\hat{Q}}(a)$ を経験上の行動価値
$u$ をupper confidence bound, $u=U_t(a)$

代入しますと

ここで上限に対する閾値をこちらで設定します。

これを $U_t(a)$ に関して解けば終了です

おや？よくみると2の位置が異なります。それは $\epsilon$ をこちらで設定する必要があるからです。confidence levelと言われます。

UCBはこのconfidence levelをパラメータとして持ちます。もっとも一般的な値は次のようになります。

そしてこの時のアルゴリズムをUCB1いいます。代入して計算すると

先程の結果になりました。では実装してみます。

実はよくない結果です。前回のEGとBSと比べるとわかります。この記事の最後に全アルゴリズムの比較を行いますのでとりあえずは進めていきます。

Bayesian UCB

UCBにベイズを応用したアルゴリズムのことです。今までは報酬の分布にベルヌーイを仮定しましたが、他にもガウス分布の仮定があります。それぞれ次のように呼びます

Bernoulli – Thompson Sampling
Gaussian – Thompson Sampling

察しの通り事後分布からパラメータをサンプリングしてアームを選択します。

本当にハードなんですが、Gaussianの場合の詳しい計算は

https://cafeunder.github.io/rosenblock-chainers-blog/2018/03/07/bayes-gaussian-mean-sigma.html

この方がやってくれています。

Thompson Sampling

定義は少し複雑ですが、実装の際はサンプリングを行うので思ったよりはシンプルです。

とある $a$ が他のどの $a'$ よりも価値が高い、という事後確率（ $\pi$ ）を計算して $a$ を選ぶアルゴリズムです。 $R_t$ は時刻tまでのアームのhistoryです。

事後確率は積分を用いて次のように計算されます。

ここで $R_i$ は $arm_i$ の報酬履歴です。左の積分が $\mathcal{Q}(a) = \theta_i$ になる確率で右の積分がその他のアームで $\mathcal{Q}(a') \leq \theta_i$ となる確率です。積分が解析的ではないので、サンプリングします。困ったときはサンプリングです。結果アルゴリズムは次のように単純化できます。

各アーム $a$ の報酬の期待値に関する事後分布 $\pi( \theta |R_a)$ から乱数 $\theta_a$ を生成
$TS(a) = \arg \max_{a\in\mathcal{A}} \theta_a \sim \pi( \theta |R_a)$

何度も言いますが報酬の分布はベルヌーイを仮定するので事後分布であるベータ分布は非常にシンプルになります。

実装では一様分布を仮定するのでパラメータは共に1とします。

Best Arm RateをUCBと比較してみます。

全アルゴリズムでBARとCumulative Rewardsも比較してみます。

Thompson Samplingが圧勝でした。

scaled inverse chi-squared Distribution

もしGaussianでThompson Samplingを実装するならばこちらを $\sigma^2$ の事前分布として導入します。（事前分布 $p(\mu, \sigma^2)$ を条件付き確率で分解する）scaled inverse chi-squared分布といいます。

$p (\sigma^2) \sim \mathcal{X}^2 (v_{0}, \hat{\sigma}_{0}^{2})$

Code

Gaussian Thompson Samplingすごく難しいですね、パラメータが多すぎてなにがなんだが、、、

次回はContextual BanditとIPSについてまとめたいと思います。でわ

References

MCMC入門 Gibbs Sampling

2019年12月27日 / コメントする

こんにちは。kzです。

本日はついにMCMCです。ベイズ推定とMAP推定がまだの方は次のリンクからどうぞ。

ギブスサンプリングをやっていくんですけど、その前にMCMCについて簡単に説明します。本当に簡単にです。

MCMC

マルコフ連鎖モンテカルロ法（Markov chain Monte Carlo methods、MCMC）　の略であり、求めたい確率分布をマルコフ連鎖を作成することをもとに、確率分布のサンプリングを行うアルゴリズムの総称である。

ここでマルコフ連鎖とは

確率過程の一種であり、未来 $t+1$ の挙動が現在 $t$ の値だけで決定され、過去の挙動と無関係である（マルコフ性）。各時刻において起こる状態変化（遷移または推移）に関して、マルコフ連鎖は遷移確率が過去の状態によらず、現在の状態のみによる系列である。

難しそうに聞こえますが簡単です。明日の飯が今日の気分だけで決まる感じです。

ちなみにMCと確率遷移行列（マルコフ行列）と呼ばれる物はセットですが、ここでは割愛。でわでわ、気を取り直してMCMCです。

ベイズ推定について述べた際に、 $P(D)$ の部分が解析的に解けないことがよくあると言いました。たとば多変量になればなるほど積分がシンドくなりますよね。ということで確率分布を直接求めるのではなく、そこからサンプリングして擬似的に求めようというものなんです。

Gibbs Sampling

で、MCMCの一つであるギブスサンプリングを今回やります。これは確率分布を条件付き確率分布に無理やり分解して一変量ずつサンプリングしようという作戦。もちろん、マルコフ性を仮定してます。

たとえば $p(x,y)$ という２変量の同時分布からサンプリングするよりも $p(x|y)$ の方が簡単ですよね。次元が一つ減ってるようなものなので。で、このアルゴリズムはCoordinate descentに似てます。注目する変数以外を固定して計算していくので座標降下法のようにジグザグにサンプリングされます。で、もちろん初期値は適当に選ぶんですけど、バーンインというものがあります。これは初期値から一定時間までの間に得られたサンプルは捨てようという期間です。

ギブスサンプリングをいきなりベイズ推定で使うのは難しいのでまずは簡単な例でアルゴリズムを理解してからベイズ推定に応用しようと思います。ではいきましょう。

2次元ガウス分布を用いた例

二次元ガウス分布（等高線プロットか3Dプロット）からサンプリングしようと思います。つまり、 $p(x,y)$ から点をどんどん取ってくるイメージです。最終的に下を目指します。（赤い点がサンプリングした点）

まずは $D$ 次元ガウス分布の式を思い出します。

今回は $D=2$ でやります。平均と分散は次のように設定します。

ただし、 $-1 < a < 1$ とします。逆行列と行列式も先に計算しておきます。

では同時分布 $p(x,y)$ をベクトル表記からスカラー表記に書き下します

で、目標の条件付き確率は

となり、先ほどの式を平方完成すると分母の周辺化が容易になるので

と、平方完成しました。あとはガッツリ積分していって条件付き確率を導出します。「なに分布にしたがうのかなー」と思いながら計算するといいです。

分母の積分をやっていくんですがガウス積分を使います。ガウス積分自体は極座標と重積分でいわゆる $I^2$ 計算で求まるのでここでは割愛します。

今、 $x_1$ 以外は固定しているので定数とみなせます。

あとはガウス積分を用いて

周辺化も計算できたことなので条件付き確率を改めて計算すると

これは $\mu= ax_2, \sigma =1$ の一次元ガウス分布ですね。つまり、正規分布にしたがうことがわかりました。よかったです。これでサンプリングできますね。次元も一つ落ちました。

ではコードを書いていく前に。アルゴリズムの流れの確認です。

$x_1, x_2$ をそれぞれ初期化
$p(x_1 \mid x_2)$ より $x1$ を発生させる
$x_1 = x_1$ で更新
$p(x_2 \mid x_1)$ より $x2$ を発生させる
$x_2 = x_2$ で更新
2.〜5.を繰り返す

上の真の分布に対してギブスサンプリングで得られたものは

いいかんじですね。今回は平均もゼロですし、シンプルだったので簡単でしたが一般化するともう僕はシンドイです。。。

ベイス推定に応用

ではギブスサンプリングを用いてパラメータの事後分布をサンプリングで得たいと思います。対象となるパラメータは一次元ガウス分布の $\mu, \sigma$ です。データ、尤度、事前分布を次のように設定します。

では $\mu$ をサンプリングするための条件付き確率の式を導出します。上の例のように正規分布になってくれるといいなーと思いながら導出します。

分母は関係ないので消し去りました。では $\mu$ に注目して計算します

よかったです。正規分布になりました。（4行目から5行目にかけては $\mu$ についての平方完成）

このノリで $\sigma$ をサンプリングするための条件付き確率の式を導出します。何度も言いますがどんな分布になるか想像しながら計算します。

先ほどと異なり、注目すべき変数は $\sigma$ です。となるとですね、