ベイズ方式による多腕バンディッドの論文を読む

テニススクール90分 英語できず

(1) ベイズ方式による多腕バンディッドの論文を読む

「Gaussian Process Optimization in the Bandit Setting:No Regret and Experimental Design」https://arxiv.org/abs/0912.3995

 バンディッドとはスロットマシンのことで、この論文は複数のスロットマシンへ出来るだけ少ない投資で沢山の報酬を得る戦略を考えるものです。

 一般に沢山投資すればする程よいスロットマシンが見つかるので、これは事前の予想を試行結果で改善するのでベイズモデルとなります。

 確率過程で無条件下では、ある時点から次の時点に推移するにはガウス分布の乱数で推移すると考えるのは合理的です。但しガウス分布の裾の広さ\sigmaは経験的に分っているとします。

      f:id:mabonki0725:20171006002642p:plain

     この確率過程で下図の様に実測が分っている場合はその点を通るモデルとしてガウス確率過程(GP:Gaussian Process)がります。

 下図はx軸に各スロットマシンが並んでおりy軸に報酬とした場合、真の平均の報酬曲線を推定する過程を示しています。GPは観測データが無い所は報酬の分散が広くなり、観測データがあると分散が狭くなる特性があります。

f:id:mabonki0725:20171005200211p:plain

 上図の様に分散が大きい所を試行すればより正確な曲線を把握できることがわかります。この様にすれば出来るだけ少ない投資で最上のマシンを見つける戦略が立てられそうです。

    上図の様に探索するには具体的には次式で探します。

    この方式をGP-UCB(Gaussian Process-Upper Confidence Bound)アルゴリズムと云います。

   x_t = argmax_{x \in \mathcal{D}} \{u_{t-1} (x)+ \beta^{1/2} \sigma_{t-1} (x)\}

      ここで

   u_{t-1}(x)1 \sim t-1回までの平均の報酬

            \sigma_{t-1}(x)1 \sim t-1回までの報酬の標準偏差

            \betaが大きいと霍乱項\sigmaを重視してxを選択します

            逆に\betaが少ないと経験を重視したグリィディな選択とります

 

 上式の値を得るためにGPは次の式で算出します。導出は下記のPRML記述参照

            u_t(x) = k_t(x) ^T( K_t + \sigma I) ^{-1} y_t     ①式

             \sigma_t^2(x) = k_t(x,x)

            k_t(x,x') = k(x,x') - k_t(x) ^T( K_t + \sigma I) ^{-1} k_t(x')

            ここで

               k(x,x') はベクトル xx'カーネル内積です

      k_t(x) = [k(x_1,x) \cdots k(x_t,x) ]^T

      y_tt時点で得られた報酬です

               K_tk(x,x')のグラム行列です

  ガウス過程では次の様なカーネルを使う場合が多いです。

     k(x,x') = \theta_0 \exp \left ( - \frac{\theta_1}{2}{|| x - x'||}^2 \right) + \theta_2 + \theta_3 x ^t x'    ガウスカーネル

     ここで \theta_1 \sim \theta_3は実際のデータより最尤法で計算されます。

 

 恒例のPRMLから①式を導出してみます。

 カーネルは2個のベクトルx \ x'を高次元に写像\phi(x)しています。

    写像関数はカーネルの種類によって異なります。

   k(x,x') = \phi(x)^T \phi(x')

 ガウス過程は高次元へ写像した関数での線形回帰を考えます。即ち高次元へ写像した方が非線形的な回帰を実現して当てはめが良くなります。

    まず損失関数J(w)を考え回帰係数w微分して極小値を採る様にします。

   J(w) = \frac{1}{2} \sum_{n=1}^N \{w^T \phi(x_n) - y_n \} - \frac{1}{2} w^Tw  ②式

 これをw微分すると

   \frac{dJ(w)}{dw} = \sum_{n=1}^N \{w^T \phi(x_n) - y_n \}\phi(x) -\lambda w = 0

            w = \frac{1}{\lambda}  \sum_{n=1}^N \{w^T \phi(x_n) - y_n \}\phi(x) ③式

    ここでa_n = \frac{1}{\lambda} \{w^T \phi(x_n) - y_n \} ④式 と置くと

   w = \sum _{n=1}^N a_n \phi(x_n) = \Phi^T a ⑤式

            但し \Phi = [\phi(x_1) \dots \phi(x_N)]^T  a = [a_1 \dots a_N]^T

  ④式をベクトル表現すると

             a = \frac{1}{\lambda} \{ \Phi w - y \}

     上式に⑤式を代入すると

    a = \frac{1}{\lambda} \{\Phi \Phi^T a - y\}

    これをaについて解くと 但し  \Phi \Phi^T = K

           a = (K + \lambda I_N) ^{-1} y

   y(x) = w^T \phi(x)カーネル写像の回帰モデルなので ⑤式を使って

           y(x) = w^T \phi(x) = a^T \Phi \phi(x) =\{\Phi \phi(x)\}^T a = k(x)^T (K + \lambda I_n) ^ {-1} y   ①式が導出された

    但し  k(x) = \{\Phi \phi(x)\} =  [\phi(x_1) \phi(x) \dots \phi(x_N) \phi(x)] = [k(x_1,x) \dots k(x_N,x) ]