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}) 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}) \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を変えるときは、ディレクトリ内で以下を実行する。 この状態で以下を実行 確認。

virtualenvの導入手順

覚書 以下を.bash_profileに記述する。
export VIRTUALENVWRAPPER_PYTHON='/opt/local/bin/python3.6'
export VIRTUALENVWRAPPER_VIRTUALENV='/opt/local/bin/virtualenv-3.6'
export VIRTUALENVWRAPPER_VIRTUALENV_CLONE='/opt/local/bin/virtualenv-clone-3.6'
source /opt/local/bin/virtualenvwrapper.sh-3.6
以下を実行する。 色々作られる。

使い方
仮想環境を作る。 自動的に今作った仮想環境に入る。 仮想環境から出るには 確認する。 仮想環境を削除する。

2017年2月26日日曜日

Canonical Labelling by Nauty

はじめに


 先のページで、論文「Learning Convolutional Neural Networks for Graphs」の紹介を行った。その中で、Canonical Labellingを行う際に、Nautyというツール(ライブラリ)を用いていた。ここでは、Nautyの提供するC言語インタフェースを用いて、Canonical Labellingを行う手順を示す。

Nautyのインストール


 ここからソースをダウンロードする。コンパイル手順はソースに含まれるREADMEに書いてある。 上の処理が終わると、ディレクトリnauty26r7の直下に実行ファイル、オブジェクトファイル、ソースファイル、ユーザガイドが混在する状態になる。上の例では、--prefixを指定してあるが、ディレクトリに含まれるmakefileにはinstall命令が記述されていない(後で気づいた)。make installできないので、実行ファイル等を手で適当な場所にコピーする必要がある。ユーザガイドはオンラインでも見ることができる。

開発環境

  1. Xcode Version 8.2.1 (C++ Language Dialect: C++14)
  2. boost library
  3. cpplinq

サンプル1


 最初に、ユーザガイドのp4の冒頭にある下図を取り上げる。
図1
図1の上段2つのグラフは同型(isomorphic)であるが、頂点の隣接関係は異なっている。これらを2つをcanonizeすると、頂点の隣接関係の等しい2つのグラフを得ることができる(図1の下段)。2つの同型のグラフは、canonical labellingにより、頂点の隣接関係の等しいグラフになる。言い換えれば、canonical labellingを用いれば、2つのグラフが同型であるか否かを判定することができるのである。この判定を、NautyのC言語インタフェースを用いて実装したものを以下に示す。 上の出力を検討してみる。最初に、図1左側のグラフについて(図2)。
図2
108行目でdensenautyを呼び出した後、配列labに以下の値が設定される。 これは以下を表現している。 すなわち、図2の上段の元のグラフの頂点番号3は0に、6は1に置き換えることを意味する(他の頂点についても同様)。配列relabelling1は分かり易いように表現方法を変えただけの値である。 これは を意味する。すなわち、元グラフの頂点番号0を6に、1を5に置き換える(他の頂点も同様)。図1右側の2つのグラフについても同じように解釈すれば良い。結局、図1下段の2つのグラフが得られたことになる(図3)。
図3
これら2つのグラフを見ると、頂点{5,1,4,0}の位置は異なるが、全頂点の隣接関係は全く同じである。これを確認しているのが148行目である。

サンプル2


 次にユーザガイドのp5冒頭にある図を考える(図4)。
図4
グラフの形はサンプル1と同じであるが、partitioning(coloring)が導入されている。頂点が色分けされている場合、同じ色に属する頂点についてcanonical labellingが実行される(サンプル1は全ての頂点が同じ色を持つと解釈される)。実装例は以下の通り。 9行目で色分けを行うことをNautyに伝えている。実際に色分けを行なっているのは、31,32行目と58,59行目である。Nautyでは色分けを2つの配列lab,ptnを用いて表現する。図4左側の2つのグラフの色分けは以下の2つの配列で記述される。 labには頂点番号が任意の順番で格納される。この格納順にptnで色の分離位置を表現する。0の場合そこが色の境界である。0以外の値のとき同じ色である。すなわち、{0,2}と{1,3,4,5,6,7}に色分けされることになる。図4では前者は黒、後者は白で描かれている。図4右側の2つのグラフの色分け(58,59行目)も同様である。densenautyの呼び出し(39,66行目)の後のlabにはcanonize後のラベルが格納され、この解釈方法はサンプル1と同じである。canonize後に得るグラフは図4の下段である。これら2つのグラフの頂点の隣接関係は異なる。これを確認しているのが80行目である。最後に、headerファイルとmain関数を示す。

