2018年4月22日日曜日

Variational Auto Encoder 〜その2〜

はじめに


 先のページで、Variational Auto Encoder(VAE)をBayes推論の枠組みで解説し、Chainerのサンプルコードをみた。今回は、サンプルコードを実際に動かし、その動作を確認する。

前回の補足


 前回の式(16)は、観測値$X$の下での未知変数$\vec{x}$の実現確率であった。 \begin{equation} p(\vec{x}|X)\approx \int d\vec{\epsilon}\;\mathcal{N}(\vec{\epsilon}|\vec{0},I_D)\;p(\vec{x}|\vec{z}) \end{equation} ここで、$z_d=\mu_{\phi,d}(X)+\sigma_{\phi,d}(X)\epsilon_d$である。$\vec{x}$の各成分が独立同分布で生成されると仮定すると、以下のように書き換えることができる。 \begin{equation} \prod_{m=1}^M p(x_{m}|X)\approx \int d\vec{\epsilon}\;\mathcal{N}(\vec{\epsilon}|\vec{0},I_D)\;\prod_{m=1}^M p(x_m|\vec{z}) \end{equation} すなわち、要素$x_m$ごとに次式が成り立つ。 \begin{equation} p(x_{m}|X)\approx \int d\vec{\epsilon}\;\mathcal{N}(\vec{\epsilon}|\vec{0},I_D)\;p(x_m|\vec{z}) \end{equation} $p(x_m|\vec{z})$としてBernoulli分布を仮定したから \begin{equation} p(x_{m}|X)\approx \int d\vec{\epsilon}\;\mathcal{N}(\vec{\epsilon}|\vec{0},I_D)\;\mathrm{Bern}(x_m|\eta_{\theta,m}(\vec{z})) \end{equation} となる。確率分布$p(x_{m}|X)$の下での$x_m$の期待値は \begin{eqnarray} <x_m>&=&\sum_{x_m=0,1} x_m\;p(x_{m}|X) \\ &\approx& \int d\vec{\epsilon}\;\mathcal{N}(\vec{\epsilon}|\vec{0},I_D)\;\sum_{x_m=0,1} x_m \mathrm{Bern}(x_m|\eta_{\theta,m}(\vec{z})) \\ &=& \int d\vec{\epsilon}\;\mathcal{N}(\vec{\epsilon}|\vec{0},I_D)\;\eta_{\theta,m}(\vec{z}) \end{eqnarray} となる。$\vec{z}$は$\vec{\epsilon}$に依存する項であることに注意する。ここまでの議論で言えることは、復号化した結果を得るには、$\eta_{\theta,m}(\vec{z})$を標準正規分布に従ってサンプリングすれば良いということである。$\eta_{\theta,m}(\vec{z})$はDecoderの出力である。

Chainerの実装の確認


 前回は、net.pyを見たので、今回はtrain_vae.pyを見る。trainerを用いた実装部分は特に指摘することはないので、結果を描画している箇所を解説する。最初は訓練データに関わる描画部分である。 適当に画像を9枚選択し、これを関数__call__で符号化・復号化している。前回指摘したように、復号化の際、$\sigma_{\phi,d}(X)$は無視されている。計算のあと元画像と復号化画像を保存している。epochを100とした結果は以下の通りである。

訓練画像


復号化した訓練画像

次はテスト画像に関わる部分である。 ここでも適当に9枚の画像を選択し、元画像と復号化画像を保存している。epochを100とした結果は以下の通りである。

テスト画像


復号化したテスト画像

最後に、標準正規分布に従う値$\vec{z}$から復号化する部分である。 9個の乱数$\vec{z}$を作り、関数decodeを呼び出している。epochを100とした結果は以下の通りである。
訓練・テスト画像を符号化・復号化した結果と比べるとかなり精度の悪い結果である。関数decodeは$\eta_{\theta,m}(\vec{z})$を出力する。上で見たように本来の$\vec{z}$は、$z_d=\mu_{\phi,d}(X)+\sigma_{\phi,d}(X)\epsilon_d$として与えらるべきものである。精度が悪いのは、$\vec{z}$を標準正規分布に置き換えたことが原因である。ところで、勾配降下法で最小にすべき式の1つが次式であった(前回の式(19))。 \begin{equation} D_{KL} \left[ q_{\phi}(\vec{z}|X)||p(\vec{z}) \right]= \frac{1}{2} \sum_{d=1}^{D}\left\{ -\ln{\sigma^2_{\phi,d}(X)}-1+\sigma^2_{\phi,d}(X)+\mu_{\phi,d}^2(X) \right\} \end{equation} これを十分小さくできれば、すなわち、$\sigma_{\phi,d}\rightarrow 1, \mu_{\phi,d}\rightarrow 0$とできれば、標準正規分布による置き換えは意味があるものになる。残念ながらepochを1000としても大して精度は良くならない。Chainerのサンプル実装を変更する必要があるかもしれない。

まとめ


 今回は、$<x_m>$が$\eta_{\theta,m}(\vec{z})$を求めることに帰着すること示し、Chainerのサンプルコードの計算結果を考察した。 さらに、標準正規分布による$\vec{z}$から計算した画像の精度が悪い理由についても述べた。改善するには、epoch数を増やすだけではなくコードの見直し(多層化、初期化関数の変更)も必要であろう。次回はこの辺りのことについてまとめたい。

2018年4月15日日曜日

Variational Auto Encoder

はじめに


 Variational Auto Encoder(VAE)をBayes推論の枠組みで解説し、Chainerのサンプルコードを読解する。

問題設定


 観測値$X=\{\vec{x}_1,\cdots,\vec{x}_N\}$が与えられたとき、未知の値$\vec{x}_*$を生成する確率分布$p(\vec{x}_*|X)$を求めたい。潜在変数$\vec{z}$を導入し、$X$と$\vec{z}$の同時確率分布$p(X,\vec{z})$を考え、Bayesの定理を適用すると次式を得る。 \begin{equation} p(\vec{z}|X) = \frac{p(X|\vec{z})p(\vec{z})}{p(X)} \label{eq9} \end{equation} 事後確率$p(\vec{z}|X)$が求まれば、次式により$\vec{x}_*$を生成する確率分布を求めることができる。 \begin{equation} p(\vec{x}_*|X)=\int d\vec{z}\;p(\vec{x}_*|\vec{z})p(\vec{z}|X) \label{eq3} \end{equation} 事後確率$p(\vec{z}|X)$を求めることが目的である。