論文「Learning Convolutional Neural Networks for Graphs」への適用


 論文「Learning Convolutional Neural Networks for Graphs」では、最初に、betweenness centralityやWLアルゴリズムにより頂点のラベル付けを行なった。そして、同じラベルを持つ頂点が存在する場合、この縮退を解くためにNautyを用いている。同じラベル値を持つ頂点を同じ色を持つ頂点と解釈し、Nautyを適用すれば良いだろう。 

2017年2月7日火曜日

Learning Convolutional Neural Networks for Graphs

1. はじめに


 論文「Learning Convolutional Neural Networks for Graphs」のアルゴリズムについてまとめる。

2. 本論文の目的


 本論文の目的は、一般的なグラフにConvolutional Neural Network(CNN)を適用することである。CNNでは畳み込み処理を行うが、これをグラフに適用する手順が提案されている。本論文で考案されたグラフ構造のためのCNNを著者らはPatchy-sanと名付けている。

3. CNNとグラフ


 最初に、画像に適用されるCNNを考えてみる。図1は畳み込みに使うフィルタ(Receptive Field: 以下RF)、図2はRFを画像(4$\times$4)に適用している様子を表したものである(本論文より引用)。
図1
図2

画像の形状は矩形であり、RFも矩形とするのが一般的である。さらに、RFを適用していく順番は左上から右下である。ところで、画像は形状が矩形であるグラフとみなすことができる。このときのノードは画素である。本論文は、任意の形状を持つグラフに適用できるように上記の手順を一般化する方法を提案している。一般化するには2つの手順を明確にする必要がある。
  1. RFを適用するノードとその順番(ノード・シーケンス)を決める。
  2. RFの形状を決める。
この2つを決めれば、通常のCNNのアルゴリズムに載せる事ができる。

4. ノード・シーケンスの決定


 画像の場合、画素の並びは左上から右下に向かって「ラベル」が付けられていると考え、ノード・シーケンスもそれに従い決定される。一般のグラフに対し一番最初に行うことは、各ノードに「ラベル」を付ける事である。ただし、以下の条件を満たすラベルでなければならない。
任意の2つのグラフ$G$と$G^{\prime}$を考える。$G$を構成するあるノード$n_G$の局所的な接続関係が、$G^{\prime}$内のあるノード$n_{G^{\prime}}$の局所的な接続関係と似ているなら、これら2つのノードに割り当てるラベルも似ている。
本論文ではこれを満たす2つの方法を取り上げている。
  1. 1次元Weisfeiler-Lehmanアルゴリズムを用いたラベリング
  2. Centralityを用いたラベリング
次にこれらを説明する。