最適化すべき量


 $p(\vec{z}|X)$を直接求めることはせず、パラメータ$\phi$を持つ関数$q_{\phi}(\vec{z}|X)$を導入し、次のKullback Leibler divergenceを最小にすることを考える。 \begin{equation} D_{KL} \left[ q_{\phi}(\vec{z}|X)||p(\vec{z}|X) \right]=\int d\vec{z}\;q_{\phi}(\vec{z}|X) \ln{ \frac{ q_{\phi}(\vec{z}|X) } { p(\vec{z}|X) } } \end{equation} これを変形すると次式を得る。 \begin{equation} D_{KL} \left[ q_{\phi}(\vec{z}|X)||p(\vec{z}|X) \right] = D_{KL} \left[ q_{\phi}(\vec{z}|X)||p(\vec{z}) \right]-E_{q_{\phi}(\vec{z}|X)}\left[\ln{p(X|\vec{z})}\right]+\ln{p(X)} \label{eq1} \end{equation} ただし、式変形の途中で式(\ref{eq9})を用いた。式(\ref{eq1})右辺にある$\ln{p(X)}$は$\phi$に依存せず、観測値だけから決まる定数である。従って、次式が成り立つ。 \begin{equation} \min_{\phi} D_{KL} \left[ q_{\phi}(\vec{z}|X)||p(\vec{z}|X) \right] = \min_{\phi} {\left[ D_{KL} \left[ q_{\phi}(\vec{z}|X)||p(\vec{z}) \right]-E_{q_{\phi}(\vec{z}|X)}\left[\ln{p(X|\vec{z})}\right] \right] } \label{eq2} \end{equation} 式(\ref{eq2})の右辺第1項を小さく、第2項の期待値を大きくすれば良い。第1項は$q_{\phi}(\vec{z}|X)$をできるだけ$p(\vec{z})$に近い形の分布にすることを要求し、この分布の下で対数尤度$\ln{p(X|\vec{z})}$の期待値を大きくすることを第2項は要求する。第1項は正則化項に相当する。

KL divergenceの計算


 式(\ref{eq2})の右辺第1項を考える。いま次の仮定をおく。 \begin{eqnarray} q_{\phi}(\vec{z}|X)&=&\mathcal{N}(\vec{z}|\vec{\mu}_{\phi}(X),\Sigma_{\phi}(X)) \\ p_(\vec{z})&=&\mathcal{N}(\vec{z}|\vec{0},I_D) \end{eqnarray} ここで、$\vec{z}$の次元を$D$とした。$I_D$は$D\times D$の単位行列である。どちらの分布も正規分布とし、$q_{\phi}(\vec{z}|X)$の平均と共分散行列は$\phi$と$X$から決まる量とする。これらは、入力$X$、パラメータ$\phi$のニューラルネットワークを用いて計算される。一方、$p(\vec{z})$の方は平均0、分散1の標準正規分布である。このとき、$D_{KL} \left[ q_{\phi}(\vec{z}|X)||p(\vec{z}) \right]$は解析的に計算することができる。 \begin{equation} D_{KL} \left[ q_{\phi}(\vec{z}|X)||p(\vec{z}) \right]=\frac{1}{2}\left[ -\ln{|\Sigma_{\phi}(X)|} -D +\mathrm{Tr}\left(\Sigma_{\phi}(X)\right)+\vec{\mu}_{\phi}(X)^T\vec{\mu}_{\phi}(X) \right] \label{eq4} \end{equation}

ここまでの処理の流れ


 式(\ref{eq2})の最適化を行う際に勾配降下法を用いる。処理の流れは以下のようになる(下図参照)。
分布$q_{\phi}(\vec{z}|X)$は$X$から$\vec{z}$を生成するEncoder、$p(X|\vec{z})$は$\vec{z}$から$X$を生成するDecoderとみなすことができる。青色で示した部分は最小化すべき量であり、赤字はサンプリングするステップである。勾配降下法を実現するには、誤差逆伝播ができなければならない。$q_{\phi}(\vec{z}|X)$はその$\phi$依存性のため誤差逆伝播時の微分鎖の中に組み込まれるが、サンプリグという処理の勾配を定義することができない。対数尤度の期待値の計算に工夫が必要である。

対数尤度の期待値の計算


 計算したい式は次式である。 \begin{equation} E_{q_{\phi}(\vec{z}|X)}\left[\ln{p(X|\vec{z})}\right]=\int d\vec{z}\;q_{\phi}(\vec{z}|X)\ln{p(X|\vec{z})} \end{equation} この式に再パラメータ化トリック(re-parametrization trick)を適用する。すなわち \begin{equation} \vec{z}\sim\mathcal{N}(\vec{z}|\vec{\mu}_{\phi}(X),\Sigma_{\phi}(X)) \end{equation} の代わりに \begin{eqnarray} \vec{\epsilon}&\sim&\mathcal{N}(\vec{\epsilon}|\vec{0},I_D)\\ \vec{z}&=& \vec{\mu}_{\phi}(X)+\Sigma_{\phi}^{1/2}(X)\vec{\epsilon} \label{eq7} \end{eqnarray} を用いてサンプリングを行う。これを用いて期待値を書き直すと次式を得る。 \begin{equation} E_{q_{\phi}(\vec{z}|X)}\left[\ln{p(X|\vec{z})}\right]=\int d\vec{\epsilon}\;\mathcal{N}(\vec{\epsilon}|\vec{0},I_D)\ln{p(X| \vec{z}=\vec{\mu}_{\phi}(X)+\Sigma_{\phi}^{1/2}(X)\vec{\epsilon})} \end{equation} このときの処理の流れは以下のようになる(下図参照)。
上図であれば誤差逆伝播が可能となる。

未知変数の生成


 未知変数を生成する確率分布は次式で与えられた。 \begin{equation} p(\vec{x}_*|X)=\int d\vec{z}\;p(\vec{x}_*|\vec{z})p(\vec{z}|X) \end{equation} 事後確率$p(\vec{z}|X)$の近似解$q_{\phi}(\vec{z}|X)$を用いると \begin{equation} p(\vec{x}_*|X)\approx\int d\vec{z}q_{\phi}(\vec{z}|X)p(\vec{x}_*|\vec{z}) \end{equation} を得る。先と同様に再パラメータ化トリックを適用すると \begin{equation} p(\vec{x}_*|X)\approx\int d\vec{\epsilon}\mathcal{N}(\vec{\epsilon}|\vec{0},I_D)p(\vec{x}_*| \vec{z}=\vec{\mu}_{\phi}(X)+\Sigma_{\phi}^{1/2}(X)\vec{\epsilon}) \end{equation} となる。

Chainer実装の確認


 ChainerのサンプルコードにVAEがある。これはMNISTデータセットにVAEを適用したものである。MNISTは2値画像であるから$\vec{x}_n$として0と1が784(=28$\times$28)個並んだベクトルを考えることになる。実際にコードを見て行く前に先に導出した式をもう少し詳細に計算しておく。

 最初に$\vec{\mu}_{\phi}(X)$と$\Sigma_{\phi}(X)$を次のように置く。 \begin{eqnarray} \vec{\mu}_{\phi}(X)&=&(\mu_{\phi,1}(X),\cdots,\mu_{\phi,D}(X))^T \label{eq5}\\ \Sigma_{\phi}(X)&=&\mathrm{diag}(\sigma^2_{\phi,1}(X),\cdots,\sigma^2_{\phi,D}(X)) \label{eq6} \end{eqnarray} このとき式(\ref{eq4})は次式となる。 \begin{equation} D_{KL} \left[ q_{\phi}(\vec{z}|X)||p(\vec{z}) \right]= \frac{1}{2} \sum_{d=1}^{D}\left\{ -\ln{\sigma^2_{\phi,d}(X)}-1+\sigma^2_{\phi,d}(X)+\mu_{\phi,d}^2(X) \right\} \label{eq8} \end{equation} また、$\vec{z}$の成分は次式で与えられる。 \begin{equation} z_d=\mu_{\phi,d}(X)+\sigma_{\phi,d}(X)\epsilon_d \end{equation} 観測値が独立同分布に従うと仮定すると対数尤度は以下のように変形される。 \begin{equation} \ln{p(X|\vec{z})}= \sum^{N}_{n=1}\ln{p(\vec{x}_n|\vec{z})} \end{equation} $\vec{x}_n$の次元数を$M$(=784)とすると \begin{equation} \ln{p(\vec{x}_n|\vec{z})}=\sum_{m=1}^{M}\ln{p(x_{n,m}|\vec{z})} \end{equation} となる。いま考える画像は0と1から構成される。従って、$p(x_{n,m}|\vec{z})$として0と1を生成する確率分布であるBernoulli分布を仮定する。 \begin{eqnarray} p(x_{n,m}|\vec{z})&=&\mathrm{Bern}\left(x_{n,m}|\eta_{\theta,m}\left(\vec{z}\right)\right) \\ \mathrm{Bern}(x|\eta)&=&\eta^{x}(1-\eta)^{1-x} \end{eqnarray} $\eta_{\theta,m}\left(\vec{z}\right)$は、入力$\vec{z}$、パラメータ$\theta$のネットワークで学習される量である。 以上を踏まえて処理の流れを書き直すと下図となる。