4-1. 1次元Weisfeiler-Lehman(WL)アルゴリズムを用いたラベリング


 アルゴリズムの手順は以下の通りである。
  1. 2つのグラフ$G$と$G^{\prime}$を考える。最初に各ノードに1を割り振る(図3)。
  2. 図3
  3. ノードAを考える(図3)。Aは右と左のノードと接続しており、そのラベルはいずれも1である。この関係を1,11と書くことにする。カンマの前にAのラベルを、カンマの後ろに右と左のラベルを並べて書いたものである。カンマの後ろに並ぶ数字の順序はあとでソートするので任意でよい。同じ事を全てのノードについて繰り返すと図4を得る。
  4. 図4
  5. 1,11などを文字列とみて昇順に並べ、新たなラベルを割り当てる。新たなラベルは既存のラベルを上書きしないものとする。
    1,11 $\rightarrow$ 2
    1,111 $\rightarrow$ 3
    1,1111 $\rightarrow$ 4
  6. $G$と$G^{\prime}$の各ノードに新たなラベルを付ける(図5)。$G$のラベルは$\{2,2,2,3,3,4\}$、$G^{\prime}$のラベルは$\{2,2,2,3,3,4\}$であり、これらは同じである。同じ場合、2と3の手順を繰り返す。
  7. 図5
  8. ノードAを考える。先と同じように接続関係から2,43を得る。今度はラベルが同じとは限らないことに注意する。同じことを全てのノードについて繰り返すと図6を得る。
  9. 図6
  10. カンマの後ろに並ぶ数字を昇順に並べ替える。例えば、2,43を2,34とする。同じことを他のラベルについても繰り返す。得られたラベルを文字列とみなしてソートし、新たなラベルを割り当てる。
    2,24 $\rightarrow$ 5
    2,33 $\rightarrow$ 6
    2,34 $\rightarrow$ 7
    3,224 $\rightarrow$ 8
    3,234 $\rightarrow$ 9
    4,2233 $\rightarrow$ 10
  11. 新たなラベルを$G$と$G^{\prime}$に割り当てる(図7)。
  12. 図7
  13. 図7のとき、$G$のラベルは$\{6,7,7,8,8,10\}$、$G^{\prime}$のそれは$\{5,5,6,9,9,10\}$となり、これらは異なる。異なるとき終了する。ただし、何回繰り返しても終了しない場合があり得るので、あらかじめ適当な繰り返し数の上限を決めておく。
  • 異なるグラフに属する2つのノードが類似の接続関係を持つなら、これらのノードは類似のラベル値を持つ。また、ラベル値が大きいノードは、多くの隣接ノードと連結していることになる。
  • あらかじめ決めておいた回数だけ繰り返した結果、ラベルのセットが同じになるなら、「これらのグラフは同型である」か、「同型でないと結論づけることはできない」かのいずれかである。ほとんどの場合、同型であると結論してよい。
  • 上で取り上げた2つのグラフのノードの総数は12である。このときラベルの上限値は12としてよい。従って、繰り返し数の上限値は、いま現在使われているラベルの最大値から判断することができる。
上で取り上げた2つのグラフは同型でない場合であった。念のため、同型となる場合の例を以下に示す。
  1. $G$と$G^{\prime}$の各ノードに1を割り振る(図8)。
  2. 図8
  3. 先と同じ手順を行うと図9を得る。
  4. 図9
  5. 1,11 < 1,111< 1,1111と並べ、2,3,4を割り当てる(図10)。
  6. 図10
  7. $G$のラベルは$\{2,3,3,4,4\}$、$G^{\prime}$のそれは$\{2,3,3,4,4\}$であり同じなので、手順を繰り返す(図11)。2,44 < 3,344 < 4,2334と並べ替え、新たなラベル5,6,7を割り当てる(図12)。
  8. 図11
    図12
  9. $G$と$G^{\prime}$のラベルは同じになる。いまの場合、何回繰り返しても同じままである。
  10. 2つのグラフは同型である。
ここまでは、2つのグラフを取り上げてラベリングの手順を見てきた。Patchy-sanに本アルゴリズムを適用する際は、訓練データとなる全てのグラフを対象としなければならない。

4-2. Centralityによるラベリング


 Centralityとは、グラフ内における各ノードの重要性を表す指標である。Centralityが大きいノードほど「重要」となる。Centralityにはいくつかの種類があり、その代表的なものは以下のものである。
  1. Betweenness Centrality
    1. 任意に取り出した2つのノードを結ぶ最短経路を見つける。
    2. その経路上にある各ノードに+1を与える。
    3. この手順を繰り返す。
    4. 大きな値を持つノードは、最短経路に寄与する回数が多く、重要なノードである。
  2. Closeness Centrality
    1. あるノードを考え、このノードから他の任意の複数のノードへの最短経路を見つける。
    2. 最短経路の長さの平均値をそのノードのCentralityとする。
    3. Centralityが大きいノードほど、たくさんのノード、遠いノードと接続しており重要である。
  3. Degree Centrality
  4. そのノードと連結する辺の数である。
図13. Betweenness Centralityの例。赤から青に向かってCentralityは大きくなる。
(Wikipediaより抜粋)
先の1次元WLアルゴリズムの場合は、全グラフを使ってラベル値を決定するが、Centralityの場合は個々のグラフからラベル値が決まる。

4-3. ノード・シーケンス


 1次元WLアルゴリズムあるいはCentralityを用いて全グラフの全ノードにラベル付けを行ったあと、個々のグラフについてラベル値の大きなものから順に$w$個のノードを取り出す。これがノード・シーケンスとなる(図14)。要素数$w$は全グラフで同じである。画像の言葉で言えば、画像サイズは固定されるということである。本論文では、1つのグラフを構成するノード数の平均値を$w$としている。
図14. {A,B,C,D,E,F}がノード・シーケンス
ノード・シーケンスの各要素においてRFを作り、畳み込みを行う。画像におけるCNNと同様に、畳み込みを行うノード(画像の場合は画素)を$s(\neq 1)$個ずつ進めることもできる。

5. Receptive Field(RF)の決定


 ノード・シーケンスの要素$v$が与えられとき、$v$を中心にしてサイズ$k$のRFを作成する。その手順は以下の通りである。
  1. $v$から出発して隣接ノードを順にたどり$k$個を越えたところで止める。
  2. 集めたノードをNormalizationする(後述)。
各手順の詳細を以下に示す。

5-1. 近傍ノードの収集


 ノード$v$に対し、図15に示した順に近傍ノードを集めて行く。図16はこれをアルゴリズムにしたものである。
図15
図16. 本論文より抜粋

5-2. 近傍ノードのNormalization


 手順は以下の通りである。
  1. $v$(赤丸)を中心に近傍ノードを集める(図17A)。
  2. $v$からの距離で色分けを行う。図17Bでは距離1と距離2で色分けを行っている。
  3. 距離1のノードをラベル値の降順に並べる(図17C)。同じことを距離2のノードについても行う。
  4. 赤ノードを先頭に1次元に展開する(図18)。ノードの総数が$k$を越えている場合は末尾から必要なだけ削除する。$k$より少なければ0パディングする。ラベル値が同じとき1次元に展開したときの位置が一意に決まらない。この場合は、Canonicalizationを行いラベル値の縮退を解く。本論文ではNautyなるツールを用いてこれを行っている(こちらに追記しました(2017/02/26))。
図17. 本論文より抜粋
図18. 本論文より抜粋
各ノードに一意の並び順を与えベクトル化することをNormalizationという。図19は上記の手順をアルゴリズムとして示したものである。
図19. 本論文より抜粋

6. ここまでのまとめ


 図20,21は、ノード・シーケンスをたどりながらRFを作成する手順を示したものである。RFは$w$個作られる。ストライド$s(\neq 1)$でたどると$w$に達する前にノード・シーケンスの要素を使い果たすことになる。その場合は、0パディングしたRFを返す(ZeroReceptiveField())。その他の関数については既に説明した。
図20. 本論文より抜粋
図21. 図20に現れるReceptiveField関数。本論文より抜粋
あとは機械的にCNNを実行すればよい。

7. CNNの実行


 本論文のネットワーク構造は以下の通りである。
第1層目の点線で囲んだ部分がグラフ固有の処理である。この層で、上で説明したグラフ固有の畳み込みが実行される。2層目以降は通常のCNNである。畳み込みは次式で定式化される。 \begin{equation} g_{m,p,i}=\sum_{k,l}\;w_{p,l,k}\;x_{m,l,i+k} \end{equation} ここで、$p$はRFの種類、$i$はノード・シーケンスの要素番号(画像の言葉で言えば画素の位置)、$k$はRFのサイズ、$l$はチャンネル数である。また、バッチ処理を行う際、複数のノード・シーケンスを一度に扱うが、$m$はそのときのノード・シーケンスの番号である。さらに、チャンネルとは、グラフの場合、ノード属性に相当する。いま、畳み込みを記号$\otimes$で表すと上式は \begin{equation} g_{m,p}=\sum_{l}\;w_{p,l}\otimes x_{m,l,} \end{equation} と書ける。$x_{m,l}$が$g_{m,p}$に更新され、今度は、$g_{m,p}$に対して畳み込みを行うというのがCNNの一連の処理である。ここまでの議論でグラフをCNNの流れに載せることができたことになる。

8. 参考文献

  1. Weisfeiler-Lehman Graph Kernels
  2. Boosting and Semi-supervised Learning
  3. Centrality
  4. 著者らのスライド
  5. PFNの人のスライド