以上で準備が整ったので順にコードを見ていく。まず最初にネットワークを定義したクラスVAEを見る。コンストラクタは以下の通り。 Encoderとして$\vec{\mu}_{\phi}(X)$と$\Sigma_{\phi}(X)$を生成する層がそれぞれ1層ずつ定義されている。Decoderとして$\vec{\eta}_{\theta}(\vec{z})$を生成する2層が定義されている。次に関数encodeを見る。 $\mu_{\phi,d}$と$\ln{\sigma_{\phi,d}^2}$を生成する処理が記述されている。次は関数decodeである。 $\vec{z}$を受け取り$\vec{\eta}_{\theta}(\vec{z})$を返す処理が記述されている。次は__call__である。 Encoderで計算した平均を入力としてDecoderを呼び出している。分散を無視して復号化している。次はget_loss_funcである。
  • 13行目:Encoderで平均と対数分散を計算する。
  • 17行目:ここから始まるループは$\vec{z}$のサンプリングのためのものである。
  • 18行目:正規分布からサンプリングする。関数F.gaussianの中で再パラメータ化トリックが実行されていることに注意する。
  • 19行目:Bernoulli分布の対数にマイナスを付けたものが計算される。
  • 23行目:式(\ref{eq8})が計算される。

  • まとめ


     今回は、VAEをBayes推論の枠組みで解説し、Chainerのサンプルコードを見た。ニューラルネットワークで計算されるのは確率分布のパラメータであることを明確に示した。言い換えると他の手法でパラメータを計算できるのであればそれでも構わないということである。計算の仮定で確率分布にいくつかの仮定(ガウス分布やBernoulli分布)をしていることに注意しなければならない。今回Bernoulli分布を使用したのはターゲットとした観測値が0と1から構成される2値画像であるためである。2値でない観測値を対象とするならそれに見合った確率分布を導入する必要がある。次回はChainerのコードを動かして得られる結果を考察したい。

    参考文献


  • Tutorial on Variational Autoencoders
  • Pattern Recognition and Machine Learning
  • ベイズ推論による機械学習入門
  • Variational Autoencoder徹底解説
  • 2018年3月11日日曜日

    強化学習 〜Fisher情報行列と自然勾配法〜

    はじめに


     先のページで方策勾配定理を導いた。すなわち、時間ステップ$t=0$から始める状態価値関数$J(\theta;s_0)$に対して次式が成り立つことを示した。 \begin{equation} \frac{\partial J(\theta;s_0)}{\partial \theta} = {\bf E}\left[\frac{\partial \ln{\pi_{\theta}(a|s)}}{\partial \theta}\;Q(s,a)\right] \end{equation} 今回は、$\theta$をベクトル$\vec{\theta}$に拡張した式 \begin{equation} \vec{\nabla}_{\theta}J(\vec{\theta};s_0) = {\bf E} \left[ \vec{\nabla}_{\theta} \ln{\pi_{\theta}(a|s)}\;Q(s,a) \right] \label{eq2} \end{equation} を考え、$J(\vec{\theta};s_0)$を勾配法で最大化する過程で用いられる手法をまとめる。以降、$J(\vec{\theta};s_0)$を$J(\vec{\theta})$と書く。

    Fisher情報行列の導出


     2つの確率分布$P(w),Q(w)$を考え、これらの間のKullback-Leibler divergenceを考える。 \begin{equation} D(P,Q)=\int dw\; P(w) \ln{\frac{P(w)}{Q(w)}} \end{equation} この量を対称化して、2つの確率分布間の「距離」を表すことができるようにする。 \begin{eqnarray} D_s(P,Q) &=&\int dw\; P(w) \ln{\frac{P(w)}{Q(w)}}+\int dw\; Q(w) \ln{\frac{Q(w)}{P(w)}}\\ &=&\int dw\; \left(P(w)-Q(w)\right) \ln{\frac{P(w)}{Q(w)}} \end{eqnarray} いま、パラメータ$\vec{\theta}$を持つモデルで表現された確率分布$P(w|\vec{\theta})$を考え、パラメータをわずかに変えた後の分布$P(w|\vec{\theta}+d\vec{\theta})$との間の距離$D_s$を計算する。 \begin{eqnarray} D_s(P(w|\vec{\theta}+d\vec{\theta}),P(w|\vec{\theta})) &=&\int dw\; \left(P(w|\vec{\theta}+d\vec{\theta})-P(w|\vec{\theta})\right) \ln{\frac{P(w|\vec{\theta}+d\vec{\theta})}{P(w|\vec{\theta})}} \\ &=&\int dw\; \delta(w|\vec{\theta}) \ln{\frac{\delta(w|\vec{\theta})+P(w|\vec{\theta})}{P(w|\vec{\theta})}} \label{eq0} \end{eqnarray} ここで、 \begin{equation} \delta(w|\vec{\theta})\equiv P(w|\vec{\theta}+d\vec{\theta})-P(w|\vec{\theta}) \end{equation} と置いた。式(\ref{eq0})は$\delta(w|\vec{\theta})$が微小量であることに注意すると以下のように変形することができる。 \begin{eqnarray} D_s(P(w|\vec{\theta}+d\vec{\theta}),P(w|\vec{\theta})) &=&\int dw\; \delta(w|\vec{\theta}) \ln{\frac{\delta(w|\vec{\theta})+P(w|\vec{\theta})}{P(w|\vec{\theta})}} \\ &=&\int dw\; \delta(w|\vec{\theta}) \ln{\left(1+\frac{\delta(w|\vec{\theta})}{P(w|\vec{\theta})}\right)} \\ &\simeq&\int dw\; \delta(w|\vec{\theta}) \frac{\delta(w|\vec{\theta})}{P(w|\vec{\theta})} \label{eq1} \end{eqnarray} ところで、$\delta(w|\vec{\theta})$は次のように計算される。 \begin{eqnarray} \delta(w|\vec{\theta}) &=&P(w|\vec{\theta}+d\vec{\theta})-P(w|\vec{\theta}) \\ &\simeq&\sum_i\;\frac{\partial P(w|\vec{\theta})}{\partial \theta_i} d\theta_i \\ &=&P(w|\vec{\theta})\sum_i\;\frac{\partial\ln{ P(w|\vec{\theta})} }{\partial\theta_i}d\theta_i \end{eqnarray} これを式(\ref{eq1})に代入する。 \begin{eqnarray} D_s(P(w|\vec{\theta}+d\vec{\theta}),P(w|\vec{\theta})) &\simeq& \int dw\; \left[P(w|\vec{\theta})\sum_i\;\frac{\partial\ln{ P(w|\vec{\theta})} }{\partial\theta_i}d\theta_i\right] \frac{P(w|\vec{\theta})\sum_j\;\frac{\partial\ln{ P(w|\vec{\theta})} }{\partial\theta_j}d\theta_j}{P(w|\vec{\theta})} \\ &=& \int dw\; \left[P(w|\vec{\theta})\sum_i\;\frac{\partial\ln{ P(w|\vec{\theta})} }{\partial\theta_i}d\theta_i\right] \sum_j\;\frac{\partial\ln{ P(w|\vec{\theta})} }{\partial\theta_j}d\theta_j \\ &=& \sum_{i,j}\;d\theta_i \left[\int dw\; P(w|\vec{\theta}) \frac{\partial\ln{ P(w|\vec{\theta})} }{\partial\theta_i} \frac{\partial\ln{ P(w|\vec{\theta})} }{\partial\theta_j}\right] d\theta_j \\ &=& \sum_{i,j}\;d\theta_i\; {\bf E}\left[ \frac{\partial\ln{ P(w|\vec{\theta})} }{\partial\theta_i} \frac{\partial\ln{ P(w|\vec{\theta})} }{\partial\theta_j}\right] d\theta_j \end{eqnarray} ここで、${\bf E}[\cdot]$は確率$P(w|\vec{\theta})$の下での期待値を表す。いま \begin{equation} F_{i,j}(\vec{\theta})\equiv {\bf E}\left[ \frac{\partial\ln{ P(w|\vec{\theta})} }{\partial\theta_i} \frac{\partial\ln{ P(w|\vec{\theta})} }{\partial\theta_j}\right] \label{eq4} \end{equation} と置くと \begin{eqnarray} D_s(P(w|\vec{\theta}+d\vec{\theta}),P(w|\vec{\theta})) &\simeq& \sum_{i,j}\;d\theta_i\;F_{i,j}(\vec{\theta})\;d\theta_j\\ &=&d\vec{\theta}^{T}F(\vec{\theta})\;d\vec{\theta} \end{eqnarray} を得る。$F(\vec{\theta})$をFisher情報行列と呼ぶ。$D_s$は微小距離の2乗に相当する量である。従って、$F(\vec{\theta})$は今考えているパラメータ空間(リーマン空間)における計量テンソルと見ることができる。

    自然勾配法


     パラメータ$\vec{\theta}=(\theta_1,\cdots,\theta_n)$の張る空間上の関数$f(\vec{\theta})$を考える。$f(\vec{\theta})$の微小変化は次式で与えられる。 \begin{equation} \delta f\equiv f(\vec{\theta}+d\vec{\theta})-f(\vec{\theta})=\vec{\nabla}f^T d\vec{\theta} \end{equation} $\delta f$が最大となる向き$d\vec{\theta}$を、$\|d\vec{\theta}\|^2=\epsilon^2$の条件の下で考える。ここで、$\epsilon$は微小な定数である。ところで、リーマン空間において 、$\|d\vec{\theta}\|^2$は計量テンソル$G(\vec{\theta})$を用いて、次のように書くことができる。 \begin{equation} \|d\vec{\theta}\|^2=d\vec{\theta}^{T}G(\vec{\theta})\;d\vec{\theta} \end{equation} 従って、$\delta f$が最大となる向きは、Lagrangeの未定乗数法を用いて、次を最大化することで求めることができる。 \begin{equation} L=\vec{\nabla}f^T d\vec{\theta} -\lambda\left(d\vec{\theta}^{T}G(\vec{\theta})\;d\vec{\theta}-\epsilon^2 \right) \end{equation} $d\theta_i$で偏微分して0と置く。 \begin{equation} \frac{\partial L}{\partial d\theta_i}=\frac{\partial f}{\partial \theta_i}-2\lambda\sum_j\;G_{i,j}(\vec{\theta})d\theta_j=0 \end{equation} これより \begin{equation} \vec{\nabla}f = 2\lambda\;G(\vec{\theta})d\vec{\theta} \end{equation} を得る。$d\vec{\theta}$について解くと \begin{equation} d\vec{\theta}\propto G^{-1}(\vec{\theta})\vec{\nabla}f \end{equation} を得る。これが微小変化$\delta f$が最大となる向きである。この向きを利用する勾配法を自然勾配法と呼ぶ。ユークリッド空間の場合は$G$を単位行列と置けば良い。

    方策勾配への適用


     $J(\vec{\theta})$の勾配を最大にする向きは、先の議論より \begin{equation} d\vec{\theta}\propto F^{-1}(\vec{\theta})\vec{\nabla}_{\theta}J(\vec{\theta}) \label{eq5} \end{equation} で与えられる。ただし、ここでの情報行列$F(\vec{\theta})$は式(\ref{eq4})の$P(w|\vec{\theta})$を$\pi_{\theta}(a|s)$に置き換えた次式で定義される。 \begin{equation} F(\vec{\theta})\equiv{\bf E} \left[ \vec{\nabla}_{\theta}\ln{\pi_{\theta}(a|s)} \vec{\nabla}_{\theta}^T\ln{\pi_{\theta}(a|s)} \right] \end{equation} 式(\ref{eq5})に式(\ref{eq2})を代入する。 \begin{equation} d\vec{\theta}\propto F^{-1}(\vec{\theta})\;{\bf E} \left[ \vec{\nabla}_{\theta} \ln{\pi_{\theta}(a|s)}\;Q(s,a) \right] \label{eq3} \end{equation} $Q(s,a)$をパラメータ$\vec{w}$を用いた次のモデルで近似することがよく行われる。 \begin{equation} Q(s,a)=\vec{w}^T \vec{\nabla}_{\theta}\ln{\pi_{\theta}(a|s)} \end{equation} これを、式(\ref{eq3})に代入すると \begin{eqnarray} d\vec{\theta} &\propto& F^{-1}(\vec{\theta})\;{\bf E} \left[ \vec{\nabla}_{\theta} \ln{\pi_{\theta}(a|s)}\;\left[\vec{w}^T \vec{\nabla}_{\theta}\ln{\pi_{\theta}(a|s)}\right] \right] \\ &=& F^{-1}(\vec{\theta})\;{\bf E} \left[ \vec{\nabla}_{\theta}\ln{\pi_{\theta}(a|s)} \vec{\nabla}_{\theta}^T\ln{\pi_{\theta}(a|s)} \right] \vec{w}\\ &=& F^{-1}(\vec{\theta})\;F(\vec{\theta})\;\vec{w}\\ &=& \vec{w} \end{eqnarray} を得る。つまり、$J(\vec{\theta})$を更新する際の$\vec{\theta}$の向きは、$\vec{w}$と一致することになる(というより、こうなるように$Q(s,a)$を近似するのだろう)。

    参考文献


    2018年2月18日日曜日

    強化学習 〜ベルマン最適方程式〜

    はじめに


     先のページでベルマン方程式の導出を行った。この議論に追記を行い、ベルマン最適方程式を示す。

    不動点方程式


     状態価値関数$V(s)$に対し、次のベルマン方程式が成り立つことを見た。 \begin{equation} V(s)=\sum_{s^{\prime},a} P(s^{\prime}|s,a)\pi(a|s)\left[r(s,a,s^{\prime})+\gamma V(s^{\prime})\right] \end{equation} ここで、右辺第1項,第2項に対し \begin{eqnarray} \eta^{V}(s)&\equiv&\sum_{s^{\prime},a}P(s^{\prime}|s,a)\pi(a|s)r(s,a,s^{\prime}) \\ M^{V}(s,s^{\prime})&\equiv&\sum_{a}P(s^{\prime}|s,a)\pi(a|s) \end{eqnarray} を定義すると \begin{equation} V(s)=\eta^{V}(s)+\gamma \sum_{s^{\prime}}M^{V}(s,s^{\prime})V(s^{\prime}) \end{equation} を得る。いま、状態が$D$個に離散化されている場合を考えると、$V(s)$は$D$次元ベクトル$\vec{V}$の第$s$番目の成分と見ることができる。$M^{V}(s,s^{\prime})$は行列$M^{V}$の$(s,s^{\prime})$成分である。従って、次式を得る。 \begin{equation} \vec{V}=\vec{\eta}^{\;V}+\gamma M^{V}\vec{V} \end{equation} この式の右辺を眺めると、平行移動と線形変換の組み合わせ、すなわち、アフィン変換であることが分かる。このアフィン変換をベルマン作用素と呼ぶ。ベルマン作用素を$T^{V}$で表すと \begin{equation} \vec{V}=T^{V}\vec{V} \end{equation} となる。これは、変換後の自身が自身に等しくなることから不動点方程式であり、$0<\gamma<1$のとき唯一解$\vec{V}$を持つことが知られている。

     次に、行動価値関数$Q(s,a)$について考える。$Q(s,a)$のベルマン方程式は次式であった。 \begin{equation} Q(s,a)=\sum_{s^{\prime}} P(s^{\prime}|s,a)\left[r(s,a,s^{\prime})+\gamma \sum_{a^{\prime}}\pi(a^{\prime}|s^{\prime})Q(s^{\prime},a^{\prime})\right] \end{equation} ここで \begin{eqnarray} \eta^{Q}(s,a)&\equiv&\sum_{s^{\prime}}P(s^{\prime}|s,a)r(s,a,s^{\prime}) \\ M^{Q}(s,a,s^{\prime},a^{\prime})&\equiv&P(s^{\prime}|s,a)\pi(a^{\prime}|s^{\prime}) \end{eqnarray} を導入すると \begin{equation} Q(s,a)=\eta^{Q}(s,a)+\gamma\sum_{s^{\prime},a^{\prime}}M^{Q}(s,a,s^{\prime},a^{\prime})Q(s^{\prime},a^{\prime}) \end{equation} を得る。今度は状態だけでなく行動も$D^{\prime}$個に離散化されている場合を考える。このとき$Q(s,a)$は$D\times D^{\prime}$次元のベクトルになる。$(s,a)$を1つの添え字で表せば、状態価値関数のときと同じ議論を繰り返すことができ、次式を得る。 \begin{equation} \vec{Q}=\vec{\eta}^{\;Q}+\gamma M^{Q}\vec{Q} \end{equation} 右辺はアフィン変換であり、ベルマン作用素$T^{Q}$を使うと \begin{equation} \vec{Q}=T^{Q}\vec{Q} \end{equation} と書くことができる。これも不動点方程式であり、$0<\gamma<1$のとき唯一解$\vec{Q}$を持つことが知られている。

    ベルマン最適方程式


     $V(s)$と$Q(s,a)$のベルマン方程式を再度示す。 \begin{eqnarray} V(s)&=&\sum_{s^{\prime},a} P(s^{\prime}|s,a)\pi(a|s)\left[r(s,a,s^{\prime})+\gamma V(s^{\prime})\right]\\ Q(s,a)&=&\sum_{s^{\prime}} P(s^{\prime}|s,a)\left[r(s,a,s^{\prime})+\gamma \sum_{a^{\prime}}\pi(a^{\prime}|s^{\prime})Q(s^{\prime},a^{\prime})\right] \end{eqnarray} これらは、方策$\pi$を用いて、ある状態に対する行動を選択している。いま、方策$\pi$を介さずに、最適な行動を直接選択することを考える。上式の$\sum_{a}\pi(a|s)$を形式的に$\max_a$で置き換えると次式を得る。 \begin{eqnarray} V^{*}(s)&=&\max_{a}\sum_{s^{\prime}} P(s^{\prime}|s,a)\left[r(s,a,s^{\prime})+\gamma V^{*}(s^{\prime})\right]\\ Q^{*}(s,a)&=&\sum_{s^{\prime}} P(s^{\prime}|s,a)\left[r(s,a,s^{\prime})+\gamma \max_{a^{\prime}}Q^{*}(s^{\prime},a^{\prime})\right] \end{eqnarray} これらは、最適状態価値関数$V^{*}(s)$と最適行動価値関数$Q^{*}(s,a)$に対し、厳密に成り立つことが知られており、ベルマン最適方程式と呼ばれる。これらについては不動点方程式の形に変形することはできないが、やはり、唯一解が存在することが知られている。

    参考文献


    2018年2月13日火曜日

    強化学習 〜方策勾配定理の導出〜

    はじめに


     前回に引き続き、強化学習のテキスト「これからの強化学習」に出てくる方策勾配定理を導出する。自身のための覚書である。

    最大化すべき目的関数


     状態価値関数$V(s)$は次式で定義された。 \begin{equation} V(s)={\bf E}\left[G_t|S_t=s\right] \end{equation} いま、 方策を表す確率$\pi(a|s)$を、パラメータ$\theta$に依存する微分可能な関数でモデル化し、 時間ステップ$t=0$から始める状態価値関数を考える。 \begin{eqnarray} V(s_0)&=&{\bf E}\left[G_0|S_0=s_0\right] \\ &=&{\bf E}\left[\sum_{t=1}^{\infty}\gamma^{t-1}R_t|S_0=s_0\right] \\ &\equiv& J(\theta;s_0) \end{eqnarray} これを$\theta$に関して最大化する。

    方策勾配定理の導出


     先に見たように、状態価値関数$V(s)$と行動価値関数$Q(s,a)$の間には次式が成り立つ。 \begin{equation} V(s)=\sum_a \pi(a|s)Q(s,a) \end{equation} $\pi(a|s)$が$\theta$に依存するとき、$V(s)$と$Q(s,a)$も$\theta$に依存する。従って次式が成り立つ。 \begin{equation} \frac{\partial V(s)}{\partial \theta}=\sum_a \left[\frac{\partial \pi(a|s)}{\partial \theta}Q(s,a)+\pi(a|s)\frac{\partial Q(s,a)}{\partial \theta}\right] \label{eq0} \end{equation} ここで、先に示した$Q(s,a)$についてのベルマン方程式 \begin{equation} Q(s,a)=\sum_{s^{\prime}} P(s^{\prime}|s,a)\left[r(s,a,s^{\prime})+\gamma\;V(s^{\prime})\right] \end{equation} の両辺を$\theta$で微分する。上式の右辺第1項は$\theta$に依存しないことに注意すると \begin{equation} \frac{\partial Q(s,a)}{\partial \theta}=\gamma\;\sum_{s^{\prime}} P(s^{\prime}|s,a)\;\frac{\partial V(s^{\prime})}{\partial \theta} \end{equation} を得る。これを、式($\ref{eq0}$)に代入する。 \begin{eqnarray} \frac{\partial V(s)}{\partial \theta} &=& \sum_a \left\{\frac{\partial \pi(a|s)}{\partial \theta}Q(s,a) + \pi(a|s) \left[ \gamma\;\sum_{s^{\prime}} P(s^{\prime}|s,a)\;\frac{\partial V(s^{\prime})}{\partial \theta} \right] \right\}\\ &=& f(s) + \sum_a \pi(a|s) \gamma\;\sum_{s^{\prime}} P(s^{\prime}|s,a)\;\frac{\partial V(s^{\prime})}{\partial \theta} \end{eqnarray} ここで、$f(s)\equiv\sum_a \frac{\partial \pi(a|s)}{\partial \theta}Q(s,a)$とした。再帰的に代入を繰り返す。 \begin{eqnarray} \frac{\partial V(s)}{\partial \theta} &=& f(s) + \sum_a \pi(a|s) \gamma\;\sum_{s^{\prime}} P(s^{\prime}|s,a) \left[ f(s^{\prime}) + \sum_{a^{\prime}} \pi(a^{\prime}|s^{\prime}) \gamma\;\sum_{s^{\prime\prime}} P(s^{\prime\prime}|s^{\prime},a^{\prime}) \frac{\partial V(s^{\prime\prime})}{\partial \theta} \right]\\ &=& f(s) + \sum_a \pi(a|s) \gamma\;\sum_{s^{\prime}} P(s^{\prime}|s,a) f(s^{\prime}) \\ &&+ \sum_a \pi(a|s) \gamma\;\sum_{s^{\prime}} P(s^{\prime}|s,a) \sum_{a^{\prime}} \pi(a^{\prime}|s^{\prime}) \gamma\;\sum_{s^{\prime\prime}} P(s^{\prime\prime}|s^{\prime},a^{\prime}) \frac{\partial V(s^{\prime\prime})}{\partial \theta} \\ &=& f(s) + \sum_a \pi(a|s) \gamma\;\sum_{s^{\prime}} P(s^{\prime}|s,a) f(s^{\prime}) \\ &&+ \sum_a \pi(a|s) \gamma\;\sum_{s^{\prime}} P(s^{\prime}|s,a) \sum_{a^{\prime}} \pi(a^{\prime}|s^{\prime}) \gamma\;\sum_{s^{\prime\prime}} P(s^{\prime\prime}|s^{\prime},a^{\prime}) f(s^{\prime\prime})+\cdots \end{eqnarray} ここで、 \begin{equation} \sum_a \pi(a|s)P(s^{\prime}|s,a)=\sum_a P(s^{\prime}|s,a)\pi(a|s)=P(s^{\prime}|s) \end{equation} が成り立つから次式を得る。 \begin{equation} \frac{\partial V(s)}{\partial \theta} =f(s)+\gamma \sum_{s^{\prime}} P(s^{\prime}|s)f(s^{\prime}) +\gamma^2 \sum_{s^{\prime},s^{\prime\prime}} P(s^{\prime\prime}|s^{\prime}) P(s^{\prime}|s)f(s^{\prime\prime})+\cdots \end{equation} 右辺第2項の$P(s^{\prime}|s)$は1ステップで状態$s$から$s^{\prime}$へ遷移する確率、第3項の$\sum_{s^{\prime}}P(s^{\prime\prime}|s^{\prime}) P(s^{\prime}|s)$は2ステップで状態$s$から$s^{\prime\prime}$へ遷移する確率を表す。これを一般化し、$k$ステップで状態$s$から$x$へ遷移する確率を$P(s\rightarrow x,k)$と書くことにすると \begin{eqnarray} \frac{\partial V(s)}{\partial \theta} &=&f(s)+\gamma \sum_{x} P(s\rightarrow x,1)f(x) +\gamma^2 \sum_{x} P(s\rightarrow x,2)f(x)+\cdots \\ &=& \sum_{k=0}^{\infty}\gamma^{k}\sum_x P(s\rightarrow x,k)f(x) \end{eqnarray} を得る。ただし、$k=0$のとき状態は変化しないので次式が成り立つことを用いた。 \begin{equation} \sum_x P(s\rightarrow x,0)=1 \end{equation} ところで、$J(\theta;s_0)$は$V(s_0)$であったから \begin{eqnarray} \frac{\partial J(\theta;s_0)}{\partial \theta} &=& \frac{\partial V(s_0)}{\partial \theta} \\ &=& \sum_{k=0}^{\infty}\gamma^{k}\sum_x P(s_0\rightarrow x,k)f(x) \end{eqnarray} が成り立つ。$f(x)$を元の式に戻して \begin{eqnarray} \frac{\partial J(\theta;s_0)}{\partial \theta} &=& \sum_s \left[\sum_{k=0}^{\infty}\gamma^{k}P(s_0\rightarrow s,k)\right]\sum_a \frac{\partial \pi(a|s)}{\partial \theta}Q(s,a)\\ &=& \sum_s d(s)\sum_a \frac{\partial \pi(a|s)}{\partial \theta}Q(s,a) \end{eqnarray} を得る。ここで、$d(s)\equiv \sum_{k=0}^{\infty}\gamma^{k}P(s_0\rightarrow s,k)$と置いた。上式をさらに変形すると \begin{eqnarray} \frac{\partial J(\theta;s_0)}{\partial \theta} &=& \sum_{s,a} d(s)\pi(a|s)\frac{1}{\pi(a|s)} \frac{\partial \pi(a|s)}{\partial \theta}Q(s,a) \label{eq1} \end{eqnarray} を得る。ここで、右辺の$d(s)\pi(a|s)$は以下のように変形できる。 \begin{eqnarray} d(s)\pi(a|s) &=& \sum_{k=0}^{\infty}\gamma^{k}P(s_0\rightarrow s,k)\pi(a|s)\\ &=& \sum_{k=0}^{\infty}\gamma^{k}P(S_k=s|S_0=s_0)\pi(a|s)\\ &=& \sum_{k=0}^{\infty}\gamma^{k}P(S_k=s|S_0=s_0)\;P(A_k=a|S_k=s)\\ &=& \sum_{k=0}^{\infty}\gamma^{k}P(S_k=s, A_k=a|S_0=s_0) \end{eqnarray} 上式は、時間ステップ$t=0$において$s_0$であった状態が、最終的に状態$s$・行動$a$に遷移する全てのステップを足し合わせた確率を表している。割引率$\gamma$により、ステップ数が多いほど確率が低くなることが考慮されている。以上の考察から、式($\ref{eq1}$)は期待値の記号を用いて表すことができる。 \begin{eqnarray} \frac{\partial J(\theta;s_0)}{\partial \theta} &=& {\bf E}\left[\frac{1}{\pi(a|s)} \frac{\partial \pi(a|s)}{\partial \theta}Q(s,a)\right]\\ &=& {\bf E}\left[\frac{\partial \ln{\pi(a|s)}}{\partial \theta}Q(s,a)\right] \end{eqnarray} 上式を方策勾配定理と呼ぶ。

    参考文献


    2018年2月12日月曜日

    強化学習 〜ベルマン方程式の導出〜

    はじめに


     強化学習のテキスト「これからの強化学習」に出てくるベルマン方程式を導出する。自身のための覚書である。

    収益


     時間ステップ$t$における収益$G_t$として、次式で定義される割引報酬和を考える。 \begin{equation} G_t=\sum_{\tau=0}^{\infty}\gamma^{\tau}R_{t+1+\tau} \end{equation} ここで、$\gamma$は割引率と呼ばれる量であり、$0\leqq\gamma\leqq 1$を満たす。$R_t$は時間ステップ$t$における報酬を表す。上式を展開すると \begin{equation} G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\cdots \end{equation} となる。つまり収益$G_t$とは、次の時間ステップ$t+1$から未来に向かって得られる報酬の和である。

    状態価値関数


     状態価値関数$V(s)$は、時間ステップ$t$における状態を表す確率変数$S_t$の観測値が$s$である条件の下で計算される収益$G_t$の期待値である。 \begin{equation} V(s)={\bf E}\left[G_t|S_t=s \right] \end{equation}

    行動価値関数


     行動価値関数$Q(s,a)$は、確率変数$S_t$の観測値が$s$、行動を表す確率変数$A_t$の観測値がaである条件の下で計算される収益$G_t$の期待値である。 \begin{equation} Q(s,a)={\bf E}\left[G_t|S_t=s,A_t=a \right] \end{equation}  ところで、$S_t=s$のとき収益$G_t$が実現する確率$P(G_t|S_t=s)$と$S_t=s, A_t=a$のとき収益$G_t$が実現する確率$P(G_t|S_t=s,A_t=a)$の間にはベイズの定理から次式が成り立つ。 \begin{equation} P(G_t|S_t=s)=\sum_a P(A_t=a|S_t=s)P(G_t|S_t=s,A_t=a) \end{equation} ここで、$P(A_t=a|S_t=s)$は、状態$s$のとき行動$a$が選択される確率であり、特に$\pi(a|s)$と表記される。これはエージェントの方策を決める確率である。上の関係式から、状態価値関数と行動価値関数の間には次式が成り立つ。 \begin{equation} V(s)=\sum_{a}\pi(a|s)Q(s,a) \end{equation}

    ベルマン方程式


     状態価値関数$V(s)$に式(2)を代入して \begin{eqnarray} V(s)&=&{\bf E}\left[G_t|S_t=s \right] \\ &=&{\bf E}\left[R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\cdots|S_t=s \right] \\ &=&{\bf E}\left[R_{t+1}|S_t=s \right] +\gamma{\bf E}\left[R_{t+2}+\gamma R_{t+3}+\cdots|S_t=s \right] \end{eqnarray} を得る。右辺第1項は \begin{eqnarray} {\bf E}\left[R_{t+1}|S_t=s \right] &=&\sum_{s^{\prime},a}P(S_{t+1}=s^{\prime},A_t=a|S_t=s)\;R_{t+1} \\ &=&\sum_{s^{\prime},a}P(S_{t+1}=s^{\prime}|S_t=s,A_t=a)P(A_t=a|S_t=s)\;R_{t+1} \\ &=&\sum_{s^{\prime},a}P(s^{\prime}|s,a)\pi(a|s)\;r(s,a,s^{\prime}) \end{eqnarray} となる。ここで、報酬関数$r(S_t,A_t,S_{t+1})$を導入した。これは現在の状態と行動、および次の状態から報酬が決定されることを表している。また、確率$P$は、確率変数ではなくその実現値に依存するものである。従って、確率変数を省略することができる。
    次に、式(9)の第2項を考える。 \begin{equation} {\bf E}\left[R_{t+2}+\gamma R_{t+3}+\cdots|S_t=s \right] = {\bf E}\left[R_{t+2}|S_t=s \right]+ \gamma{\bf E}\left[R_{t+3}|S_t=s \right]+\cdots \end{equation} これの右辺第1項は \begin{eqnarray} {\bf E}\left[R_{t+2}|S_t=s \right] &=& \sum_{s^{\prime\prime},s^{\prime},a^{\prime},a} P(S_{t+2}=s^{\prime\prime},A_{t+1}=a^{\prime},S_{t+1}=s^{\prime},A_t=a|S_t=s)\;R_{t+2} \\ &=& \sum_{s^{\prime\prime},s^{\prime},a^{\prime},a} P(S_{t+2}=s^{\prime\prime},A_{t+1}=a^{\prime}|S_{t+1}=s^{\prime})P(S_{t+1}=s^{\prime},A_t=a|S_t=s)\;R_{t+2} \\ &=&\sum_{s^{\prime},a} P(S_{t+1}=s^{\prime},A_t=a|S_t=s)\sum_{s^{\prime\prime},a^{\prime}}P(S_{t+2}=s^{\prime\prime},A_{t+1}=a^{\prime}|S_{t+1}=s^{\prime})\;R_{t+2} \\ &=&\sum_{s^{\prime},a} P(s^{\prime},a|s)\;{\bf E}\left[R_{t+2}|S_{t+1}=s^{\prime} \right] \\ &=&\sum_{s^{\prime},a} P(s^{\prime}|s,a)\pi(a|s)\;{\bf E}\left[R_{t+2}|S_{t+1}=s^{\prime} \right] \end{eqnarray} となる。式(16)からの(17) への変形では、確率変数を省略し、式(10)を用いた。式(13)の他の項についても同様に計算することにより次式を得る。 \begin{eqnarray} {\bf E}\left[R_{t+2}+\gamma R_{t+3}+\cdots|S_t=s \right]&=&\sum_{s^{\prime},a} P(s^{\prime}|s,a)\pi(a|s)\;{\bf E}\left[R_{t+2}+\gamma R_{t+3}+\cdots|S_{t+1}=s^{\prime} \right] \\ &=& \sum_{s^{\prime},a} P(s^{\prime}|s,a)\pi(a|s)\;V(s^{\prime}) \end{eqnarray} 式(19)から(20)への変形では$V(s)$の定義を用いた。最後に式(12)と(20)から次式を得る。 \begin{equation} V(s)=\sum_{s^{\prime},a} P(s^{\prime}|s,a)\pi(a|s)\left[r(s,a,s^{\prime})+\gamma V(s^{\prime})\right] \end{equation} これを状態価値関数に関するベルマンの方程式と呼ぶ。

     次に行動価値関数についてのベルマン方程式を求める。 \begin{eqnarray} Q(s,a)&=&{\bf E}\left[G_t|S_t=s,A_t=a \right] \\ &=&{\bf E}\left[R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\cdots|S_t=s,A_t=a \right] \\ &=&{\bf E}\left[R_{t+1}|S_t=s,A_t=a \right] +\gamma{\bf E}\left[R_{t+2}+\gamma R_{t+3}+\cdots|S_t=s,A_t=a \right] \end{eqnarray} 右辺第1項は \begin{eqnarray} {\bf E}\left[R_{t+1}|S_t=s,A_t=a \right] &=&\sum_{s^{\prime}}P(S_{t+1}=s^{\prime}|S_t=s,A_t=a)\;R_{t+1} \\ &=&\sum_{s^{\prime}}P(s^{\prime}|s,a)\;r(s,a,s^{\prime}) \end{eqnarray} 右辺第2項は \begin{equation} {\bf E}\left[R_{t+2}+\gamma R_{t+3}+\cdots|S_t=s,A_t=a \right] = {\bf E}\left[R_{t+2}|S_t=s,A_t=a \right]+ \gamma{\bf E}\left[R_{t+3}|S_t=s,A_t=a \right]+\cdots \end{equation} これの右辺第1項は \begin{eqnarray} &&{\bf E}\left[R_{t+2}|S_t=s,A_t=a \right] \\ &=& \sum_{s^{\prime\prime},s^{\prime},a^{\prime}} P(S_{t+2}=s^{\prime\prime},A_{t+1}=a^{\prime},S_{t+1}=s^{\prime}|S_t=s,A_t=a)\;R_{t+2} \\ &=& \sum_{s^{\prime\prime},s^{\prime},a^{\prime}} P(S_{t+2}=s^{\prime\prime},A_{t+1}=a^{\prime}|S_{t+1}=s^{\prime})P(S_{t+1}=s^{\prime}|S_t=s,A_t=a)\;R_{t+2} \\ &=&\sum_{s^{\prime}} \sum_{s^{\prime\prime},s^{\prime},a^{\prime}} P(S_{t+2}=s^{\prime\prime}|S_{t+1}=s^{\prime},A_{t+1}=a^{\prime}) P(A_{t+1}=a^{\prime}|S_{t+1}=s^{\prime}) \times\\ && \hspace{200pt}P(S_{t+1}=s^{\prime}|S_t=s,A_t=a)\;R_{t+2} \\ &=&\sum_{s^{\prime}} P(S_{t+1}=s^{\prime}|S_t=s,A_t=a) \sum_{a^{\prime}} P(A_{t+1}=a^{\prime}|S_{t+1}=s^{\prime})\times \\ && \hspace{200pt}\sum_{s^{\prime\prime}} P(S_{t+2}=s^{\prime\prime}|S_{t+1}=s^{\prime},A_{t+1}=a^{\prime})\;R_{t+2} \\ &=&\sum_{s^{\prime}} P(S_{t+1}=s^{\prime}|S_t=s,A_t=a) \sum_{a^{\prime}} P(A_{t+1}=a^{\prime}|S_{t+1}=s^{\prime}) \;{\bf E}\left[R_{t+2}|S_{t+1}=s^{\prime},A_{t+1}=a^{\prime} \right] \\ &=&\sum_{s^{\prime}} P(s^{\prime}|s,a) \sum_{a^{\prime}} \pi(a^{\prime}|s^{\prime}) \;{\bf E}\left[R_{t+2}|S_{t+1}=s^{\prime},A_{t+1}=a^{\prime} \right] \end{eqnarray} 他の項についても同様な計算を行えば次式を得る。 \begin{eqnarray} &&{\bf E}\left[R_{t+2}+\gamma R_{t+3}+\cdots|S_t=s,A_t=a \right]\\ &=& \sum_{s^{\prime}} P(s^{\prime}|s,a)\sum_{a^{\prime}} \pi(a^{\prime}|s^{\prime}) \;{\bf E}\left[R_{t+2}+\gamma R_{t+3}+\cdots|S_{t+1}=s^{\prime},A_{t+1}=a^{\prime} \right] \\ &=& \sum_{s^{\prime}} P(s^{\prime}|s,a)\sum_{a^{\prime}} \pi(a^{\prime}|s^{\prime}) \;Q(s^{\prime},a^{\prime}) \\ \end{eqnarray} 式(26)と(37)から最終的に次式を得る。 \begin{equation} Q(s,a)=\sum_{s^{\prime}} P(s^{\prime}|s,a)\left[r(s,a,s^{\prime})+\gamma \sum_{a^{\prime}}\pi(a^{\prime}|s^{\prime})Q(s^{\prime},a^{\prime})\right] \end{equation} 式(6)を使えば \begin{equation} Q(s,a)=\sum_{s^{\prime}} P(s^{\prime}|s,a)\left[r(s,a,s^{\prime})+\gamma\;V(s^{\prime})\right] \end{equation} とも書ける。これらが、行動価値関数についてのベルマン方程式である。

    2017年10月13日金曜日

    pyenvの導入手順

    覚書
    参照先

    macportsにはpyenvがない。以下を実行する。
    使い方

    以下のコマンドで、インストール可能なpythonインタープリターの一覧が表示される。 インストールしてみる。 インストールしたバージョンを見る。 切り替え 確認する。 アンインストールする。 この状態でpythonを起動すると、 ディレクトリを作ってその中だけでversionを変えるときは、ディレクトリ内で以下を実行する。 この状態で以下を実行 確認。